数据结构真题精选.docx
《数据结构真题精选.docx》由会员分享，可在线阅读，更多相关《数据结构真题精选.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构真题精选
2020年数据结构真题精选
[填空题]
1线性表存放在整型数组A[arrsize]的前elenum个单元中，且递增有序。
编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
参考答案：
本题是在一个递增有序表中插入元素x，基本思路是从有序表的尾部开始依次取元素与x比较，若大于x，此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置，将x插入。
具体算法如下：
[填空题]
2串是由字符组成的，长度为1的串和字符是否相同？
为什么？
参考答案：
虽然串是由字符组成的，但串和字符是两个不同的概念。
串是长度不确定的字符序列，而字符只是一个字符。
即使是长度为1的串也与字符不同。
例如，串"a"和字符'a'就是两个不同的概念，因为在存储时串的结尾通常加上串结束标志'/0'。
[填空题]
3设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为（）
参考答案：
41
[填空题]
4设单循环链表L1，对其遍历的结果是：
x1，x2，x3，…，xn-1，xn。
请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：
x1，x3，…；L2中含有原L1表中序号为偶数的结点且遍历结果为：
…，x4，x2。
参考答案：
算法如下：
[填空题]
5在分块查找方法中，首先查找索引，然后再查找相应的（）。
参考答案：
块
[单项选择题]
6、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（）的起始地址相同。
A. M[2][4]
B. M[3][4]
C. M[3][5]
D. M [4][4]
参考答案：
B
[填空题]
7写出如图所示的树的叶子结点、非终端结点、每个结点的度及树深度。
参考答案：
（1）叶子结点有：
B、D、F、G、H、I、J。
（2）非终端结点有：
A、C、E。
（3）每个结点的度分别是：
A的度为4，C的度为2，E的度为3，其余结点的度为0。
（4）树的深度为3。
[填空题]
8栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。
参考答案：
顺序存储结构和链接存储结构（或顺序栈和链栈）；栈顶指针top=-1和top=NULL；栈顶指针top等于数组的长度和内存无可用空间
[填空题]
9什么样的矩阵叫特殊矩阵？
特殊矩阵压缩存储的基本思想是什么？
参考答案：
我们把相同的元素或零元素在矩阵中的分布有一定的规律的称为特殊矩阵。
压缩存储的原则是：
对多个值相同的元素只存储一次，对零元素甚至不分配存储空间。
[填空题]
10一棵度为2的树与一棵二叉树有什么区别？
参考答案：
度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。
[填空题]
11栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。
参考答案：
后进先出；先进先出；对插入和删除操作限定的位置不同
[填空题]
12在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为（）。
参考答案：
6，9，11，12
[单项选择题]
13、一棵二叉树第五层的结点数最多为（）
A.16
B.15
C.8
D.32
参考答案：
A
[填空题]
14循环队列的引入是为了克服（）。
参考答案：
假溢出
[填空题]
15在一棵度为M树中，度为1的结点数为N1，度为2的结点数为N2，……，度为M的结点数为NM，则该数中含有多少个叶子结点？
有多少个非终端结点？
参考答案：
[填空题]
16已知二叉排序树的左右子树均不为空，则（）上所有结点的值均小于它的根结点值，（）上所有结点的值均大于它的根结点的值。
参考答案：
左子树；右子树
[单项选择题]
17、按照二叉树的定义，具有三个节点的二叉树有（）种
A.3
B.4
C.5
D.6
参考答案：
C
[填空题]
18用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。
参考答案：
O
（1）；O（n）
参考解析：
在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。
[填空题]
19如图所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。
参考答案：
[填空题]
20从有序表（10，16，25，40，61，28，80，93）中依次二分查找40和61元素时，其查找长度分别为（）和（）。
参考答案：
1；3
[填空题]
21一棵深度为h的满二叉树具有如下性质：
第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。
若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，试计算：
整棵树结点数
参考答案：
（mh-1）/（m-1）
更多内容请访问《睦霖题库》微信公众号
[单项选择题]
22、若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。
A.不确定
B.n-i
C.n-i-1
D.n-i+1
参考答案：
D
[填空题]
23如图所示的二叉树，要求：
（1）写出按先序、中序、后序遍历得到的结点序列。
（2）画出该二叉树的后序线索二叉树。
参考答案：
[单项选择题]
24、在表长为n的链表中进行顺序查找，它的平均查找长度为（）
A.ASL＝n
B.ASL＝（n＋1）／2
C.ASL＝√n＋1
D.ASL≈log2（n＋1）－1
参考答案：
B
[填空题]
25二叉树采用二叉树链表的结构存储，设计一个算法求二叉树中指定结点的层数。
参考答案：
[单项选择题]
26、一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）。
A.54321
B.45321
C.43512
D.12345
参考答案：
C
[填空题]
27将如图所示的二叉树转换为树。
参考答案：
第一步，加线。
第二步，抹线。
第三步，调整。
过程如图所示。
[单项选择题]
28、散列表的地址区间为0-17，散列函数为H（K）=Kmod17。
采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。
元素59存放在散列表中的地址是（）。
A.8
B.9
C.10
D.11
参考答案：
D
[单项选择题]
29、在一个具有n个顶点的有向完全图中，所含的边数为（）
A.n
B.n（n-1）
C.n（n-1）/2
D.n（n+1）/2
参考答案：
B
[单项选择题]
30、假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？
（）
A.k-1次
B.k次
C.k+1次
D.k（k+1）/2次
参考答案：
D
[单项选择题]
31、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。
A.栈
B.队列
C.数组
D.线性表
参考答案：
B
[填空题]
32将如图所示的森林转换成二叉树。
参考答案：
[多项选择题]
33、数据结构里，structstudent{charname[20]；charsex[10]；intage；intscore；}；定义结构体后，定义变量、数组赋值正确的是（）。
A.structstudents={"张三"，"男"，18，100}；
B.structstudentstu[3]={{"张三"，"男"，18，100}，{"李四"，"男"，19，90}，{"王五"，"男"，23，97}}；
C.structstudents={"李四"；"女"；18；100}；
D.structstudentstu[3]={{"张三"，18，"男"，100}，{"李四"，19，"男"，90}，{"王五"，23，"男"，97}}；
参考答案：
A,B
[单项选择题]
34、二叉查找树的查找效率与二叉树的树型有关，在（）时其查找效率最低。
A.结点太多
B.完全二叉树
C.呈单枝树
D.结点太复杂
参考答案：
B
[单项选择题]
35、一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（）。
A.4321
B.1234
C.1432
D.3241
参考答案：
B
[单项选择题]
36、无向图G＝（V，A），其中V＝｛a，b，c，d，e｝，A={，，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}对该图进行扑拓排序，下面序列中（）不是拓扑序列。
A.adcbe
B.dabce
C.abdce
D.abcde
参考答案：
D
[单项选择题]
37、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。
A. 4
B. 5
C. 6
D. 7
参考答案：
C
[单项选择题]
38、数据结构里，定义名称为plan结构体，其有5个元素的结构体数组的定义方式是（）。
A.structplan数组名[5]；
B.structplan数组名[10]；
C.planstruct数组名[5]；
D.plan数组名[5]；
参考答案：
A
[单项选择题]
39、对包含n个元素的哈希表进行查找，平均查找长度为（）
A.O（log2n）
B.O（n）
C.O（nlog2n）
D.不直接依赖于n
参考答案：
D
[单项选择题]
40、设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。
为这两个栈分配空间的最佳方案是（）。
A.S1的栈底位置为0，S2的栈底位置为n-1
B.S1的栈底位置为0，S2的栈底位置为n/2
C.S1的栈底位置为0，S2的栈底位置为n
D.S1的栈底位置为0，S2的栈底位置为1
参考答案：
A
参考解析：
两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。
[单项选择题]
41、当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）
A.必定快
B.不一定
C.在大部分情况下要快
D.取决于表递增还是递减
参考答案：
B
[单项选择题]
42、在一棵二叉树上第4层的结点数最多为（）。
A. 2
B. 4
C. 6
D. 8
参考答案：
D
[单项选择题]
43、数据结构里，下列选项中是结构体指针变量在使用时的符号的是（）。
A.->
B..
C.->>
D.#
参考答案：
A
[单项选择题]
44、下面关于二分查找的叙述正确的是（）
A.表必须有序，表可以顺序方式存储，也可以链表方式存储
B.表必须有序且表中数据必须是整型，实型或字符型
C.表必须有序，而且只能从小到大排列
D.表必须有序，且表只能以顺序方式存储
参考答案：
D
[判断题]
45、栈可以作为实现过程调用的一种数据结构。
参考答案：
对
[单项选择题]
46、设n，m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。
A. n在m右方
B. n在m左方
C. n是m的祖先
D. n是m的子孙
参考答案：
B
[填空题]
47什么叫动态查找？
什么叫静态查找？
什么样的存储结构适宜于进行静态查找？
什么样的存储结构适宜于进行动态查找？
参考答案：
静态查找是指只在数据元素集合中查找是否存在关键字等于某个给定关键字的数据元素。
动态查找除包括静态查找的要求外，还包括在查找过程中同时插入数据元素集合中不存在的数据元素，或者从数据元素集合中删除已存在的某个数据元素的要求。
[单项选择题]
48、数据结构里，下列选项中是定义结构体类型的指针变量的格式的是（）。
A.struct结构名指针变量名
B.struct结构名变量名
C.static结构名指针变量名
D.struct指针变量名结构名
参考答案：
A
[单项选择题]
49、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）
A.必定快
B.不一定
C.在大部分情况下要快
D.取决于表递增还是递减
参考答案：
C
[单项选择题]
50、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）
A.希尔排序
B.起泡排序
C.插入排序
D.选择排序
参考答案：
C
[判断题]
51、在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。
参考答案：
错
[单项选择题]
52、从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（）。
A.x=top；top=top->next；
B.x=top->data；
C.top=top->next；x=top->data；
D.x=top->data；top=top->next；
参考答案：
D
[填空题]
53改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。
参考答案：
[判断题]
54、空串与空格串是相同的。
参考答案：
错
[判断题]
55、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
参考答案：
对
[判断题]
56、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
参考答案：
对
[判断题]
57、链队列的出队操作总是需要修改尾指针。
参考答案：
错
[单项选择题]
58、元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。
A.18，16，14，20
B.20，14，16，18
C.18，16，20，14
D.14，20，18，16
参考答案：
C
[单项选择题]
59、二叉排序树的查找效率与二叉树的（）有关。
A.高度
B.结点的多少
C.树型
D.结点的位置
参考答案：
C
[填空题]
60在n个结点的单链表中要删除已知结点*p，需找到它的（），其时间复杂度为（）。
参考答案：
前驱结点的地址O（n）
升级会员 