科目组合

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

已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（）

A. O(n)

B. O(m * n)  

C. O(min(m, n))

D. O(max(m, n))

一个栈的入栈序列为 1,2,3,…,n ，其出栈序列是 p1,p2,p3,…,pn ，若 p2=3 ，则 p3 可能取值的个数是（ ）。

A. n−3

B. n−2

C. n−1

D. 无法确定

若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。

A. 0

B. 1

C. 2

D. 3

已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是

A. 27  

B. 46  

C. 54

D. 56

若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y 。则 X 的右线索指的是（ ）。

A. X 的父结点

B. 以 Y 为根的子树的最左下结点

C. X 的左兄弟结点 Y

D. 以 Y 为根的子树的最右下结点

在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树 T2 ，再将 v 插入 T2 形成二叉排序树 T3 。下列关于 T1 与 t3 的叙述中，正确的是（ ）。

I. 若 v 是 T1 的叶结点，则 T1 与 T3 不同

II. 若 v 是 T1 的叶结点，则 T1 与 T3 相同

III. 若 v 不是 T1 的叶结点，则 T1 与 T3 不同

IV. 若 v 不是 T1 的叶结点，则 T1 与 T3 相同

A. 仅I、III

B. 仅I、IV

C. 仅II、III

D. 仅II、IV

设图的邻接矩阵 A 如下所示。各顶点的度依次是（）

A. 1，2，1，2    B. 2，2，1，1

C. 3，4，2，3    D. 4，4，2，2

若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）

A. h，c，a，b，d，e，g，f

B. e，a，f，g，b，h，c，d

C. d，b，c，a，h，e，f，g

D. a，b，c，d，h，e，f，g

下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（）

A. c 和 e

B. d 和 e

C. f 和 d

D. f 和 h

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

A.5

B. 7

C. 8

D. 14

对给定的关键字序列 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

已知一个整数序列 A=(a0,a1,…,an−1) ，其中 0≤ai<n(0≤i<n) 。若存在 ap1=ap2=⋯=apm=x 且 m>n/2(0≤pk<n,1≤k≤m) ，则称 x 为 A 的主元素。例如 A=(0,5,5,3,5,7,5,5) ，则 5 为主元素；又如 A=(0,5,5,3,5,1,5,7) ，则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出 −1 。要求：

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

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

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

设包含 4 个数据元素的集合 S={“do”, “for”, “repeat”, “while”} ，各元素的查找概率依次为： p1=0.35,p2=0.15,p3=0.15,p4=0.35 。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2 。请回答：

⑴ 若采用顺序存储结构保存 S ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

⑵ 若采用链式存储结构保存 S ，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？