数据结构答疑2014

1、 数据结构答疑数据结构答疑郑州大学信息管理学院郑州大学信息管理学院徐爱琴徐爱琴一、考试方式 闭卷笔试二、考试的基本要求 本课程要求了解各种常用的数据结构、各种数据结构内涵的逻辑关系及其在计算机中的存储表示以及这些数据结构上的运算和实际的执行算法。掌握线性表、栈、队列的数据结构及各种操作和算法实现，树、图的逻辑结构及物理存储，常用的排序和查找算法。三、考试题型及试卷结构 试卷有选择题占20%、是非题占20%、数据处理题占30%、编写算法题占30%。四、例题解析 按照以上四种题型，选取部分例题，介绍解题思路及解答方法。（一）选择题1采用线性链表表示一个向量时，要求占用的存储空间地址( D )。 A

2、必须是连续的 B部分地址必须是连续的 C一定是不连续的 D可连续可不连续2在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行( D )。 As-link=p-link; p-link=s; Bp-link=s; s-link=q; Cp-link=s-link; s-link=p; Dq-link=s; s-link=p; 3设有两个串t和p，求p在t中首次出现的位置的运算叫做( B )。 A求子串 B模式匹配 C串替换 D串连接 4将一个递归算法改为对应的非递归算法时，通常需要使用( A )。 A栈 B队列 C循环队列 D优先队列 5在循环队列中用数组A0.m-1存

3、放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是( D )。 A(front-rear+1)%m B(rear-front+1)%m C(front-rear+m)%m D(rear-front+m)%m 6在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ D ）。 Aq一next=p一next；p一next=q； Bp一next=q一next；q=p； Cq一next=p；p一next=q； Dp一next=q一next；q一next=p； 7向二叉排序树中插入一个元素时，其时间复杂度大致为（ B ）。 AO（1） BO（1

4、og2n） CO（n） D O（nlog2n） 8在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ D ）条边。 An Bn*(n+1)/2 Cn*n Dn-19假定一棵完全二叉树的结点个数为50，则它的深度为（ D ）。 A3 B4 C5 D610队列的另外一个别称是（ A ） A先进先出表 B后进先出表 C链队列 D顺序队列11一个算法的实现依赖于采用的（B ）A逻辑结构 B存储结构 C时间复杂度 D空间复杂度 12一个数组第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是（ B ）A110 B108 C100 D12013一个栈的入栈序列是a,b,c,d,e，

5、则栈的不可能的输出序列是（ C ）Aedcba Bdecba Cdceab Dabcde14判断一个循环队列QU（最多元素为maxsize）为空的条件是（ A ）AQUfrontQUrearBQUfront！QUrearCQUfront（QUrear1）maxsizeDQUfront！（QUrear1）maxsize15如果一棵二叉树任意一层的结点数都达到该层的最多数,该二叉树称为（ C ）A平衡二叉树 B二叉排序树 C满二叉树 D完全二叉树16在一个长度为n的顺序存储的线性表中，删除第i个元素（1in）时，需要从前向后依次前移（ A ）个元素。A n-i B n-i+1 C n-i-1 D

6、i17一个深度为k的满二叉树有（ B ）个结点A2k B2k1 C2k-1 D2k118树最适合用来表示（ C ）A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据19对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ D ）An B(n1)2 Cn1 Dn220排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ D ）A希尔排序 B气泡排序 C插入排序 D选择排序（二）是非题1. 直接插入排序方法是稳定的。（ ）2. 若已知一个数组的起始存储地址和维数以及每维的上、下界，且已知每个数组元素所占有的单

7、元数，则不管按照行优先还是列优先，元素aij 的存储地址是一样的。（ ）3. 顺序表只能用顺序方式来查询。（ ）4. 将一个森林或者一棵树转换成一棵二叉树后，得到的二叉树不惟一。（ ）5. 将一棵树转换成一棵二叉树之后，二叉树的根结点的右子树必定为空。（ ）6.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面。 （ ）7二分查找和二叉排序树的时间性能是相同的。（ ）8可以对链表进行二分法排序。（ ）9无向完全图的顶点数为n，则边的数目为n*n。（ ）10二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。（ ）（三）数据处理题1.设给定权集w2，3，

8、4，7，8，9，试构造关于w的一棵哈夫曼树。181599785423332.请给出上图的先序和后序遍历结点序列。ABDEHCFIGJDHEBIFJGCAFBADEGHIJC3. 请给出上图的二叉树形态。ABDEFCGIHJABDEFCGIHJ4.写出下图的拓扑序列.A C B D E FABCDEF5.使用普里姆算法（或克鲁斯卡尔算法）构造出下图的一棵最小生成树。12435 616355、2664512435 66.设下图以邻接矩阵形式存储，指出从顶点1出发的深度优先遍历和广度优先遍历序列。 深度优先遍历和广度优先遍历序列均是12345124537.已知一关键字序列为70，83，100，65，

9、10，32，7，9，请给出采用直接插入排序法对该序列作升序排序时的每一趟的结果。初始：（70），83，100，65，10，32，7，91趟：（70，83），100，65，10，32，7，92趟：（70，83，100），65，10，32，7，93趟：（65，70，83，100），10，32，7，94趟：（10，65，70，83，100），32，7，95趟：（10，32，65，70，83，100），7，96趟：（7，10，32，65，70，83，100），97趟：（7，9，10，32，65，70，83，100）8.已知一关键字序列为17，18，60，40，7，32，73，65，85，请给出采用直接

10、气泡排序法对该序列作升序排序时的每一趟的结果。初始：17，18，60，40，7，32，73，65，851趟：17，18，40，7，32，60，65，73，852趟：17，18，7，32，40，60，65，73，853趟：17，7，18，32，40，60，65，73，854趟：7，17，18，32，40，60，65，73，855趟：7，17，18，32，40，60，65，73，85第5趟无元素交换，则排序结束。9.已知有一关键字序列为13，15，6，10，20，8，3, 19，现采用简单选择排序的方法进行排序（按照升序排列），请给出每一趟排序的结果。 (0) 13 15 6 10 20 8 3

11、19 (1) 3 15 6 10 20 8 13 19 (2) 3 6 15 10 20 8 13 19 (3) 3 6 8 10 20 15 13 19 (4) 3 6 8 10 20 15 13 19 (5) 3 6 8 10 13 15 20 19 (6) 3 6 8 10 13 15 20 19 (7) 3 6 8 10 13 15 19 20 （四）编写算法1.已知一个顺序表A，其中的元素按值非递减有序排列，编写一个函数插入一个元素x后保持该顺序表仍按非递减有序排列。void insert(listtp A, int n, x) int i, j; if(x=An-1) An=x e

12、lse i=0; while(x=Ai) i+; for(j=n-1; j=i; j-) Aj+1=Aj; Ai=x; n+;2.编写一个函数将一个顺序表A（有n个元素，且任何元素均不为0）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。void ret(listtp A, int n) listtp B, C; int p, q; p=0;q=0; for(int i=0; i0) Bp=Ai; p+; else Cq=Ai; q+; 3.编写一个链接两个单链表的算法。设有链表A和B，B链表链接在A链表之后，产生新链表C，原链表不破坏。linklist *merge(

13、linklist *headA,linklist *headB) linklist *headC; headC=(struct lnode *)malloc(sizeof(struct lnode); headC-next=null; lnode *p,*q; p=headA-next; r=headC; while(p!=null) s=(struct lnode *)malloc(sizeof(struct lnode); s-data=p-data; s-next=null; r-next=s; r=s; p=p-next; p=headB-next; while(p!=null) s=

14、(struct lnode *)malloc(sizeof(struct lnode); s-data=p-data; s-next=null; r-next=s; r=s； p=p-next; return(headC); 4.编写将一单链表逆置的算法。 linklist * invert (linklist *head) list * p , * q, * r; p =head-next ; q =p -next; while (q !=null) r = q - next ; q - next=head-next ; head-next =q ; q = r ;r=r-next; p -

15、next =null ; return head;5.设计算法，将顺序串r中所有字符按相反的次序逆置。 void invert(SqString &r) int i; char tmp; for (i=0;i(r.len/2);i+) tmp=r.chi; r.chi=r.chr.len-i-1; r.chr.len-i-1=tmp; 6.设计算法，从顺序串r中删除其值等于ch的所有字符。 void delall(SqString &r,char ch) int i,j; for (i=0;ir.len;i+) if (r.chi=ch) for (j=i;jlchild); num2=nodes(b-rchild); return(num1+num2+1); 8.设计一个算法，求出给定二叉排序树中最小和最大的关键字。 KeyType MinKey(BSTNode