2017年杭州电子科技大学数字媒体与艺术设计学院851数据结构考研冲刺密押题
● 摘要
一、填空题
1． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
2． 表达式
【答案】
3． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
4． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
5． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
6． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为
7． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量
第 2 页，共 56 页 值32）所组成的字符串；空格个数 的后缀表达式是_____。
移动数据元素的问题。
8． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
9． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
10．在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
11．按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
12．用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。 【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
二、选择题
13．已知循环队列存储在一维数组
rear 的值分别是（ ）。
A.0, 0
B.0, n-1
C.n-1, 0
D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
第 3 页，共 56 页 中，且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和
14．在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是（ ）。
A. 可变分配，全局置换
B. 可变分配，局部置换
C. 固定分配，全局置换
D. 固定分配，局部置换
【答案】
【解析】分配和置换策略有下面三个组合：①固定分配、局部置换；②可变分配、全局置换；
，或根据程序员、③可变分配、局部置换。固定分配是指基于进程的类型（交互型或批处理型等）
程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变，采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n 个页面中选出一个页换出，然后再调入一页，才能保证分配给该进程的内存空间不变，因此不能有固定分配，全局置换组合。
15．n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
16．用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9
【答案】A
6条边【解析】一共5个结点
17．下列存储器中，在工作期间需要周期性刷新的是（ ）。
A.SRAM
B.SDRAM
C.ROM
D.FLASH
【答案】B
电容上的电荷一般只能维持 【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，因此即使电源不掉电，信息也会自动消失。为此，每隔一定时间必须刷新。
18．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
D.-3
【答案】B
；负数的补码和原码的转化是：【解析】能表示的最小整数一定是负数，符号位占用1个“1”
原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码
第 4 页，共 56 页
相关内容
相关标签