2017年济南大学信息科学与工程学院847计算机学科专业基础综合之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 下列程常段的时间复杂度是（ ）
A.
B.
C.
D.
【答案】C
【解析】外部循环的退出条件是
内部循环的退出条件是而对于k ，每次循环都执行所以循环次数为对于j ，每次循环都执行所以每次循环次数为n 次。所以此程序段的时间复杂度为O 即选C 。
2． 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a , b , c , d , e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。
A.b ，a , c , d ，e
B.d ，b , a , c ，e
C.d ，b , c , a ，e
D.e ，c ，b , a ，d
【答案】C
【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。
假设L 代表从左端入队，R 代表从右端入队，出队都是从左端L 出。四个选项所给序列的进队操作序列分别为：
选项 A. aL （或 aR ）, bL, cR, dR, eR 选项 B. aL （或 aR ）, bL, cR，dL , eR 选项C. 不可能出现 选项 D. aL （或 aR ）, bL, cL, dR, eL
3． —个具有1025个结点的二叉树的高h 为（ ）。
A.11
B.10
C.11至1025之间
D.10至1024之间
【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
4． 下列四个序列中，哪一个是堆（ ）？
A.75，65，30，15，25，45，20，10
B.75，65，45，10，30，25，20，15
C.75，45，65，30，15，25，20，10
D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义：
n 个关键字序列
且
且
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆；
大根堆：满足第②种情况的堆。
根据堆定义即可得出答案。
5． 已知串其Next 数组值为（ ）。
A.0123
B.1123
C.1231
D.1211
【答案】A
【解析】KMP 算法的next 数组建立的原则
6． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面
按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。
7． 下列介质访问控制方法中，可能发生冲突的是（ ）
A.CDMA
B.CSMA
C.TDM AC
D.FDMA
【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 。
8． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希（Hash ）表
B. 广度优先搜索网
C. 前序（根）遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
9． 若一个栈以向量
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
【答案】C
【解析】题中初始栈顶指针top 为n+1, 而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
10．元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作：