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

一、填空题

1． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

2． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

3． 设数组

数组中任一元素均占内存48个二进制位，从首地址2000开始

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

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

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

第8列有9个元素，共占

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

个单元数。

个字节，因此至少需要

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

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

的起始地址是_____。

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

4． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）

【答案】93

在B

【解析】对于上三角矩阵，将代入得93。

5． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

6． 在循环队列中，队列长度为n ，存储位置从0到，

【答案】

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

要在此队列中插入一个新元素，新元素的位置是（ ）。

7． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

的元素，如该元素已在哈希表中，报告出错。

【答案】

【解析】本题是在哈希表ht[]中插入值为

8． 在单链表中设置头结点的作用是_____。

【答案】方便运算

9． 完善算法：求KMP 算法.next 数组。

END ； 【答案】 10．中缀式运算结果为_____。

【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

对应的前缀式为_____，若

则后缀式

的

二、选择题

11．已知小根堆为8，15，10，21，34， 16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。

A.1 B.2

C.3 D.4

【答案】C

【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15, 所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调 整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。

12．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。

A. 机械特性 B. 功能特性 C. 过程特性 D. 电气特性 【答案】C 。

【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。

13．下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。

A. 仅1 B. 仅2 C. 仅 1，2 D. 仅 2, 3 【答案】C

【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响

14．在有向图的邻接表存储结构中，顶点V 在链表中出现的次数是（ ）。

A. 顶点V 的度 B. 顶点V 的出度 C. 顶点V 的入度 D. 依附于顶点V 的边数 【答案】B

【解析】在有向图中，第j 个链表中的结点个数只是顶点Vi 的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。