浙江工商大学数据结构与计算机网络2005考研试题研究生入学考试试题考研真题
● 摘要
浙江工商大学2005年硕士研究生入学考试试卷（A卷）
招生专业：计算机应用技术
考试课目：数据结构、计算机网络
考试时间：3小时
A、数据结构（共75分）
一、简答题（本大题共5小题 每小题5分 共计25分）
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。
（本大题共1小题 每小题10分 共计10分）
图2
四、设单链表L 是一个递减有序表，请写一算法（以函数的形式）将x 插入L 中，并使L 仍保持有序性。（本大题共1小题 每小题10分 共计15分）
五、编制一个算法（函数）计算一个用三元组表示的稀疏矩阵的对角线元素之和。（本大题共1小题 每小题10分 共计15分）
B、计算机网络（共75分）
一、填空题（每空1分，共20分）
相关内容
相关标签