数据结构练习题级参考答案文档格式.docx
《数据结构练习题级参考答案文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构练习题级参考答案文档格式.docx（31页珍藏版）》请在冰点文库上搜索。
各种方法的基本思想：
顺序存储：
逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。
存储：
通过附加指针域表示数据元素之间的关系。
索引存储：
除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。
散列存储：
根据关键字直接计算出该结点的存储地址，通常称为关键字－地址转换法。
第2章
2.1线性表L=（a1，a2，…，an），下列说确的是：
A.每个元素都有一个直接前驱和一个直接后继。
B.线性表中至少有一个元素。
C.表中元素的排列顺序必须是由小到大或由大到小。
D.除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。
2.2下面关于线性表的叙述中，错误的是：
A．线性表若采用顺序存储，必须占用一片连续的存储单元
B．线性表若采用顺序存储，便于进行插入和删除操作
C．线性表若采用存储，不必占用一片连续的存储单元
D．线性表若采用存储，便于插入和删除操作
2.3在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为：
A.n-i+1B.n-iC.iD.i-1
2.4删除长度为n的顺序表中的第i（1≤i≤n）个位置上的元素，元素的移动次数为：
A.n-i+1B.n-iC.iD.i-1
2.5已知一个带头结点单链表L，在表头元素前插入新结点*s的语句为：
A.L=s;
s->
next=L;
B.s->
next=L->
next;
L->
next=s;
C.s=L;
D.s->
s=L;
2.6已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为：
L=s;
2.7已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为：
A．p->
next=p->
B．s->
p->
C．p->
next=s->
D．p->
2.8已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是：
A．s=p->
p=p->
free（s）;
B．p=p->
free（p）;
C．s=p->
D．p=p->
free（p->
next）;
2.9设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构效率最高？
A.单链表B.双链表C.单循环链表D.带尾指针的单循环链表
2.10线性表的存储结构是一种（）存储结构。
A.随机存取B.顺序存取C.索引存取D.散列存取
2.11链表不具备的特点是：
A.插入删除不需要移动元素B.不必事先估计存储空间
C.可随机访问任一结点D.所需空间与其长度成正比
2.1在单链表L中，指针p所指结点有后继结点的条件是p->
next!
=NULL。
2.2判断带头结点的单链表L为空的条件L->
next==NULL。
2.12顺序表和链表中能实现随机存取的是顺序表，插入、删除操作效率高的是链表。
2.13对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为
O
（1）；
若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为O（n）。
2.14顺序表的存储密度大，链表的存储密度小。
2.15比较顺序表和链表这两种线性表不同存储结构的特点。
顺序表
存储密度大
存储空间连续
静态分配
随机存取
插、删效率低
链表
存储空间可不连续
动态分配
顺序存取
插、删效率高
2.16简述头结点的作用。
头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。
即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特殊处理。
2.17写出单链表存储结构的C语言描述。
typedefintDataType;
typedefstructNode
{DataTypedata;
structNode*next;
}LinkList;
完善程序题：
2.18设计一个算法，其功能为：
向一个带头结点的有序单链表（从小到大有序）中插入一个元素x，使插入后链表仍然有序。
请将代码补充完整。
typedefintDataType;
typedefstructNode
{DataTypedata;
;
/*定义指向该结构类型的指针变量next*/
}Linklist;
voidinsert（Linklist*L,DataTypex）
{Linklist*s,*p=L;
while（p->
next&
&
next->
data<
x）
;
/*p指针后移一步*/
/*申请一个新结点空间，将其地址赋给变量s*/
s->
data=x;
;
/*将*s结点插入到*p结点的后面*/
}
structNode*next;
s=（LinkList*）malloc（sizeof（LinkList））;
p->
2.19设计一个函数功能为：
在带头结点的单链表中删除值最小的元素。
typedefNode/*定义结构体类型*/
{DataTypedata;
structNode*next;
voiddeleteMin（LinkList*L）
{LinkList*p=L->
next,*q;
/*首先查找值最小的元素，指针q指向最小元素结点*/
q=p;
while（p）
{if（p->
data<
q->
data）
q=p;
;
/*p指针后移一步，比较单链表中的每一个结点*/
}
if（!
q）return;
/*不存在最小结点（空表）时，直接退出*/
p=L;
/*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/
while（）
p=p->
;
/*从单链表中删除最小元素结点（指针q所指结点）*/
/*释放指针q所指结点的空间*/
struct
=q
next=q->
free（q）;
算法设计题：
2.20已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。
分两种情况编写函数：
（1）线性表采用顺序存储；
（2）线性表采用单链表存储。
（1）线性表采用顺序存储
#defineMAX1024
typedefstruct
{DataTypedata[MAX];
intlast;
}SeqList;
intLocateElem（SeqList*L,DataTypeitem）
{inti,j=0;
for（i=0;
i<
=L->
last;
i++）
if（L->
data[i]>
item）j++;
returnj;
（2）线性表采用单链表存储
typedefstructNode
{DataTypedata;
structNode*next;
}LinkList;
intlocateElem（LinkList*L,DataTypeitem）
{LinkList*p=L->
inti=0;
while（p）
if（p->
data>
item）i++;
returni;
}
2.21试写一算法实现对不带头结点的单链表H进行就地（不额外增加空间）逆置。
typedefstructNode
{DataTypedata;
LinkList*Reverse（LinkList*L）
{LinkList*p,*q;
if（!
L）return;
p=H->
q=H->
next=NULL;
while（q）
{q=q->
next=L;
L=p;
p=q;
returnL;
第3章
3.1设一个栈的输入序列是1，2，3，4，5，则下列序列中，是栈的合法输出序列的是：
A.51234B.45132C.43215D.35241
3.2设有一顺序栈，元素1，2，3，4，5依次进栈，如果出栈顺序是2，4，3，5，1则栈的容量至少是：
A.1B.2C.3D.4
3.3若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当入队一个元素，再出队两个元素后，rear和front的值分别为：
A.1和5B.2和4C.4和2D.5和1
3.4栈和队列都是操作受限的线性表，栈的运算特点是LIFO，队列的运算特点是FIFO。
3.5若序列a、b、c、d、e按顺序入栈，假设P表示入栈操作，S表示出栈操作，则操作序列PSPPSPSPSS后得到的输出序列为acdeb。
3.6已知一个顺序栈*s，栈顶指针是top，它的容量为MAXSIZE，则判断栈空的条件为s->
top==-1，栈满的条件是s->
top==MAXSIZE-1。
3.7对于队列来说，允许进行删除的一端称为队头，允许进行插入的一端称为队尾。
3.8某循环队列的容量MAXSIZE=6，队头指针front=3，队尾指针rear=0，则该队列有_3_个元素。
3.9栈上的基本运算有哪些？
栈的基本运算有：
（1）初始化栈initStack（s）：
构造了一个空栈s。
（2）判栈空empty（s）：
若栈s为空栈，返回值为“真”
（1），否则返回值为“假”（0）。
（3）入栈push（s，x）：
在栈s的顶部插入一个新元素x，x成为新的栈顶元素。
（4）出栈pop（s）：
删除栈s的栈顶元素。
（5）读栈顶元素top（s）：
栈顶元素作为结果返回，不改变栈的状态。
3.10循环顺序队列的存储结构图示及C语言描述？
C语言描述：
循环顺序队列图示：
#defineMAXSIZE1024
typedefintDataType;
typedefstruct
{DataTypedata[MAXSIZE];
intrear,front;
}SeQueue;
SeQueue*sq;
3.11简述栈和队列有哪些联系与区别？
栈和队列都是运算运算受限的线性表，逻辑结构相同；
都可以顺序存储和存储，存储结构也相同；
插入和删除运算都限制在线性表的表端完成，且不需要查找运算。
二者差别主要体现在运算的限制不同：
栈是后进先出（LIFO）的线性表，限制它的
插入和删除操作仅在表的一端进行。
队列是先进先出（FIFO）的线性表，只允许在表
的一端进行插入，而在表的另一端进行删除。
3.12通常称正读和反读都相同的字符序列为“回文”，例如，“abcdeedcba”、“abcdcba”是回文。
若字符序列存储在一个单链表中，编写算法判断此字符序列是否为回文。
（提示：
将一半字符先依次进栈）
#definemaxsize100
typedefchardatatype1;
typedefstruct
{datatype1data[maxsize];
inttop;
}seqstack;
typedefintdatatype;
typedefstructnode
{datatypedata;
structnode*next;
}Linklist;
Duichen（Linklist*head）
{inti=1;
Linklist*p;
seqstack*s;
s=initSeqStack（）;
p=head->
n=0;
while（p）{n++;
p=head->
while（i<
=n/2）
{push（s,p->
data）;
i++;
if（n%2!
=0）p=p->
while（p&
p->
data==pop（s））
p=p->
if（p）return0elsereturn1;
第5章
5.1设数据结构D-S可以用二元组表示为D-S=（D，S），r∈S，其中：
D={A，B，C，D}，
r={<
A，B>
，<
A，C>
B，D>
}，则数据结构D-S是：
A．线性结构B．树形结构C．图形结构D．集合
5.2树最适合用来表示：
A．有序数据元素B.无序数据元素
C．元素之间具有分支层次关系的数据D.元素之间无联系的数据
5.3有关二叉树下列说确的是：
A．二叉树是度为2的有序树B．二叉树中结点的度可以小于2
C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2
5.4深度为10的完全二叉树，第3层上的的结点数是：
A.15B.16C.4D.32
5.5设一棵树的度为4，其中度为1、2、3、4的结点个数分别为6、3、2、1，则这棵树中叶子结点的个数为：
A.8B.9C.10D.11
5.6对于二叉树来说，第i层上最多包含的结点个数为：
A．2i-1B.2i+1C．2iD.2i
5.7树的后根遍历序列等同于与该树对应的二叉树的哪种序列？
A.前序序列B.中序序列C.后序序列D.层序序列
5.8设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是：
A．M1B．M1+M2C．M3D．M2+M3
5.9二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是11。
5.10包含n个结点的二叉树，高度最大为n，高度最小为
。
5.11某完全二叉树共有200个结点，则该二叉树中有1个度为1的结点。
5.12一棵高度为10的满二叉树中的结点总数为210-1个，其中叶子结点数为29。
5.13某完全二叉树结点按层顺序编号（根结点的编号是1），若21号结点有左孩子结点，则它的左孩子结点的编号为__42___。
5.14深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点。
5.15n个结点的线索二叉树上含有n+1条线索。
5.16画出包含三个结点的树和二叉树的所有不同形态。
5.17找出满足下面条件的二叉树：
（1）前序遍历与中序遍历结果相同：
只有右分支的单分支二叉树
（2）前序遍历和后序遍历结果相同：
只有一个根结点的二叉树
（3）中序遍历和后序遍历结果相同：
只有左分支的单分支二叉树
5.18一棵二叉树的中序、后序遍历序列分别为：
GLDHBEIACJFK和LGHDIEBJKFCA，请回答：
（1）画出二叉树逻辑结构的图示。
（2）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。
（3）画出上题中二叉树的中序线索二叉树。
（4）画出中序线索二叉链表存储结构图示并给出C语言描述。
（1）二叉树的逻辑结构图示：
（2）二叉链表存储结构的图示及C语言描述：
typedefcharDataType;
typedefstructNode
{DataTypedata;
structNode*lchild,*rchild;
}BiTree;
（3）中序线索二叉树：
（4）中序线索二叉链表的图示及C语言描述：
intltag,rtag;
}BiThrTree;
5.19设有森林如图5.31所示，请回答：
（1）画出与该森林对应的二叉树的逻辑结构图示。
（2）写出该二叉树的前序、中序、后序遍历序列。
（3）画出该二叉树的中序线索二叉链表的图示并给出C语言描述。
图5.31
（2）前序遍历序列：
ABCDFGEH，
中序遍历序列：
ADGFCBHE
后序遍历序列：
GFDCHEBA
（3）中序线索二叉链表的图示及C语言描述：
5.20设有森林B=（D,S）,
D={A,B,C,D,E,F,G,H,I,J},r∈S
A,B>
<
A,C>
A,D>
B,E>
C,F>
G,H>
G,I>
I,J>
}请回答：
（1）画出与森林对应的二叉树的逻辑结构图示。
（2）写出此二叉树的前序、中序、后序遍历序列。
（3）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。
（1）与森林对应的二叉树的逻辑结构图示：
ABECFDGHIJ，
EBFCDAHJIG
EFDCBJIHGA
（3）二叉链表存储结构的图示及C语言描述：
5.21请画出5.32中的各二叉树对应的森林。
图5.32
5.22假设用于通信的电文由字符集{a，b，c，d，e，f，g，h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，试为这8个字母进行哈夫曼编码。
请回答：
（1）画出哈夫曼树（按根点权值左小右大的原则）。
（2）写出依此哈夫曼树对各个字母的哈夫曼编码。
（3）求出此哈夫曼树的带权路径长度WPL。
（1）哈夫曼树：
（2）各字母的哈夫曼编码：
a:
1010
b:
00
c:
10000
d:
1001
e:
11
f:
10001
g:
01
h:
1011
（3）哈夫曼树的带权路径长度WPL：
=0.07×
4+0.19×
2+0.02×
5+0.06×
4+0.32×
2+0.03×
5+0.21×
2+0.10×
4=2.61
5.23设计一个算法，其功能为：
利用中序线索求结点的中序后继。
structNode*lchild,;
BiThrTree*InOrderNext（BiThrTree*p）/*求中序后继*/
{if（）p=p->
r
升级会员 