数据结构复习题及答案Word文件下载.docx
《数据结构复习题及答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构复习题及答案Word文件下载.docx（51页珍藏版）》请在冰点文库上搜索。
next=head。
17.在栈结构中，允许插入的一端称为_栈顶;
在队列结构中，允许插入的一端称为_队尾。
18.队列中元素的入队和出队应遵循一先进先出__原则，数据元素1，2,3,4，5按照次序入队
后，第一个出队的是_1。
19.在循环队列中，存储空间为0〜n-1。
设队头指针front指向队头元素前一个空闲元素，队尾指
针指向队尾元素，那么其队空标志为rear=front，队满标志为_（rear+1）%n=front_。
20.设顺序表有19个元素，第一个元素的地址为200,且每个元素占3个字节，则第14个元素的存
储地址为_239。
21.在一个长度为n的顺序表中删除第i个元素（Ki<
n）,需向前移动n-i个元素。
22.在一个长度为n的顺序表中第i个元素前（Ki<
n）,插入一个元素，需向后移动n-i+1
个元素。
23.在顺序存储的线性表中插入或删除一个元素平均约移动表中__50%_（或一半）_的元素。
24.在顺序表中访问任意一结点的时间复杂度均为0
（1）,因此，顺序表也称为随机存取的数据
结构。
25.在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。
26.一个广义表为（a,（a,b）,d,e,（（i,j）,k）），则该广义表的长度为__5___，深度为3。
27.已知广义表A=（（a,b,c）,（d,e,f）），则运算tail（head（tail（A）））=（e,f）__。
28.已知广义表Ls=（a,（b,c,d）,e），运用head和tail函数取出Ls中的原子b的运算是
_。
29.广义表（（a,b）,c,d）的表头是_（a,b）_表尾是_（c,d）_。
30.广义表（a,b,c,d）的表头是_a表尾是（b,c,d）_。
31.两个串相等的充分必要条件是:
串长相等且对应的字符相等。
32.不含任何字符的串称为空串其长度为0。
33.对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素所在的
行、—列以及它的值。
34.若二叉树中有20个叶子结点，则该二叉树有_19个度为2的结点。
35.若二叉树中度为2的结点有15个，则该二叉树有__16个叶子结点。
36.深度为h且有2F-1个结点的二叉树称为满二叉树。
37.深度为k的二叉树最多有_2*1个结点，最少有_Js—个结点，第i层上最多有
_2A（i-1）个结点。
38.深度为5的满二叉树共有_J1个结点，其中有16个叶子节点。
39.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_34个结点。
40.深度为15的满二叉树上，第11层有_个结点。
41.一棵具有100个结点的完全二叉树，它的深度为_7_，其中度为1的结点有_1_个。
42.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为_dab。
43•哈夫曼树是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度的二叉树。
44.具有m个叶子结点的哈夫曼树共有2m-1个结点。
45.已知一棵哈夫曼树含有60个叶子结点，则该树中共有_59个非叶子结点。
46.在一个具有n个顶点无向完全图中，含有_n（n-1）/2边；
在一个具有n个顶点有向完全
图中，含有_n（n-1）边。
一个具有4个顶点的无向完全图有_6_条边。
47.具有n个顶点的连通图至少需有_n-1_条边。
48.一个连通图的生成树是该图的极小_连通子图。
若这个连通图有n个顶点，则它的生成树
有n-1_条边。
49.在有向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的_出度第i列中非零
元素的个数正好是第i个顶点的_入度_。
50.在一个图中，所有顶点的度数之和等于所有边数的_2_倍。
51.在无向图G的邻接矩阵A中，若A[i][j]等于1,贝UA：
j:
:
i]等于—1。
52.对二叉排序树进行—中序—遍历，可以得到按关键字从小到大排列的结点序列。
53.一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，当折半查找值为82的
结点时，经过_4_次比较后查找成功。
54.在线性表中采用折半查找法查找一个数据元素，线性表中元素应该按值有序，并且采用顺序
存储—存储方法。
55.在简单选择排序、堆排序、快速排列、归并排序四种排序方法中，排序方法稳定的是_归并排序。
56.冒泡排序是一种稳定的排序方法，对n个元素的序列进行冒泡排序时，最多需进行_n-1_趟。
该
排序方法的时间复杂度为_0（n2）_。
57.给定序列｛100,86,48,73,35,39,42,57,66,21｝，按堆的定义，则它一定—大根—堆。
58.数据结构是指数据及其相互之间的一种或多种关系。
当结点之间存在M对N（MN）的联
系时，称这种结构为图状结构。
59.队列的插入操作是在队列的队尾进行，删除操作是在队列的队头进行。
60.每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做直接
插入_排序；
每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序
方法叫做__简单选择（或直接选择）排序。
61.二叉树的前序遍历序列为A,B,C,E,F,D,GH,中序遍历序列为A,E,C,F,B,G,,H,
其后序遍历序列为E,F,C,G,H,D,B,A。
62.对于一棵具有n个结点的二叉树，若一个结点的编号为i（0vivn-1），则它的左孩子结点的编
号为_2i，右孩子结点的编号为_2i+1，双亲结点的编号为_i/2。
63.在一个具有6个顶点的无向完全图中，包含有_15条边，在一个具有6个顶点的有向完全
图中，包含有_30条弧。
64.快速排序在平均情况下的时间复杂度为__0（nlog2n）_,在最坏情况下的时间复杂度为__
2
0（n）__。
65.从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明—查找成功，
若元素的值小于根结点的值，则继续向—左子树_____查找，若元素的大于根结点的值，则继续
向__右子树_______查找。
66.在循环单链表中，最后一个结点的指针域指向___首—结点。
67.假定一棵树的广义表表示为A（C,D（E,F,G）,H（I，J））,贝U树中所含的结点数为_9_个，树
的深度为__3___，树的度为__3__o
68.通常从四个方面评价算法的质量：
正确性、可读性_、健壮性—和效率与低存储量
需求_。
69.假设一棵完全二叉树含1000个结点，则其中度为2的结点数为499。
70.一个算法的时间复杂度为（3n3+2n—7）/（5n），其数量级表示为_O（n2）。
71.在快速排序、堆排序和归并排序中，最坏时间复杂度为O（n2）的排序算法有_快速排序。
72.数据结构被形式地定义为（D,R）,其中D是数据元素的有限集合，R是D上的关系有
限集合。
73.在归并排序中，进行每趟归并的时间复杂度为O（n），整个排序过程的时间复杂度为
O（nlog2n），空间复杂度为O（n）。
74.若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为__9___。
75.对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为O（n2）_,
对用邻接表表示的图进行任一种遍历时，其时间复杂度为_O（n+e）_。
76.从有序表（12,18,30,43,56,78,82,95）中依次二分查找43和56元素时，其查找长度分
别为__1和—3___。
77.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为2n个，其中n-1个用
于指向孩子，n+1个指针是空闲的。
78.从逻辑结构看，线性表是典型的—线性结构__,树是典型的—非线性结构—。
79.设二叉树中结点的两个指针域分别为Ichild和rchild，则判断指针变量p所指向的结点为叶子
结点的条件是p->
lchild==NULL&
&
p->
rchild==NULL。
80.栈是一种__先进后出表。
队列又称为先进先出表。
81.若对序列（49,38,65,97,76,13,27,50）采用直接选择排序法排序，则第三趟结束后序列的
状态是__（13,27,38）,97,76,49,65,50
82.利用关键码分别为10,20,30,40的四个结点，能构造出__14__种不同的二叉排序树.
83.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对
其进行（按递增排序），—冒泡排序—最省时间，—快速排序—最费时间。
84.空串的长度是__0_；
空格串的长度是__空格的个数_。
串中所含字符个数称为该串的_长度_.
85.在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为__O（n）_。
86.设SQ为循环队列，存储在数组d[m]中，贝USQ出队操作对其队头指针front的修改是_front=
（front+1）%m=。
87.树的度是指—树内各结点的度的最大值。
88.已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为__
_p_>
next=top_和_top=p_o
89.堆排序的空间复杂度___O
（1）__o
90.深度为n（n>
0）的二叉树最多有25-1个结点。
91.设关键字序列为（K,K2,…，KJ，则用筛选法建初始堆必须从第_n/2个元素开始进行筛选。
92.图有_邻接矩阵—、邻接表_等存储结构，遍历图有_深度优先搜索_、—广度优
先搜索__等方法。
93.在一个有向图的邻接表中，一个顶点的链表中结点的个数等于这个顶点的__出度__，在逆邻接
表中，一个顶点的链表中结点的个数等于这个顶点的入度。
94.对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有
序表中的位置可能是」，3,6,9一。
95.折半查找有序表（4,6,12,20,28,38,50,70,88,100）,若查找表中元素20,它将依次
与表中元素比较大小。
96.在对一组记录关键字（54,38,96,23,15,72,60,45,83）进行冒泡排序时，整个冒泡排序过程中需进行_8_趟才能完成。
97.对关键字序列（52,80,63,44,48,91）进行一趟快速排序之后得到的结果为48,44,52,63,
80,91。
98.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序;
若初始记录基本无序，
则最好选用—快速排序—。
99.在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序时，当把第7个记录
60插入到有序表时，为寻找插入位置至少需比较_3次。
100.设一组记录关键字序列为（80,70,33,65,24,56,48），则用筛选法建成的初始堆为_（80,
70,56,65,24,33,48）或_（24,65,33,80,70,56,48）。
二、单选题
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
在数据结构中，数据的基本单位是（）
A.数据项
B.数据元素C.数据对象D.数据文件
数据结构是（
A.—种数据类型
．数据的存储结构
C.一组性质相同的数据元素的集合
D.相互之间存在一种或多种特定关系的数据元素的集合
在数据结构的讨论中把数据结构从逻辑上分为（
）.
A.内部结构与外部结构
B.静态结构与动态结构
C.线性结构与非线性结构
D.紧凑结构与非紧凑结构。
算法指的是（
）。
A.计算机程序
B•解决问题的计算方法
C.排序算法
D•解决问题的有限运算序列
算法分析的目的是（
A.辨别数据结构的合理性
B.评价算法的效率
C.研究算法中输入与输出的关系
.鉴别算法的可读性
某程序的时间复杂度为（3n+nlog
2n+n
2+8）,其数量级表示为（
A.O（n）B.O（nlog2n）
C.O（n）D.O（log2n）
for（i=0；
i<
n；
i++）
for（j=0；
j<
j++）
A[i][j]=i*j；
上述程序段的时间复杂度为（）
A.O（n2）B.O（n）C.O
2n）
D.O
（1）
以下数据结构中哪一个是非线性结构？
A.队列
B.栈C.
线性表
D.二叉树
设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）
A.5
B.6
C.7
D.9
线性表采用链式存储结构时，要求内存中可用存储单元的地址
A.必须是连续的
B.
必须是部分连续的
C.一定是不连续的
D.连续和不连续都可以
线性表是具有相同数据类型的n个
的有限序列。
A.数据项
B.数据元素C.表元素D.字符
12.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是
A.O
（1）B.O（n）C.O（n2）D.O（nlog2n）
13.用链接方式存储的队列，在进行插入运算时（）
A.仅修改头指针
C.仅修改尾指针
头、尾指针都要修改
D.头、尾指针可能都要修改
14.在长度为n的顺序表中删除第
i个元素（1wiwn）时，元素移动的次数为（
A.n-i+1B.iC.i+1
D.n-i
15.若带头结点的单链表的头指针为
head，则该链表为空的判定条件是（）
A.head==NULL
B.head->
next==NULL
C.head!
=NULL
D.head->
next==head
16.已知栈的最大容量为
4。
若进栈序列为
1，
2，3，
4，
5，
6，
且进栈和出栈可以穿插进行
则可能
出现的出栈序列为（
A.5，4，3，2，1，6
B.2
，3，
C.3，2，5，4，1，6
D.1
，4，
2，
17.若某线性表中最常用的操作是取第
个元素和找第i个元素的前趋元素，则采用（
存储方式最节省时间。
A.单链表
B.双链表
C.单向循环
D.顺序表
18.对一个算法的评价，不包括如下（
方面的内容。
A.健壮性和可读性
B.并行性
C.正确性
D.时空复杂度
19.队列的删除操作是在（
）进行。
A队首B•队尾C•队前
.对后
20.计算机识别、存储和加工处理的对象被统称为
A.数据
数据元素
C.数据结构
D.
数据类型
21.串是任意有限个（
1符号构成的序列
2符号构成的集合
3字符构成的序列
4字符构成的集合
22.如果以链表作为栈的存储结构，
则退栈操作时（
①必须判别栈是否满
2对栈不作任何判别
3必须判别栈是否空
4判别栈元素的类型
23.二分查找要求被查找的表是（
①键值有序的链接表②链接表但键值不一定有序
③键值有序的顺序表④顺序表但键值不一定有序
24.
25.
①n2
②nlog2n
③Iog2n
④n-1
堆是一个键值序列{k1,k2,…,kn},对
i=1,2，…,|_n/2_|,
满足（
①ki<
k2iwk2i+1
②ki<
k2i+1<
k2i
26.
27.
28.
③kiwk2i且kiwk2i+1（2i+1wn）
队列的插入操作是在（
A.队首
B.队尾C.队前
一棵具有5层满二叉树中节点总数为（
A、31B、32C、33
D、
④kiwk2i
．对后
或ki
wk2i+1（2i+1
wn）
快速排序在最坏情况下的时间复杂度为（
A.O（Iog2n）
B.O（nIog2n）
C.
0（n）
D.0（n2）
当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（
29.广义表是线性表的推广，它们之间的区别在于
A能否使用子表
C.表的长度
B.能否使用原子项
.是否能为空
30.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A.
B.连通图
有向完全图
C.强连通图
有向无环图
31.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
A.O
（1）
B.O（Iog2n）
C.O（n）
D.O（nIog
32.与线性表相比，串的插入和删除操作的特点是
A.通常以串整体作为操作对象
需要更多的辅助空间
C.算法的时间复杂度较高
涉及移动的元素更多
A.head==NULL
C.head!
B.head->
next==NULL
D.head->
next==head
34.
在单链表中,指针
p指向值为x的结点，能实现“删除x的后继”
的语句是
A.p=p->
next;
B.p=p->
next->
C.p->
next=p;
D.p->
next=p->
35.
一个栈的入栈序列是
a,b,c,d,e,则栈的输出序列不可能是（
）
假设带头结点的单向循环链表的头指针为
head,则该链表为空的判定条件是（
33.
A.dceabB.decbaC.edcbaD.abcde
36.若进栈序列为a,b,c,进栈过程中允许出栈，则以下是不可能得到的出栈序列。
A.a,b,cB.b,a,cC.c,a,bD.c,b,a
37.若进栈序列为1,2,3,4,进栈过程中允许出栈，则可能的出栈序列是。
A.2,4,1,3
B.3,1,4,2
C.3,4,1,2
D.1,2,3,4
38.设有一个栈，按
A、BCD的顺序进栈，则可能为出栈序列的是
A.DCBAB.CDAB
C.DBACD.DCAB
39.一个队列的入队序列是1，2，3，4，则队列的输出序列是（）
A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1
40.—个最多能容纳m个元素的顺序存储循环队列Q其头尾指针分别为front和rear,则判定该队
列为满的条件是
A.（Q.rear+1）%m==Q.frontB.Q.front==Q.rear
C.Q.rear+1==Q.frontD.（Q.front+1）%m==Q.rear
41.
A.front=front+1
设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）.
B.front=（front+1）%m
C.rear=（rear+1）%m
D.front=（front+1）%（m+1）
42.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为
front和rear。
若设定尾指针指向
队列中的队尾元素，
头指针指向队列中队头元素的前一个位置，
则当前存于队列中的元素
升级会员 