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

一、填空题

1． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

2． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

3． 对单链表中元素按插入方法排序的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 是下个待插入结点的指针

4． 已知如下程序段:

语句1执行的时间复杂度为_____:语句2执行的时间复杂度为_____:语句3执行的时间复杂度为_____:语句4执行的时间复杂度为_____。

【答案】(1)n＋1

(2)n

(3)n(n＋3)/2

(4)n(n＋l)/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋(n＋l) 加起来就是n(n＋3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n(n＋l)/2。

5． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

二、单项选择题

6． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

A.h ﹣＞next ＝s ；

B.s ﹣＞next ＝h ；

C.s ﹣＞next ＝h ；h ﹣＞next ＝s ；

D.s ﹣＞next ＝h ﹣next ；h ﹣＞next ＝s ；

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。

7． 在支持多线程的系统中, 进程P 创建的若干个线程不能共享的是（ ）。

A. 进程P 的代码段

B. 进程P 中打开的文件

C. 进程P 的全局变量

D. 进程P 中某线程的栈指针

【答案】D

【解析】现代操作系统中, 进程是资源分配的基本单位, 线程是处理机调度的基本单位。因此, 进程是线程运行的容器, 本题中, 进程的代码段, 进程打开的文件, 进程的全局变量等都是进程的资源, 唯有进程中某线程的栈指针是属于线程的, 那么, 属于进程的资源可以共享, 属于线程的栈是独享的, 不能共享。

8． 某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机. 该系统可能会发生死锁的K 最小值是（ ）.

A.2

B.3

C.4

D.5

【答案】C

【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果. 计算机系统的资源分配充分体现了这一原理. 考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行(这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析). 所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁.

9． 某计算机的Cache 共有16块，采用2路组相联映射方式(即每组2块). 每个主存块大小为32字节，按字节编址. 主存129号单元所在主存块应装入到的Cache 组号是（ ）.

A.0

B.2

C.4

D.6

【答案】C

【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K ＝ImodQ(K代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数) 来计算Cache 的组号. 由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4，Cache 共有16块，采用2路组相联映射方式(即每组2块) ，故Cache 有8组，按照上面的公式可以计算得到Cache 的组号＝4mod8＝4.

10．下列关于RISC 的叙述中，错误的是（ ）.

A.RISC 普遍采用微程序控制器

B.RISC 大多数指令在一个时钟周期内完成

C.RISC 的内部通用寄存器数量相对CISC 多

D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少

【答案】A

【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器.

11．对于循环队列（ ）。

A. 无法判断队列是否为空

B. 无法判断队列是否为满

C. 队列不可能满