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

一、单项选择题

1． n 个结点的完全有向图含有边的数目（ ）。

A.n*n

B.n(n+1)

C.n/2

D.n*(n－1)

【答案】D

【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。

2． 一个具有1025个结点的二叉树的高h 为（ ）。

A.11

B.10

C.11至1025之间

D.10至1024之间

【答案】C

【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。

3． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）

A.007.110.119.114.911.120.122

B.007, 110, 119, 114, 911, 122, 120

C.007, 110, 911, 114, 119, 120, 122

D.110, 120, 911, 122, 114, 007, 119

【答案】C

【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。

4． 在OSI 参考模型中, 直接为会话层提供服务的是（ ）

A. 应用层

B. 表示层

C. 传输层

D. 网络层

【答案】C

【解析】OSI 参考模型中, 下层直接为上层提供服务, 而会话层的下层为传输层。

5． 假定变量i 、f 和d 的数据类型分为int 、float 和double(int用补码表示, float 和double 分别用IEEE754单精度和双精度浮点数格式表示) , 已知

器中执行下列关系表达式, 则结果为“真”的是（ ）。

(Ⅰ)

(Ⅱ)

(Ⅲ)

(Ⅳ)

A. 仅Ⅰ和Ⅱ

B. 仅Ⅰ和Ⅲ

C. 仅Ⅱ和Ⅲ

D. 仅Ⅲ和Ⅳ

【答案】B

【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。Ⅱ中, f 的数据类型从float 转换为int 时, 小数点后面4位会丢失, 故Ⅱ的结果不为真; Ⅳ中, d+f时需要对阶, 对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故Ⅳ的结果也不为真。

Ⅰ和Ⅱ进行数据类型的转换的时候并没有改变其值。

6． 二叉树在线索化后，仍不能有效求解的问题是（ ）。

A. 前序线索二叉树中求前序后继

B. 中序线索二叉树中求中序后继

C. 中序线索二叉树中求中序前驱

D. 后序线索二叉树中求后序后继

【答案】D

【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。

7． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A.N

B.2N －1

C.2N

D.N －1

【答案】A

【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序

。若在32位机

表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。

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

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

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

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

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

【答案】C 。

【解析】对于A 、B 、D 显然是可以进行处理机调度的, 对于C , 当进程处于临界区时, 只要不破坏临界资源的使用规则, 是不会影响处理机调度的, 比如, 通常访问临界资源可能是慢速的外设(如打印机) , 如果在进程访问打印机时, 不能处理机调度, 那么系统的性能将是非常低的。几种不进行处理机调度的情况如下:

①在处理机中断的过程中;

②进程在操作系统内核程序临界区中;

③其他需要完全屏蔽中断的原子操作过程中。

9． 某计算机使用4体交叉存储器, 假定在存储器总线上出现的主存地址(十进制) 序列为8005, 8006, 8007, 8008, 8001, 8002, 8003, 8004, 8000, 则可能发生发生缓存冲突的地址对是（ ）。

A.8004, 8008

B.8002、8007

C.8001、8008

D.8000、8004

【答案】D

【解析】交叉存储器, 又称低位交叉编址, 即低位地址为体号, 高位地址为体内地址。本题中, 主存地址对应的体号分别是:1, 2, 3, 4, 1, 2, 3, 4, 4。地址为8004和8000都是存取的四号储存器, 可能导致8004存储还未完成而又存取8000地址, 因此可能发生缓存冲突。

10．将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。

A. 前序遍历

B. 中序遍历

C. 后序遍历

【答案】B

【解析】树的后序遍历恰好对应于二叉树的中序遍历。