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

一、选择题

1． 图的BFS 生成树的树高比DFS 生成树的树高（ ）。

A. 小或相等 B. 小 C. 大或相等 D. 大

【答案】A

【解析】BFS 称作广度优先搜索，DFS 称作深度优先搜索。广度优先搜索类似与二叉树的层序遍历算法，深度优先搜索类似于树的先序遍历。因为深度优先搜索算法遵循的策略是尽可能的“深”地搜索一个图。所以图的BFS 生成树的树高比DFS 生成树的树高小或者相等。

2． 假定编译器将赋值语句“x=x+3; ”转换为指令” add xaddt, 3”，其中xaddt 是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，且Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（ ）。

A.0

B.1

C.2

D.3

【答案】C

【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中，如果给出的地址在TLB 中，则直接根据该地址取数据或指令，仅需要一次访问内存。Cache 使用直写方式时，计算完需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存2次。

3． 设栈S 和队列Q 的初始状态为空，元素依次通过栈S ，一个元素出栈

后即进队列Q ，若6个元素出队的序列是则栈S 的容量至少应该是（ ）。

A.6

B.4

C.3

D.2

【答案】C

4． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。

A.245Mbps

B.979Mbps

C.

D.

【答案】D

的时间用来刷新【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到

1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：

5． 当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ） 。

A.4个

B.5个

C.3个

D.6个

图

【答案】C

【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t , 有两种结果此总共有3种结果。

6． 链表不具有的特点是（ ）。

A. 插入、删除不需要移动元素

B. 可随机访问任一元素

C. 不必事先估计存储空间

D. 所需空间与线性长度成正比

【答案】B

【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。

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

A. 程序计数器

B. 程序状态字寄存器

C. 通用数据寄存器

D. 通用地址寄存器

【答案】B 。

【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而

若首字符为则只有一种结果因

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

8． 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）

A.5

B.6

C.8

D.9

【答案】C 【解析】所以至少需要8位才能表示完130个地址。

9． —棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。

A.2h

B.

C.

D.

【答案】B

【解析】此树满足哈夫曼树，除根节点外每层有两个节点。

10．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。

A.4

B.5

C.6

D.7

【答案】C

【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个

全二叉树的高度为

或结点的完由完全二叉树类推到完全三叉树可知，n 个结点的完全三 叉树的高度为

或

11．若路由器R 因为拥塞丢弃IP 分组，则此时R 可向发出该IP 分组的源主机发送的ICMP 报文件类型是（ ）。

A. 路由重定向

B. 目的不可达

C. 源抑制

D. 超时