kok电子竞技

本文格式为Wordkok电子竞技，下载可任意编辑——数据结构课后习题答案1习题1

1．解释以下概念：规律结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法。

2．理解以下关系：算法与数据结构的关系；数据结构与抽象数据类型的关系；算法和数据结构与问题求解的关系。

3.写出以下程序段的平均状况下的时间代价O表示式。(1)a=b+c;d=a+e(2)sum=0;

for(i=0;i=(y+1)*(y+1))y++;(4)s=0;if(even(n))

for(i=0;i0){

if(x>lO0){x=x-10;n=n-1;}elsex=x+1;}

4．对于给定的n个元素，可以构造出有，，，四种。

规律结构

的5.按增长率由小到大的顺序排列以下各函数：

33n2n4nn

2,(),(),(),n,n2,n!,n,log2n,n/log2n

233100

习题2

2.1已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最终一个结点，试从以下提供的语句中选出适合的语句序列：(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)在单链表L首插入s结点：(4)在单链表L后插入s结点：提供的语句：

①p->next＝s；②p->next＝p->next->next；③p->next=s->next；④s->next=p->next；⑤s->next＝L；⑥s->next=p；⑦s->next=NULL；⑧q＝p；

⑨while(p->next!=q)p=p->next；⑩while(p->next!=NULL)p=p->next；⑾p=q；⑿p=L；⒀L＝s；⒁L＝p；

2.2已知p结点是某双向链表的中间结点，试从以下提供的语句中选出适合的语句序列。

(1)在p结点之后插入s结点：(2)在p结点之前插入s结点：(3)删除p结点的直接后继结点：(4)删除p结点的直接前驱结点：提供的语句：

①p->next＝p->next->next；②p->prior=p->prior->prior；③p->next=s；④p->prior=s；⑤s->next=p；⑥s->prior＝p；

⑦s->next=p->next；⑧s->prior=p->prior；⑨p->prior->next=p->next；⑩p->prior->next＝p；⑾p->next->prior＝p；⑿p->next->prior＝s；

⒀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、3、5、4、2、6的出栈序列?并说明为什么得不到或如何得到。3.3利用两个栈模拟一个队列的入队、出队和判断队列空的运算。3.4写一算法，将一个顺序栈中的元素依次取出，并打印元素值。3.5写一算法，将一个非负十进制整数转换成二进制。

3.6写一算法，将一个链式队列中的元素依次取出，并打印元素值。

3.7设有编号为1、2、3、4的4辆车，顺序进入一个栈式结构的站台，试写出这4辆车开出站台的所有可能的顺序。

3.8写一个算法，借助于栈将一个单链表逆置。

习题4

4.1空串和空格串有什么区别?

4.2两个字符串相等的充要条件是什么?4.3串的三种机内表示方法是什么?

4.4设S＝'Iamastudent'，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＝'This'，F＝'asample'，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(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,inti,intm)，删除串S中从位置i开始连续的m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则S中从位置i开始直至末尾的字符均被删去.。

4.7采用顺序结构存储串，编写一个函数，求串s和串t的一个最长的公共子串。

提醒:需要采用三重循环来实现。

习题5

1.假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占4个字节。问以下元素的存储地址是什么?

(1)a0000(2)a1111(3)a3125(4)a82472.假设一个准对角矩阵

按以下方式存储于一维数组B[4m]中：

写出由一对下标(i,j)求k的转换公式。3.现有如下的稀疏矩阵A，要求画出三元组表示法。

习题6

10.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计赫夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

11．一棵度为2的树与一棵二叉树有何区别?树与二叉树之间有何区别?12．对于如下图的树，试给出：(1)双亲数组表示法示意图；(2)孩子链表表示法示意图；

(3)孩子兄弟链表表示法示意图。

13．画出下图所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。

14．将如下图的二叉树转换成相应的森林。

15．在具有n(n>1)个结点的各棵树中，其中深度最小的那棵树的深度是多少?它共有多少叶子和非叶子结点?其中深度最大的那棵树的深度是多少?它共有多少叶子和非叶子结点?

16．画出和以下已知序列对应的树T：树的先根访问序列为：GFKDAIEBCHJ；树的后根访问序列为：DIAEKFCJHBG。17．画出和以下已知序列对应的森林F：森林的先序访问序列为：ABCDEFGHIJKL；森林的中序访问序列为：CBEFDGAJIKLH。

18．对以孩子－兄弟链表表示的树编写计算树的深度的算法。

习题7

1对于右图所示的有向图，试给出：(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所得的结点序列；

5对于下图所示的带权图

(1)依照普里姆算法，从顶点v1出发生成最小生成树，按生成次序写出各条边；(2)依照克鲁斯卡尔算法，生成最小生成树，按生成次序写出各条边；(3)画出其最小生成树，并求出它的权值。

6写出下图所示的AOV网的全部可能的拓扑有序序列。

7对下图所示的带权有向图G，试回复以下问题：

(1)写出其带权邻接矩阵arcs；

(2)求出从顶点v1到其他各顶点之间的最短路径。