邯郸职业技术学院2010—2011学年第二学期
数据结构期末试题B
系别_______专业_______班级_______姓名_______学号____成绩______
一、 简答
1. 描述以下三个概念的区别：头指针，头结点，首元结点。
2. 什么是算法？算法的5个特性是什么？如何评价一个算法？
二、 分析题
1. 求下列算发的时间复杂度
（1） for(i=0;i
for(j=0;j
a[i][j]=0;
（2） i=s=0;
while(s
{
i++;
s+=i;
}
（3） s=0;
for(i=0;i
for(j=0;j
s+=b[i][j];
sun=s;
（4） i=1;
while(i
i=i*2;
2. 写出程序的输出结果
void main(){
stack S;
char x,y;
Initstacks(S);
x=’c ’;y=’k ’;
1
教研室主任：陈文兰 教学主任：赵裕民 班级人数：69人
Push(S,x) ; Push(S,’a ’) ; Push(S,y);
Pop(S,x); Push(S,’t ’) ; Push(S,x);
Pop(S,x) ; Push(S,’s ’);
while(!stackempty(S)){ Pop(S,y); printf(y);}
printf(x);
}
3. 假设一颗二叉树的中序序列为DCBGEAHFIJK 和后序序列为DCEGBFHKJIA, 请画出该树。
4. 设有12个数据（25，40，33，47，12，66，72，87，94，22，5，58），它们存储在哈希表中，使用线性探测再散列解决冲突，要求插入数据的平均查找长度不超过3次。求哈希表的表长应该为多少？请设计相应的哈希函数，计算查找成功时的平均查找长度。
三、 编程题
已知序列（17，18，60，40，7，32，73，65，85），写出使用冒泡排序的算法，并写出每一趟的排序结果。
教研室主任：陈文兰
教学主任：赵裕民
班级人数：69人 2
邯郸职业技术学院2010—2011学年第二学期
数据结构期末试题B
系别_______专业_______班级_______姓名_______学号____成绩______
一、 简答
1. 描述以下三个概念的区别：头指针，头结点，首元结点。
2. 什么是算法？算法的5个特性是什么？如何评价一个算法？
二、 分析题
1. 求下列算发的时间复杂度
（1） for(i=0;i
for(j=0;j
a[i][j]=0;
（2） i=s=0;
while(s
{
i++;
s+=i;
}
（3） s=0;
for(i=0;i
for(j=0;j
s+=b[i][j];
sun=s;
（4） i=1;
while(i
i=i*2;
2. 写出程序的输出结果
void main(){
stack S;
char x,y;
Initstacks(S);
x=’c ’;y=’k ’;
1
教研室主任：陈文兰 教学主任：赵裕民 班级人数：69人
Push(S,x) ; Push(S,’a ’) ; Push(S,y);
Pop(S,x); Push(S,’t ’) ; Push(S,x);
Pop(S,x) ; Push(S,’s ’);
while(!stackempty(S)){ Pop(S,y); printf(y);}
printf(x);
}
3. 假设一颗二叉树的中序序列为DCBGEAHFIJK 和后序序列为DCEGBFHKJIA, 请画出该树。
4. 设有12个数据（25，40，33，47，12，66，72，87，94，22，5，58），它们存储在哈希表中，使用线性探测再散列解决冲突，要求插入数据的平均查找长度不超过3次。求哈希表的表长应该为多少？请设计相应的哈希函数，计算查找成功时的平均查找长度。
三、 编程题
已知序列（17，18，60，40，7，32，73，65，85），写出使用冒泡排序的算法，并写出每一趟的排序结果。
教研室主任：陈文兰
教学主任：赵裕民
班级人数：69人 2