2007解放军理工大学指挥自动化学院考研专业课数据结构与概率论.doc

2007解放军理工大学指挥自动化学院考研专业课——数据结构与概率论.txt心脏是一座有两间卧室的房子，一间住着痛苦，一间住着快乐。人不能笑得太响，否则会吵醒隔壁的痛苦。 本文由wkszksyfnu贡献 本文由胥秀峰贡献 pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 机密★启用前 中国人民解放军理工大学 2007 年全国硕士研究生入学统一考试试卷 考试科目代码：805 考试科目名称：数据结构与概率论 说明：所有答案必须按序号书写在考场提供的答题纸上，可不抄写原题， 做在试卷和草稿纸上的一律无效。 数据结构部分 一、填空题（本题共 10 空，每空 2 分，满分 20 分） 1． 已知一棵树中含有父子关系的边是： (L,N)， (G,K)， (G,L)， (G,M)， (B,E)， (B,F)，(D,G)，(D,H)，(D,I)，(D,J)，(A,B)，(A,C)，(A,D)。 （1）请画出这棵树的树形。 （2）该树的高度是。 2．含 3 个结点的二叉树的树形共有（1）种，其树形分别为（2） 。 其中，有（3）个是完全二叉树。 3．已知二叉树的扩充先序序列是“ABC 空空 DE 空 FG 空空空空空”。那 么， 它的中序序列是 （1） ， 后序序列是 （2） 。 第 1 页（共 11 页） 4．如果排序期间，序列的变化情况依次是： ① 25，84，21，47，15，27，68，35，20（原始排列） ② 20，15，21，25，47，27，68，35，84 ③ 15，20，21，25，35，27，47，68，84 ④ 15，20，21，25，27，35，47，68，84 那么，所用的排序方法是排序。 5．对于下面的加权图： A 6 B 12 C 4 9 5 8 G 20 D 12 15 16 10 F 13 E （1）写出用 Kruskal 算法求最小生成树时，依次得到的树边（写出边的两 个顶点和长度，形如 AB6）。 （2）画出所求出的最小生成树。 二、单项选择题（本题共 10 空，每空 2 分，满分 20 分） 1．设进栈序列是 1，2，3，…，n，出栈序列为 p1，p2，p3，…，pn。 （1）若 p1=n，则 pi（1＜i≤n）为。 A）i B）n-i C）n-i+1 D）不确定 第 2 页（共 11 页） （2）若 pn=n，则 pi（1≤i＜n）为。 A）i B）n-i C）n-i+1 D）不确定 （3）若 p1=3，则 p2 为。 A）可能是 2 B）不可能是 2 C）可能是 1 D）必是 1 （4）若 p3=1，则 p1 为。 A）必是 2 B）可能是 3 C）必定是 3 D）不可能是 3 （5）若 pn=1，则 pi（1≤i＜n）为。 A）有多种可能 B）n-i C）i D）n-i+1 2． 对有序数组 a[12]进行二分查找时， 查找长度最大的元素下标为。 A）1，4，7，9，11 B）0，3，6，9，11 C）1，3，6，9，11 D）0，4，8，9，10 3．在双向链表中，删除 p 所指结点（不考虑回收结点）不正确的操作是 。 A）p-Llink-Rlink=p-Rlink, p-Rlink-Llink=p-Llink; B）p-Llink= p-Rlink, p-Rlink=p-Llink; C）p=p-Llink,p-Rlink= p-Rlink-Rlink, p-Rlink-Llink=p; D）p=p-Rlink,p-Llink= p-Llink-Llink, p-Llink-Rlink=p; 第 3 页（共 11 页） 4．若 k 元正则树中共有 m 个非叶结点，则叶子数。 A）≥(k-1)m B）≤km C）=(k-1)m-1 D）=(k-1)m+1 5．用 Dijkstra 算法求下图中，顶点 A 到其余各顶点的最短路径时，将按 照的次序，依次求出 A 到它们的最短路径。 A）BEDFC B）BEDCF C）BCEDF D）EDFCB A 3 B 6 5 E 8 F 7 12 C 15 10 4 D 6．以下序列不是堆。 A）100，85，98，77，80，60，82，40，20，10，66 B）100，98，85，82，80，77，66，60，40，20，10 C）10，20，40，60，66，77，80，82，85，98，100 D）100，85，40，77，80，60，66，98，82，10，20 三、程序填空题（本题共 10 空，每空 2 分，满分 20 分）