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

一、填空题

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

【答案】4；2

2． 设数组数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

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

(2)存放数组的第8列的所有元素至少需要的单元数_____；

(3)数组按列存储时，元素A[5，8]的起始地址是_____。

【答案】270；27；2204

【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。

3． 已知；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，t) ，LEN(t)＋1))

:

【答案】 ，求REPLACE(S，V ，m) ＝_____。

4． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____

【答案】FEGHDCB ；BEF

【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。

5． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

6． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

二、单项选择题

7． 假定主存地址为32位, 按字节编址, 主存和Cache 之间采用直接映射方式, 主存块大小为4个字, 每字32位, 采用回写(Write Back) 方式, 则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。

A.146k

B.147K

C.148K

D.158K

【答案】B

【解析】Cache 和主存直接映射方式的规则为:主存储器分为若干区, 每个区与缓存容量相同; 每个区分为若干数据块, 每个块和缓存块容量相同; 主存中某块只能映象到Cache 的一个特定的块中。本题中, Cache 总共存放4K 字数据, 块大小为4个字, 因此cache 被分为

要包含所存的数据4个字, 每个字32位, 18位标记位和一个有效位, 因此总容量为:

。

8．

参考模型的网络层提供的是（ ）。

A. 无连接不可靠的数据报服务

B. 无连接可靠的数据报服务

C. 有连接不可靠的虚电路服务

D. 有连接可靠的虚电路服务

【答案】A

【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。

9． 假定基准程序A 在某计算机上的运行时间为100秒, 其中90秒为CPU 时间, 其余为若CPU 速度提高

A.55秒

B.60秒

C.65秒

D.70秒

【答案】D 。

CPU 速度提高50%, 即CPU 性能提高比为【解析】

秒。, 改进之后的CPU 运行时间速度不变, 仍维持10秒, 所以运行基准程序A 所耗费的时间为70秒。

个块, 由10位表示。块内共16字节, 所以由4位表示, 于是标记位为32-10-14=18位。所以, Cache 的每一行需时间。, 速度不变, 则运行基准程序A 所耗费的时间是（ ）。

10．偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中, 不属于偏移寻址方式的是（ ）。

A. 间接寻址

B. 基址寻址

C. 相对寻址

D. 变址寻址

【答案】A

【解析】在四种不同的寻址方式中, 间接寻址按指令的形式地址从主存中取出操作数的有效地址, 然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。

11．数据序列(8，9，10，4，5，6，20，1，2) 只能是下列排序算法中的（ ）的两趟排序后的结果。

A. 选择排序

B. 起泡排序

C. 插入排序

D. 堆排序

【答案】C

【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。

12．b ，(c，d) ，(e，(f，g))) ， 广义表A ＝(a，则式子Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。

A.(g)

B.(d)

C.c

D.d

【答案】D

【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。也就是tail 得到的元素需要在外层再加一个（ ）。

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

A.4

B.5

C.6

D.7

【答案】C

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