资源简介：西北大学数据结构1998年考研真题考研试题    

        下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载

 

西北工业大学 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 个孩子，
写出一个算法，实现插入一个叶结点，使该树各内结点始终处于平衡状态（即分支数和

 

说明：本站提供的《西北大学数据结构1998年考研真题考研试题 》源自权威渠道，为历年考过（被使用过）的真题试卷，除标注有“回忆版”字样的试题外，其余均为原版扫描，权威可靠；回忆版试题由当年参加全国硕士、博士研究生入学考试考生回忆，内容完整。