|
《数据结构》部分
一、简答题（15 分，每题 5 分）
1、什么是原地工作？
2、什么是完全二叉树？
3、什么是稳定的排序方法？
二、应用题（45 分）
1、设有一个顺序栈 S，元素 s1, s2, s3, s4, s5, s6 依次进栈，如果 6 个元素的出栈顺序为 s2, s3,
s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。（10 分）
2、
给定一棵二叉树如右图所示
（1）写出该树的前序、中序、后序遍历结果；
（2）画出该二叉树的中序线索树；
（3）将它转换成等价的树或森林。
（15 分）
3、已知一个无向图如下图所示，要求用 Kruskal 算法生成最小树，试画出构造过程。（10
分）（10 分）
4. 某整形数组 A 的数组元素分别是 6，2，9，7，3，8，4，5，0，试用下例各排序方法将 A
中元素由小到大排序。（10 分）
(1)用第一元素中的值 6 作为枢轴，试写出快速排序第一次分割后 A 中的结果。
(2)A 中的元素是否为堆，如果不是，请将其调整为堆，写出将 A 调整成堆后 A 中的结果。
三、算法设计题（30 分)
答题要求：
①用自然语言说明所采用算法的思想；
②给出每个算法所需的数据结构定义，并做必要说明；
③用 C 语言写出对应的算法程序，并做必要的注释。
1 2
6
5 4
3
20
10
11
6
6
18
10 14
5
9
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
