一、填空题

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

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

2． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

3．

给定一组数据以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

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

【答案】2(N-1)

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

阵至少有2(N-1)个非零元素。

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

【答案】查找顶点的邻接点的过程；0(n+e); 0(n+e); 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

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

【答案】9174；8788

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

则它的存储地址为

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

7． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。

【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

8． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

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

【答案】9

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

10．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

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

【答案】n (n-l )/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n (n-l )。又因为每

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

条边重复出现两次，所有无向完全图的边数为n (n-l )/2。

12．在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

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

【答案】

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

所以

14．VSAM (虚拟存储存取方法)文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

15．文件由_____组成；记录由_____组成。

【答案】记录；数据项

二、判断题

16．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为

【答案】

【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是

17．若一个广义表的表头为空表，则此广义表亦为空表。( )

【答案】×

【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。

18．数组不适合作为任何二叉树的存储结构。( )

【答案】×

【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构是高效率的(存储密度大)。

19．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。( )

【答案】√

【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。

( )。