|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
西北工业大学 98 年数据结构考研题
LBHIDDEN[0]LBHIDDEN 西北工业大学 98 考研题
考试科目：数据结构
一：简答：（20 分）
1．什么是数据结构，什么是算法，它们之间有什么关系？
2．数组，广义表与线形表之间有什么样的关系？
3．树和二*树之间有什么样的关系？
4. 关于后序线索二*树，怎样查找任意结点的直接后继；对于半序线索二*树，怎样查找任
意结点的直接前驱？
5. 请给出右图所示的有向图的两种存储形式。
二。：算法应用（20 分）（写出计算步骤）
1．已知有 8 个初始归并段，其长度分别为 10，20，25，30，45，12，16，2，现用 T0，T1，
T2 三条磁带进行二路多步归并并排序，写出每遍归并后各归并段的分布，并给出初始归并
段在磁带上的最佳分布。
2．设有一组数据{984，55，93，306，271，850，198，226，3，15}，请建立一个相应的初
始堆，并将排序结果列表输出。对于下图所示 AOE 一网，求：
A．关键路径和完成工程的最短时间。
B．怎样可以缩短工程限制
C．选用何种存储结构较优。
三．证明（10 分）
1．若二*树中度为 1 的结点数为 0，则该二*树的总分支数为 2（no-1），其中 no 为叶结点数。
2．利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。
四．算法思想（20 分）
1，说明拓扑排序的基本思想。
2，写出在连通网上构造最小生成树的算法思想。
五．算法实现（用 PASCAL 语言或 C 语言编写程序或过程）（30 分）
1．对于含有+，—，*，/及括号的算术表达式（串缀表示）写一个算法，将该表达式构造成
相应的二*树表示。
2．对于一个高度均衡的树，它的内结点可以有 2 个或 3 个孩子，而且最多只能有 3 个孩子，
写出一个算法，实现插入一个叶结点，使该树各内结点始终处于平衡状态（即分支数和深度
均处于平衡状态）。
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
