当前位置：问答库＞考研试题

浙江工商大学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

8 9 10 图1

(a) (b) (c)

三、对下图2所示的连通图，请用Prim 算法构造其最小生成树，设开始顶点是

1。

分）

图2

四、设单链表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