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

一、填空题

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

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

【答案】

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

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

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

【答案】

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

4． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

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

第 2 页，共 66 页

对应的前缀式为_____，若

则后缀式

的

【答案】

，）则

的地址为_____。

若

6． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若

则

则的地址为

的地址为将代入得33。

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

【答案】69

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

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

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

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

二、选择题

9． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。

A.1 B.2 C.3 D.4

【答案】C 。

【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。

10．某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns 、80ns 、70ns 和60ns , 则该计算机的CPU 时钟周期至少是（ ）。

A.90ns B.80ns C.70ns D.60ns 【答案】A

【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功

第 3 页，共 66 页

能段执行时间为准。

11．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（ ）。

A.5位 B.6位 C.15 位 D.33 位 【答案】C 。

，根据每个类中微命令的多少可以分别【解析】33个微命令分成5个互斥类（即5个字段）

确定字段的长度 为3、2、4、3、3位，又因为采用直接编码方式，所以它们之和

也

就是操作控制字段的位数。

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

A.107 B.108 C.214 D.215

【答案】B

【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有以

13．下列因素中，不会影响信道数据传输速率的是（ ）

A. 信噪比 B. 频率宽带 C. 调制速率 D. 信号传播速度 【答案】D

【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。

14．在OSI 参考模型中，直接为会话层提供服务的是（ ）

A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C

【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。

第 4 页，共 66 页

所

也就是说若对其进行哈夫曼编码，共能得到108个码字。