数据结构马睿、孙丽云习题答案

1、一、选择题1、C 2 、 C 3 、二、判断题X 4 X#”语句的执行频度（ n 为正整数）。1X 2 X 3 三、简答题（略） 四、算法分析题：1）频度：n ，时间复杂度：O（n）2）频度：1 ，时间复杂度：O（1）3）频度：n 2，时间复杂度：O（n2）4）频度：n/2-1 ，时间复杂度： O（ n）5）频度：1100写出下列各程序段关于 n的时间复杂度。1）O( log 3n)1. 分析下列程序段中带标号“22）O（n2）3）O（n2）6、7、8、9、一、选择题1、A4. D 5. C 7. A二、填空题1. 、线性表2、3、前驱，后继 p->next; s->data; t

2、4、5、q->next head->next = NULL6、p->next, s7、8、p->next != pO(1), O(n)一、选择题1、C二、填空题10. D1. 、 n-12、3、O(n)135424、2xy+1x-/*5、a2, a 4, a 1, a 先进后出，加 满，空， n 线性结构2, 21， 减 110、4三、判断题1. 、错第2章 线性表第3 章 栈和队列2、3、4、5、6、7、错对错对错错14可能的顺序:四、解答题4、列车进入一个栈式结构的车站，开岀车站有abcd; abdcadcb acdb, acbdbdca.bcda, bead ba

3、cd, badc cdba, cbda, cbad, dcba列车进入一个队列式结构的车站，开岀车站有6, 24staxychar第一个循环：队列Q中的元素依次岀队，1可能的顺序：abcd5、7、8、9、岀队后即进栈第二个循环：栈S中的元素依次岀栈，岀栈后即进入队列第4章串一、选择题1、A 2、D 3、C 4、C 5、D二、简答题0。而空格串是由一个或多个空格组成的串,1、含零个字符的串称为空串，用表示，串的长度为 串的长度为所含空格的个数。由串中任意连续字符组成的子序列称为该串的子串。包含子串的串相应地被称为主串。假如一个串S= "a 0a1a2a n-1 ”(n > 0)，

4、其中：S为串名，用双引号括起来的内容为串的值，双引 号本身不是串的值。2、当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，两个串才相等。3、19，7，good，e， 0， 3，” I am a good teacher "，” a goodyestea ”4、j0123456模式串abcabaan extj-1000121三、算法题1、void Assig n( stri ng *s, stri ng t) Loc ( 3, 3) = Loc ( 0, 0 n =( 676 - 2 - 644) / 2 = 15)+ 3 * 15 + 3 = 644 + 45 + 3 =

5、692.2、( 1) 数组 B共有 1 + 2 + 3 +? + n= ( n+1 ) *n / 2 个元素。(2)只存下三角部分时，若i ? j，则数组元素 Aij 前面有i-1行(1?i-1，第0行第0列不算)，第1行有1个元素，第2行有2个元素，?，第i-1行有i-1个元素。在第i行中，第j号元素 排在第j个元素位置，因此，数组元素Aij 在数组B中的存放位置为：1 + 2 + ? +(i-1 )+ j =( i-1 ) *i / 2 + j若i < j ，数组元素 Aij 在数组B中没有存放，可以找它的对称元素Aji。在数组B的第(j-1 ) *j / 2 + i位置中找到。如果

6、第0行第0列也计入，数组 B从0号位置开始存放，则数组元素Aij 在数组B中的存放位置可以改为：当i ? j时，=i*(i+1 )/ 2 + j当i < j时，=j*(j+1 )/ 2 + i3、(1)Head(Tail(Tail(L1)(2)Head(Head(Tail(L2)(3)Head(Head(Tail(Tail(Head(4)Head(Head(Tail(Tail(L4)(5)Head(Tail(Head(L5)(6)Head(Head(Tail(Head(Tail(L3)(L6)4、由于线性表中的每个结点对应稀疏矩阵的一个非零元素，其中包括下标、列下标和值，结点间的次序按矩

7、阵的行优先顺序排列，这个线性表用顺序的方法存储在连续 的存储区，则对应的三元组为其十字链表形式为：)3个字段，分别为该元素的行5、6、L=(a,(b，C),(d®n 0 I四、算法题1、从前向后找零元素【算void move(i nt A,i nt n)int i=0,j=n-1;int temp;while(ivj)while(Ai!=0) i+;while(Aj=0) j-;if(i<j)tem p=Ai;Ai=Aj;Aj=tem p;2、【算法分析】为保证算法的时间复杂度为 就能生成C数组，我们可采用设三个下标指针从后向前元素1 AJ0dA将Ai与Aj交换。的最大值)、B

8、数组的第一个元素(B数组的最大值)、 数组的最大值大者放C数组k所指单元；在上述比较中若否则j所指单元数送完后j后移，同时k前移，直到把【算法源代码】O(m+n),即需要对数组 A和B的数据元素仅扫描一次 i,j,k初始时分别指向 A数组的最后一个元素(C数组将存放最大值的位置，然后比较 A数组i所指单元数大，则送完后iA与B数组的所有元素扫描完。A数组A与B前移，#defi ne m 3#defi ne n 4void Merge(i nt A,i nt B,i nt C)i nt i,j,k;i=m-1;j=0; k=m+n-1;while(i>=0)&&(j<

9、=n-1)if(Ai>Bj)Ck=Ai; i-;elseCk=Bj; j+; k-; Ck=Ai;i-;k-;Ck=Bj;j+;k-; while(i>=0)while(j<=n-1)3、【算法分析】 三元组表示中要求按行的顺序存放，所有转置过程不能直接将行下标和列下标转换， 还必须使得列按顺序存放。因此在A 中首先找出第一列中的所有元素，它们是转置矩阵中第一行非元素，并把它们依次放在转置矩阵三元组数组 B 中；然后依次找出第二列中的所有元素，把它们依 次放在数组B中；按照同样的方法逐列进行，直到找岀第n列的所有元素，并把它们依次放在数组中。【算法源代码】*/void tra

10、nspose(TSMatrix A,TSMatrix *B)/*A是稀疏矩阵的三元组形式，B是存放A的转置矩阵的三元组数组int i,j,k;B->mu=;B->nu=;B->tu=;if(B->tu>0)j=1;for(k=1;k<=;k+)for(i=1;i<=;i+)ifi.col=k)B->dataj.row=i.col;B->dataj.col=i.row; B->dataj.e=i.e; j+;4、算法分析】 在求广义表深度的递归算法中，若结点为原子则深度为 返回头指针与尾指针所指广义表的深度最大值。【算法源代码】0 ，若

11、是空表深度为 1，否则int Glist_Getdeph(Glist L) int m,n;if(!L->tag) return 0; else if(!L) return 1; m=Glist_Getdeph(L->+1; n=Glist_Getdeph(L-> return m>n?n:n;一选择题1、B 2 、A 3 、B 4 、A 5 、C 6 、C A 7 、 BB 9 、D 10、B11、 B 12 、B 13 、B 14 、 A 15 、C 16 、D 17 二填空题1 1 前驱 2 一个前驱结点 3 后继418 、A 19 、 C 20 、D后继n-1n

12、 o=n2 +11 2 2 101 A 2 D G F A C E 76. 2507. 18. 2n 0-19. 1 D 2 F10. 1 GEACBDF 2 111. 1 InOrderTraverse2.3.4.5.3 113 B E 4 A C 右85 B左9 210 4p ri ntf(T->data) 3InO rderTraverse (T->right)12.1C；n。n 1三.判断题1.X 2.X 3.V4. X 5. X6.V 7.X 8.V9. X 10. V四.操作题1 .(1)GCABFED(T->left)2(5)2.所有结点均没有左孩子的二叉树。

13、所有结点均没有右孩子的二叉树 只有一个根结点的二叉树证明：当n=1时，前序序列和中序序列均只有一个元素且相同， 叉树。假设n<m-1时，结论成立，现证明当 n=m时也成立。设前序序列为：a1 , a2，am,中序序列为：b1,b2，bm。因为前序序列由前序遍历得到，则a1为根结点元素；又中序序列由中序遍历得到，则在中序序列中必能找到和a1相同的元素并设为bj(1 < j w m),由此可得 b 1，-, bj-1为左子树的中序序列， bj+1 ,，bm为 右子树的中序序列。(1) 若j=1即b1为根，此时二叉树的左子树为空， b 2 ,，bm即为右子树的中序序列，右子树的结点数为

14、右子树，也唯一确定了二叉树。(2) 若j=m即bm为根，此时二叉树的右子树为空， b 2，bm即为左子树的中序序列，同(1), 二叉树。(3) 2< j w m-1，则子序列 a2，aj和序列，这两个序列唯一确定了左子树；子序列a3.(1)4.即为根，由此唯一地确定了这颗二2，am即为右子树的前序序列, m-1,由此，这两个序列唯一确定了2，am即为左子树的前序序列, 这两个序列唯一确定了左子树，也唯一确定了b1 ,，bj-1分别为左子树的前序序列和中序 j+1 ,，am和 bj+1 ,，bm分别为右子树的前序序列和中序序列，这两个序列唯一确定了右子树； 由此，证明了知道一棵二叉树的前序

15、序列和中序序列，就能唯一地确定一棵二叉树。5.GDN©MCGKDNHOM6.07.AB(b)AB(c)(d)54(e)WPL=1*5+3*5+5*4+9*3+16*2+20*1=119A:01B:0001C:001D:1E:00001F:000008.f波兰式：-+a*b-cd/ef逆波兰式:abcd-*+ef/-五.算法设计题=P；p=p->lchild;if(t op 匸-1) return stackt op .T; else return NULL;6.BiThrNode *P reOrder_Next(BiThrNode *p) n ");v=0;elsep

16、=(q->fron t)->n ext;(q->fron t)->n ext=p->n ext;if(p->n ext=NULL) q->rear=q->front; v=p->T;free( p);return v;void visite(LINKQUEUE *q, BiTree p)if(p!=NULL)prin tf("%c “,p->data); en li nkqueue( q,p);void Level_Traverse(BiTree T)/* LINKQUEUE Que,*Q;BiTree p;Q=&Q

17、ue;in itli nkqueue(Q);if(T匸NULL)按层次遍历二叉树*/p=dellinkqueue(Q); visite(Q,p->lchild); visite(Q,p->rchild);*/ visite(Q,T); while(!emptylinkqueue(Q) printf("The pointer which points at the last Node is %xn",p);/* 给出离根结点最远的一个结点(即最后一个出队的结点)的指针8int9/*Node(BiTree T) 求以孩子兄弟链表存储的树或森林 T 中的结点数，并通过

18、函数值返回 */int count; BiTree T1;if(T =NULL) return 0;else if(T->firstchild =NULL) return 1;else count=0; T1=T->firstchild; while(T1) count=cout+Node(T1);T1=T1->nextsibling?; return count?;/*bt 为空时，结点数为 0*/int/*High(BiTree T) 求以孩子兄弟链表存储的树或森林 T 的高度，并通过函数值返回 */int h1,h2;BiTree T1;if(T =NULL) retu

19、rn 0;else h1=High(T->firstchild)+1; h2=High(T->nextsibling); return h1>h2? h1:h2;/*bt 为空时，结点数为 0*/ 10char Pred,Midd; .Build_Sub(1,n,1,n); .分析: 本算法利用了这样一个性质 ,即一棵子树在前序和中序序列中所占的位置总是连续的 .因此,就 可以用起始下标和终止下标来确定一棵子树 .Pre_Start,Pre_End,Mid_Start 和 Mid_End 分别指示子 树在前序子序列里的起始下标 , 终止下标 , 和在中序子序列里的起始和终止下

20、标 .第 7章 图一、选择题1. B 2 . B 3 . B 和 C 4 . D和 E 5 . C 6. D 7 . A 8 . A 9 . D 10 . B二、填空题1. 1 n(n-1) 2 n(n-2)/2 32. 1 ABCDFE 2 ABCEFD3. 1 按深度4 极大5. 图本身6. 主对角线2 按广度n-17. 1 i 2 j8. 1 n-1 29. 20大于 n-1 3小于 n-12e 3 n10. 1 n+2e 211. 1 n+e 2 e 312. 无环三、判断题1X 2 V四、（略）五、（略）3 .VX 6 . X 7.X 8.X181920一、选择题1、 C 2 、 B

21、第8 章 查找、C 5 、C 6 、D 7 、B 8 、B 9 、 B 10 、D11、 C 12 、13 、 D14 、 D 15 、D 16 、C 17 、A 18 、B 19 、 D 20 、B二、判断题1 【答案】 【分析】顺序查找并没有假设数有序或者无序，因此有序或无序对平均查找长度没有影响。 2错误3答案】错误 答案】正确 答案】错误4【分析】链表表示的有序表不能用折半查找法查找。5 【答案】错误6 【答案】错误【分析】最优二叉树是静态树表， AVL 是动态树表，二者范围不同。 78910答案】正确答案】正确答案】正确【答案】正确【答案】错误11【分析】除非被删除的结点是叶子结点，

22、否则删除后再插入同一结点得到的二叉排序树与原来的二叉排序树不同。12【答案】错误13【答案】错误14【答案】错误15【答案】正确16【答案】正确17【答案】错误【分析】a越小，只能说发生冲突的可能性越小，但依然有可能发生冲突。答案】正确答案】正确答案】正确三、填空题1 .【分析】最优二叉树是对叶子结点带权平均查找路径长度最小的树，最优查找树是对所有结点带 权查找路径长度最小的树，构造这两种树均需要知道关键字的查找概率。【解答】叶子结点数结点数需要n个关键字的查找概率表?log 2n+1,所以，最大比较次数为?log 2n+1。2. 【分析】折半查找法在查找成功与不成功时进行比较的关键字个数最多

23、不超过树的深度，而具有 n个结点的判定树的深度为【答案】？log 2n+13.【分析】平均检索长度ASJs=(s+n/s)/2+1，所以当 S=jn 时，ASG 取得最小值 “+1。21每个结点两个关键字,1 22X 1 + 2 X 3 + 2X 3 =26。【解答】16174.【分析】第4层是叶子结点,【答案】26四、简答题1. 【解答】判定树如下所示：596等概率查找时成功的平均查找4ASLsucc=110(1 X 1+2 X 2+3 X 4+4 X 3)=(2)(3)2 .【解(1)/1 2=找。序树：10c=(1+2+DecI50 100答D键字的顺序构造的二叉8Jan根据构造的二叉A

24、SLsu2*2+3*3+4*3+b中元素先进行排序字树求查找成功时的平均查找长度：*1)/12=构造二叉排序树，则构造的二叉排序树是一棵单支树,的情况下查找成功A这种情况3. 【解答】4. 插入军答】勺查找长度贝(Sep)30'60 70 290插入20-插9入10(2080入640290插入110930201006020那么,可知道12018030 40删除150705 .【解答】令Fk表示含有最少结点的深度为k的平衡二叉树的结点数目。hashf1(1)=1hashf1(13)=2n = Fn-2 +Fn-l + 1.F1=1,F2=2,.F含有12个结点的平衡二叉树的最大深度为5.

25、例如:6.7.C黑测再【解答】452王要8.哈H解答】使用线性探测列法来构造哈希表【解答】IB6070记录数0. 30L口链地址法Na乜0 30丿 Q_60 7O7地址数据012345678910331131234382722hashf1(12)=1hashf1(34)=3hashf1(38)=5hashf1(27)=5hashf1(22)=0hashf2(12) = (1+1)%11=2hashf3(12)= (1+2)%11=3hashf2(34)=(3+1)%11=4hashf1(33)=0hashf2(27)=(5+1)%11=6hashf2(22)=(0+1)%11=1hashf3(

26、22)=2hashf4(22)=3hashf5(22)=4 hashf6(22)=5 hashf7(22)=6 hashf8(22)=7装填因子？= 8/11查找成功所需的平均查找次数：(1+1+3+2+1+1+2+8)/8=19/8使用链地址法来构造哈希表如下图所示：0查找9.解2(1*3+2*3+3*1)/8=3/234AprDecFeb平均5查找长度为678910111213141516MarMayJuneJulySepOctNov5Jan(2)AprAug ADec I A10Feb JanMar OctJuneA1 NovAJuly ASep 卜10 11 12 13 14 15 1

27、6平均查找长度为：3/2五、算法设计题1.【分析】算法思想：先遍历右子树后遍历左子树。【解答】算法如下：In order(BiSTree bt, dataty pe X) if (bt) Inorder(bt->rchild，X);if(bt->data >=X) printf( “ %c ， bt->data);Inorder(bt->lchild，X);2.【分析】在合并过程中，并不释放或新建任何结点，而是采取修改指针的方式来完成合并，这样, 就必须按照后序序列把一棵树中元素逐个连接到另一棵树上，否则将会导致树的结构的混乱。解答】算法如下：void BiTMe

28、rge(BiSTree *T, BiSTree *S) if(S->lchild) BiTMerge (T if(S->rchild) BiTMerge (T Insert_Node(T , S);void Insert (BiSTree *T if(S->data>T->data) if (!T->rchild) T->rchild=S; else Insert (T->rchild else if(S->data<T->data) if (!T->lchild) T->lchild=S; else Insert

29、(T->lchildS->lchild=NULL;S->rchild=NULL;/* 把二叉排序树合并到 T 中*/, S->lchild);, S->rchild)/* 合并子树 */，BiSTNode *S)，S);，S);/*把树结点S插入到T的合适位置*/* 插入的新结点必须和原来的左右子树断绝关系/* 否则会导致树结构的混乱 */*/3【分析】算法思想；以 x 为分界点遍历原二叉树并构造两棵新的二叉排序树。 【解答】算法如下 :void BiTSplit(BiSTree *T, BiSTree *A, BiSTree *B/*把二叉排序树T分裂为两棵二叉

30、排序树A和B,其中, int x)A的元素全部小于等于x，B 的元素全部大于 x*/ if (T->lchild) BiTSplit(T->lchildif (T->rchild) BiTSplit(T->rchildif (T->data<=x) Insert(Aelse Insert(B , T);void Insert (BiSTree *T,BiSTNode *S)/*把树结点S插入到T的合适位置上*/,A,A,B,B,x);x);/* 分裂左右子树*/,T);/* 将元素结点插入到T 的合适位置上 */*考虑到刚开始分裂时树A和树B为空的情况*/

31、if(!T) T=S;else if(S->data>T->rchild)if (!T->rchild) T->rchild=S;else Insert (T->else if(S->data<T->data) if(T->lchild) T->lchild=S; else Insert (T->S->lchild=NULL;S->rchild=NULL;4【提示】对于每次查找的思想是相同的,只是查找区间发生了变化,因此写为递归算法时要将查 找区间的上下限作为参数,递归调用时查找区间的上下限是变化的。int B

32、inSearch(datatype R , int low, int hig, keytype K) int mid;if (low<hig) return(0);else mid=(low+hig)/2;if(K=Rmid.key) return(mid);else if (K> Rmid.key) return(Binsearch(R, mid+1,hig,K); else return( Binsrch (R,low,mid-1,K) );5【提示】先在有序表 R 中利用折半查找法查找关键字值小于或等于x 的结点， mid 指向关键字正好等于x的结点或low指向关键字正好大于

33、 x的结点，然后采用移动法插入 x结点即可。void BinInsert (datatype R, KeyType x) int low=1,hig=n,mid,inplace,i,find=0;while (low<=hig && !find) mid=(low+hig)/2;if < Rmid.key) hig=mid-1;else if > Rmid.key) low=mid+1;else i=mid;find=1;if (find) inspace=mid;else inspace=low;for (i=n;i>=inspace;i-) Ri+1

34、=Ri; Rinspace=x;6【提示】调整中序递归遍历算法，先遍历右子树，然后输出根结点的值，再遍历左子树。void PrintNode (BiSTree T) if (T)PrintNode(T->rchild); printf( T->data) ;PrintNode(T->lchild);7【提示】解决本题的关键是递归函数的参数设置，采用逐渐缩小查找区间的方法来实现。void fun(BiSTree T int x, int *a, int *b) if (T) if (x<T-> *b =T-> ;/*当x小于根结点时，修改 b,在左子树上继续查

35、找*/fun(T->lchild, x,a,b); else if (x>T->/*当x大于根结点时，修改a,在右子树上继续查找*/ *a = T-> ;fun(T->rchild,x,a,b);else if (T->lchild) p=T->lchildwhile (p->rchild) p=p->rchild; *a=p->/* 当 x 等于根结点时， a 是其左子树的最右下结点，/* 是其右子树的最左下结点 */b*/if (T->rchild) p=T->rchild;while (p->lchild )

36、p=p->lchild;*b=p->8【提示】判断一棵二叉树是否是二叉排序树，可以采用递归算法。对于树中所有结点，检查其左 子树上所有结点的关键字是否都小于它的关键字，检查其右子树上所有结点的关键字是否都大于它 的关键字。int BinSortTree(BiSTree T)判别由二叉链表存储的二叉树是否为二叉排序树，是则返回/*1，否则返回 0*/int l,r;if (!T ) return 1;else if (T->lchild=NULL && T->rchild=NULL ) return 1;/* 空树是二叉排序树 */* 只有一个根结点是二叉

37、排序树 */else l = BinSortTree( T->lchild);r = BinSortTree( T->rchild);if (T->lchild && T->rchild )if (T->key>T->lchild->key && T->key<T->rchild->key && l && r) return 1;else ruturn 0;else if (T->lchild=NULL )return ( T->key < T->rchild->key && r) else return( T->key > T->lchild->key && l)/ * 只有一个根结点是二叉排序树 */* 只有一个根结点是二叉排序树*/9【提示】输入关键字后，应先确定其哈希地址，再将其插入到相应的单链表中去。typedef struct HNode