2018年云南大学软件学院904计算机程序设计[专业硕士]之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】O(m＋n)
2． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
3． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
4． 已知如下程序段:
语句1执行的时间复杂度为_____:语句2执行的时间复杂度为_____:语句3执行的时间复杂度为_____:语句4执行的时间复杂度为_____。
【答案】(1)n＋1 (2)n
(3)n(n＋3)/2 (4)n(n＋l)/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋(n＋l) 加起来就是n(n＋3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n(n＋l)/2。
5． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。
6． 阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
二、判断题
7． —个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）
【答案】×
【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序， 这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则 称这种排序算法是稳定的；否则称为不稳定的。
8． 设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为O(i)。（ ）
【答案】 ×
【解析】由于该栈采用顺序存储结构，时间复杂度应该为O(1)。
9． 栈和队列都是限制存取点的线性结构。（ ）
【答案】 √
10．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
11．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第k ﹣1层具有的最多结点数为余下的
【答案】 √
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为k ﹣1层全满时，此时从根结点到第k ﹣1层具有最大的结点数为
12．一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）
【答案】 √
【解析】树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。
个结点在第k 层的任一位置上。（ ）
三、单项选择题
13．假定有4个整数用8位补码分别表示为
放在一个8位寄存器中, 则下列运算会发生溢出的是（ ）。
A. B. C. D. 【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为数
,
, 在4个选项中, 只有
。现在4个整数都是负
, 结果溢出, 其余3个算式结果
。若将运算结果存
都未超过127, 不发生溢出
14．在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）.
A. 数据链路层