当前位置：问答库＞考研试题

一、填空题

1． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称

增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

2． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。 【答案】

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，

所以

3． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

4． 二进制地址为011011110000，大小为和块的伙伴地址分别为：_____

【答案】011011110100；011011100000

011011110000是块的起始地址，【解析】大小分别为式如下：

当大小为4时，起始地址

为当大小为16时，起始地址为

：

5． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

6． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

和其伙伴块的起始地址计算公

7． 在哈希函数中，P 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

8． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

9． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的

数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

②执行程序，f （6，4）=_____。

【答案】①1; 1; f （m ，n －1）; n ②9

10．已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

二、判断题

11．二维以上的数组其实是一种特殊的广义表。（ ）

【答案】√

【解析】广义表是线性表的推广。广义表中的元素还有可能是广义表。对于维数大于二的数组，它在某一维上的元素还是数组。符合广义表的定义，因此二维以上的数组其实是一种特殊的广义表。

12．顺序存储结构的主要缺点是不利于插入或删除操作。（ ） 【答案】

【解析】因为顺序表的插入删除会移动大量的元素。

13．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ） 【答案】

【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。

14．外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）

【答案】×

【解析】外部排序方法：按可用内存大小，将外存上含n 个记录的文件分成若干长度为z 的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串（run ）。对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序（产生初始归并段）所需的时间外 存信息读写的时间内部归并所需的时间

15．由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）

【答案】×

【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。并且序列在基本有序的情况下，直接插入排序也会提高。

16．设栈采用顺序存储结构。若已有个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为（ ） 【答案】

【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。

17．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 【答案】

【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。

18．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ）

【答案】√

【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。