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

一、填空题

1． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】2（N-1）

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。

2． 设二维数组A 的行和列的下标范围分别为

【答案】

当其值为

和每个元素占2个单元，按行优先顺处的元素为_____。

序存储，第一个元素的存储起始位置为b ，则存储位置为

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。

3． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

4． 设数组

数组中任一元素

均占内存48个二进制位，从首地址2000开始

连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是_____；

（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要

第8列有9个元素，共占

因为每个元素占内存48个二进制位，即6个字节。故总

个单元数。

个字节，因此至少需要

个单元数。由题知，每个元素占3

个字节，因为主内存字长为16位，即2个字节，所以至少需要

的起始地址是_____。

个单元。按列存储时，的起始地址为

5． 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的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

6． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

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

7． 空格串是指_____，其长度等于_____。

【答案】由空格字符（

值32）所组成的字符串；空格个数

8． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

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

【答案】15

【解析】当时，而

，时，

10．假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

；

（“图有回路”）

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

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为

二、判断题

11．广义表

【答案】×

【解析】长度为1。因为只含一个元素即子表

12．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）

【答案】√

【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。

13．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第的最多结点数为

【答案】√

【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为

层全满时，

此时从根结点到第

层具有最大的结点数为

14．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环（回路）。

【答案】√

【解析】采用深度优先搜索算法主要是通过设置标志位可以判断出一个有向图中是否有环。采用拓扑排序算法，如果能够构成一个拓扑排序，则有向图中没有环，否则，有向图中有环。

15．强连通分量是无向图的极大强连通子图。（ ）

【答案】×

【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。

16．倒排文件的目的是为了多关键字查找。（ ）

【答案】√

【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为：多重表文件和倒排文件。

余下的

个结点在第k 层的任一位置上。（ ） 的长度是4。（ ）

层具有