安徽大学复试数据结构.doc

安徽大学《 数据结构 》
一、填空题
1、在具有n个单元的循环队列中，队满时共有个元素。
2、下面程序段的时间复杂度是。
for (i=0;i<n;i++)
for (j=0;j<m;j++)
A[i][j]=0;
3点的编号。
(4)编号为i的结点的第j个孩子结点(若有)的编号。
2已知图G的邻接表如图1所示，请写出：
（1）其从顶点v1出发的深度有限搜索序列；
（2）其从顶点v1出发的广度优先搜索序列。
v1
v2
v3
v4 ^
v5
v6 ^
V2
V5
V4 ^
v3
V5 ^
V4
V6
V3 ^
V6 ^
图1 图G的邻接表
3、 以关键码序列（503,087,512,061,908,170,897,275,653,426），为例，手工执行快速排序排序算法，写出每一趟排序结束时的关键码状态：
4．使用哈希函数H(key)=key % 11，把一个整数值转换成哈希表下标，现要把数据1、13、12、34、38、33、27、22插入到哈希表（表1）中。
（1）使用线性探测再散列法构造哈希表，请在表1所示的哈希表中与哈希地址对应的位置上，填写出相应的关键字值和元素插入时的探查次数。
（2）假设查找每个元素的概率相同，求出查找成功时的平均查找长度。
表1
哈希
地址
0
1
2
3
4
5
6
7
8
9
10
关键字值
探查次数
四、算法阅读题（每小题9分，共18分）
1、完成二叉树按层遍历的算法。
void leveltravel ( struct treenode *bt)
{ struct treenode *p,*a[n];
int rear=front = -1;
p=bt;
rear =__________;
a[rear]=p;
while (rear != front)
{ front = ___________;
p=a[front];
printf(“%c”,p->data);
If ( p->left !=null)
{ rear =(rear +1)% n
a[rear]= _________; }
If (p->right!= null)
{rear = (rear +1)%n ;
a[rear]=_________; }
}
}
2、下面算法是对直接插入排序算法的改进，请填写完整
void weizhisort(struct node r[ n+1],int n)
{ int low,high,mid,j,i;
for(i=2;i<=n;i+