2017年暨南大学信息科学技术学院830数据结构考研仿真模拟题
● 摘要
一、填空题
1． 假定查找有序表
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
2． 关键码序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。
【答案】（Q ，A ，C ，S ，Q ，D ，F ，×，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
3． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
（3）（4）（5）
4． 设广义表
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针 则
是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
5． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
6． 实现字符串拷贝的函数strcpy 为：
【答案】
7． 在单链表中设置头结点的作用是_____。
【答案】方便运算
8． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
9． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
10．外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
二、选择题
11．假定编译器规定int 和short 类型长度分别为32位和16位，执行下列C
语言语句
得到y 的机器数为（ ）。
【答案】B 。
【解析】X 和y 均为无符号数，其中X 为16位，y 为32位，将16位无符号数转化成32位 无符号数，前面要补零。因为所以
12．下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务 B. 高响应比优先 C. 时间片轮转
D. 非抢占式短任务优先 【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时 间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个? 我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到 调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有尚响应比优先算法。
13．下列选项中，不会引起指令流水线阻塞的是（ ）。
A. 数据旁路（转发） B. 数据相关 C. 条件转移 D. 资源冲突 【答案】A
【解析】由于采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：
①结构相关，又称资源相关； ②数据相关；
③控制相关，又称指令相关，主要由转移指令引起。
14．中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。
A. 程序计数器 B. 程序状态字寄存器 C. 通用数据寄存器