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

一、填空题

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

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

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

2． 设有两个算法在同一机器上运行，其执行时闻分别为_____。

【答案】15

【解析】当时，而

，时，

3． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。

4． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n

个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）若

是边，则

的值等于_____，若

不是边，则

的值是一个比任

何边的权，矩阵的对角线元素全为0。

（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若

【答案】（1）

已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边

（3）算法结束时，相邻矩阵中。

5． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度

【答案】完全；只有一个叶结点的二叉树

要使前者快于后者，n 至少为

6． 求最短路径的Dijkstra 算法的时间复杂度为_____。

【答案】

7． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

8． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

9． 模式串

的next 函数值序列为_____。

的存储地址为_____；若以列序为主序顺序存储，则元素

的存储地址

【答案】01122312

10．数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

11．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

12．若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】n （n-l ）/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。

13．—棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

14．线性表

【答案】（n －1）/2

用数组表示，假定删除表中任一元素的概率相同，则删除一个元素

平均需要移动元素的个数是_____。

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为

15．外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

二、选择题

16．假定变量i 、f 和d 的数据类型分为int 、float 和double （int 用补码表不，float 和double 分，已知别用IEEE754单精度和双精度浮点数格式表示）

位机器中执行下列关系表达式，则结果为“真”的是（ ）。

A. 仅I 和II B. 仅I 和III C. 仅II 和III D. 仅III 和IV 【答案】B

II 中，f 的数据类型从float 【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。转换为int 时，小数点后面4位会丢失，故II 的结果不为真；IV 中，d+f时需要对阶，对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故IV 的结果也不为真。I 和II 进行数据类型的转换的时候并没有改变其值。

17．假定编译器规定int 和short 类型长度分别为32位和16位，执行下列C

语言语句

得到y 的机器数为（ ）。

【答案】B 。

【解析】X 和y 均为无符号数，其中X 为16位，y 为32位，将16位无符号数转化成32位无符号数，前面要补零。因为所以

18．从堆中删除一个元素的时间复杂度为（ ）。

若在32