昆明理工大学2010年硕士研究生招生入学考试试题A卷.doc

《昆明理工大学2010年硕士研究生招生入学考试试题A卷.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、昆明理工大学2010年硕士研究生招生入学考试试题(A卷)考试科目代码：835考试科目名称：数据结构教程试题适用招生专业：系统理论、系统分析与集成考生答题须知1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3．答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4．答题时不准使用涂改液等具有明显标记的涂改用品。一、单项

2、选择题：（每题3分，共30分）1．非线性结构中每个结点。A.无直接前驱结点B.只有一个直接前驱和直接后继结点C.无直接后继结点D.可能有多个直接前驱和多个直接后继结点2．在表长为n的单链表中，算法时间复杂度为O(n)的操作是。A.查找单链表中第i个结点B.在p结点之后插入一个结点C.删除表中第一个结点D.删除p结点的直接后继结点3．在链表中最常用的操作是在最后一个数据元素之后插入一个数据元素和删除第一个数据元素，则最节省运算时间的存储方式是。A.仅有头指针的单链表B.仅有头指针的单循环链表C.仅有头指针的

3、双向链表D.仅有尾指针的单循环链表4.设有10阶矩阵A，其对角线以上的元素aij(1≤j≤10，11）的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点。A.仅有左孩子B.仅有右孩子C.仅有一个孩子D.都有左、右孩子7.关于连通图的BFS和DFS生成树高度论述正确的是。A.

4、BFS生成树高度DFS生成树高度D.BFS生成树高度≥DFS生成树高度第3页共3页8．对线性表用二分法查找时要求线性表必须是。A.顺序表B.单链表C.顺序存储的有序表D.散列表9.在采用线性探查法处理冲突的散列表中进行查找，查找成功时所探测位置上的健值。A.一定都是同义词B.一定都不是同义词C.不一定是同义词D.无任何关系10．堆排序是一种。A)插入排序B)选择排序C)交换排序D)归并排序二、判断题（每题2分，共20分）1．在单

5、链表中存取某个元素，只要知道指向该元素的指针，因此单链表是随机存取的存储结构。（）2．若一个有向图的邻接矩阵中对角线以下的元素均为零，则该图的拓扑序列必定存在。（）3．消除递归必须用栈来实现。（）4．稀疏矩阵压缩存储后必会失去随机存取的功能。（）5．堆排序所需要附加空间数取决于待排序的记录的个数。（）6．在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（）7．采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的所在位置置为空，因为这将会影响以后的查找。（

6、）8．对于n个顶点的无向图，若其边数大于或等于n-1，则其必是连通图。（）9．一棵完全二叉树中的结点若无左孩子，则其必是叶结点。（）10．将二叉排序树的中序序列中的关键字依次插入初始为空的树中，所得到的二叉排序树与原二叉排序树是相同的。（）三、简答题（共50分）1．对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题：（1）图中有多少条边？（2）任意两个顶点i和j是否有边相连？（3）任意一个顶点的度是多少？（18分）2．判断下列序列是否为堆，若不是堆则把它们调整为堆。（12分）（1

7、）（100，86，48，73，35，39，42，57，66，21）第3页共3页（2）（12，70，33，65，24，56，48，92，86，33）3．特殊矩阵和稀疏矩阵哪一种压缩存储会失去随机存储功能？为什么（10分）4．设栈s和队列q初始状态为空，元素a、b、c、d、e、f依次通过栈s，一个元素出栈后即进入队列，若6个元素出队的序列是bdcfea，则栈s的容量至少应该存多少个元素？（10分）四、已知一组记录的关键字为{18，2，10，6，78，56，45，50，110，8}。（1）按输入顺序画出此组记录

8、的平衡二叉树，求等概率情况下查找成功的平均查找长度。若查找每个元素的概率不等时，这时的平衡二叉树是否是最佳查找树？为什么？（2）设装填因子α=0.77，散列函数H（key）=keyMOD11，用线性探测再散列方法解决冲突，试构造散列表，并求出在等概率情况下查找成功和查找不成功的平均查找长度。（15分）五、设图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小。（10分）六、已知