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

一、单项选择题

1． 下列说法不正确的是（ ）。

A. 图的遍历是从给定的源点出发每个顶点仅被访问一次

B. 遍历的基本方法有两种:深度遍历和广度遍历

C. 图的深度遍历不适用于有向图

D. 图的深度遍历是一个递归过程

【答案】C

【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。

2． 本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（ ）.

A. 命令解释程序

B. 中断处理程序

C. 系统调用服务程序

D. 用户登录程序

【答案】B

【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式. 其工作原理是:利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受中断则会停止当前进程的运行，转而服务发出中断的物理设备(注意与陷阱，即软中断有区别），那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢? 这就要借助中断向量，中断向量一般是由硬件根据中断的类型(不同外设不同）计算所得，或计算机系统在开机配置时所配置的. 处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址. 所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候(一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去. 如此，最先响应键盘的必然是中断处理程序. 本题中，像命令解释器(例如cmd 窗口）、系统调用服务和用户登录程序都在中断处理程序后面.

3． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。

A.24, 10, 5和24, 10, 7

B.24, 10, 5和24, 12, 7

C.24, 10, 10和24, 14, 11

D.24, 10, 5和24, 14, 6

【答案】D

【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。

4． 下列选项中, 不可能是快速排序第2趟排序结果的是（ ）

A.2, 3, 5, 4, 6, 7, 9

B.2, 7, 5, 6, 4, 3, 9

C.3, 2, 5, 4, 7, 6, 9

D.4, 23, 5, 7, 6, 9

【答案】C

【解析】对于快速排序, 每一趟都会使一个元素位于有序时的位置, 而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比, 只有9位于它有序的时候的位置, 显然不是第二趟快速排序的结果

5． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。

A.(2，5，12，16)26(60，32，72)

B.(5，16，2，12)28(60，32，72)

C.(2，16，12，5)28(60，32，72)

D.(5，16，2，12)28(32，60，72)

【答案】B

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较:28比72小，不交换;

第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;

第三次比较:16比28小，不交换；

第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;

第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;

第六次比较:28比12大，不交换；

第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;

一次划分结束。

6． 在一棵具有15个关键字的4阶B 树中, 含关键字的结点数最多是（ ）

A.5 B.6 C.10 D.15

【答案】D

【解析】M 阶B 树非根结点含关键字个数

键字, 一共有15个关键字那么最多有15个含有关键字的结点

7． 5个字符有如下4种编码方案, 不是前缀编码的是（ ）

A.01, 0000, 0001, 001, 1

B.011, 000, 001, 010, 1

C.000, 001, 010, 011, 100

D.0, 100, 110, 1110, 1100

【答案】D

【解析】在一个字符集中, 任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符„0‟, 右分支表示字符„1‟, 则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中, 编码110是编码1100的前缀, 故不符合前缀编码的定义

8． 循环两列放在一维数组。 4阶B 树非根结点含关键字1~3个, 所以要使关键字结点数量最多, 那么每个结点只有一个关中, end1指向队头元素, end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作, 队列中最多能容纳M-1个元素。初始时为空, 下列判断队空和队满的条件中, 正确的是（ ）

A. 队空:endl==end2; 队满:endl==(end2+l)modM

B. 队空Gendl==end2; 队满:Gend2==(endl+1)mod(M-1)

C. 队空Gend2==(endl+1)modM; 队满:Gendl==(end2+l)modM

D. 队空:

【答案】A

【解析】在循环队列中, 在少用一个元素空间的前提下, 可约定入队前, 测试尾指针在循环意义下加1后是否等于头指针, 若相等, 则队满。而队空的条件还是首尾指针是否相等。

9． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）

队满: A.O(2n)

B.O(n)

C.O(n2)

D.O(log2n )