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

一、填空题

1． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

2． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】

要加“虚结点”。

设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是

。

3． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)

4． 中缀式

运算结果为_____。 【答案】

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

5． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态) 链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式的

6． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

二、单项选择题

7． 在一株高度为2的5阶B 树中, 所含关键字的个数最少是（ ）

A.5

B.7

C.8

D.14

【答案】A

【解析】根据B 树的定义可知, 跟结点最少含有max(2, (m-1))个关键字, 高度为2的阶B 树最少有(5-1)+1=5个关键字, 其中根节点含有(5-1)个关键字, 第2层结点含有1个关键字。

8． 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A. 二叉排序树

B. 哈夫曼树

C.A VL 树

D. 堆

【答案】D

【解析】堆的定义:

n 个关键字序列K 1，K 2，... ，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :

(1)

(2)

且且或

满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。

由堆的定义可知堆可以满足上述性质。

9．

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

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

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

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

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

【答案】A

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

因此答案是A 。

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

A.5

B.6

C.8

D.9

【答案】C 【解析】, ,

所以至少需要8位才能表示完130个地址。

11．用户程序发出磁盘请求后, 系统的正确处理流程是（ ）。

A. 用户程序—系统调用处理程序—中断处理程序—设备驱动程序

B. 用户程序—系统调用处理程序—设备驱动程序—中断处理程序

C. 用户程序—设备驱动程序—系统调用处理程序—中断处理程序

D. 用户程序—设备驱动程序—中断处理程序—系统调用处理程序

【答案】B

【解析】对于一次设备的调用, 操作系统为用户准备了系统调用的接口, 当用户使用设备时, 首先在用户程序中发起一次系统调用, 操作系统的内核接到该调用请求后调用处理程序进行处理, 根据调用格式和形参, 再转到相应的设备驱动程序去处理; 大部分设备在运行时是需要时间的, 所以设备驱动程序会以中断方式驱动设备, 即设置好控制寄存器参数和中断向量等参数后阻塞自己; 当设备准备好或所需数据到达后设备硬件发出中断, 设备驱动程序唤醒, 将数据按上述调用顺序逆向回传到用户程序中, 或继续驱动设备执行下一条指令。因此, 正确的顺序应该是用户到系统调用到驱动到中断处理。中断处理处于最底层。

12．在OSI 参考模型中，自下而上第一个提供端到端服务的层次是（ ）.

A. 数据链路层

B. 传输层

C. 会话层

D. 应用层

【答案】B

【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意. 题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不