级电类联合数据结构课程期末考试正式卷.pdfVIP

华南理工大学2005级电类联合班数据结构课程期末考试

B

1．填空题(10题，4’x10分)

1)哈希表的长度m=1000，哈希函数h(k)=[m*(k*Amod1)]，其中[]表示向下取整，若键值k=60

映射到位置500，则实数A的一个可能取值是。

2)有向图G的邻接矩阵为，则|E|=，图G是连通图(填写强、弱或不)。

3)算法A的时间复杂度是lnn!，算法B是nlnn，则当n很大时，算法运行得更快。

4)数组charA[3][4][5]在内存中以行主序线性存放，且元素A[0][1][2]的内存地址是

0x0100，则元素A[1][2][3]的内存地址是，如果以列主序线性存放，结果

为。(以16进制表示)

5)排序在最好情况下的时间复杂度为，选择排序在平均情况下的时间复杂度

为。(仅计算比较操作，用大O记法表示)

6)二叉树节点的中序遍历结果为。

7)高度为h的m叉树至少包含个叶子节点，至多包含个叶子节点。

8)在一个包含N个顶点的简单有向图中，如果每个顶点的入度都为1，则该图包含条边。

9)若[D,A,T,A,S,T,R,U,C,T,U,R,E]表示一个最大堆的初始状态(按照字母表顺序)，使用非叶

子节点下沉算法将其转化成合法的最大堆的过程中(相同元素不需要交换，在相同元素中选择交换

节点的时候，优先考虑左侧节点)，一共需要做次数组元素的交换，你认为这一算法的平

均时间复杂度是。

10)利用一个栈将输入序列1,2,3,4转换成输出序列，则可能的输出序列一共有种。

2．单项选择题(4题，4’x4分)

1)若长度为n的线性表采用链式结构，在其第i个位置一个新元素的时间复杂度为：

()

A.O(1)

B.O(n)

C.O(n2)

D.O(lnn)

2)要形成二叉有哪些信誉好的足球投注网站树，可能的节点序列为：()

A.4,6,1,2,3

B.4,6,3,2,1

C.4,2,3,6,1

D.4,3,2,5,1

3)假设数组A包含元素序列7,1,8,0,5,2,4,9，采用下列哪种排序算法将数组元素从小到大排序

需要的元素交换次数最少：()

A.冒泡排序

B.选择排序

C.排序

D.快速排序(以每一分划的第一个元素为基准)

4)借助一个无约束的双向队列，能够从输入序列1,2,3,4,5得到的输出序列有：

()

A.5,3,1,4,2

B.5,2,3,4,1

C.5,2,3,1,4