浙江工商大学程序设计2005年考研真题考研试题

浙江工商大学 2005 年硕士研究生入学考试试卷（A）
招生专业：管理科学与工程
考试科目：423 程序设计
考试时间：3 小时
一、简答题（本大题共 5 小题 每小题 5 分 共计 5 分）
1、在单链表、双链表和单循环链表中，若仅知道指针 P 指向某结点，不知道头
指针，能否把 P 所指结点从相应的链表中删除？若可以，其时间复杂度各为多
少？
2、已知二叉树的中序序列为 GBADECF，后序序列为 GBEDFCA，请画出该二叉树。
3、DFS 和 BFS 遍历各采用什么样的数据结构来暂存顶点？当要求连通图的生成
树的高度最小，应采用何种遍历？
4、有序数组是堆吗？请说明理由。
5、试证明有 n 个叶子的哈夫曼树共有 2n-1 个结点。
二、将图 1 所示的森林转化为相应的中序线索二叉树，请给出过程。（本大题共
1 小题 每小题 10 分 共计 10 分）
1 4 11
2 3 5 6 7 12 13 14
8 9 10 图 1
(a) (b) (c)
三、对下图 2 所示的连通图，请用 Prim 算法构造其最小生成树，设开始顶点是
1。（本大题共 1 小题 每小题 10 分 共计 10 分）
2
2 5
4 30 10 图 2
15 6
10
四、设单链表 L 是一个递减有序表，请写一算法（以函数的形式）将 x 插入 L
中，并使 L 仍保持有序性。（本大题共 1 小题 每小题 10 分 共计 15 分）
五、编制一个算法（函数）计算一个用三元组表示的稀疏矩阵的对角线元素之和。
（本大题共 1 小题 每小题 10 分 共计 15 分）
六、阅读下面的程序并写出程度执行结果：
（本大题共 4 小题 每小题 5 分 共计 20 分）
1、
#define P(x) printf("%6s",x)
#includes ＜stdio.h＞
char*c[]={"You can make statement","for the topic","The sentences","How
about"};
char **p[ ]={c+3,c+2,c+1,c};
char ***pp=p
1
2
3
5
6
4