Question

数据结构试题

一、 选择

1. 将含有100个节点的完全二叉树，从上到下，从左到右进行编号，根节点编号为1，则编号27的双亲为[ ]。

A.17 B.13 C.14 D.54

2. 深度为h的满二叉树的第m层有[ ]个结点。

A. B. C. D.

3. 设用邻接矩阵A表示有向图G的存储结构，则G中顶点i的出度为[ ]。

A. 第i行非0元素的个数之和 B.第i列非0元素的个数之和

C. 第i行0元素的个数之和 D. 第i列0元素的个数之和

4. 已知一个长度为16的顺序表，元素升序排列，采用折半法查找，若查找成功所需要比较次数最多是[ ]。

A. 4 B. 5 C. 6 D.
7

5. 对n个记录进行快速排序，所需要的辅助存储空间大致为[ ]。

A. O（1） 　B.
O（n）　　 C. O（1og2n） D. O（n2）

6. 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为[ ]。

A． 2，3，5，8，6 B． 3，2，5，8，6

C． 3，2，5，6，8 D．2，3，6，5，8

二、 填空

1. i=0，s=0；while (s<n) {s=s+i；i++；}的时间复杂度为__ ___。

2. 假定一棵树的广义表表示为A（B，C（E，F，G(H)），D（I，J）），则树中所含的结点数为 个，树的深度为_ 。

3. 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是 ，若按行存放时，元素A[8][5]的起始地址是 ，若按列存放时，元素A[8][5]的起始地址是 。

4. 已知广义表 D = ( E, F ) = ((a, (b, c))，F ) 求：

Head[ D ] = Tail [ D ]=

Head[ E ] = Tail [ E ]=

5. 下面算法为快速查找方法中的一次划分，请补充完整。

int Partition ( int L[], int low,
int high ){

L[0]
= L[low];　pivotkey = L[low]; 　　　

while
(low < high) {　　　　

while ( ) --high;

L[low] = L[high];　

while (low < high && L[low]
<= pivotkey )　++low;

;　　

} // while

;　　 // 枢轴记录到位

return
low; 　　　　 　// 返回枢轴位置

} // Partition

三、 综合题

1.
假设一棵二叉树的先序遍历序列为 ABDGHJKECFIM 和中序遍历序列为 GDJHKBEACFMI，请画出该树。

2. 从顶点1出发,用Prim算法构造下图的一棵最小生成树。

3.已知一组元素为（10,28,13,54,50,62,45）画出按元素排序输入生成的一棵二叉排序树，并在等概率条件下求ASL。

四、算法设计

1. 利用下面Record数据结构，完成折半法查找算法BiSearch。

typedef struct Record{

int
key;

int
others;

}
Record;

int
BiSearch(Record r[ ],int len, int k)

{ //r[0]空余不用，len数组r的长度，k待查找的关键字

//若找到k,返回它的位置，否则返回0;
怎么没有人回答呀

Answer 1

已发送您的邮箱