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

一、填空题

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

【答案】FEGHDCB ；BEF

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

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

【答案】方便运算

3． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行

(2)q //将当前结点作为头结点后的第一元素结点插入

4． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

5． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块

的起始地址为_____; 。

【答案】480+8=488，480－32=448

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:

根据上述公式起始地址就为488。

6． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

:_____:

{_____)

(_____、

:_____；_____；p ＝u ；

【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中

(2)p!＝NULL //当链表尚未到尾，p 为工作指针

(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针

(4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中

(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针

二、单项选择题

7． 程序P 在机器M 上的执行时间是20秒, 编译优化后, P 执行的指令数减少到原来的70%而CPI 增加到原来的

A.

B.

D. 秒 秒 秒 倍, 则P 在M 上的执行时间是（ ） C.14秒 【答案】D 【解析】

8． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是

取值的个数是（ ） A. B. C.

。若, 则, 则可能

D. 无法确定

【答案】C

【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。

9． 串的长度是指（ ）。

A. 串中所含不同字母的个数

B. 串中所含字符的个数

C. 串中所含不同字符的个数

D. 串中所含非空格字符的个数

【答案】B

【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。

10．假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz ，则总线带宽是（ ）.

A.10MB/s

B.20MB/S

C.40MB/S

D.80MB/S

【答案】B

【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送. 总线时钟频率为10MHz ，时钟周期为，总线周期占用2个时钟周期，为＝一个总线周期中并行传输4字节信息，则总线带宽是＝20MB/s.

11．n 个结点的线索二叉树上含有的线索数为（ ）。

A.2n

B.n ﹣1

C.n ＋1

D.n

【答案】C

【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n ＋1个空链域。

12．若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。

A. 在进程结束时能进行处理机调度

B. 创建新进程后能进行处理机调度

C. 在进程处于临界区时不能进行处理机调度

D. 在系统调用完成并返回用户态时能进行处理机调度

【答案】C 。