2022年数据结构预测卷

2023-03-26 12:00:00
4阅读

本试卷为2022年数据结构预测卷，题目包括：单项选择题。

本卷包括如下题型：

一、单项选择题

数据结构预测卷

一、单项选择题 （共50题，每题2分，共计100分）

（  B  ） 
1、深度为4的完全:二叉树的结点数至少为 。
A、4
B、8
C、13
D、15
（  B  ） 
2、一个算法应该是(  )。
A、程序
B、问题求解步骤的描述
C、要满足五个基本特性
D、A 和C.
（  A  ） 
3、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( A )。
A、CBEFDA
B、FEDCBA
C、CBEDFA
D、不定
（  B  ） 
4、(4分)顺序表中有10个数据元素,若第- 一个元素的存储地址是1000, 则最后-一个元素地址是1036,第5个元素的地址是(B)。
A、1010
B、1016
C、1018
D、1019
（  D  ） 
5、(4分)顺序表便于(D)。
A、插入结点
B、删除结点
C、:按值查找结点
D、按序号查找结点
（  C  ） 
6、(3分)若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反,那么这棵:二叉树- -定是(C) 。
A、结点均无左孩子的二叉树
B、结点均无右孩子的二叉树
C、高度为n的二叉树
D、存在度为2的结点的二叉树
（  B  ） 
7、(6分)计算机算法指的是解决问题的有限运算序列,它必具备输入输出和()等五个特性。
A、可行性、可移植性和可扩充性
B、可行性、确定性和有穷性
C、确定性、有穷性和稳定性
D、易读性、稳定性和安全性
（  A  ） 
8、下列叙述正确的是()
A、线性表是线性结构
B、栈和队列是非线性结构
C、线性链表是非线性结构
D、二叉树是线性结构
（  D  ） 
9、串是()。
A、少于一个字母的序列
B、任意个字母的序列
C、不少于一个字符的序列
D、有限个字符的序列
（  A  ） 
10、当待排序的整数是有序序列时，采用 （ ）方法比较差，达到最坏情况下时间复杂度为O(n2)
A、快速排序
B、冒泡排序
C、归并排序
D、直接选择排序
（  A  ） 
11、假设以行序为主序存储二维数组A=array[1...100,1...100],设每个数组元素占2个存储单元,基地址为10,则LOC[5,5]=
A、818
B、808
C、1010
D、1020
（  B  ） 
12、在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素。
A、n-i
B、n-i+1
C、n-i-1
D、I
（  C  ） 
13、在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。
A、p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B、p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C、q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D、q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
（  C  ） 
14、下面程序段的时间复杂性的量级为（ ）。For(int i=0;i

A、O(m3)
B、O(n2)
C、O(m*n)
D、O(m+n)
（  B  ） 
15、在一个顺序表的表尾插入一个元素的时间复度的量级为（）。
A、O(n)
B、O(1)
C、O(n2)
D、O(log n)
（  D  ） 
16、下面关于二分查找叙述正确的是（ ）
A、表必须有序，表可以顺序方式存储，也可以链表方式存储
B、表必须有序且表中数据必须是整型，实型或字符型
C、表必须有序，而且只能从小到大排序
D、表必须有序，且表只能以顺序方式存储
（  D  ） 
17、假定利用数组A[N]顺序存储一个栈，top表示栈顶指针，已知栈未满，则x入栈时所执行的操作是（ ）。
A、a[--top]=x;
B、a[top--]=x
C、a[++top]=x
D、a[top++]=x
（  A  ） 
18、算法的空间复杂度是指()。
A、算法在执行过程中所需要的计算机存储空间
B、算法所处理的数据量
C、算法程序中的语句或指令条数
D、算法在执行过程中所需要的临时工作单元数
（  A  ） 
19、下列叙述中正确的是()。
A、在栈中,栈顶指针的动态变化决定栈中元素的个数
B、在循环队列中,队尾指针的动态变化决定队列的长度
C、在循环链表中,头指针和链尾指针的动态变化决定链表的长度
D、在线性链表中,头指针和链尾指针的动态变化决定链表的长度
（  B  ） 
20、下列叙述中正确的是()。
A、结点中具有两个指针域的链表一定是二叉链表
B、结点中具有两个指针域的链表可以是线性结构,也可以是非线性结构
C、二叉树只能采用链式存储结构
D、循环链表是非线性结构
（  D  ） 
21、栈在（ ）中应用。
A、递归调用
B、子程序调用
C、表达式求值
D、A，B，C
（  B  ） 
22、设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。
A、2n
B、n
C、n/2
D、n(n-1)
（  B  ） 
23、具有5层结点的AVL树至少有( )个结点。
A、10
B、12
C、15
D、17
（  C  ） 
24、哈希查找的基本思想是根据()来决定元素的存储地址
A、元素的序号
B、元素个数
C、关键字值
D、非关键字属性
（  D  ） 
25、以下关于快速排序的叙述中正确的是( )。
A、快速排序在所有排序方法中为最快,而且所需辅助空间也最少
B、在快速排序中,不可以用队列替代栈
C、快速排序的空间复杂度为O(n)
D、快速排序在待排序的数据随机分布时效率最高
（  C  ） 
26、以下排序方法中,( )不需要进行关键字的比较。
A、快速排序
B、归并排序
C、基数排序
D、堆排序
（  D  ） 
27、非线性结构中的每个结点（ ）。
A、无直接前驱结点
B、无直接后继结点
C、只有一个直接前驱结点和一个直接后继结点
D、可能有多个直接前驱结点和多个直接后继结点
（  A  ） 
28、算法能正确的实现预定功能的特性称为算法的（ ）。
A、正确性
B、易读性
C、健壮性
D、高效性
（  A  ） 
29、下列程序的空间复杂度是( )。For(i=1;i<=n;++i){ for(j=1;j<=m;++j){ c[i][j]=0; }}
A、O(m*n)
B、O(m+n)
C、O(m-n)
D、O(m/n)
（  B  ） 
30、在单链表中设置头结点的作用是( )
A、单链表定义而已
B、为方便链表的操作
C、为双向链表做准备
D、为循环链表做准备
（  D  ） 
31、算法分析不研究()
A、算法的空间复杂度
B、算法的时间复杂度
C、算法的正确性
D、算法的易读性
（  A  ） 
32、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用( )存储方式最节省时间。
A、顺序表
B、单链表
C、双链表
D、单循环链表
（  A  ） 
33、设串长为n,模式串长为m,则KMP算法所需的附加空间为( )。
A、O(m)
B、O(n)
C、O(m*n)
D、O(nlog2m)
（  A  ） 
34、设a,b为一棵二叉树上的两个结点,在中序遍历时,a在b后面的条件是( )。
A、a在b的右方
B、a在b的左方
C、a是b的祖先
D、a是b的子孙
（  B  ） 
35、对20个的元素的线性表进行查找时,第一个元素的命中概率为0.5,其他元素命中概率一样(不考虑查找失败),则平均查找长度为。
A、5.5
B、6
C、7.5
D、8
（  D  ） 
36、某哈希查找表有n条记录,对应的哈希函数具有m个值,则( )
A、n

B、n>m
C、n<=m
D、n>=m
（  D  ） 
37、设一组初始记录关键字序列为(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序的第一趟冒泡排序结束后的结果是( )。
A、F,H,C,D,P,A,M,Q,R,S,Y,X
B、P,A,C,S,Q,D,F,X,R,H,M,Y
C、A,D,C,R,F,Q,M,S,Y,P,H,X
D、H,C,Q,P,A,M,S,R,D,F,X,Y
（  A  ） 
38、引入二叉线索树的目的是( )
A、加快查找结点的前驱和后继
B、为了能在二叉树中方便地进行插入和删除
C、为了能方便地找到双亲
D、使得二叉树地遍历结果唯一
（  C  ） 
39、如果X是二叉中序线索中有一个左孩子的结点,且X不为根,则X的前驱为( )。
A、X的双亲
B、X的右子树中最左的结点
C、X的左子树中最右的结点
D、X的左子树中最右叶结点
（  A  ） 
40、广义表(A,(a,b,c))的表头和表尾是( )。
A、A ((a,b,c))
B、aB,c
C、(a,b,c) A
D、(a,b) c
（  C  ） 
41、在任何情况下,时间复杂度均为O(nlgn) 的不稳定的排序方法是( )。 (2.0分)
A、直接插入
B、快速排序
C、堆排序
D、归并排序
（  A  ） 
42、对长度为4的顺序表进行查找,若查找第一个记录的概率为1/24, 查找第二个记录的概率为1/6, 查找第三个记录的概率为2/3, 查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为( )。 (5.0分)
A、23/8
B、20/8
C、17/8
D、13/8
（  B  ） 
43、在表长为n的链表中进行顺序查找,它的平均查找长度为( )。 (5.0分)
A、n/2
B、(n+1)/2
C、√n+1
D、lg(n+1)-1
（  C  ） 
44、在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。（1分）
A、顺序查找
B、折半查找
C、哈希查找
D、分块查找
（  C  ） 
45、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（）。（1分）
A、O（log2n）
B、O（1）
C、O（n）
D、O（n^2）
（  A  ） 
46、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是（ ）
A、空间复杂性和时间复杂性
B、正确性和简明性
C、可读性和文档性
D、数据复杂性和程序复杂性
（  A  ） 
47、用链式存储的栈，在进栈操作时，将要进栈的结点放在链表的（ ）
A、头部
B、尾 部
C、中间
D、用户指定的位置
（  D  ） 
48、用链式存储的栈，在进行出栈和入栈运算时（ ）
A、仅修改头指针
B、仅修改尾指针
C、头、尾指针都要修改
D、头、尾指针可能都要修改
（  B  ） 
49、用链式存储的栈，在出栈操作之前，需要（ ）
A、判断栈是否满了
B、判断栈是否空了
C、不需判断
D、以上答案都不对
（  C  ） 
50、设有 13 个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（ ）个结点。
A、12
B、13
C、25
D、26
相关标签：
  • 数据结构
上一篇2023年数据结构精选样卷 下一篇数据结构