西北工业大学数据结构1998年考研真题考研试题-考博信息网

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

，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。

上一篇文章：西北工业大学数据结构1999年考研真题考研试题

下一篇文章：西北工业大学设施规划与设计2004年考研真题考研试题

考博信息网提供全国高校历年考研真题，电子扫描版样张:

北京第二外国语学院821国际贸易与国际金融2010年考研真题

北京外国语大学翻译硕士专业学位（MTI）英汉互译（笔译）2010年考研真题