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

一、填空题

1． 设数组

数组中任一元素

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

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

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

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

数组的元素个数为需要

第8列有9个元素，共占

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

个单元数。

个字节，因此至少需要

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

队头和队尾指针分别为front 和rear , 则此循

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

的起始地址是_____。

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

2． 已知一循环队列的存储空间为其中环队列判满的条件是（ ）

【答案】

3． 实现字符串拷贝的函数strcpy 为：

【答案】

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

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

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

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

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。 6． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

7． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4; 2

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

【答案】2（N-1）

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

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

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储 10．假定查找有序表

【答案】37/12

【解析】折半查找时每个的次数如表所示：

表

平均查找次数为

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____

二、选择题

11．以太网交换机进行转发决策时使用的PDU 地址是（ ）。

A. 目的物理地址 B. 目的IP 地址 C. 源物理地址 D. 源IP 地址 【答案】A

【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息（源结点的MAC 地址、目的结点的MAC 地址）, 就会得到与每个端口所连接结点的MAC 地址, 并在交换机的内部建立一个“端口-MAC 地址”映射表。建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为A 。

12．下列排序算法中，占用辅助空间最多的是（ ）。

A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 【答案】A

【解析】

归并排序的辅助空间为

快速排序所占用的辅助空间为

堆排序所占

用的辅助空间为

13．若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度

【答案】C

【解析】最快查找一次成功，最慢查找n

次成功。平均查找次数为

那么

14．浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）

。若有两个数

则用浮点加法计算X+Y的最终结果是（ ）。

A.001111100010

B.001110100010 C.010000010001 D. 发生溢出 【答案】D

【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步。X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐。因此将Y 对阶后得到：Y=

然后将尾数相加，得到尾数之和为：34/32。因为这

是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在-8〜+7之间。而阶码本身等于7, 再加1就等于8。因此，最终结果发生溢出。

15．图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）

A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图

D.G 所有顶点的度的总和为n （n-1） 【答案】A

【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量

为（ ）。