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

一、填空题

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

【答案】2（N-1）

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

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

【答案】由空格字符（

3． 设数组

值32）所组成的字符串；空格个数 数组中任一元素

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

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

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

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

数组的元素个数为需要

第8列有9个元素，共占

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

个单元数。

个字节，因此至少需要

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

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

的起始地址是_____。

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

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

【答案】4; 2

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

【答案】

6． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

7． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。

【答案】视哨。

8． 设广义表

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监

则 是_____tail（L ）是_____；L 的长度是_____；深度是_____。

；；2；2 【答案】（ ）（（ ））

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

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

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

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

10．二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

二、选择题

11．下列有关RAM 和ROM 的叙述中，正确的是（ ）。

I.RAM 是易失性存储器，ROM 是非易失性存储器 II.RAM 和ROM 都采用随机存取方式进行信息访问 III.RAM 和ROM 都可用作Cache IV.RAM 和ROM 都需要进行刷新 A. 仅I 和II B. 仅II 和III C. 仅 I 、II 和IV

D. 仅II 、III 和IV 【答案】A

RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性），同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）区别在于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。

12．下列选项中，不能改善磁盘设备

A. 重排

请求次序

B. 在一个磁盘上设置多个分区 C. 预读和滞后写

D. 优化文件物理块的分布 【答案】B 。 【解析】磁盘的一个瓶颈。“重排

性能主要是指其读写速度。相对而言，磁盘的

性能是计算机性能提高

请求次序”可以优化磁臂调度的算法，减少读写时间，故正确；“预读和滞

性能，

性能的是（ ）。

后写”是利用内存作为磁盘的缓存，使得对磁盘的访问变为对内存的访问，也可以在总体上提高其性能；“优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间，也可以提高磁盘而磁盘分区仅在磁盘空间的组织上进行划分，

对磁盘性能的提升没有什么帮助，是不能改善磁盘设备性能的，故答案为B 。

13．下列选项中，用于设备和控制器（’接口）之间互连的接口标准是（ ）

A.PCI B.USB C.AGP

D.PCI-Express 【答案】B 【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。

14．采用简单选择排序，比较次数与移动次数分别为（ ）。

【答案】C

【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比 较的次数为

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

语言语句

得到y 的机器数为（ ）。