当前位置:问答库>考研试题

2017年中国传媒大学新媒体研究院821数据结构与计算机网络考研强化模拟题

  摘要

一、填空题

1. 在n 个顶点的非空无向图中,最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边,都是孤立的顶点时,有n 个连通分量。

2. 栈是_____的线性表,其运算遵循_____的原则。

;后进先出 【答案】操作受限(或限定仅在表尾进行插入和删除操作)

3. 在有n 个顶点的有向图中,每个顶点的度最大可达。

【答案】2(n-l )

【解析】当有向图为完全连通图时每个顶点的度达到最大,出度入度均为n-1。

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

【答案】2(N-1)

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

5. 执行顺序查找时,存储方式可以是_____,折半查找时,要求线性表_____,分块查找时要求线性表_____,而哈希表的查找,要求线性表的存储方式是_____。

【答案】顺序存储或链式存储;顺序存储且有序;块内顺序存储,块间有序;散列存储

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

【答案】m/2

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

7. 无用单元是指_____,例_____

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

8. 在循环队列中,队列长度为n ,存储位置从0到,

【答案】

编号,以rear 指示实际的队尾元素,现

要在此队列中插入一个新元素,新元素的位置是( )。

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

【答案】

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

10.高度为h 的堆中,最多有_____元素,最少有_____个元素。

【答案】

当最后一层只有

【解析】当这个堆构成的是满二叉树时,元素的个数最多,

元素个数为一个元素时,此时堆的元素个数最少,元素个数为

11

.=_____

【答案】5

12.设数组

数组中任一元素

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

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

(1)存放该数组至少需要的单元数是_____;

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

第8列有9个元素,共占个单元。按列存储时,

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

个单元数。

个字节,因此至少需要的起始地址为

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

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

的起始地址是_____。

二、选择题

13.已知关键字序列5, 8, 12, 19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后的小根堆是( )。

A.3, 5,12,8, 28,20, 15,22,19 B.3, 5, 12, 19, 20, 15, 22, 8, 28

C.3, 8, 12, 5, 20, 15, 22, 28, 19 D.3, 12, 5, 8, 28, 20, 15, 22, 19 【答案】A

【解析】在堆中插入或删除一个元素后,将不再满足堆的性质。为了使其成为新堆,在输出堆顶元素后,需要调整剩余元素。具体过程如图(1)〜(5)所示,(1)为原堆,(2)为插入3后,(3)、(4)为调整过程,(5)为调整后的小根堆。