数据结构复习题目和答案.docx
《数据结构复习题目和答案.docx》由会员分享，可在线阅读，更多相关《数据结构复习题目和答案.docx（41页珍藏版）》请在冰点文库上搜索。
数据结构复习题目和答案
《数据结构-C语言版》
第一章绪论
单项选择题
1．在数据结构中，数据的基本单位是_________。
A.数据项B.数据类型C.数据元素D.数据变量
2．数据结构中数据元素之间的逻辑关系被称为______。
A.数据的存储结构B.数据的基本操作C.程序的算法D.数据的逻辑结构
3．在数据结构中，与所使用计算机无关的是数据的_______。
A.存储结构B.逻辑和物理结构C.逻辑结构D.物理结构
4．在链式存储结构中，数据之间的关系是通过________体现的。
A.数据在内存的相对位置B.指示数据元素的指针
C.数据的存储地址D.指针
5．计算算法的时间复杂度是属于一种_______。
A.事前统计的方法B.事前分析估算的方法
C.事后统计的方法D.事后分析估算的方法
6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是______。
A.n2B.nlognC.nD.logn
7．设使用某算法对n个元素进行处理，所需的时间是T（n）=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。
A.O
（1）B.O（n）C.O（200n）D.O（nlog2n）
CDCBBDD
第二章线性表
单项选择题
1．链表不具有的特点是________。
A.可随机访问任一元素B.插入和删除时不需要移动元素
C.不必事先估计存储空间D.所需空间与线性表的长度正比
2．设顺序表的每个元素占8个存储单元。
第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。
A.139B.140C.147D.148
3．在线性链表存储结构下，插入操作算法。
A.需要判断是否表满B.需要判断是否表空
C.不需要判断表满D.需要判断是否表空和表满
4．在一个单链表中，若删除p所指结点的后继结点，则执行。
A.p->next=p->next->next;B.p->next=p->next;
C.p=p->next->next;D.p=p->next;p->next=p->next->next;
5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。
A.O（n）B.O
（1）C.O（m）D.O（m+n）
6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。
A.单链表B.静态链表C.线性链表D.顺序存储方式
ACCABB
填空题
1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。
2．在单链表中，指针p所指结点为最后一个结点的条件是。
3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。
4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。
5．在长度为n的顺序表中插入一个元素的时间复杂度为。
1前驱
2p->next==NULL
3.1
4.n-i+1
5.O（n）
例题解析
【例2-1】编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。
解：
该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。
实现本题功能的函数如下：
voidinverse（Lnode*h）
{s=h->next;
if（s==NULL）return;
q=NULL;
p=s;
while（p!
=NULL）
{p=p->next;
s->next=q;/*逆转指针*/
q=s;/*指针前移*/
s=p;
}
h->next=q;/*头指针h的后继是p*/
}
【例2-2】编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。
解：
对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。
从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。
当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。
设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。
若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到C中的元素c为
例如：
A=（3,5,8,11）
B=（2,6,8,9,11,15,20）
则C=（2,3,5,6,8,8,9,11,11,15,20）
实现本题功能的函数如下：
Lnode*hb（Lnode*pa,Lnode*pb）
{Lnode*p,*q,*pc;
pc=（Lnode*）malloc（sizeof（Lnode））;/*建立表c的头结点pc*/
p=pc;/*p指向C表头结点*/
while（pa!
=NULL&&pb!
=NULL）
{
q=（Lnode*）malloc（sizeof（Lnode））;/*建立新结点q*/
if（pb->datadata）/*比较A、B表中当前结点的数据域值的大小*/
{q->data=pb->data;/*B中结点值小，将其值赋给q的数据域*/
pb=pb->next;/*B中指针pb后移*/
}
else
{q->data=pa->data;/*相反，将A结点值赋给q的数据域*/
pa=pa->next;/*A中指针pa后移*/
}
p->next=q;/*将q接在p的后面*/
p=q;/*p始终指向C表当前尾结点*/
}
while（pa!
=NULL）/*若表A比B长，将A余下的结点链在C表尾*/
{q=（Lnode*）malloc（sizeof（Lnode））;
q->data=pa->data;
pa=pa->next;
p->next=q;
p=q;
}
while（pb!
=NULL）/*若表B比A长，将B余下的结点链在C表尾*/
{q=（Lnode*）malloc（sizeof（Lnode））;
q->data=pb->data;
pb=pb->next;
p->next=q;
p=q;
}
p->next=NULL;
p=pc;/*p指向表C的头结点pc*/
pc=p->next;/*改变指针状态，使pc指向p的后继*/
free（p）;/*释放p空间*/
return（pc）;
}
此算法的时间复杂度为O（m+n），其中m，n分别是两个被合并表的表长。
第三章栈和队列
单项选择题
1．在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是。
A.ｃB.ｄ C.ｂD.ｅ
2．若某堆栈的输入序列是1，2，3，...，n，输出序列的第一个元素为n，则第i个输出元素为。
A.iB.n-iC.n-i+1D.哪个元素无所谓
3．向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行。
A.h->next=s;B.s->next=h;
C.s->next=h;h=h->next;D.s->next=h->next;h->next=s;
4．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是。
A.edcbaB.decbaC.dceabD.abcde
5．栈和队列的共同点是。
A.都是先进后出B.都是先进先出
C.只允许在端点处插入和删除元素D.没有共同点
6．对于循环队列。
A.无法判断队列是否为空B.无法判断队列是否为满
C.队列不可能满D.以上说法都不是
7.若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A.1和5B.2和4C.4和2D.5和1
8.判定一个循环队列QU（最多元素为m0）为满队列的条件是。
A.QU->front==QU->rearB.QU->front!
=QU->rear
C.QU->front==（QU->rear+1）%m0D.QU->front!
=（QU->rear+1）%m0
9.判定一个循环队列QU（最多元素为m0）为空的条件是。
A.QU->front==QU->rearB.QU->front!
=QU->rear
C.QU->front==（QU->rear+1）%m0D.QU->front!
=（QU->rear+1）%m0
BCDCCDACA
填空题
1．在求表达式值的算符优先算法中使用的主要数据结构是。
2．设有一个空栈，现输入序列为1，2，3，4，5。
经过push，push，pop，push，pop，push，pop，push后，输出序列是。
3．仅允许在同一端进行插入和删除的线性表称为。
7．在顺序栈s中，栈为空的条件是，栈为满的条件是_____。
4．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为。
5．用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是。
1.栈
2.234
3.栈
4.s.top==s.base,s.top-s.base>=s.stacksizeSXSSXSXX
5.993
例题解析
【例3-1】编程实现：
用除法把十进制数转换成二进制数。
解：
算法思想：
用初始十进制数除以2把余数记录下来并且若商不为0则再用商去除以2直到商为0，这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）就得到了相应的二进制数，如把十进制数35转换成二进制数的过程如图3-1所示。
图3-1十进制数转换成二进制数的过程
由题意可知，我们可以用一个栈来保存所有的余数，当商为0时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下：
voidconversion（）{
StackS;
intn;
InitStack（&S）;
printf（"Inputanumbertoconvert:
\n"）;
scanf（"%d",&n）;
if（n<0）{
printf（"\nThenumbermustbeover0."）;
return;
}
if（n==0）Push（S,0）;
while（n!
=0）{
Push（S,n%2）;
n=n/2;
}
printf（"theresultis:
"）;
while（!
StackEmpty（*S））{
printf（"%d",Pop（S））;
}
}
}
第四章串
单项选择题
1．串是一种特殊的线性表，其特殊性体现在。
A.可以顺序存储B.数据元素是一个字符
C.可以链接存储D.数据元素可以是多个字符
2．设有两个串p和q，求q在p中首次出现的位置的运算称作。
A.连接B.模式匹配C.求子串D.求串长
3．串是一个B的序列。
A.不少于一个字母B.有限个字符C.不少于一个字符D.空格或字母
4．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为。
A.8B.9C.36D.37
BBBD
填空题
1．两个串相等的充分必要条件是。
2．空格串是,其长度等于。
3．在串S=’tuition’中，以t为首字符且值不相同的子串有个。
4.使用“求子串”substring（S,pos,len）和“联接”concat（S1,S2）的串操作，可从串s=’conduction’中的字符得到串t=’cont’，则求t的串表达式为。
1.两个串的长度相等且对应位置的字符相同
2.由一个或多个空格字符组成的串其包含的空格个数
3.10
4.concat（subString（s,1,3）,substring（s,7,1））
第五章数组与广义表
单项选择题
1．常对数组进行的两种操作是。
A.建立与删除B.索引和修改C.查找和修改D.查找与索引
2．假设8行10列的二维数组a[1..8,1..10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3][5]的地址与以列序为主序时元素_______的地址相同。
A.a[5][3]B.a[8][3]C.a[1][4]D.答案A、B、C均不对
3．将一个A[1..100,1..100]的三对角矩阵以行序为主序存入一维数组B[1..298]中，元素A[66，65]在B数组中的位置k等于_______。
A.198B.197C.196D.195
4．稀疏矩阵一般的压缩存储方法有两种，即。
A.二维数组和三维数组B.三元组和散列
C.三元组和十字链表D.散列和十字链表
5.一个非空广义表的表头_______。
A.不可能是子表B.只能是子表C.只能是原子D.可以是原子或子表
6.设head（L）、tail（L）分别为取广义表表头、表尾操作，则从广义表L=（（x,y,z）,a,（u,v,w））中取出原子u的运算为_______。
A.head（tail（tail（head（L））））B.tail（head（head（tail（L））））
C.head（tail（head（tail（L））））D.head（head（tail（tail（L））））
7．广义表（a,（（b,（c,d,（e,f）））,g））的深度为_______。
A.3B.4C.5D.6
CDDCDDC
填空题
1．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占四个单元，则元素A[7,5]的地址为。
2．二维数组A[0..9,0..19]采用行序为主方式存储，每个元素占一个存储单元，并且元素A[0,0]的存储地址是200，则元素A[6,12]的地址是。
3．二维数组A[10..20,5..10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10,5]的存储地址是1000，则元素A[18,9]的地址是。
4．有一个10阶对称矩阵A，采用压缩存储方式（以行序为主序存储，且元素A[0,0]地址为1），则元素A[8,5]的地址是。
5．设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[]
是函数的符号，给出下列广义表的运算结果：
HEAD[（a，b，c）]的结果是。
TAIL[（a，b，c）]的结果是。
HEAD[（（a），（b））]的结果是。
TAIL[（（a），（b））]的结果是。
HEAD[TAIL[（a，b，c）]的结果是。
TAIL[HEAD（（a，b），（c，d））]的结果是。
HEAD[HEAD[（a，b），（c，d））]]的结果是。
TAIL[TAIL[（a，（c，d））]]的结果是。
①a；②（b，c）；③（a）；④（（b））；⑤b；⑥（b）；⑦a；⑧（）
1.1100
2.332
3.1208
4.42
5.①②③④⑤⑥⑦⑧
第6章树和二叉树
选择题
1．以下说法错误的是。
A.树形结构的特点是一个结点可以有多个直接前趋
B.线性结构中的一个结点至多只有一个直接后继
C.树形结构可以表达（组织）更复杂的数据
D.树（及一切树形结构）是一种"分支层次"结构
2.如图6-2所示的4棵二叉树中，不是完全二叉树。
图6-24棵二叉树
3.以下说法错误的是。
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B.在三叉链表上，二叉树的求双亲运算很容易实现
C.在二叉链表上，求根，求左、右孩子等很容易实现
D.在二叉链表上，求双亲运算的时间性能很好
4.如图6-3所示的4棵二叉树，是平衡二叉树。
图6-34棵二叉树
5.如图6-4所示二叉树的中序遍历序列是。
A.abcdgefB.dfebagcC.dbaefcgD.defbagc
图6-41棵二叉树
6.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。
A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca
7.将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。
A.42B.40C.21D.20
8.一棵二叉树如图6-5所示，其后序遍历的序列为。
A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh
图6-51棵二叉树
9.深度为5的二叉树至多有个结点。
A.16B.32C.31D.10
10.设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数至少有个。
A.k+1B.2kC.2k-1D.2k+1
11.对含有B个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A.0B.1C.2D.不存在这样的二叉树
1-5ACDBB
6-10DDCCC
填空题
1.有一棵树如图6-7所示，回答下面的问题：
图6-71棵二叉树
（1）这棵树的根结点是；
（2）这棵树的叶子结点是；
（3）结点k3的度是；
（4）这棵树的度为；
（5）这棵树的深度是；
（6）结点k3的孩子是；
（7）结点k3的双亲结点是。
2.深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是。
答：
①2
②2
-1③2
+1
3.一棵二叉树的第i（i≥1）层最多有个结点；一棵有n（n>0）个结点的满二叉树共有个叶子和个非终端结点。
答：
①2
②
③
4.具有n个结点的完全二叉树的深度为。
5.哈夫曼树是带权路径度_______的树，通常权值较大的结点离根_______。
①最短②较近
6．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
1.答：
①k1②k2k5k7k4③2④3⑤4⑥k5，k6⑦k1
2.①②③
3.①②③
4.floor（log2n）+1
5.①②
6.先根
例题解析
【例6-1】由如图6-1所示的二叉树，回答以下问题。
（1）其中序遍历序列为①；
（2）其前序遍历序列为②；
（3）其后序遍历序列为③；
（4）该二叉树的中序线索二叉树为④；
（5）该二叉树的后序线索二叉树为⑤；
（6）该二叉树对应的森林是⑥。
图6-11棵二叉树
解：
①中序遍历序列为dgbaechif②前序遍历序列为abdgcefhi
③后序遍历序列为gdbeihfca④该二叉树的中序线索二叉树如图6.1.1（a）所示⑤该二叉树的后序线索二叉树如图6-1-1（b）所示
⑥该二叉树对应的森林如图6-1-2所示
图6-1-1二叉树的中序线索二叉树和后序线索二叉树
图6-1-2二叉树对应的森林
1．二叉树结点数值采用顺序存储结构，如表6-2所示。
表6-2二叉树的顺序存储结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
e
a
f
d
g
c
j
h
i
b
（1）画出二叉树表示；
（2）写出前序遍历，中序遍历和后序遍历的结果；
（3）写出结点值c的父结点，其左、右孩子。
解：
（1）该二叉树如图6-9所示。
图6-91棵二叉树
（2）本题二叉树的各种遍历结果如下：
前序遍历：
eadcbjfghi
中序遍历：
abcdjefhgi
后序遍历：
bcjdahigfa
（3）c的父结点为d，左孩子为j，没有右孩子。
2．有一份电文中共使用5个字符：
a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。
解：
依题意，本题对应的哈夫曼树如图6-15所示。
各字符对应的哈夫曼编码如下：
a：
001
b：
10
c：
01
d：
000
e：
11
图6-15一棵哈夫曼树
3．设给定权集w={2，3，4，7，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。
解：
本题的哈夫曼树如图6-16所示。
图6-16一棵哈夫曼树
其加权路径长度WPL=7×2+8×2+4×3+2×4+3×4+9×2=80
4.已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。
解：
由后序序列的最后一个结点a可推出该二叉树的树根为a，由中序序列可推出a的左子树由cbed组成，右子树由hgijf组成，又由cbed在后序序列中的顺序可推出该子树的根结点为b，其左子树只有一个结点c，右子树由ed组成，显然这里的e是根结点，其右子树为结点d，这样可得到根结点a的左子树的先序序列为：
bcde；再依次推出右子树的先序序列为：
fghij。
因此该二叉树如图6-17所示。
图6-17二叉树
设二叉树的先序线索链表如图6-18所示。
图6-18二叉树的先序线索链表
第7章图
单项选择题
1．在一个图中，所有顶点的度数之和等于所有边数的倍。
A.1/2B.1C.2D.4
2．在一个有向图中，所有顶点的入度之和等于所有顶点
升级会员 