数据结构综合习题集含答案.docx
《数据结构综合习题集含答案.docx》由会员分享，可在线阅读，更多相关《数据结构综合习题集含答案.docx（24页珍藏版）》请在冰点文库上搜索。
数据结构综合习题集含答案
数据结构习题集
、选择题
1数据结构中所定义的数据元素，是用于表示数据的。
（C）
A.最小单位B.最大单位C.基本单位D.不可分割的单位
2•从逻辑上可以把数据结构分为（C）
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
3.当待排序序列中记录数较少或基本有序时，最适合的排序方法为（A）
A.直接插入排序法B.快速排序法C.堆排序法D.归并排序法
4.关于串的的叙述，不正确的是（B）
A.串是字符的有限序列B.空串是由空格构成的串
C•替换是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
5.带表头结点链队列的队头和队尾指针分别为front和rear,则判断队空的条件为（A）
A.front==rearB.front!
=NULLC.rear!
=NULLD.front==NULL
6.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B）
A.n/2B.nC.（n+1）/2D.n+1
7.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（A）
A.nB.2n-1C.2nD.n2
&设顺序表有19个元素，第一个元素的地址为200,且每个元素占3个字节，则第14个
元素的存储地址为（B）
A.236B.239C.242D.245
9.一个栈的入栈序列是a,b,c,d,e,则栈的输出序列不可能是（A）
A.dceabB.decbaC.edcbaD.abcde
10.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作
为栈顶指针，则出栈处理后，top的值应修改为（D）
A.top=topB.top=n-1C.top=top-1D.top=top+1
11.设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储，a00为第一个元素，
其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（B）
A.13B.35C.17D.36
12.栈和队列（C）
A.共同之处在于二者都是先进先出的特殊的线性表
B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作
D.没有共同之处
13.含有n个结点的二叉树用二叉链表表示时，空指针域个数为
A.n-1B.nC.n+1D.n+2
14.
（C）
49的结点，它的左孩子的编
对一棵有100个结点的完全二叉树按层序编号，则编号为号为（B）
18.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
19.对线性表进行二分查找时，要求线性表必须（C）
A.以顺序方式存储B.以链式方式存储
C.以顺序方式存储，且结点按关键字有序排列
D.以链接方式存储，且结点按关键字有序排列
20.二分查找算法的时间复杂度是（D）
A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）
21.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（C）
A.插入和快速B.冒泡和快速C.选择和插入D.选择和冒泡
22.闭散列表中由于散列到同一个地址而引起的堆积”现象，是（B）
A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的
C.由同义词之间或非同义词之间发生冲突引起的
D.由散列表溢出”引起的
23.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。
这种方式主要适合于（B）
A.静态查找表B.动态查找表
C.静态查找表与动态查找表D.静态查找表或动态查找表
24.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（B）
A.选择排序B.插入排序C.冒泡排序D.快速排序
25.下列程序段的时间复杂度为。
（C）
for（i=0;ifor（j=0;ji][j]=0;
for（i=0;ifor（j=0;jfor（k=0;kc=c:
i][j]+a[i][k:
*b:
k][j]；
A.O（m+nxt）B.O（m+n+t）C.O（mXnX）D.O（mxt+n）
26.数据的四种基本逻辑结构是指（D）
A.数组、链表、树、图形结构
B.线性表、链表、栈队列、数组广义表
C.线性结构、链表、树、图形结构
D.集合、线性结构、树、图形结构
27.在表长为n的顺序表上做插入运算，平均要移动的结点数为（C）。
A.n/4B.n/3C.n/2D.n
28.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（A）。
A.3B.4C.5D.6
29.定义二维数组A[1•-8,0・・10],起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式
下，该元素的存储地址为（D）。
A丄OC+28LB.LOC+36LC.LOC+50LD.LOC+52L
30.下列程序段的时间复杂度为。
（D）
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
for（k=1;k<=n;k++）
s=i+j+k;
A.O（m2）B.O（m3）C.O（n2）D.O（n3）
31.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（B）。
A.选择排序B.插入排序C.冒泡排序D.快速排序
32.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是（A）。
A.DCBAB.CDABC.DBACD.DCAB
33.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（A）。
A.24B.25C.98D.99
34.对一棵二叉排序树采用中序遍历进行输出的数据一定是（D）。
35.
A.由同义词之间发生冲突引起的
B.由非同义词之间发生冲突引起的
C.由同义词之间或非同义词之间发生冲突引起的
D.
由散列表溢出”引起的
E.
37.下列程序段的时间复杂度为
38.
k=1;
A[i][j:
=k++;
38•数据的四种基本存储结构是指
A..顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
39.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C）
A.线性结构B.树形结构
C.线性结构和树型结构D.线性结构和图状结构
40.在表长为n的顺序表上做删除运算，其平均时间复杂度为（B）
A.O
（1）B.O（n）C.O（nlog2n）D.O（n2）
14个
41•顺序表中有19个元素，第一个元素的地址为200,且每个元素占一个字节，则第
元素的存储地址为（B）
42.当待排序序列中记录数较少或基本有序时，最适合的排序方法为（A）
A.直接插入排序法B.快速排序法C.堆排序法D.归并排序法
43.在完全二叉树中，若一个结点是叶结点，则它没有（C）
A.左孩子结点B.右孩子结点
C.左孩子结点和右孩子结点D.左孩子结点，右孩子结点和兄弟结点
44.
（C）
设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为
45.
A.700
B.1120C.1180D.1140
46.用n个值构造一棵二叉排序树，它的最大高度为（B）
A.n/2B.nC.n+1D.log2n
47.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（A）
A.3B.4C.5D.6
48.一个具有n个顶点的无向连通图，它所包含的连通分量数为（B）
A.0B.1C.nD.不确定
49.
（C）
B.以链式方式存储
堆积”现象，是（B）
B.由非同义词之间发生冲突引起的
对线性表进行二分查找时，要求线性表必须
A.以顺序方式存储
C.以顺序方式存储，且结点按关键字有序排列
D.以链接方式存储，且结点按关键字有序排列
50.散列表中由于散列到同一个地址而引起的
A.由同义词之间发生冲突引起的
C.由同义词之间或非同义词之间发生冲突引起的
D.由散列表溢出”引起的
51.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。
这种方式主要适合于（B）
A.静态查找表B.动态查找表
C.静态查找表与动态查找表D.静态查找表或动态查找表
52.要解决散列引起的冲突问题，常采用的方法有（D）
A.数字分析法、平方取中法B.数字分析法、线性探测法
C.二次探测法、平方取中法D.二次探测法、链地址法
53.设用链表作为栈的存储结构，则进行出栈操作时（）。
A必须判别栈是否为满B必须判别栈是否为空
C判别栈元素的类型D对栈不作任何判别
54.栈和队列的共同特点是（A）。
A.只允许在端点处插入和删除元素
B.都是先进后出C.都是先进先出D.没有共同点
55.若有10个元素的有序表存放在一维数组A[11]中，第一个元素放A[1]中，最后一个数据存入A[10],对这组数据进行二分查找，则查找A:
3]的比较序列的下标依次为（A）
B.6,4,3
A.5,2,3
C.6,2,3D.4,2,3
56.用链表方式存储的队列，在进行插入运算时（C）.
A.仅修改头指针B.头、尾指针都要修改
C.仅修改尾指针D.头、
尾指针可能
总都要修改
57•下列各项键值序列中不是堆的为（
C）
A.{5,23,16,68,94,72,71,73}
B.{5,
16,
23,68,
94,
72,
71,
73}
C.{5,23,16,73,94,72,71,68}
D.{5,
23,
16,68,
73,
71,
72,
94}
58.以下数据结构中哪一个是非线性结构？
（D）
A.队列B.栈C.线,
性表
D.二叉树
59二叉树的第k层的结点数最多为（A）.
A.2k-1B.2K+1C.2K-1D.2k-1
60•若有18个元素的有序表存放在一维数组A［19］中，第一个元素放A［1］中，现进行二分查
找，则查找A:
3］的比较序列的下标依次为（D）
A.1,2,3B.9,5,2,3
C.9,5,3D.9,4,2,3
61.设有6个结点的无向图，该图至少应有（A）条边才能确保是一个连通图。
A.5B.6C.7D.8
62.下面关于线性表的叙述错误的是（D）。
A线性表采用顺序存储必须占用一片连续的存储空间
B线性表采用链式存储不必占用一片连续的存储空间
C线性表采用链式存储便于插入和删除操作的实现
D线性表采用顺序存储便于插入和删除操作的实现
63.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该哈夫曼树中总共
有（B）个空指针域。
A2m-1B2mC2m+1D4m
64.设某完全无向图中有n个顶点，则该完全无向图中有（A）条边。
An（n-1）/2Bn（n-1）Cn2Dn2-1
65.设一组初始记录关键字序列（5,2,6,3,8），以第一个记录关键字5为基准进行一趟
快速排序的结果为（C）。
A2,3,5,8,6B3,2,5,8,6
C3,2,5,6,8D2,3,6,5,8
66.设指针变量p指向单链表中结点A的前驱节点，若删除单链表中结点A，则需要执行
的操作序列为（C）。
Aq=p->next;p->data=q->data;p->next=q->next;free（q）;
Bq=p->next;q->data=p->data;p_>next=q_>next;free（q）;
Cq=p->next;p_>next=q_>next;free（q）;
Dq=p->next;p->data=q->data;free（q）;
67.设某强连通图中有n个顶点，则该强连通图中至少有（C）条边。
An（n-1）Bn+1CnDn（n+1）
68.设用链表作为栈的存储结构则出栈操作时（B）。
A必须判别栈是否为满B必须判别栈是否为空
C判别栈元素的类型D对栈不作任何判别
69.数据的最小单位是（A）。
A数据项B数据类型C数据元素D数据变量
70.若入栈顺序为1、2、3、4、5、6，则出栈序列为（B）。
A5,3,4,6,1,2B3,2,5,6,4,1
C3,1,2,5,4,6D1,5,4,6,2,3
71.下列关键码序列中，属于堆的是（A）
A.（15,30,22,93,52,71）B.（15,71,30,22,93,52）
C.（15,52,22,93,30,71）D.（93,30,52,22,15,71）
二、填空题
1•在栈结构中，允许插入的一端称为—栈顶。
2.从一个长度为n的顺序表中删除第i个元素（13•深度为k的二叉树，结点数最多有__2k-1个。
4.在图中，第一个顶点和最后一个顶点相同的路径称为—回路或环。
5•对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为―（n+1）/2。
6.快速排序算法的时间复杂度为_0（nlogn）。
7.若图的邻接矩阵不是一个对称矩阵，则该图一定是一个—有向图。
&若一个无向完全图具有n个顶点，则该图的边的条数为_n（n-1）/2。
9.有m个叶子结点的哈夫曼树，其结点总数是_2m-1。
10.堆排序需_1个记录大小的辅助存储空间。
11•在队结构中，允许插入的一端称为队尾;在栈结构中，允许插入的一端称
为。
12.在数据结构中，数据的存储结构有存储、存储、存储
和存储四种方式。
13.若某二叉树中度为1的结点数为4,度为2的结点数为6，则该树叶子结点数为
7。
14.
三种存储结构表示
树在数据结构中常采用
15.设一个顺序栈S,元素si,s2,s3,s4,s5,s6依次进栈，如果6个元素的退栈顺序为s2,s3,s4,s6,s5,si，则顺序栈的容量至少为3。
16.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为
25。
17.一个具有10个顶点的完全无向图中有_^45条边。
18.在无向图G的邻接矩阵A中，若A[i][j]等于0，则A[j][i]等于0。
19•对二叉排序树进行遍历，可得到排好序的递增结点序列。
20.设顺序表的表长为n,且查找每个元素的概率相等，则采用顺序查找法查找表中任一元
素，在查找成功时的平均查找长度为。
21.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是的。
22.对顺序表执行删除操作，其删除算法的平均时间复杂性为O（n）。
23.对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行丄趟起泡。
24.在图中，第一个顶点和最后一个顶点相同的路径称为。
25.在栈结构中，允许插入的一端称为，另一端称
为。
26.从一个长度为n的顺序表中删除第i个元素（127.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素
为__n-i+1。
28.深度为k的二叉树，结点数最多有个。
29.二路归并排序算法的时间复杂度为。
30.含有n个顶点和n-1条边的连通图G采用—邻接表存储结构较省空间。
31.在图中，第一个顶点和最后一个顶点相同的路径称为。
32.对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为。
33.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，
然后再用查找法在块中找到具体的元素值。
34.对n个元素进行冒泡排序时，最少的比较次数为_n-1。
35.快速排序法在待排序数据—基本有序的情况下最不利于发挥其长处。
36.快速排序算法的时间复杂度为_O（nlogn）。
37.在一棵二叉排序树上按遍历得到的结点序列是一个有序序列。
38.若图的邻接矩阵不是一个对称矩阵，则该图一定是一个。
39.若一个无向完全图具有n个顶点，则该图的边的条数为。
40.有m个叶子结点的哈夫曼树，其结点总数是。
41.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号
为__25。
42.具有n个顶点的连通图至少需有条边。
43.堆排序需1个记录大小的辅助存储空间。
44.队列是一种线性表。
45.算法的特性有：
输入、、、可行性、输出。
46.对任意非空二叉树，若叶子结点数为nO,度为1的结点数为n1,度为2的结点数为n2,
贝Hn0=
47.中序遍历二叉树步骤是：
若二叉树非空，1）中序遍历左子树，2）,3）中序遍历右子树
48.n阶上三角矩阵采用一维数组存放时，可压缩存储到个元素中。
49.连通图的最小生成树中有n个顶点，条边，并不能存在。
50.n个结点的完全二叉树，结点按从上到下从左到右编号，其中序号为i结点的左孩子序
号—2i
三、应用题
1.有一字符串序列为5*-x-y/x+2,利用栈的运算将其输出结果变为5x-*yx+/-2,描述栈的操
作特点，试写出该操作的入栈和出栈过程（用push（a）表示a入栈，pop（a）表示a出栈）。
特点自己从书上找。
Push（5）pop（5）push（*）push（-）push（x）pop（x）pop（-）
pop（x）push（-）push（y）pop（y）push（/）push（x）pop（x）
push（+）pop（+）pop（/）pop（-）push
（2）pop
（2）
2.在栈的输入端有6个元素，输入顺序为A,B,C,D,E,F。
请描述栈的操作特点，并判断能否在栈的输出端得到序列DCFEBA，若能，给出入栈、出栈操作的过程，若不
能,简述其理由。
（push（A）表示入栈，pop（A）表示出栈）
栈的操作特点自己查找
能
Push（A）Push（B）Push（C）,Push（D）,Pop（D）,
Pop（C）Push（E）,Push（F）Pop（F）,Pop（E）,Pop（B）,Pop（A）
3•有一字符串的次序为-3*y+a/y!
2，试利用栈将输出次序改变为3y*-ay!
2/+,描述栈的操作特点，写出该输出序列对应的进栈和退栈的操作步骤。
（用push（x）表示x进栈，pop（x）
表示x退栈）
Push（-）push（3）pop（3）push（*）push（y）pop（y）pop（*）pop（-）push（+）push（a）pop（a）push（/）push（y）pop（y）push（!
）pop（!
）push
（2）pop
（2）pop（/）pop（+）
4.已知一棵二叉树的先根遍历序列为ABCDEGHF,中根遍历序列为CBEDAGFH,画出该
二叉树，并写出后序遍历序列。
后序遍历序列：
CEDBFHGA
5•已知无向图G的邻接矩阵如图所示。
请画出该无向图，并写出v0出发按深度优先遍历
时的访问序列。
6.已知散列函数为H（key）=key%7，散列表长度为7（散列地址空间为0..6），待散列序列为:
（25,48,32,50,68）。
根据以上条件构造一散列表，并用线性探测法解决有关地址冲
突；若要用该散列表查找元素68,给出所需的比较次数。
H（25）=25%7=4
H（68）=68%7=5
H（32）=32%7=4
H（50）=50%7=1H（48）=48%7=6
68
50
25
32
48
查找68:
首先计算：
H（68）=68%7=5,68与32比较，68与48比较，68与68比较查找成功，共比较3次。
7.给定表（39,14,22,8,65,28,88,29,67,13,10）,试按元素在表中的顺序将它
们依次插入一棵初始时为空的二叉排序树，描述二叉排序树的定义，画出插入完成后的
二叉排序树。
定义自己从书上找
&用冒泡排序算法对数据序列（49,38,65,97,76,134,27,49）进行升序排序，写出
整个冒泡排序的各趟排序过程。
第一趟排序结果：
38,49,65,76,97,27,49,134
第二趟排序结果：
38,49,65,76,27,49,97,134
第三趟排序结果：
38,49,65,27,49,76,97,134
第四趟排序结果：
38,49,27,49,65,76,97,134
第五趟排序结果：
38,27,49,49,65,76,97,134
第六趟排序结果：
27,38,49,49,65,76,97,134
9.某通讯电文由
A,B,C,D,E,F六个字符编码组成，每个字符编码在电文中出现的次
数分别是6,5,
9,10,
升级会员 