科目组合

数据结构 、计算机组成原理 、操作系统 、计算机网络

设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。

x = 2;
while (x < n / 2) 
    x = 2 * x;

A. O(log⁡n)

B. O(n)

C. O(nlog⁡n)

D. O(n^2)

元素a，b，c，d，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，知道所有元素都出栈，则在所有可能的出现序列中，一元素d开头的序列个数是（ ）。
A、3    B、4    C、5    D、6

已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是______。

A. 0，0

B. 0，n-1

C. n-1，0

D. n-1，n-1

若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）

A．257

B．258

C．384

D．385

若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的 中序遍历序列不会是（）

A．1,2,3,4

B．2,3,4,1

C．3,2,4,1

D．4,3,2,1

已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（ ）。

A. 115

B. 116

C. 1895

D. 1896

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是______。

A. 95，22，91，24，94，71

B. 92，20，91，34，88，35

C. 21，89，77，29，36，38

D. 12，25，71，68，33，34

下列关于图的叙述中，正确的是（）

Ⅰ. 回路是简单路径

Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间

Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

A．仅Ⅱ

B．仅Ⅰ、Ⅱ

C．仅Ⅲ

D．仅Ⅰ、Ⅲ

为提高哈希（Hash）表的查找效率，可以采取的正确措施是______。

Ⅰ.增大装填因子

Ⅱ.设计冲突少的哈希函数

Ⅲ.处理冲突时避免产生堆积现象

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ

D. 仅Ⅱ、Ⅲ

为实现快速排序算法，待排序序列宜采用的存储方式是（）

A．顺序存储

B．散列存储

C．链式存储

D．索引存储

已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）

A．1

B．2

C．4

D．5

已知有6个顶点（顶点编号为0～5）的有向带权图 G ，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

⑴ 写出图 G 的邻接矩阵 A 。

⑵ 画出有向带权图 G 。

⑶ 求图 G 的关键路径，并计算该关键路径的长度。

一个长度为 L(L≥1) 的升序序列 S ，处在第 ⌈L/2⌉ 个位置的数称为 S 的中位数。例如，若序列 S1=⟨11,13,15,17,19⟩ ，则 S1 的中位数是 15 。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列 S2=⟨2,4,6,8,20⟩ ，则 S1 和 S2 的中位数是 11 。现有两个等长的升序序列 A 和 B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：

⑴ 给出算法的基本设计思想。

⑵ 根据设计思想，采用C或C++或Java语言描述，关键之处给出注释。

⑶ 说明你所设计算法的时间复杂度和空间复杂度。