华南理工大学网络教育学院数据结构同步练习册答案

1、第1章绪论习题11.1什么是数据、数据元素、原子元素？，它们有何区别？。答：数据：用以描述客观事物的数、字符以及所有能被计算机接受和处理的符号的集合 称为数据。例如整数、实数、字符、字符串、表格及各种图像、声音等。数据元素：就是数 据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可 以由若干数据项组成。原子元素是物理学的概念。1.2分析下列程序段的运行时间(时间复杂度)。void mysteiy (mt n) mt i,j, k,for(i=l;i<n; i卄)foi (j = i+l, j<= n, j+)for (k = l;k<=j;k+)

2、;)答：0(2)void odd (int n) int 1, j, x = 0, y = 0;foi (1 =1, i <= li, i卄)if odd(i) foiQ = i, j <= n, j+)x+;for( j = l;j<= i; j+-b)y十)答：0(1?)void lecuisive (int n) if (n <= 1) leturn 1,else letinn (recursive (n -1)十 recuisive(n -1);)答：0(11)1.3设舁为正整数，试确定下列各程序段中带标号的语句的频度。(1) int 1 =l,k= 0：whi

3、le (i <= n-1) k = k十10*i： i = i+l： 答：n-1(2丿 int 1 -1, j - 0；wlule (i+j) <= n)if (i>i)卄七else 1十十；答：ii/2(3丿 int 1 =l,k= 0：while (1 <= u) k = k+10h;i卄；)答：11-1解析:1=1;/Ik=O,/lwlule(i<n) /nk=k+10*i,/n-l1+; /ll-l)由以上列出的各语句的频度，可得该程序段的时间消耗：T (n)= 1+1 +n+ (n-1)+(n-1 )=3n可表示为T(n)=O(n)(4丿 100：wlu

4、le (v > 0) if (x> 100) x = x -10, v;)else x十十；答：100解析：x=91;/lv=100, /Iv4ule(v>0) /1101if(x>100)/1100 x=x-10,/100y;/100)elsex-H-; /1000以上程序段右侧列出了执行次数。该程序段的执行时间为：T(n)=O(l)(5) mtx- 0,for (int 1 =1; 1 <= n; i卄)for (int j=l, j<=i, j+) for (int k = 1; k <= j; k卄)x卄;答：ir/2+ii(6) int x

5、= n, y = 0,/ n> 1while (x >= (y+l)*(v+l) v十十;答：yfy-1解析：由x=n且x的值在程序中不变，又wiule的循环条件(x>=(y十l)*(y十1)可知：当 (y+i)*(v+i)刚超过a的值时退出循环。fb(y4-l)*(y4-l)<n 得：yvM0.5-l所以，该程序段的执行时间为：向下取整(110.5-1)第2章线性表习题22.1描述以下三个概念的区别：头指针、头结点、首元结点。此外叙述有序表的特性何在?， 以及向量与有序表的异同点？，头指针变量和头结点的作用？。并比较顺序存储结构和链式存 储结构的优缺点。答：首元结点是

6、指链表中的第一个结点，也就是没有直接前驱的那个结点。链表的头指 针是一指向链表开始结点的指引(没有头结点时)。单链表由头指针唯一确定，因此单链表可 以用头指针的名字来命名。头结点是人为地在链表做开始结点之前附加的一个结点。有了头 结点之后.头指针指向头结点，不论链表是否为空，头指针总是非空.而且头指针的设置使 得对链表的第一个位置的操作与在表其他位置上的操作一致(都是在某一结点之后)。2.2试写出将链表L从某元素R处分成两个链表L和K的算法。R为K表的第一个元素。答：提示：链表最终将分成两个链表。处理好L的尾结点(即R的前驱结点)，和K的 头结点(R)。void depaii_Node(Nod

7、e * head,mt R,Node *head_K)Node *p=head,*temp,while (p) if(p->data=R) break, te j)p=p,p=p->next,)tejnp->next=NUll;liead_k->next=p,)23给定一个n项元素的线性表V,写一个过程，将元素排列的次序颠倒过来。要求占用原 来的空间，并且用顺序表和单表两种方法表示(要求用最少的附加空间来完成)。答：假设向量A的数据元素存于一维向量“c C0.R-1中，算法可为:int invert ( L ) sequenlist * L;int i;八逆置向童n*/

8、"L是顺斥表类型指针变量，其口一个域用于存放一维向量datatype x;( *L ) -last /*last用丁描示向量的最:后一个元素所在的位置*/ for ( L = 0； l < k%2; i + + ) x= ( *L)<veci;(*L) <veciJ = (*L> .vecfk-i+1 ； (*L)vec(k-i+YJ-x;1return ( 1 )： /,Tmver t"/void LinkL st_xcversc (Link list 61) 徒表的就地逆宣；为简化算法'假设衣忙大于L 匸一>nexL；q=p->

9、;nexL；s=q->next;p->next=NULL;while (s->next) q->next=p;p=q；q = s; s=s->nex;/ /把L的元素逐个插入新表表头Iq->next-p;>ne2ct-q;A- >n;1/Linklist reverse2.4已知单链表L中的结点是按值非递减有序排列的。试写一算法将值为x的结结点插入表L 中，使得L仍然有序。答：因已知顺序表L是按值非递减有序表，所以只要从头找起找到第一个比它大(或相等) 的结点数据，把只插入到这个数所在的位置就可以了。void InsertIncreaseList

10、( Seqlist *L , Datatype x int i;for (i-0; i<L-> length && L->data 1 <x； i + +)；j ：鱼找并比较'分号不能InseitList ( L , x , 1 ) ;/调川顺序农捕人晅数2.5假设分别以两个元素值递增有序的线性表A, B表示两个集合(即同一个线性表中的元素 各不相同)。现要求构成一个新的线性表CC表示真合A与B的交，且C中元素也递增有 序。试分别以下顺序表和单链表为存储结构，编写实现上述运算的算法.答：void LinkList_Intersect(LinkLi

11、st A,LinkList B,LinkList &C)p=A>next;q=B->next;pc» (LNode*)malloc(sizeof(LNode);while (p&&q)if g>data<q->data) p=p->next;else if (p->data>q->data) q=q->next;else(9= (LNode*)malloc(sizeof CLNode);s->data-p>data;pc->next=s;pc=s;p=p>next;q=q-&g

12、t;next;/whileC=pc；/LinkList Intersect第3章栈、队列习题33-1对于一个适当大小的栈，设输入项序列为A、B、C、D、E。为得到下列的处理序列，需 要做什么样的运算序列(由PUSH、POP组成)？。如果其中某处理序列得不到时，试说明理 由？： A、B、C、D、E； B、C、D、E、A；E、A、B、C、D; E、D、C、B、A。答：(D PUSH(A), POP(A), PUSH(B), POP(B), PUSH(C), POP(C), PUSH(D), POP(D), PUSH(E), POP(E) PUSH(A), PUSH(B), POP(B), PUSH

13、(C), POP(C), PUSH(D), POP(D), PUSH(E), POP(E), POP(A) 无法实现。 PUSH(A), PUSH(B), PUSH(C), PUSH(D), PUSH(E), POP(E), POP(D), POP(C), POP(B), POP(A)3-2用链表存放着个字符，试用算法判断读字符串是否有中心对称关系。例如obccba, abcbo 都算是中心对称的字符串。要求用尽可能少的时间完成判断(提示：将一半的字符先依次进 栈)。答：int judgA)linkllsc seqscack s；inc I;Linklisltz j5->top- *1;

14、r=i；P-head:wUle(pi=null)(S->tOp3->LQp4-l；c- ><3ata a->copPP款二,)p-heed；vhlle(pj-null)(p=p->noxt；3->top一)els亡(1=0;p-s-null;return(I);J3-3现有中缀表达式E = (100-4) -3 + 3x (36-7) *2、写出与E等价的后缀表达式. 并用栈来模拟表达式的转换过程，画出转换过程中栈的内容的变化图。答：1004 3 专 3 36 7 x 十2 x图略。第4章多维数组、广义表、串习题44.1现有三个数组An+1, Bn+l

15、ni和CMln十2,试问各个数组能存放多少个元素。 答：11 十 1(n+l)*m (n-t-1 )*(n+2)4.2有三维数组A (2, 3, 4、)、数组中元素长度为4个字节。试求元素A232的相对地址。 答：1524.3已知下图为广义表的存储结构图，写出此图表示的广义表。答：©,(y),(0),0,)4.4 有广义表人=(),B = (A, e, d), C = (A), D = (e, (a, b, B), A, C)。( 1)画出上 述各广义表的图形。(2)求表D的长度和深度；(3)画出D表的链表表示。答：(2)长度：4深度：24.5简述下列每对术语的区别：空串和空格串；串

16、变量和串常量，主串和子串，串变量的名 字与串变量的值。答：详见课本。4.6在顺序串上实现串的判等运算equal(s,t),在链串上实现判等运算equal(s,t)的算法.答：int StrComp(cliar *sl, chai *s2)lilt 1=0；wlule (sli=s2i && sli!=,0>) HH-,return (sli-s2i);mt Sti Con)p(liuk *headL link * head 2)link *pl,*p2;pl=headl->next;p2=headl->next;while (pl ->data=p2-&

17、gt;data && po&&p2)p 1 =p 1 ->next,p2=p2->next,if(pl|p2)return 0,elseretiiin 1;第6章树、二叉树习题66.1分别就下图中的二叉树和树回答下列问题：哪个是根结点?；哪些是叶子结点?；哪 个是G的双亲?，哪些是G的祖先?，哪些是E的子孙?；哪些是E的兄弟?，哪些是C 的兄弟?；结点B和I的层数分别是多少?。答：左边的图形1 ) A 2)D,J3)E 4)E A 5)GH,I ,J 6)E 兄弟：B,C 兄弟：F,G7)2 和 5右边的图形1 ) A 2)DHJ,J,F,G 3)C

18、 4)C,A5)H,IJ 6)E 兄弟：D,C 兄弟：B 7) 2 和 46.2分别画出含3个结点的无序树与二叉树的所有不同形态。答：二又树6.3分别写出题6.1所示二叉树的先根，中根和后根序列。答：先根：ABCDEFGHIJ 中根：DCBAFEHJIG 后根：DCBFJIHGEA6.4已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和DECBHGFA,试画出这棵 二叉树。答：由后根遍历序列得到二叉树的根结点A（后根序列中最后一个结点）；在中序序列中,A的左力是A的左子树上的结点，A的右边是A的右子树上的结点；再到后根序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树。6.5将

19、下图所示的森林转换成二叉树。06.6分别画出下图所示各二叉树对应的森林。#C O R 0 A 0CizbftOOLFOco6.7给定权值7, 18, 3, 32, 5, 26, 12, 8、构造相应的哈夫曼树。答：按权值大小排列后3 5 78 12 18 26 32只要按照将最小的两个合并，合并后的值再 入列中（最小的两个出列），至到列中只有一个值.按上面要求构造哈夫曼树如下：/树列完后，可取左树编码为0,右为1,（左为1,右为0亦可）3、'小57'、'小8小(8)小'120YT1小'(15)小180，',7'1X WW''

20、;(20)小26Of门 q q /|(33)小320,',7,1O'WlV7'7(46)(65)则按上面的树可得到各权值所对应的编码i/其编码是从树顶到该权值点所经过的1或0的序列 7:' 10 0 018：'ro i3宀 0 0 0 032宀115:' 0 0 0 126:''0 112小 0 0 8:' 10 0 1第7章图习题77.1对有向图，试给出：每个顶点的入度和出度；邻接矩阵；邻接表；强连通分量;该图是强连通的吗?。答：节点1:入度2,出度1节点2:入度2,出度2节点3:入度1,出度2节点4:入度1,出度3节点

21、5:入度3,出度0节点6:入度2,出度3 强连通分量2T4T3T6 不是7.2对下图从顶点Vi出发，分别画出其深度和广度生成树。答：图略。7.3对于下面给出的AOE网络：求出每个活动的最早开始时间和最迟开始时间；完成该 工程的最早时间为多少?；哪些活动是关键活动；是否存在某些活动，只要提高其速度就 可以缩短工程的时间；画出所有可能的拓扑排序结果。44答： 参照课本进行计算，列表。 23天 1-6-5-8-910 提高关键活动的速度就可以缩短工程时间。 图略。7.4 按顺序输入顶点对：（1、2）, （1、6）, （2、6） （、4）, （6、4）, （1、3）, （3、4）, （6、5）, （4

22、、5）, （1、5）, （3、5）, （0、0）,根据生成算法画出相应的邻接表.给定V°=4,写出 按深度优先和广度优先搜索的思想写一个算法，求一条从V。出发到点的简单路径.答：按题中顺序输入各条边后建立起来的邻接表图略。在邻接表上进行深度优先遍历所得到的DFS序列为4, 5, 3, 1, 6, 2;在邻接表上进行 广度优先遍历所得到的BFS序列为4, 5, 3, 6, 1, 2.mt visitedMAXSIZE; 指示顶点是否在当前路径上intexist_path_DFS（ALGraphG,int Mnt j）/深度优先判断有向图G中顶点1到顶点j是否有路径, 是则返回1,否则返

23、回0if（i=j） letum 1, /i 就是 jelsevisited i=l;for(p=G.veiticesi.fiistaic.p,p=p->nextaic)kp->adjvex,if(!visi(edk&&exist_path(k,j) retiun l;/i 下游的顶点到 j 有路径/for/else)/exist_path_DFSint exist_path_BFS(ALGraph G,mt ljnt j)广度优先判断有向图G中顶点1到顶点j是否有路径, 是则返回1,否则返回0mt isited MAXSIZE;IiutQueue(Q),Eli Qu

24、eue (Qj);while (! QueueEmpty(Q)DeQueue(Q,u);visitedu=l,for(p=G.verticesi.firstaic,p,p=p->nextaic)k=p->adjvex,if(k=j) l etimi 1;if(?visitedk) EnQueue(Q,k);/for)/wluleletin ii 0、 /exi st_path_B FS7.5试利用最短路径的算法求下图从顶点1到其它各点间的最短路径，写出执行算法过程中各步的状态。答：1-2: 1-3-2 9;1-3: 1-3 5;1-4: 1-6-419;1-5: 1-3-2-5 1

25、9;1-6: 1-3-6 15;7.6画出下图的最小生成树。25答：12; 1-6; 3-6; 4-6; 5-6;总共5条边构成最小生成树。图略。第9章查找表习题99.1 设一有序文件的关键字为 2, 5, 8, 11, 13, 17, 25, 36, 47, 55, 60, 63, 65, 67, 76, 94,当用折半查找算法查找关键字2, 55, 63时，试决定关键字的比较次数。答：2 :比较4次；55:比较3次；63:比较4次9.2若用分块查找法，一个有144项的表，分成几块最好？。每块的最佳长度是多少？，假 定每块长度为8,则其平均查长度是多少？。答：分为12块，144的开平方;平均

26、长度：0.5（8十144/8）十1=149.3试比较开放地址法和链地址法冲突处理技术的优缺点。答：开放定址法，即是由关键码得到的哈希地址一旦产生了冲突，也就是说，该地址已 经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能 找到，并将数据元素存入。链地址法的相关内容见课本。9.4假设结点序列F= （60, 30, 90, 50, 120, 70, 40, 80）。试用查找树的插入算法，用F 中的结点俅次进行插入，画出P中结点所构成的查找树g.再用查找树的删除算法，从查找 树"中删除60,画出删除后的查找树4答：图略。第10章内部排序、外部排序习题1010

27、.1 有如下 12 个整数:23, 37, 7, 79, 29, 43, 73, 19, 31, 61, 23, 47,按下列方法将 这组整数排序，分别写出每遍处理后的数列：气泡排序；插入排序；选择排序；快速 排序；归并排序；基数排序。答：以排序码序列为12, 2,16, 30,28,10,16*, 20,6,18为例子,题目的做法跟卜面一致.（1）直接插入排序初始样列0 123456789拮序码比较次数1-11221630281016*20618L1-22、121630281016*206L811-32121630281016*2061811 421216302810162061821 -5

28、2 12162830io16*2061851 -62 10、2、6、28、3016206L831 -72 10121616、8、302061831-82 1012161620、28、301 61831 -92 6、6、“、20、28、01882 610121616*18、20、28>30(2)快速;排序PivotPvtpos0123456789排序码比较次数120231 1221630281016*20618 1960,16fpos2 10tP°s12 28 1616#2030182284,5,6,7,826 1012128 16fpos fpos16*fpos2030fpos

29、 |pos1«15134,626 101218 16|pos fpos16*fpos202830】316-426101216 16 |po01216 16 18202830左子仔列递归深度为b右子序列递归深度为3。（3）堆排序第一步，形成初始的最大堆（略八第二步，做堆排序。交换与9°对象交换琳与7#对象 从0#到6#币:新形成堆交换0#与3#对象（4）基数排序按址低位分配f0 fll f2 耳习 fl4 耳5f6f7f8f9收集 | 30 W L0 田 20 円 L2 L6 円 G28 円 18 |flO fll 脏】 f3耳4】f5f6 fI7

30、flS fI910.2假定被排序的数据集合用一个单向链表表示，其表头结点指针为f,结点的类型定义如 下：Type celltype = RecordData : lecoidsnext: t celltypeEud,ist = celltype;分别按下列算法写岀分类过程soi(F):插入排序;选择排序。答：略。第12章文件习题1212.1什么是文件的逻辑记录和物理记录?，它们有什么区别与联系？。答：逻辑结构是记录在用户或应用程序面前呈现的方式，是用户对数据的表示和存取方 式。物理结构是数据在物理存储器上存储的方式，是数据的物理表示和组织。12.2如何选择合适的文件组织形式？，决定于哪些因素?

31、，简述文件组织的基本方法。答：文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类 型、大小和关键字的数目以及对文件作何种操作。文件的基本组织方式有顺序组织、索引组织、散列组织和链组织。文件的存储结构可 以采用将基本组织结合的方法，常用的结构有顺序结构、索引结构、散列结构.(1) 顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文件 本质上就是顺序表.若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之 间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整 个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况.(2) 带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索 引项包括数据表中数据的关键字和相应地址，索引弟有序，其物理顺序体现了文件的逻辑次 序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能隋机存取。(3) 散列结构，也称计算寻址结构，相应文件称为