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

一、单项选择题

1． 线性表的顺序存储结构是一种（ ）。

A. 随机存取的存储结构

B. 顺序存取的存储结构

C. 索引存取的存储结构

D.Hash 存取的存储结构

【答案】A

【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。

2． 假设栈初始为空, 将中缀表达式

当扫描到f 时, 栈中的元素依次是（ ） A.

B.

C.

D.

【答案】B

【解析】中缀表达式转后缀表达式遵循以下原则:

(1)遇到操作数, 直接输出;

(2)栈为空时, 遇到运算符, 入栈;

(3)遇到左括号, 将其入栈;

(4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出;

(5)遇到其他运算符

符入栈;

(6)最终将栈中的元素依次出桟, 输出。

所以扫描到‟/‟, 入栈„描到‟+‟, 由于‟+‟优先级比‟/'低, 所以将‟/‟弹出, ‟+‟入栈; 扫描到‟*,, 优先级比‟+‟高, 入栈; 扫描到‟(„, 入栈; 扫描到‟一„, 将栈中优先级更高的‟*‟弹出, „一, 入栈; 扫描到‟*‟, 优先级比‟一„高, 入栈。所以扫描至“f的时候, 栈中元素为:+(一*

转换为等价后缀表达式的过程中, 时, 弹出所有优先级大于或等于该运算符的栈顶元素, 然后将该运算

3． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A. 通常不会出现栈满的情况

B. 通常不会出现栈空的情况

C. 插入操作更容易实现

D. 删除操作更容易实现

【答案】A

4． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A.107

B.108

C.214

D.215

【答案】B

【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有n0＝n2＋+l，所以215＝n0＋n2＝2*n2＋l ，n2＝107，n0＝108。也就是说若对其进行哈夫曼编码，共能得到108个码字。

5． 下列选项中, 不能构成折半查找中关键字比较序列的是（ ）。

A.500, 200, 450, 180

B.500, 450, 200, 180

C.180, 500, 200, 450

D.180, 200, 500, 450

【答案】A

【解析】折半查找的过程是:先确定待查找记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足:对每一个关键字, 其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误, 第三次比较的关键字为450, 说明待查关键字位于200〜450间, 所以第四次比较时不会遇到关键字180。

6． 在下列存储形式中，哪一个不是树的存储形式？（ ）

A. 双亲表示法

B. 孩子链表表示法

C. 孩子兄弟表示法

D. 顺序存储表示法

【答案】D

【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。

7． 下列选项中, 属于多级页表优点的是（ ）

A. 加快地址变换速度

B. 减少缺页中断次数

C. 减少页表项所占字节数

D. 减少页表所占的连续内存空间

【答案】D

【解析】多级页表避免了把所有的页表一直保存在内存中

8． 中断处理和子程序调用都需要压桟以保护现场, 中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。

A. 程序计数器

B. 程序状态字寄存器

C. 通用数据寄存器

D. 通用地址寄存器

【答案】B 。

【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关, 而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序, 并要求其去处理某一事件的一种常用手段。因此, 除了要保护当前程序的地址, 计数器(指针) 和数据寄存器以外, 还需要保存程序状态字。子程序调用是与当前进程有关, 是正在运行的程序有意安排执行的, 这一类调用发生的时间以及位置具有确定性, 处于同一个进程内, 因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。

9． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）.

A.1000

B.2000

C.3000

D.4000

【答案】A

【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为min{4000，2000) ＝2000字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000－1000＝1000字节，正确选项为A.

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