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

一、填空题

1． 设有N 个结点的完全二叉树顺序存放在向量

【答案】 中，其下标值最大的分支结点为_____。

【解析】最大的分支结点是最后一个叶子结点的父结点。

2． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)

【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序(quick sort) 的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

3． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

4． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。

【答案】15

2n 【解析】当时，100n2>2n，而，时，100n ＜2

5． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)

【答案】3个

【解析】以3，4先出栈的序列有34521、34215、34251共3个。

二、单项选择题

6． 下列选项中, 会导致用户进程从态切换到内核的操作是（ ）

Ⅰ. 整数除以零

Ⅱ.sin （ ）函数调用

Ⅲ.read 系统调用

A. 仅Ⅰ、Ⅱ

B. 仅Ⅰ、Ⅲ

C. 仅Ⅱ、Ⅲ

D. Ⅰ、Ⅱ和Ⅲ

【答案】B

【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。

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

A.N

B.2N －1

C.2N

D.N －1

【答案】A

【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。

8． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。

两个操作完成后, 2的值（ ）。

A. 可能为-1或3

B. 只能为1

C. 可能为0、1或2

D. 可能为-1、0、1或2

【答案】C

【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。

本例中, 由于没有采取保证数据同步的相应措施, 则最后结果就会出现差错。例如, 当正常情况下, 进程P1和P2先后对x 操作, 可以看到x 值的变化为初始

则x 值的变化为初始的过程, 若P2, P1先后操作, , 这是正确的。若考虑一种并发的情况, 进程P1和P2先后执行了取数load 的操作, 它们得到的x 值均为1, 运算后, P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的操作了, 哪个进程后操作, 结果就是那个进程的x 值, 所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。

9． 某主机的IP 地址为, 子网掩码为

分组, 则目的地址可以是（ ）。 A. B. C. D.

【答案】D 。

【解析IPv4地址中的特殊地址, 直接广播地址, 也就是把主机位全部设置为1, 这里77的二进制是01001101, 子网掩码252的二进制是11111100, 由此可以看到77的前6位作为子网位, 后四位

, 也就是, 因此答案是D 。 作为主机位, 由此可以知道其广播地址是

10．计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。

A. 可执行性、可移植性、可扩充性

B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性

D. 易读性、稳定性、安全性

【答案】B

【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性:有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。

11．若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。

A.X 的双亲

B.X 的右子树中最左的结点

C.X 的左子树中最右的结点

D.X 的左子树中最右的叶结点

【答案】C

【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X 的左子树中最右的结点。

。若该主机向其所在子网发送广播