数据结构212201-a试题训练卷.docx

2021～2022学年第一学期试卷课程名称：数据结构考试形式：闭卷试卷：A卷

第(PAGE4)页共(NUMPAGES4)页

专业班级：计算机学院2020

专业班级：计算机学院2020级专业班级：学号：姓名：

装订线

一

二

三

总分

标准分

30

50

20

100

得分

注：答案一律填写在答题纸上，写在试卷上无效。

一、程序分析题（每小题6分，5小题，共30分）

1.分析下列程序段，写出运行结果。

intmain(){

charx,y;

SqStacks;

InitStack(s);

x=a;

y=b;

push(s,x);

push(s,c);

push(s,y);

pop(s,x);

push(s,d);

push(s,x);

pop(s,x);

push(s,e);

while(!StackEmpty(s)){

pop(s,y);

printf(%c,y);

}

printf(%c\n,x);

return0;

}

2.阅读并分析下面算法，回答问题。

intFunction(SStringS,SStringT,intpos){//S,T为字符串

inti=pos;

intj=1;

while(i=S[0]j=T[0]) {

if(S[i]==T[j]){

++i;

++j;

}

else{

i=i-j+2;

j=1;

}

}

if(jT[0]) returni-T[0];

else return0;

}

(1)请指出Function(SStringS,SStringT,intpos)算法的功能。

(2)若S=”aaaababac”,T=”bac”,pos=1,执行Function(S,T,pos)后，返回的结果为多少？

3.分析下面程序的时间复杂度

intsum=0,i,j;

for(i=1;in;i*=2)

for(j=0;jn;j++)

sum++;

4.阅读并分析下面算法，回答问题。

Statuschange(inta[n][n],intb[n]){

inti,j,x;

for(i=0;in;i++)

for(j=0;jn;j++)

if(i=j){

x=i*(i+1)/2+j;b[x]=a[i][j];

}

}

（1）假设二维数组a是下三角矩阵，change算法的功能是什么？

（2）已知二维数组

执行该函数后，一维数组b的内容是什么？

2.阅读并分析下面算法，回答问题。

voidBubbleSort(inta[],intn){

inti,j,flag;

j=n-1;

do{

flag=1;

for(i=1;i=j;i++)

if(a[i+1]a[i])

{temp=a[i+1];a[i+1]=a[i];a[i]=temp;flag=0;}

if(!flag)j--;

}while(!flagj);

}

（1）请指出该算法的功能。

（2）算法中变量flag的作用。

二、应用题（1-6小题每题7分，第7小题8分，共50分）

1．已知一个文件中仅有8个不同的字符，各字符出现的个数分别为7,9,2,6,32,20,3,10。试重新为各字符编码，以节省存储空间。要求生成的哈夫曼树左子树权值小于右子树。

2．设哈希表地址范围为0~14，哈希函数为H(key)=keyMOD13,用线性探测法处理冲突，输入关键字(10,24,32,17,31,30,46,47,40,63,56)，构造哈希表。

1）画出哈希表示意图；

2）若查找概率相等，求平均查找长度。

3．对下图所示的有向带权图，根据迪杰斯特拉算法，画出生成从结点v1到其余各结点最短路径的过程。

4.已知某图的邻接表结构如下所示，请按要求解答问题。

（1）请绘制出该图的结构，并判断该图是有向图还是无向图。

（2）请写出该图从节点1开始的深度优先遍历序列。

（3）请写出该图从节点1开始的广度优先遍历序列。

注意：在遍历过程中，请严格按照邻