数据结构练习题级参考答案.docx
《数据结构练习题级参考答案.docx》由会员分享，可在线阅读，更多相关《数据结构练习题级参考答案.docx（32页珍藏版）》请在冰点文库上搜索。
数据结构练习题级参考答案
第1章
选择题：
1.1数据结构在计算机内存中的表示是指：
A．数据的存储结构B.数据结构
C．数据的逻辑结构D.数据元素之间的关系
1.2数据的逻辑结构是指：
A.数据所占的存储空间量
B．各数据元素之间的逻辑关系
C.数据在计算机中顺序或链接的存储方式
D.存储在内存或外存中的数据
1.3在下列的叙述中，正确的是：
A．数据的逻辑结构是指数据的各数据项之间的逻辑关系。
B．数据的物理结构是指数据在计算机内的实际存储形式。
C．在顺序存储结构中，数据元素之间的关系是显示体现的。
D．链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。
填空题：
1.4数据结构主要研究数据的逻辑结构，数据的存储结构，数据的运算三个方面的内容。
1.5链接存储的特点是通过附加指针域来表示数据元素之间的逻辑关系。
1.6数据结构中讨论的三种经典结构包括：
线性表，树，图。
1.7数据结构中常用的存储方法有：
顺序，链接，索引，散列。
1.8顺序存储结构可以通过位置隐含表示关系，链接存储结构通过附加指针来显示表示关系。
1.9算法的特性包括有穷性，确定性，可行性，输入和输出。
1.10算法性能分析的两个主要定量评价指标是时间复杂度和空间复杂度。
简答题：
1.11数据结构研究的三方面内容之间有什么联系和区别？
数据结构研究的三方面内容包括:
数据的逻辑结构、存储结构和运算。
数据的逻辑结构是数学模型，存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。
1.12简述数据结构中讨论的三种经典结构的逻辑特征是什么？
三种经典结构：
线性表、树和图。
逻辑特征分别为：
（1）线性表：
一对一。
有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点。
（2）树：
一对多。
有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点。
（3）图：
多对多。
可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点。
1.13简述各种常用存储方法的基本思想。
各种方法的基本思想：
顺序存储：
逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。
链接存储：
通过附加指针域表示数据元素之间的关系。
索引存储：
除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。
散列存储：
根据关键字直接计算出该结点的存储地址，通常称为关键字－地址转换法。
第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;s->next=L;D.s->next=L;s=L;
2.6已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为：
A.L=s;s->next=L;B.s->next=L;L=s;
C.s=L;s->next=L;D.s->next=L;s=L;
2.7已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为：
A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;
2.8已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是：
A．s=p->next;p=p->next;free（s）;B．p=p->next;free（p）;
C．s=p->next;p->next=s->next;free（s）;D．p=p->next;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&&p->next->data;/*p指针后移一步*/
;/*申请一个新结点空间，将其地址赋给变量s*/
s->data=x;
;;/*将*s结点插入到*p结点的后面*/
}
structNode*next;
p=p->next;
s=（LinkList*）malloc（sizeof（LinkList））;
s->next=p->next;
p->next=s;
2.19设计一个函数功能为：
在带头结点的单链表中删除值最小的元素。
请将代码补充完整。
typedefintDataType;
typedefNode/*定义结构体类型*/
{DataTypedata;
structNode*next;
}LinkList;
voiddeleteMin（LinkList*L）
{LinkList*p=L->next,*q;/*首先查找值最小的元素，指针q指向最小元素结点*/
q=p;
while（p）
{if（p->datadata）
q=p;
;/*p指针后移一步，比较单链表中的每一个结点*/
}
if（!
q）return;/*不存在最小结点（空表）时，直接退出*/
p=L;/*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/
while（）
p=p->next;
;/*从单链表中删除最小元素结点（指针q所指结点）*/
;/*释放指针q所指结点的空间*/
}
struct
p=p->next;
p->next!
=q
p->next=q->next;
free（q）;
算法设计题：
2.20已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。
分两种情况编写函数：
（1）线性表采用顺序存储；
（2）线性表采用单链表存储。
（1）线性表采用顺序存储
#defineMAX1024
typedefintDataType;
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）线性表采用单链表存储
typedefintDataType;
typedefstructNode
{DataTypedata;
structNode*next;
}LinkList;
intlocateElem（LinkList*L,DataTypeitem）
{LinkList*p=L->next;
inti=0;
while（p）
if（p->data>item）i++;
returni;
}
2.21试写一算法实现对不带头结点的单链表H进行就地（不额外增加空间）逆置。
typedefintDataType;
typedefstructNode
{DataTypedata;
structNode*next;
}LinkList;
LinkList*Reverse（LinkList*L）
{LinkList*p,*q;
if（!
L）return;
p=H->next;q=H->next;L->next=NULL;
while（q）
{q=q->next;p->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->next;n=0;
while（p）{n++;p=p->next;}
p=head->next;
while（i<=n/2）
{push（s,p->data）;i++;}
if（n%2!
=0）p=p->next;
while（p&&p->data==pop（s））
p=p->next;
if（p）return0elsereturn1;
}
第5章
选择题：
5.1设数据结构D-S可以用二元组表示为D-S=（D，S），r∈S，其中：
D={A，B，C，D}，
r={，，}，则数据结构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语言描述：
typedefcharDataType;
typedefstructNode
{DataTypedata;
structNode*lchild,*rchild;
intltag,rtag;
}BiThrTree;
5.19设有森林如图5.31所示，请回答：
（1）画出与该森林对应的二叉树的逻辑结构图示。
（2）写出该二叉树的前序、中序、后序遍历序列。
（3）画出该二叉树的中序线索二叉链表的图示并给出C语言描述。
图5.31
（1）二叉树的逻辑结构图示：
（2）前序遍历序列：
ABCDFGEH，
中序遍历序列：
ADGFCBHE
后序遍历序列：
GFDCHEBA
（3）中序线索二叉链表的图示及C语言描述：
typedefcharDataType;
typedefstructNode
{DataTypedata;
structNode*lchild,*rchild;
intltag,rtag;
}BiThrTree;
5.20设有森林B=（D,S）,
D={A,B,C,D,E,F,G,H,I,J},r∈S
r={,,,,,,,}请回答：
（1）画出与森林对应的二叉树的逻辑结构图示。
（2）写出此二叉树的前序、中序、后序遍历序列。
（3）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。
（1）与森林对应的二叉树的逻辑结构图示：
（2）前序遍历序列：
ABECFDGHIJ，
中序遍历序列：
EBFCDAHJIG
后序遍历序列：
EFDCBJIHGA
（3）二叉链表存储结构的图示及C语言描述：
typedefcharDataType;
typedefstructNode
{DataTypedata;
structNode*lchild,*rchild;
}BiTree;
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设计一个算法，其功能为：
利用中序线索求结点的中序后继。
请将代码补充完整。
typedefcharDataType;
typedefstructNode
{DataTypedata;
structNode*lchild,;
intltag,rtag;
}BiThrTree;
BiThrTree*InOr
升级会员 