安徽大学2005年度 硕士研究生入学考试 数据结构部分 大登 一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题后的括号内。每题2分，共20分） 01． 如果待排序序列中两个数据元素具有相同的值，在排序A. 起泡排序 B. 归并排序 C. Shell排序 D. 直接插入排序 02．下面关于二分查找的叙述正确的是 ( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 03.若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则他的后序序列是( ) A、EFGHBCD B、FEGHDCB C、FEGBHDC D、EFBGCHD 04一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A． 250 B． 500 D．505 D．以上答案都不对 05.有一个具有n个顶点的连通图生成的最小生成树中,具有( )条边。 A、n B、n-1 C、n+1 D、2n-1 06. 下面的二叉树中，（ ） 不是平衡二叉树。 A B C D 07.若串S1=’ABCDEFG’, S2=’9898’,S3=’###’,S4=’012345’,执行concat(replace(S1, substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（ ） A． ’ABC###G0123’ B． ’ABCD###2345’ C． ’ABC###G1234’ D． ’ABCD###1234’ 08. 设有数组A[i,j]，数组的每个元素长度为5字节，i的值为0 到5 ，j的值为0 到6，数得 分 项 分 一 二 三 四 五 六 七 -----------------------------------------------------------------------------------------------------------组从内存首地址AB开始顺序存放，当用以列为主序存放时，元素A[5，5]的存储首地址为( )。 A. AB+180 B. AB+175 C. AB+200 D. AB+205 09. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 10.从具有n 个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为( ) A、0(n) B、0(1) C、0(logn) D、O(n2) 二、填空题（每空1分，共20分） 得分 1.对于双向链表,在两个结点之间插入一个新结点时需要修改的指针共有____个。 3.有K个叶子结点的哈夫曼树，其结点的总数为 。 4.对于17个元素的有序表A[1]-A[17]作二分查找,在查找其等于A[10]的元素时需比较_____次. 5.树的三种存储结构是 、孩子表示法和孩子兄弟表示法。 6.对二叉排序树进行 遍历，就可以得到排好序的顶点序列。 7.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性，通常可分为四类基本结构：集合、线性结构 和图状结构。 8.已知一个无向图的邻接表如下图所示: 则从顶点Vo出发进行深度优先搜索遍历得到的顶点序列为_____________和广度优先搜索得到的顶点序列为_______________. 0 V0 2 ^ 3 1 V1 4 ^ 6 2 V2 5 3 3 V3 6 5 6 1 ^ 4 V4 3 2 ^ 5 V5 4 3 6 V6 第二题，第8小题图 总分 阅卷人 装前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。 2.已知完全二叉树的第10层有10个叶子结点,则整个二叉树的结点数最多为_______个。 订线----------------------------------------
0 ^ 2 0 ^ 1 ^ 9. N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。 得分 共 6 页，第 1 页 学生答题注意：勿超黑线两端；注意字迹工整。 共 6 页，第 2 页 三、分析计算题（第1题6分，2,3,4每题8分，5题10分,共40分） 1. 试以数据集{2，5，7，9，13}为权值构造一棵哈夫曼树，并计算其带权路径长度. 2．对于如下的连通图，请给出从顶点Vo出发，利用普里姆（Prim）算法求出它的最小生成树的过程中得到的顶点集和边集及最小生成树的权，并画出所得到的最小生成树。 A 6 7 1 4 B 4 D C 2 2 6 5 3 F 10 E 3 （第三大题第2题图） 3．某赋权有向图如下图所示： 用迪杰斯特拉（Dijkstra）算法思想，求源点A到各其余顶点的最短路径及路径长度 1 B 3 A 2 C 3 D 3 1 1 2 F E 1 G 5 （第三大题第3题图） 4. 记录的关键字集合K={23，9，39，5，68，12，62，48，33 }，给定的增量序列D={4，2，1}，请写出对K按“SHELL方法”排序时各趟排序结束时的结果。 5．给定关键字序列35,67,42,21,29,86,95,47,50,36,91，试分别用顺序查找、二分查找、二叉共 6 页，第 3 页 学生答题注意：勿超黑线两端；注意字迹工整。 共 6 页，第 4 页 排序树查找、散列查找(其中，散列函数H(k)=k，用线性探查法和拉链法来解决冲突)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及两种散列查找的散列表)，并求出每一种查找的成功平均查找长度。
四、算法设计题（每题10分，共20分）
2. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉
得分 1. 二叉树以二叉链表存储，设计算法求二叉树中叶子结点和非叶子结点的个数。
数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），并分析算法的时间复杂度。
共 6 页，第 5 页 学生答题注意：勿超黑线两端；注意字迹工整。 共 6 页，第 6 页
安徽大学2005年度硕士研究生入学考试 - 图文
