文档库

最新最全的文档下载
当前位置:文档库 > 数据结构课后习题答案1--7

数据结构课后习题答案1--7

习题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

sum++;

(3) x=n;

y=0;

while (x>=(y+1)*(y+1))

y++;

(4) s=0;

if(even(n))

for (i=0;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, (3

2)

n, (2

3)

n, (4

3)

n, n n, n3

2

, n!, n, log2n, n/log2n

习题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='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='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(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个字符。若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) a8247

2.假设一个准对角矩阵

数据结构课后习题答案1--7

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

数据结构课后习题答案1--7

写出由一对下标(i,j) 求k的转换公式。

3.现有如下的稀疏矩阵A,要求画出三元组表示法。

数据结构课后习题答案1--7

习题6

数据结构课后习题答案1--7

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

12.对于如图所示的树,试给出:

数据结构课后习题答案1--7

(1)双亲数组表示法示意图;

(2)孩子链表表示法示意图;

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

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

数据结构课后习题答案1--7

14.将如图所示的二叉树转换成相应的森林。

数据结构课后习题答案1--7

15.在具有n(n>1)个结点的各棵树中,其中深度最小的那棵树的深度是多少?

它共有多少叶子和非叶子结点?其中深度最大的那棵树的深度是多少?它共有多

少叶子和非叶子结点?

16.画出和下列已知序列对应的树T:

树的先根访问序列为:GFKDAIEBCHJ;

树的后根访问序列为:DIAEKFCJHBG。

17.画出和下列已知序列对应的森林F:

森林的先序访问序列为:ABCDEFGHIJKL;

森林的中序访问序列为:CBEFDGAJIKLH。

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

习题7

数据结构课后习题答案1--7

1 对于右图所示的有向图,试给出:

(1)每个顶点的入度和出度。

(2)邻接矩阵。

(3)邻接表。

(4)逆邻接表。

(5)强连通分量。

数据结构课后习题答案1--7

2 设无向图G如右图所示,试给出:

(1)该图的邻接矩阵。

(2)该图的邻接表。

(3)该图的多重邻接表。

(4)从v0出发的“深度优先”遍历序列。

(5)从v0出发的“广度优先”遍历序列。

3请对下边的无向带权图,

(1)写出它的邻接矩阵,并按普里姆算法求其最小生成树;

(2)写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。

数据结构课后习题答案1--7

4 对下图所示的带权有向图G,试回答以下问题:

数据结构课后习题答案1--7

(1)求出G中从结点v1出发按深度优先搜索遍历G所得到结点序列;

(2)求出G中从结点v1出发按广度优先搜索遍历G所得的结点序列;

5 对于下图所示的带权图

数据结构课后习题答案1--7

(1)按照普里姆算法,从顶点v1出发生成最小生成树,按生成次序写出各条边;

(2)按照克鲁斯卡尔算法,生成最小生成树,按生成次序写出各条边;

(3)画出其最小生成树,并求出它的权值。

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

数据结构课后习题答案1--7

7 对下图所示的带权有向图G,试回答以下问题:

数据结构课后习题答案1--7

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

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