数据结构第二版习题Word格式.docx
《数据结构第二版习题Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构第二版习题Word格式.docx（15页珍藏版）》请在冰点文库上搜索。
k++）
x=x+1;
四、试编写算法，求一元多项式Pn（x）=a0+a1x+a2x2+a3x3+…anxn的值Pn（x0），并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。
注意：
本题中的输入ai（i=0,1,…,n）,x和n，输出为Pn（x0）。
通常算法的输入和输出可采用下列两种方式之一：
（1）通过参数表中的参数显式传递。
（2）通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。
第二章
线性表
2.1
描述以下三个概念的区别：
头指针，头结点，首元素结点。
2.2
填空：
（1）
在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元
素个数与＿＿插入或删除的位置＿＿有关。
（2）
在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。
在单链表中，逻
辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。
（3）
在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点
的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。
2.3
已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。
按要求从下列语句中选择合适的语句序列。
a.
在P结点后插入S结点的语句序列是：
。
b.
在P结点前插入S结点的语句序列是：
c.
在表首插入S结点的语句序列是：
d.
在表尾插入S结点的语句序列是：
供选择的语句有：
（1）P->
next=S;
（2）P->
next=
P->
next->
next;
（3）P->
S->
（4）S->
（5）S->
L;
（6）S->
NULL;
（7）Q=
P;
（8）while（P->
next!
=Q）
P=P->
（9）while（P->
=NULL）
（10）P=
Q;
（11）P=
（12）L=
S;
（13）L=
2.4
已知线性表L递增有序。
试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。
Status
Insert_SqList（SqList
&
va,int
x）//把x插入递增有序表va中
{
if（va.length+1>
va.listsize）
return
ERROR;
va.length++;
for（i=va.length-1;
va.elem[i]>
x&
i>
=0;
i--）
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
OK;
}//Insert_SqList
2.5
写一算法，从顺序表中删除自第i个元素开始的k个元素。
2.6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。
试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：
mink和maxk是给定的两个参变量，它们的值为任意的整数）
2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,
a2...,
an）逆置为（an,
an-1,...,
a1）。
（1）以顺序表作存储结构。
以单链表作存储结构。
2.8
假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编
写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C.
2.9
假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。
已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
2.10
已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
2.11
设线性表A=（a1,
a2,…,am），B=（b1,
b2,…,bn），试写一个按下列规则合并A、B为线性表C的算法，使得：
C=
（a1,
b1,…,am,
bm,
bm+1,
…,bn）
当m≤n时；
或者
b1,…,an,
bn,
an+1,
…,am）
当m>
n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。
单链表的长度值m和n均未显式存储。
2.12
将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。
2.13
建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。
并在此链表上实现对二进制数加1的运算
。
2.14
设多项式P（x）采用课本中所述链接方法存储。
写一算法，对给定的x值，求P（x）的值。
第三章
栈和队列
按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：
⑴
如进站的车厢序列为123，则可能得到的出站车厢序列是什么？
⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。
（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
设队列中有A、B、C、D、E这5个元素，其中队首元素为A。
如果对这个队列重复执
行下列4步操作：
输出队首元素；
把队首元素值插入到队尾；
删除队首元素；
（4）
再次删除队首元素。
直到队列成为空队列为止，则是否可能得到输出序列：
（A）
A、C、E、C、C
（B）
A、C、E
（C）
A、C、E、C、C、C
（D）
A、C、E、C
给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式
求值时操作数栈和运算符栈的变化过程：
A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ
试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1
序列2’模式的字符序列。
其中序列1和序列2
中都不含字符’&
’，且序列2
是序列1的逆序列。
例如，‘a+b&
b+a’是属该模式的字符序列，而‘１+３&
３－１’则不是。
假设表达式由单字母变量和双目四则运算算符构成。
试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设
头指针），试编写相应的队列初始化、入队列和出队列的算法。
要求循环队列不损失一个空间全部都能得到利用,
设置一个标志域tag
以tag为0或1
来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
简述以下算法的功能（其中栈和队列的元素类型均为int）：
（1）void
proc_1（Stack
S）
int
i,
n,
A[255];
n=0;
while（!
EmptyStack（S））
{n++;
Pop（&
S,
A[n]）;
}
Push（&
A[i]）;
}
（2）void
proc_2（Stack
e）
Stack
T;
d;
InitStack（&
T）;
EmptyStack（S））
d）;
if
（d!
=e）
Push（
T,
EmptyStack（T））
（3）void
proc_3（Queue
*Q）
S）;
EmptyQueue（*Q））
DeleteQueue（Q,
EnterQueue（Q，d）
第四章
串
设s=’I
AM
A
STUDENT’,
t=’GOOD’,
q=’WORKER’。
给出下列操作的结果：
StrLength（s）;
SubString（sub1,s,1,7）;
SubString（sub2,s,7,1）;
StrIndex（s,’A’,4）;
StrReplace（s,’STUDENT’,q）;
StrCat（StrCat（sub1,t）,
StrCat（sub2,q））;
编写算法，实现串的基本操作StrReplace（S,T,V）。
假设以块链结构表示串，块的大小为1，且附设头结点。
试编写算法，实现串的下列基本操作：
StrAsign（S,chars）；
StrCopy（S,T）；
StrCompare（S,T）；
StrLength（S）；
StrCat（S,T）；
SubString（Sub,S,pos,len）。
4．
叙述以下每对术语的区别：
空串和空格串；
串变量和串常量；
主串和子串；
串变量的名
字和串变量的值。
5．
已知：
S=”（xyz）*”,T=”（x+z）*y”。
试利用联接、求子串和置换等操作，将S转换为
T.
6．
S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T
匹配的子串逆置。
7．
S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及
从第k个字符删除len个字符。
以下算法用定长顺序串：
8．
写下列算法：
将顺序串r中所有值为ch1的字符换成ch2的字符。
将顺序串r中所有字符按照相反的次序仍存放在r中。
从顺序串r中删除其值等于ch的所有字符。
从顺序串r1中第index
个字符起求出首次与串r2相同的子串的起始位置。
（5）
从顺序串r中删除所有与串r1相同的子串。
9．
写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。
10．
写算法，实现顺序串的基本操作StrCompare（s,t）。
11．
写算法，实现顺序串的基本操作StrReplace（&
s,t,v）。
第五章
数组和广义表
1．
假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。
已知A的
基地址为1000，计算：
数组A共占用多少字节；
数组A的最后一个元素的地址；
按行存储时，元素A36的地址；
按列存储时，元素A36的地址。
第六章
数和二叉树
1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
给出满足下列条件的所有二叉树：
a）
前序和中序相同
b）
中序和后序相同
c）
前序和后序相同
n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？
8．画出与下列已知序列对应的树Ｔ：
树的先根次序访问序列为GFKDAIEBCHJ；
树的后根次序访问序列为DIAEKFCJHBG。
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：
0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10
请为这8个字母设计哈夫曼编码。
10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是
否可不用递归且不用栈来完成?
请简述原因.
11.
画出和下列树对应的二叉树：
12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：
对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14．分别写函数完成：
在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。
正则二叉树是指：
在二叉树中不存在子树个数为1的结点。
20．计算二叉树最大宽度的算法。
二叉树的最大宽度是指：
二叉树所有层中结点个数的最大值。
21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
22.
证明：
a）给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；
B）
给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；
23.
二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
24.
二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。
第七章
图
7.1
已知如图所示的有向图，请给出该图的：
每个顶点的入度、出度；
邻接矩阵；
邻接表；
逆邻接表；
十字链表；
（6）
强连通分量。
7.2
已知如图所示的无向图，请给出该图的：
邻接多重表；
（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点
的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。
从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；
（给出深度优先搜
索树）
从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。
（给出广度优先搜
7.3
已知如图7.31所示的AOE-网，试求：
每个事件的最早发生时间和最晚发生时间；
每个活动的最早开始时间和最晚开始时间；
给出关键路径。
7.4
已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，
并给出算法执行过程中各步的状态。
7.5
编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
7.6
试在邻接矩阵存储结构上实现图的基本操作：
InsertVertex（G,v）;
InsertArc（G,
v,
w）;
DeleteVertex（G,v）和DeleteArc（G,
w）。
7.7
试对邻接表存储结构重做题6。
7.8
试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。
算法中涉及的图的基本操作必须在此存储结构上实现。
7.9
同上题要求。
试基于图的广度优先搜索策略写一算法。
7.10
试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。
算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。
7.11
采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。
7.12
下图是带权的有向图G的邻接表表示法。
从结点V1出发，深度遍历图G所得结点序列为（
），广度遍历图G所得结点序列为（
B
）；
G的一个拓扑序列是（
C
从结点V1到结点V8的最短路径为（
D
从结点V1到结点V8的关键路径为（
E
）。
其中A、B、C的选择有：
V1,V2,V3,V4,V5,V6,V7,V8
V1,V2,V4,V6,V5,V3,V7,V8
V1,V2,V4,V6,V3,V5,V7,V8
V1,V2,V4,V6,V7,V3,V5,V8
V1,V2,V3,V8,V4,V5,V6,V7
V1,V2,V3,V8,V4,V5,V7,V6
V1,V2,V3,V8,V5,V7,V4,V6
D、E的选择有：
V1,V2,V4,V5,V3,V8
V1,V6,V5,V3,V8
V1,V6,V7,V8
V1,V2,V5,V7,V8
7.13
已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。
升级会员 