2017年闽南师范大学计算机学院916计算机专业基础之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
2． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
3． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
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．
【答案】5
=_____
6． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
7． 顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
8． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注：（1）图的顶点号从0开始计；
（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；
（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。
）
.
【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
；
（“图有回路”）
9． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
10．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
二、选择题
11．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
。
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：28比72小，不交换； 第二次比较：28比5大，交换，此时为第三次比较：16比28小，不交换； 第四次比较：32比28大，交换，此时为第五次比较：28比2大，交换，此时为第六次比较：28比12大，不交换； 第七次比较：28比60小，交换，此时为
一次划分结束。
12．浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）
。若有两个数
则用浮点加法计算X+Y的最终结果是（ ）。
A.001111100010
B.001110100010 C.010000010001 D. 发生溢出 【答案】D
【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步。X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐。因此将Y 对阶后得到：Y=
然后将尾数相加，得到尾数之和为：34/32。因为这
是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在-8〜+7之间。而阶码本身等于7, 再加1就等于8。因此，最终结果发生