数据结构课后习题答案

1、习题1 1解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法。 2理解以下关系：算法与数据结构的关系；数据结构与抽象数据类型的关系；算法和数据结构与问题求解的关系。 3. 写出下列程序段的平均情况下的时间代价O表示式。(1) a=b+c; d=a+e(2) sum=0; for (i=0;i<3;i+) for (j=0;j<n;j+) sum+;(3) x=n; y=0; while (x>=(y+1)*(y+1) y+;(4) s=0; if(even(n) for (i=0;i

2、<n;i+) sum+; else s=s+n;(5) x=66;n=200; while (n>0) if(x>lO0) x=x-10; n=n-1; else x=x+1; 4对于给定的n个元素，可以构造出的逻辑结构有 ， ， ， 四种。 5.按增长率由小到大的顺序排列下列各函数：2100, ()n, ()n, ()n, nn, n, n!, n, log2n, n/log2n习题22.1已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选出合适的语句序列：(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)在单链表

3、L首插入s结点：(4)在单链表L后插入s结点：提供的语句：p->nexts； p->nextp->next->next；p->next=s->next； s->next=p->next；s->nextL； s->next=p；s->next=NULL； qp；while(p->next!=q)p=p->next； while(p->next!=NULL)p=p->next；p=q； p=L；Ls； Lp；2.2已知p结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。(1)在p结点之后插入

4、s结点：(2)在p结点之前插入s结点：(3)删除p结点的直接后继结点：(4)删除p结点的直接前驱结点：提供的语句：p->nextp->next->next； p->prior=p->prior->prior；p->next=s； p->prior=s；s->next=p； s->priorp；s->next=p->next； s->prior=p->prior；p->prior->next=p->next； p->prior->nextp；p->next->priorp

5、； p->next->priors；p->prior->next=s； p->next->prior=p->prior；q=p->next； q=p->prior；free(p)； free(q)；2.3试编写一个计算头结点指针为L的单链表长度的算法。2.4试编写一个将单循环链表逆置的算法。2.5已知一顺序表A，其元素值非递减有序排列，编写一个算法，删除顺序表中多余的值相同的元素。习题3 3.1 简述栈和线性表的区别。简述栈和队列的相同点和不同点。 3.2 如果进栈的数据元素序列为1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、

6、3、5、4、2、6的出栈序列?并说明为什么得不到或如何得到。 3.3 利用两个栈模拟一个队列的入队、出队和判断队列空的运算。 3.4 写一算法，将一个顺序栈中的元素依次取出，并打印元素值。 3.5 写一算法，将一个非负十进制整数转换成二进制。 3.6 写一算法，将一个链式队列中的元素依次取出，并打印元素值。 3.7 设有编号为1、2、3、4的4辆车，顺序进入一个栈式结构的站台，试写出这4辆车开出站台的所有可能的顺序。 3.8 写一个算法，借助于栈将一个单链表逆置。习题44.1 空串和空格串有什么区别?4.2 两个字符串相等的充要条件是什么?4.3 串的三种机内表示方法是什么?4.4 设S

7、9;I am a student'，T'good'，Q'worker'。求： (1)StrLength(S) (2)SubString(&Sub，S，8，7) (3)SubString(&Sub，T，2，1) (4)Index(S，'a'，1) (5)Index(S，T，1) (6)Replace(&S，'Student'，Q) (7)Concat(&N，SubString(&V，S，6，2)，Concat(&P，T，SubString(&W,S,7,8)4.5 设A

8、'This'，F'a sample'，C'good'，D'ne'，B' '，G'is'。求： (1)Coneat(&S，A，Concat(&Z，SubString(&Y，F，2，7)，Concat(&X，B，SubString(A，3，2) (2)Concat(&U，SubString(&X，C，3，1)，D) (3) Replace(&F，SubString(&X，F，3，6)，C) (4)StrLength(S) (5)Index(

9、V，G，1) (6)Index(U，G，1) (7) Concat(&V，S，Concat(&Z，B，Concat(&Y，F，Concat(&X，B，U)4.6 利用C的库函数strlen、strcpy(或strcat)写一个算法voidStrDelete(char *S,int i,int m)，删除串S中从位置i开始连续的m个字符。若istrlen(S)，则没有字符被删除；若i+mstrlen(S)，则S中从位置i开始直至末尾的字符均被删去.。 4.7 采用顺序结构存储串，编写一个函数，求串s和串t的一个最长的公共子串。 提示: 需要采用三重循环来实现。习题

10、51. 假设按行优先存储整数数组A9358时，第一个元素的字节地址是100，每个整数占4个字节。问下列元素的存储地址是什么?(1) a0000 (2) a1111 (3) a3125 (4) a82472. 假设一个准对角矩阵按以下方式存储于一维数组B4m中：写出由一对下标 (i,j) 求k的转换公式。3. 现有如下的稀疏矩阵A，要求画出三元组表示法。习题610. 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计赫夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。11一棵度为2的树与

11、一棵二叉树有何区别?树与二叉树之间有何区别?12对于如图所示的树，试给出： (1)双亲数组表示法示意图； (2)孩子链表表示法示意图；(3)孩子兄弟链表表示法示意图。13画出下图所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。14将如图所示的二叉树转换成相应的森林。15在具有n(n>1)个结点的各棵树中，其中深度最小的那棵树的深度是多少?它共有多少叶子和非叶子结点?其中深度最大的那棵树的深度是多少?它共有多少叶子和非叶子结点?16画出和下列已知序列对应的树T：树的先根访问序列为：GFKDAIEBCHJ；树的后根访问序列为：DIAEKFCJHB

12、G。17画出和下列已知序列对应的森林F：森林的先序访问序列为：ABCDEFGHIJKL；森林的中序访问序列为：CBEFDGAJIKLH。18对以孩子兄弟链表表示的树编写计算树的深度的算法。习题71 对于右图所示的有向图，试给出： (1)每个顶点的入度和出度。 (2)邻接矩阵。 (3)邻接表。 (4)逆邻接表。 (5)强连通分量。2 设无向图G如右图所示，试给出： (1)该图的邻接矩阵。 (2)该图的邻接表。 (3)该图的多重邻接表。 (4)从v0出发的“深度优先”遍历序列。 (5)从v0出发的“广度优先”遍历序列。3请对下边的无向带权图， (1)写出它的邻接矩阵，并按普里姆算法求其最小生成树； (2)写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。4 对下图所示的带权有向图G，试回答以下问题：(1)求出G中从结点v1出发按深度优先搜索遍历G所得到结点序列；(2)求出G中从结点v1出发按广度优先搜索遍历G所得的结