数据结构答案20150617.doc

数据结构复习资料参考答案（红色字体为答案）一、 选择题 40题 1. 下面程序段的时间复杂度为_ for(int i=0; im; i+) for(int j=0; jnext=p一next；p一next=q；C. q一next=p一next；p一next=q；B. p一next=q一next；q=p； D. p一next=q一next；q一next=p；12在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为_。A.e B.2e C.n2-e D.n2-2e13.二叉树中第5层上的结点个数最多为_A.8 B.15C.16 D.3214. 一个无向连通图的生成树是含有该连通图的全部顶点的_。A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图15. 堆的形状是一棵_。A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树16. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_。A. n B. n-1 C. n+1 D. 2*n17有向图的一个顶点的度为该顶点的_。A. 入度 B. 出度 C. 入度与出度之和 D. (入度出度)/218. 对线性表进行折半查找时，要求线性表必须_。A. 以顺序方式存储B. 以链接方式存储C. 以顺序方式存储，且元素按关键字有序排序D. 以链接方式存储，且元素按关键字有序排序19在一个有向图中，所有顶点的度数之和等于所有弧数的_倍。A. 3 B. 2 C. 1 D. 1/220一棵树的广义表表示为a(b(c), d(e(g(h), f)，则该二叉树中度为1的结点数为_。A. 2 B. 3 C. 4 D. 521在一棵深度为h的完全二叉树中，所含结点个数不大于_。A. 2h B. 2h+1 C. 2h -1 D. 2h-122对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64)，为查找元素26，若采用折半查找，需要比较_次才能查找成功。A. 3 B. 4 C. 5 D. 623在对n个元素进行简单选择排序的过程中，需要进行_趟选择和交换。A. n/2 B. n-1 C. n D. n+124顶点个数为n的无向图最多有_条边。A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)25.用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的结果情况如下_： 23，21，47，15，27，59，35，20，72 21，23，15，27，47，35，20，59，72 21，15，23，27，35，20，47，59，72则所采用的排序方法是_A.选择排序 B.起泡排序C.归并排序 D.快速排序26. 设散列表长m=14,散列函数H（K）=K11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是_。A 8 B 3 C 5 D 927. 一个无向连通图的生成树是含有该连通图的全部项点的_。A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图28. 设x是一棵树，x是对应于x的二叉树，则x的后根次序遍历和x的_次序遍历相同A.先序 B.中序 C.后序 D.都不是29设有100个元素，用折半查找法进行查找时，在查找成功的情况下，最大比较次数是_ 。A.100 B.50 C.99 D.730. 下面关于图的存储的叙述中，哪一个是正确的。 _A 用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B 用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关31对于哈希函数H(key)=key MOD 13，被称为同义词的关键字是_A.35和41 B.23和39C.15和44 D.25和5132对下列二叉树进行后序遍历，其遍历结果为（ ）。a b c d e f gAgfedcbaBdbgefcaCbdecgfaDdbaecgf33. 从二叉排序树中查找一个元素时，其时间复杂度大致为_。A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2)34. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）。A1和5B2和4C4和2D5和135. 快速排序算法在最好情况下的时间复杂度为（ ）。AO(n)BO(n2)CO(nlog2n)DO(log2n)36. 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ）。A堆排序C直接插入排序B冒泡排序D快速排序37在线索化二叉树中，t所指结点没有左子树的充要条件是（ ）。A. tleft=NULL B. tltag=1 C. tltag=1且tleft=NULL D. 以上都不对38深度为5的二叉树至多有（ ）个结点。A. 16 B. 32 C. 31 D. 10 39 折半查找有序表（6,15,30,37,65,68,70,72,89,99），若查找元素37，则需要依次与表中元素（ ）进行比较。A.65,15,37B. 68,30，37C. 65,15,30D.65,15,30,3740 对长度为10的表作选择排序（简单选择排序），共需要比较（ ）次关键字。A. 45 B. 90 C. 55 D. 110二、 填空题 24题 1. 在有n个顶点的有向图中，每个顶点的度最大可达_2（n-1）_。2. 折半搜索只适合用于_顺序存储的有序表_。3. 已知二叉树中叶子数为50，共有一个孩子的结点数为30，则总结点数为_129_。4. 在二叉链表中判断某指针P所指结点为叶子结点的条件是_P-lchild=NULL&P-rchild=NULL_。5. 在非空线性表中除第一个元素外，集合中每个数据元素只有一个_直接前驱_；除最后一个元素之外，集合中每个数据元素均只有一个_直接后继_。6. 在二查排序树中，按照_中序_方式进行结点的遍历能够得到结点的递增有序序列。7. 某带头结点的循环单链表的头指针head，判定该链表为空的条件_head-next=NULL_。8. 有n各结点的二叉树的最大高度为_n_,最小高度为_log2n取整_+1_。9.三个结点的二叉树，最多有_5_种形状。10 设有10个值，构成哈夫曼树，则该哈夫曼树共有_19_个结点。11将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_排序_。12.如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_连通图_。13 设一行优先顺序存储的数组A56，A00的地址为1100，且每个元素占2个存储单元，则A23的地址为_1130_。14. 某带头结点的单链表的头指针head，判定该单链表非空的条件_head-next!=NULL_。15 假定一棵二叉树的结点个数为32，则它的最小深度为_6_。16下图所示二叉树存储在一维数组中，则元素F的下标位置为_11_。17. 每次从无序表中挑选出一个最大或最小元素，把它交换到有序表的一端，此种排序方法叫做_简单选择_排序。18假定一组数据的关键字为46,79,56,38,40,84，则利用堆排序方法建立的初始小顶堆为_38,40,56,79,46,84_。19. 对20个记录进行2路-归并排序时，共需要进行_5_趟归并。20. 任何一棵二叉树，若n0，n2分别是度为0，2的结点的个数，则n0和n2的关系为_ n0=n2+1 _ _。21. 在具有n个结点的二叉链表中，有_n+1_个空链域。22. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_O（log2n）_。23.在一个有向图中，所有顶点入度之和等于所有出度之和的 1 倍。24在一棵二叉树中，度为0的结点个数为N0，度为2的结点个数为N2,则N0= N2+1 。三、 解答题 12题 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，写直接插入排序算法的各趟排序结束时，关键字序列的状态。初始态: 265301 751 129 937 863 742 694 076 438第一趟：265 301751 129 937 863 742 694 076 438第二趟：265 301 751129 937 863 742 694 076 438第三趟：129 265 301 751937 863 742 694 076 438第四趟：129 265 301 751 937863 742 694 076 438第五趟：129 265 301 751 863 937742 694 076 438第六趟：129 265 301 742 751 863 937694 076 438第七趟：129 265 301 694 742 751 863 937076 438第八趟：076 129 265 301 694 742 751 863 937438第九趟：076 129 265 301 438 694 742 751 863 937 2.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，写快速排序算法的各趟排序结束时，关键字序列的状态。初始态： 265 301 751 129 937 863 742 694 076 438第二层： 076 129 265 751 937 863 742 694 301 438第三层： 076 129 265 438 301 694 742 751 863 937第四层： 076 129 265 301 438 694 742 751 863 937第五层： 076 129 265 301 438 694 742 751 863 937第六层： 076 129 265 301 438 694 742 751 863 937 3.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，写冒泡排序算法的各趟排序结束时，关键字序列的状态。初始态 265 301 751 129 937 863 742 694 076 438第一趟： 076 265 301 751 129 937 863 742 694 438第二趟： 076 129 265 301 751 438 937 863 742 694第三趟： 076 129 265 301 438 694 751 937 863 742第四趟： 076 129 265 301 438 694 742 751 937 863第五趟： 076 129 265 301 438 694 742 751 863 937第六趟： 076 129 265 301 438 694 742 751 863 9374. .以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，写直接选择排序算法的各趟排序结束时，关键字序列的状态。初始态 265 301 751 129 937 863 742 694 076 438第一趟： 076 301 751 129 937 863 742 694 265 438第二趟： 076 129 751 301 937 863 742 694 265 438第三趟： 076 129 265 301 937 863 742 694 751 438第四趟： 076 129 265 301 937 863 742 694 751 438第五趟： 076 129 265 301 438 863 742 694 751 937第六趟： 076 129 265 301 438 694 742 751 863 937第七趟： 076 129 265 301 438 694 742 751 863 937第八趟： 076 129 265 301 438 694 742 751 937 863第九趟： 076 129 265 301 438 694 742 751 863 937 5.一棵度为2的有序树与一棵二叉树有何区别? 一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。6. 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。三个结点的树如下：只有两种形态 / | | 三个结点的二叉树如下所示：有五种形态： (1) (2) (3) (4) (5) / / / / / 7.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，.nm个度为m的结点，问该树中有多少片叶子? 设该树中的叶子数为n0个。该树中的总结点数为n个，则有： n=n0+n1+n2+nm (1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为： n-1=0*n0+1*n1+2*n2+m*nm (2) 联立(1)(2)方程组可得： 叶子数为：n0=1+0*n1+1*n2+2*n3+.+(m-1)*nm8 高度为h的完全二叉树至少有多少个结点?至多有多少个结点? 高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。9 在具有n个结点的k叉树(k=2)的k叉链表表示中，有多少个空指针?n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+110 假设二叉树包含的结点数据为1，3，7，12。(1)画出两棵高度最大的二叉树；(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。 (1)高度最大的两棵二叉树如图：1 1/ 3 3/ 7 7/ 2 2/ 12 12(2)两棵完全二叉树如下：12 12/ / 7 3 7 3/ / 1 2 2 111. 高度为h的严格二叉树至少有多少个结点?至多有多少个结点? 所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。 所以：高度为h的的严格二叉树至少有2h-1个结点；至多有2h-1个结点(即满二叉树)。12.假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10.(1)为这8个字母设计哈夫曼编码。(2)若用这三位二进制数(07)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分 之几?它使电文总长平均压缩多少? (1)哈夫曼编码 根据上图可得编码表：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87% 其平均码长是等长码的87%。 所以平均压缩率为13%。四、 算法题4题 1. 将下面算法填完整。int Search_Bin(SSTable ST, KeyType key) /在有序表ST中折半查找其关键字等于key的数据元素，若找到，则返回该元素/在表中的位置，否则返回0 low=1;high=ST.length; while(low=high) mid=_(_low+high)/2_; if(key= ST.elemmid.key) return _mid_; else if(ke