2017年北京联合大学软件工程803软件基础之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 线性表
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为 2
．
求REPLACE （S ，V , m ）=_____。
【答案】
其中
队头和队尾指针分别为front 和rear , 则此循
3． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
4． 阅读下列程序说明和裎序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。
存放还没有转换过的结点，它的栈顶指针为
。
已
知
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
（1）
{（2）
If （ （3） ）
}
}}
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
5． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
6． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和
每个元素占2个单元，按行优先顺处的元素为_____。
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。 7． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则
的地址为
8． 中缀式运算结果为_____。
【答案】
将
代入得33。 对应的前缀式为_____，若
则后缀式
则
的地址为
，）则 的地址为_____。
若
的
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
9． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
10．设有两个算法在同一机器上运行，其执行时闻分别为_____。
【答案】15 【解析】当
时，
而
，
时，
要使前者快于后者，n 至少为
二、选择题
11．在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
12．若
A.x+y B.-x+y C.x-y D.-x-y
【答案】C
则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
【解析】8位定点补码能表示的数的范围为：码能表示的数的范围，会发生溢出
13．静态链表中指针表示的是（ ）。
A. 下一元素的地址 B. 内存储器的地址 C. 下一元素在数组中的位置 D. 左链或右链指向的元素的地址 【答案】C
【解析】静态链表的一般结构为：
A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
14．有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612 B.453126 C.346521 D.234156 【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。
15．单处理机系统中，可并行的是（ ）。
I. 进程与进程 II. 处理机与设备 III. 处理机与通道 IV . 设备与设备 A.I 、II 和III B.I 、II 和IV C.I 、III 和IV