2018年闽南师范大学粒计算重点实验室916计算机专业基础之数据结构考研核心题库
● 摘要
一、填空题
1． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
2． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈
【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
3． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
4． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为_____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
5． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)
6． 高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
。当最后一层只有
。 【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为
二、单项选择题
7． 下列选项中, 会导致用户进程从态切换到内核的操作是（ ）
Ⅰ. 整数除以零
Ⅱ.sin （ ）函数调用
Ⅲ.read 系统调用
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。
8． 在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）.
A.12kbps
B.24kbps
C.48kbps
D.96kbps
【答案】B
【解析】首先要根据信道有无噪声来确定是否采用奈奎斯特定理. 解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率＝2×3×log2(4×4) ＝6×4＝24kbps.
9． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。
A.24, 10, 5和24, 10, 7
B.24, 10, 5和24, 12, 7
C.24, 10, 10和24, 14, 11
D.24, 10, 5和24, 14, 6
【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。
10．某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ） A. B.
C.
D.
【答案】A
偏移量有32-8-4-4=16位 【解析】寄存器个数
指令编址方式如下所示:
16位补码取值范围为 , 所以偏移量取值范围为
11．用直接插入排序方法对下面4个序列进行排序(由小到大) ，元素比较次数最少的是（ ）。
A.94，32，40，90，80，46，21，69
B.32，40，21，46，69，94，90，80
C.21，32，46，40，80，69，90，94
D.90，69，80，46，21，32，94，40
【答案】C
12．下列有关浮点数加减运算的叙述中, 正确的是（ ）。
Ⅰ. 对阶操作不会引起阶码上溢或下溢
Ⅱ. 右规和尾数舍入都可能引起阶码上溢
Ⅲ. 左规时可能引起阶码下溢
Ⅳ. 尾数溢出时结果不一定溢出
A. 仅Ⅱ Ⅲ
B. 仅Ⅰ Ⅱ Ⅳ
C. 仅Ⅰ Ⅲ Ⅳ
D. Ⅰ Ⅱ ⅢⅣ
【答案】D
【解析】浮点数的加减运算步骤包括:①对阶, 使两个操作数的小数点位置对齐, 阶码小的尾数右移, 可能产生溢出, 但是阶码不会溢出; ②尾数求和, 将对阶后的尾数按定点数加(减) 运算规则运算; ③规格化, 包括左规和右规, 左规时阶码减少, 可能出现阶码下溢, 而右规时, 阶码增加可能出现阶码上溢; ④舍入, 该过程可能需要右规调整, 因此可能出现阶码上溢; ⑤溢出判断, 浮点数的溢出与否是由阶码的符号决定的, 而不是由尾数溢出判断的, 因此尾数溢出时结果不一定溢出。因此Ⅰ Ⅱ Ⅲ Ⅳ均正确。
13．将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N －1
C.2N
D.N －1