2022年数据结构测试卷
本试卷为2022年数据结构测试卷，题目包括：单项选择题。
本卷包括如下题型：
数据结构测试卷
一、单项选择题 （共50题，每题2分，共计100分）
（ D ）
1、使用二叉线索树的目的是便于(D)。
（ B ）
2、链表不具有的特点是( B )
（ C ）
3、当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( C )
（ B ）
4、一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是( B )
（ B ）
5、(4分)若构造一颗具有n个结点的二叉排序树,在最坏情况下,其深度为(B)。
（ A ）
6、下列选项中,可以唯一确定-棵二叉树的两种遍历序列是(A)。
（ C ）
7、下列线性表中,能使用二分查找的是(C)。
（ A ）
8、(10分)有一组记录的关键序列为(46,79,56,38,40,84). 利用快速排序的方法,以第一一个纪录为基准得到的一 趟排序结果为(A)。
（ A ）
9、以下说法正确的是( )。
（ C ）
10、一棵具有 1028 个结点的二叉树的深度 h 为( )。
（ D ）
11、判断顺序栈（最多结点数为m）为栈满的条件是
（ A ）
12、如果含有n个顶点的图形成一个环,则它有( )棵生成树
（ A ）
13、串是一种特殊的线性表,其特殊性体现在
（ C ）
14、二叉树是非线性数据结构，所以
（ B ）
15、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是( )
（ B ）
16、一个递归算法必须包括（ ）。
（ B ）
17、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。
（ C ）
18、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。
（ C ）
19、下列关于线性链表的叙述中,正确的是()。
（ A ）
20、下列排序法中,每经过一次元素的交换会产生新的逆序的是()。
（ D ）
21、设顺序表的长度为 16,对该表进行简单插入排序。在最坏情况下需要的比较次数为()
（ D ）
22、设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。。
（ C ）
23、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。
（ D ）
24、适合折半查找的数据是()
（ B ）
25、下述排序算法中，稳定的是
（ A ）
26、顺序表存取数据操作的时间复杂度为( )。 (3.0分)
（ D ）
27、对于一个具有N个顶点的无向图,若采用邻接矩阵表示,则该矩阵大小是( )
（ B ）
28、若需要时间复杂度在O(nlog2n)内,对整数数组进行排序,且要求排序方法是稳定的,则可选择的排序方法是 ( ) 。
（ A ）
29、抽象数据类型的三个组成部分分别为( )。
（ A ）
30、队列的插入操作是在( )。
（ A ）
31、一个顺序栈S,空栈时top的初始值为0,其栈顶指针为top,则将元素e入栈的操作是( )。
（ B ）
32、栈的插入和删除操作在( )。
（ A ）
33、下面关于稀疏矩阵的快速转秩算法说法正确的是( )。
（ B ）
34、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作,则对于S=’Beijing&Nanjing’,SUBSTR(S,4,5)=( )。
（ A ）
35、以下有关广义表的表述中,正确的是( )
（ C ）
36、设某棵二叉树中有2000个结点,则该二叉树的最小高度为 ( )。
（ A ）
37、设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为( )。
（ D ）
38、设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为( )。
（ A ）
39、设二叉排序树上有n个结点,则在二叉排序树上查找结点的最多的时间复杂度()
（ A ）
40、串是一种特殊的线性表,特殊性表现在( )
（ D ）
41、设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>},假设每条边长度为1,则1点到4点的最短距离为()
（ D ）
42、设一棵4叉树中有N1个度数为1的结点,N2个度数为2的结点,……,N4个度数为4的结点,则该树中共有( )个叶子结点。
（ C ）
43、设F是一个森林,B是由F变换得到二叉树。若F中有n个非终端(叶子)结点,则B中右指针域为空的结点有( )个。
（ D ）
44、评价一个算法时间性能的主要标准是( )。 (5.0分)
（ C ）
45、当采用分块查找时,数据的组织方式为( )。 (5.0分)
（ C ）
46、一棵深度为k的平衡二叉树,其每个非终端结点的平衡因子均为0,则该平衡二叉树共有( )个结点。 (5.0分)
（ A ）
47、链表适用于( )。 (5.0分)
（ C ）
48、向一个队首指针为 front、队尾指针为 rear 的链队列中插入一个 s 所指结点时，其操作步骤为（ ）
（ A ）
49、已知一个有向图的边集为{,,,,,}， 则由该图产生的一种可能的拓扑序列为（ ）
（ D ）
50、在有向图 G 的拓扑序列中，若顶点 Vi 在顶点Vj 之前，则下列情形不可能出现的是（ ）
相关标签：
- 数据结构