《数据结构习题集作业.docx》由会员分享，可在线阅读，更多相关《数据结构习题集作业.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点像一个元素结点)。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结 点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为 了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。2. 2填空题。解：在顺序表中插入或者删除一个元素，需要平均挪移表中一半元素,具体挪移的元素个数与兀 素在表中的位置有关。(2)顺序表中逻辑上相邻的元素的物理位置必然紧邻。单链表中逻辑上相邻的元素的物理位置不一定 紧邻。(3)在单链表中，除了首元结点外，任一结
2、点的存储位置由其前驱结点的链域的值指示。(4)在兽唾液中设置头结点、的作用是插入和删除首元结点时不用进行特殊处理2. 3在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机 存取。2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中 选择合适的语句序列。a在P结点后插入S结点的语句序列是.b.在P结点前插入S结点的语句序列是。c,在表首插入S结点的语句序列是.d.在表尾插入S结点的语句序列是 o(l)P-next=S; (2)P-next=P-next-next ; (3)P-ne
3、xt=S-next; (4)S-next=P-next; (5)S-next=L; (6)S-next=NULL;(7)Q=P；(8)while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(H)P=L;(12)L=S;(13)L=P;解：a. (4) (1) b,)(8)c.(5)(12) d.2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答 案中选择合适的语句序列。a删除P结点的直接后继结点的语句序列是.b.删除P结点的直接前驱结点的语句序列是a2 =1x2+1x34-2
4、x4+4x5an= 1 xn+1 x(n+1 )+2x(n+2)+4x(n+3)Sn = 8N+17=驯舞+ 17NU1ZN + l 17ASL =+ 28第io章 第i题没答案 自己做c.删除P结点的语句序列是。d.删除首元结点的语句序列是 Oe.删除尾元结点的语句序列是 o(1 )P=P-next;(2)P-next=P;(3)P-next=P-next-next;(4)P=P-next-next;(5)while(P!=NULL)P=P-next;(6)while(Q-next!=NULL)P=Q;Q=Q-next;(7) while(P-next!=Q)P=P-next;(8)whil
5、e(P-next-next!=Q)P=P-next;(9)while(P-next-next!=NULL)P=P-next;(10)Q=P；(1 l)Q=P-next;(I2)P=L;(13)L=L-next;(14)free(q);解：a. (11)(14)b.(10)(12)(8)(3)(14)c.( 10X12)(7X3)(14)d.(12)(ll)(3)(14)已(11 )(3)( 14)2. 13试写一算法在带头结点的单链表结构上实现线性表操作Located,x);解：int LocateElem_L(LinkList &L,ElemType x)int i=0;LinkList p
6、=L;while(p&p-data! =x) p=p-next;i+；if(!p)return 0;else return i;2.23设线性表A=(4a2 ,am)B=(b,b2 ，h),试写一个按下列规则合并A3为所生表C的算法，即使得C=(a,bi ,am,bm,b+,bj 当mSn 时；C=(ai.9am) 当mn 时。线性表A,B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长 度值m和n均未显式存储。解：将合并后的结果放在C表中，并删除B表Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)L
7、inkList pa, pb,qa,qb;pa=A-next;pb=B-next;C=A;while(pa&pb)qa=pa;qb=pb;pa=pa-next; pb=pb-next;qb-next=qa-next;qa-next=qb;if(! pa)qb-next=pb;pb=B； free(pb);return OK;2.25假设以两个元素依值递增有序罗列的线性表A和B分别表示两个集合(即同一表中的元素值各不相 同)，现要求另辟空间构成一个线性表C,其元素为A和B中元素的蜂，且表C中的元素有依值递增有序 罗列。试对顺序趣写求C的算法。解：将A、B求交后的结果放在C表中Status Lis
8、tCross_Sq(SqList &A,SqList &B,SqList &C)int i=O,j=O,k=O;while(iA.length & jB.length)if(A.elemiJB.elemj)j+;elseListInsert_Sq(C,k,A.elemi);i+；k+;return OK;3.2简述栈和线性表的差别。解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或者删除操作的 线性表。3. 3写出下列程序段的输出结果(栈的元素类型SElemType为char)。 void main() Stack S;char x,y;InitStack(s);x=
9、e；y二k；Push(S,x); Push(S/a,); Push(S,y);Pop(S,x);Push(S/f); Push(S,x);Pop(S,x);Push(S,s,);while(!StackEmpty(S)Pop(S,y);printf(y);printf(x); | 解：stack 3.11简述队列和堆栈这两种数据类型的相同点和差异处。解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。3.12写出以下程序段的输出结果(队列中的元素类型QElemType为char)。 v
10、oid main(Queue Q;InitQueue(Q);char x=,e,y=,c,;EnQueue(Q/h*);EnQueue(Q,r,);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q/a);While(! QueueEmpty(Q) ( DeQueue(Q,y): couty; 人 coutX;解：char第四章串4.34.4 参考习题集后面的答案4.13int Delete_SubString(Stringtype &s,Stringtype t)从串s 中删除所有与t相同的子 串，喻啜for(n=OJ=
11、l ;i=Strlen(s)-Strlen(t)+l ;i+)if(!StrCompare(SubString(s,i,Strlen(t),t) )StrAssign(head,SubString(S44-l)；StrAssign(tail,SubString(S4+Strlen(t),Strlen(s)-i-Strlen(t)+l);StrAssign (S, Concat (head, tail);/JC hd, tail 连接为新事n+;/ifreturn n/Delete_SubString第5章数组与广义表5. 10 解:(1 )GetHead (p,h,w) = p(2)GetTa
12、il【(b,k,p,h) =(k,p,h)(3)GetHead (a,b),(c,d) 二(a,b)(4)GetTail (a,b),(c,d) =(c,d)(5)GetHead GetTail (a,b),(c,d) = Getllead (c, d) =(c, d)(6)GetTail GetHead (a,b),(c,d) = GetTail (a,b) =(b)(7)GetHead GetTail GetHead (a,b),(c,d) = GetHead (b) = b(8)GetTail GetHead GetTail (a,b),(c,d) = GetTail (c,d)l =(
13、d) 5.125. 13 解：(l)List=(x,(y),(),(0),(z)(2)List=(a,b,(),(),(a,(b),()6章树和二叉树6. 1参考习题集后的答案6.4一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每一个结点都有k 棵非空子树。如果按层次顺序从1开始对全部结点编号，问：(1)各层的结点数目是多少？(2)编号为p的结点的父结点(若存在)的编号是多少？(3)编号为p的结点的第1个儿子结点(若存在)的编号是多少？(4)编号般的点有右兄弟的条件是什么？其右兄弟的编号是多少？缶刀Z.X恿目T解：(1)(2)如果p是其双亲的最小的孩子(右孩子)，则p
14、减去根结点的一个结点，应是k的整数倍，该整数 即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果P是其双亲的最大的孩子(左 孩子)，则p+k-1为其最小的弟弟，再减去一个根结点，除以k,即为其双亲结点的编号。综合来说，对于p是左孩子的情况，i=(p+k-2)/k; 对于p是右孩子的情况，i=(p-l)/k如果左孩子的编号为1k贝续右孩子编号必为p+k-1,所以，其双亲结点的编号为向下取整，如1.5向下取整为1(3)结点p的右孩子的编号为kp+1,左孩子的编号为kp+1-k+l=k(p-1)+2,第1个孩子的编号为 k(p- l)+2+i- l=kp-k+i+l 0(4)当(p-
15、l)%k!=O 时，结点p有右兄弟，其右兄弟的编号为p+1。6.6已知在一棵含有n个结点的树中，惟独度为k的分支结点和度为0的叶子结点。试求该树含有的叶子 节点数目。解：利用上题结论易得结果。设度为k的结点个数为几则总结点数为0=1时。叶子结点的数目应等于总结点数减去度不为0的结点的数目，即一1“0 =一如k6. 14找出所有满足下列条件的二叉树：(a)它们在先序遍历和中序遍历时，得到的节点访问序列相同;(b)它们在后序遍历和中序遍历时，得到的结点访问序列相同;(c)它们在先序遍历和后序遍历时，得到的节点访问序列相同。解：(a)不含左子树的二叉树。(b)不含右子树的二叉树。(c)即不含左子树，
16、也不含右子树的二叉树。7.1 解：(1)ID(1)=3OD(1)=0OD(6)=300000111ID(2)=2 OD(2)=2ID(3)=1 OD(3)=2ID(4)=1 OD(4)=3ID(5)=2 OD(5)=1ID(6)=200 0 01001010 0001010 010(4)(5)有三个连通分量1、5、23467.3解：邻接表：邻接多重表:深度优先搜索的顺序为1 5 6 4 3 2广度优先搜索的顺序为1 5 6 3 2 4 ,15161312247. 9题参考习题集后的答案7.14 解：Status CreateAG(ALGraph &G)int n,e,k,ij；cout 请输入
17、顶点数：;cinn;cout* 请输入边数：； cine;G. vernum=n;G.arcnum=e;/建立顶点数组for(k=0;kG. vernum;k+) cout。请输入顶点信息：；cinG.vertices kJ .data;G. verticeskj .firstarc=NULL;/建立邻接表VertexType vl,v2;ArcNode *p,*q;for(k=0;kG.arcnum;k+) cout*请输入弧的始点和终点信息，中间用空格分开：;cinvlv2;i=LocateVex(G,v 1);if(iG.vernum-1)return ERROR;j=LocateVex
18、(G, v2);if(jG.vernum-1)return ERROR;if(i二二j) return ERROR;p=new ArcNode;if(!p)return ERROR;p-adjvex=j;p-nextarc=NULL;q=G.verticesi.firstarc;if(!q)G.verticesil.firstarc=p; elsewhile(q-nextarc)q=q-nextarc;/指针定位于邻接表的尾结点q-nextarc=p;return OK;int LocateVex(ALGraph& G,VertexIype v)int i=0;while(G.verticesi.data!=v&iG.vernum)i+;if(G.verticesLiJ.data=v)returnelse return -1;第9章查找9. 1解：（1）相同，平均查找长度为士（n + 1）相同，平均查找长度，给 碘n合期对于有序顺序表，平均查找长度为,对于无序顺序表,则为目后伽寺醺9. 2解:查找e的过程如下:III9.7 解:al = lx 14-1x2+2x3+4x4