滨州学院数据结构期末复习题及参考答案.docx

《滨州学院数据结构期末复习题及参考答案.docx》由会员分享，可在线阅读，更多相关《滨州学院数据结构期末复习题及参考答案.docx（49页珍藏版）》请在优知文库上搜索。

1、2023年下学期数据结构（考试课）复习资料一、单项选择题1 .若要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是（）。（3分）A.s-next=p-next;p-next=s;B.p-next=s;s-next=p-next;C.p-next=s-next;s-next=p;D.s-next=p;p-next=s-next;答案：A2 .如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（）。（l分）A.有向完全图B.连通图C.强连通图D.有向无环图答案：D3 .vp在下列排序方法中，空间复杂性为O（n）的方法为（）。（l分）A.快速排序B.直接插入排序C.堆排序D.归并排

2、序答案：D4 .在C语言中，串的存储方式是（）。（l分）A.顺序存储B.散列存储C.索引存储D.链式存储答案：A5二叉树的结构如下图所示，其中序遍历的序列为（）。（1分）A.a,b,d,g,c,e,f,hB.d,g,b,a,e,c,h,fC.g,d,b,e,h,f,c,aD.a,b,c,d,e,f,g,h答案：B6.队列操作的原则是（）。（l分）A.先进先出B.后进先出C.队尾删除D.队头插入答案：A7图的深度遍历必须借助（）作为辅助空间。（l分）A.栈B.队列C.查找表D.数组答案：A8 .p在n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素个数为（）。p（l分）A.nB.n*eC.e

3、D.2*e答案：D9 .vp对关键字序列Q,H,C,Y,P,A,M,S,R,D,F,X,用下列（）方法进行第一趟排序的结果为F,H,C,D,P,A,M,Q,R,S,Y,Xp（l分）A.直接插入排序B.二路归并排序C.以第一元素为基准的快速排序D.基数排序答案：C10 .vp与邻接表表示相比，邻接矩阵表示更适合（）。p（l分）A.无向图B.有向图C.稠密图D.稀疏图答案：C11 .若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。（1分）A.单链表B.双链表C.带头结点的双循环链表D.容量足够大的顺序表答案：D12 .适用于静态的查找方

4、法为（）。（1分）A.二分查找、二叉排序树查找B.二分查找、索引顺序表查找C.二叉排序树查找、索引顺序表查找D.二叉排序树查找、散列法查找答案：B13 .vp对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8,查找后面5个元素的概率相同，均为3/40,则查找任一元素的平均查找长度为（）。p（l分）A.5.5B.5C.39/8D.19/4答案：C14 .vp在待排关键字序列基本有序的前提下，效率最高的排序方法是（）。p（1分）A.直接插入排序B.快速排序C.直接选择排序D.归并排序答案：A15 .p算法分析是指（）。p（l分）A.分析算法的正确性B.分析算法的可读性C.分析算

5、法的健壮性D.分析算法的时空性能答案：D16 .在下列排序方法中，空间复杂性为O（Iog2n）的方法为（）。（1分）A.直接选择排序B.归并排序C.堆排序D.快速排序答案：D17 .将数组称为随机存储结构是因为（）0（1分）A.数组元素是随机的B.随时可以对数组元素进行访问C.对数组的任一元素的存取时间是相等的D.数组的存储结构是不定的答案：C18 .vp关键字比较次数与数据的初始状态无关的排序算法是（）。p（l分）A.直接选择排序B.冒泡排序C.直接插入排序D.希尔排序答案：A19 .若一个图的边集为（A,B）,（A,C）,（B,D）,（C,F）,（D,E）,（D,F）,则从顶点A开始对该图

6、进行深度优先搜索，得到的顶点序列可能为（）。（1分）A.A,B,C,F,D,EB.A,C,F,D,E,BC.A,B,D,C,F,ED.A,B,D,F,E,C答案：B20 .引起循环队列队头位置发生变化的操作是（）。（1分）A.入队B.出队C.取队头元素D.取队尾元素答案：B21 .p若要在O（I）的时间内将两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）。p（l分）A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案：B22 .vp从理论上讲，将数据以（）结构存放，查找一个数据的时间不依赖于数据的个数n。p（l分）A.二叉查找树B

7、.链表C.散列表D.顺序表答案：C23 .p若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（）。p（l分）A.单链表B.顺序表C.双链表D.单循环链表答案：B24 .p在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）。p（l分）A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示答案：C25 .p设S=abc;T=xyz”，则StrCmP（S,T）的值为（）p（l分）A.正数B.负数C.零D.不确定答案：B26 .p对n个结点的二叉树，按（）遍历顺序对结点编号（号码为ln）时，任一结点

8、的编号等于其左子树中结点的最大编号加1,又等于其右子树中结点的最小编号减1。p（l分）A.前根B.中根C.后根D.层次答案：B27 .vp连通网的最小生成树是其所有生成树中（）。p（l分）A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树答案：D28 .对长度为n的顺序表，访问第i个元素的时间是（）。（1分）A.0（n2）B.O（n）C.O（nlog2n）D.O（1）答案：D29 .关于矩阵的三元组表表示，以下叙述正确的是（）。（1分）A.转置运算时只需把每个三元组的行、列下标互换即可。B.存储时只需要各非零元素的三元组信息，不需要其它信息。C.

9、适合于对称矩阵的压缩存储。D.访问元素时不能随机存取。答案：D30.vp对n个顶点的有向图，若所有顶点的出度之和为s,则所有顶点的入度之和为（）0p（l分）A.sB.s-1C.slD.n答案：A31.p二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（）。p（l分）A.可能改变B.一定会改变C.一定不改变D.可能变也可能不变答案：C32.p以下叙述错误的是（）。p（l分）A.树的先根遍历需要借助栈来实现。B.树的层次遍历需要借助队列来实现。C.树的后根遍历与对应二叉树的后根遍历相同。D.树的先根序列与对应二叉树的先根序列相同。答案：C33 .vp若一个图中包含有k个连通分量，若要按照深度

10、优先搜索的方法访问所有顶点，则必须调用（）次深度优先搜索遍历的算法。p（l分）A.1B.kC.k-1D.k+1答案：B34 .p在n个顶点和e条边的无向图的邻接表中，存放表头结点的数组的大小为（）。p（l分）A.nB.n+eC.n+2eD.e答案：A35 .已知一个有向图的边集为。6,。,411,1）6,&0,则由该图产生的一种可能的拓扑序列为（）。（1分）A.a,b,c,d,eB.a,c,d,e,bC.a,c,b,e,dD.a,c,d,b,e答案：A36 .p设计一个判断表达式中左右括号是否配对出现的算法，采用（）数据结构最好。p（l分）A.顺序表B.链表C.队列D.栈答案：D37 .vp给

11、定整数集合（3,5,6,9,12,与之对应的哈夫曼树是（）。（1分）A.AB.BC.CD.D答案：C38下图是一棵（）。imgheight=9,width=245alt=src=7UserFilesImagehsmcd15.png（1分）A.4阶B-树B.4阶B+树C.3阶B-树D.3阶B+树答案：D39 .设输入序列为A,B,C,D,借助一个栈得到的输出序列不可能是（）。（l分）A.ABCDB.ACDBC.DABCD.DCBA答案：C40 .用链表表示线性表的优点是（）。（1分）A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同答案：C41

12、.下列有关线性表的叙述中，正确的是（）。（1分）A.元素之间是线性关系B.线性表中至少有一个元素C.任一元素有且仅有一个直接前趋D.任一元素有且仅有一个直接后继答案：A42 .最好和最坏时间复杂度均为O（nlog2n）且稳定的排序方法是（）。（l分)A.快速排序B.堆排序C.归并排序D.基数排序答案：C43 .vp求单链表中当前结点的后继和前趋的时间复杂度分别是()。(l分)AQ(n)和O(I)BQ和O(I)CQ(I)和0(n)D.O(n)和0(n)答案：C44 .对n个顶点和e条边的有向图，以邻接矩阵存储，则求图中某顶点入度的时间复杂度为()OA)O(n)B)O(e)C)O(n+e)D)0(n2)(1分)A.AB.BC.CD.D答案：A45.若下图表示某广义表，则它是一种()。(1分)A.线性表B.纯表C.再入表D.递归表答案：D46.基数排序中的“基数”可以是()。(1分)A.10B.8C.16D.以上都可以答案：D47 .vpn个顶点的强连通图若只有n条边，则该有向图的形状是()。(l分)A.无回路B.有回路C.环状D.树状答案：C48 .vp在AVL树中，任一结点的（）。（l分）A.左、右子树的高度均相同B.左、右子树高度差的绝对值