数据结构综合习题集含答案Word文档下载推荐.docx
- 文档编号:7184846
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:24
- 大小:151.80KB
数据结构综合习题集含答案Word文档下载推荐.docx
《数据结构综合习题集含答案Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构综合习题集含答案Word文档下载推荐.docx(24页珍藏版)》请在冰点文库上搜索。
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;
i<
m;
i++)
for(j=0;
j<
t;
j++)c:
i][j]=0;
j++)
for(k=0;
k<
n;
k++)
c=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;
=n;
i++)
for(j=1;
for(k=1;
=n;
s=i+j+k;
A.O(m2)B.O(m3)C.O(n2)D.O(n3)
31.排序算法中,第一趟排序后,任一元素都不能确定其最终位置的算法是(B)。
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.由非同义词之间发生冲突引起的
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,且每个元素占一个字节,则第
42.当待排序序列中记录数较少或基本有序时,最适合的排序方法为(A)
A.直接插入排序法B.快速排序法C.堆排序法D.归并排序法
43.在完全二叉树中,若一个结点是叶结点,则它没有(C)
A.左孩子结点B.右孩子结点
C.左孩子结点和右孩子结点D.左孩子结点,右孩子结点和兄弟结点
44.
设顺序表有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)
48.一个具有n个顶点的无向连通图,它所包含的连通分量数为(B)
A.0B.1C.nD.不确定
49.
B.以链式方式存储
堆积”现象,是(B)
B.由非同义词之间发生冲突引起的
对线性表进行二分查找时,要求线性表必须
A.以顺序方式存储
50.散列表中由于散列到同一个地址而引起的
51.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插入到集合中。
这种方式主要适合于(B)
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,
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;
next=q->
free(q);
Bq=p->
q->
data=p->
p_>
next=q_>
Cq=p->
next;
Dq=p->
67.设某强连通图中有n个顶点,则该强连通图中至少有(C)条边。
An(n-1)Bn+1CnDn(n+1)
68.设用链表作为栈的存储结构则出栈操作时(B)。
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个元素(1<
i胡时)需向前移动—n-i个元素。
3•深度为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。
三种存储结构表示
树在数据结构中常采用
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个元素(1<
i帥)需向前移动_n-i个元素。
27.一个栈的输入序列是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,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 综合 习题集 答案