数据结构212201-a卷

—•二三总分intj=1;标准分whilei=S[O]j=T

[0]30520KX得分’{ifS[i]==T[j]{++i；注答案一律填写在答题纸上，写在试卷上无效++j；

一、程序分析题每小题6分，5小题，共30分点else较

1.分析下列程序段，写出运行结果inti=i-j+2;main{j二l；char x,y;SqStack s;}InitStacks;x=a;y=b；pushs,x；pushs,c;pushs,y;pops,x;pushs/d;else return0;pushs,x;pops,x;pushs,e;1while!请指出FunctionSString S,SString T,int pos算法的功能1StackEmptys{pops,y;若S=aaaababac,T=bac,pos=l,执行Function S,T,pos后，返Fl的结果为多QprintfH%cn,y;少？

3.分析下面程序的时间复杂度int sum=,i,j;for i=l;in;i*=2forj=0;jn;j++sum++;

4.阅读并分析下面算法，回答问题Status changcinta[nJln],int b[nj{int i,j,x;fori=;in;i++printf,%c\n,,x;forj=0;jn;j++return0;ifi=j{x=i*i+l/2+j;b[x]=a[i]U];

2.阅读并分析下面算法，回答问题int FunctionSStringS,SString T,int pos//S,T为字符串inti=pos;

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

（2）已知二维数组2）若查找概率相等，求平均查找长度

3.对下图所示的有向带权图，根据迪杰斯特拉算法，画出生成从结点v1到其余各结点最短路径的过程执行该函数后，一维数组b的内容是什么？

2.阅读并分析下面算法，回答问题void BubbleSortinta[],int n{int i,j,flag;j=n-l;doflag=l;而科fori=l;i=j;i++

4.已知某图的邻接表结构如下所示，请按要求解答问题ifa[i+l]a[i]{temp=a[i+l];a[i+l]=a[i];a[i]=lemp;flag=0;}if!flagj-;}while!flag j;1请指出该算法的功能蕊昼2算法中变量flag的作用心态

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

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

1.已知一个文件中仅有8个不同的字符，各字符出现的个数分别为7,9,2,6,32,

（2）请写出该图从节点1开始的深度优先遍历序列运心20,3,10试重新为各字符编码，以节省存储空间要求生成的哈夫曼树左子树权值

（3）请写出该图从节点1开始的广度优先遍历序列三o派小于右子树注意在遍历过程中，请严格按照邻接表内容来求取第一个邻接点和下一个邻接点七湍

2.设哈希表地址范围为〜14,哈希函数为H（key）二key MOD13,用线性探测法处内容三烹理冲突，输入关键字（10,24,32,17,31,30,46,47,40,63,56）,构造哈希表

5.已知图结构如下所示，请任选一种方法，求取该图的最小生成树，并计算其权值1）国出哈希表示意图；

6.请把下面的二叉树转换为树或森林，并画出此二叉树的中序线索树_答题纸二三总分—•第4题标准分3530KX得分

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

1、edcab_______________

2、

（1）串的模式匹配；

（2）

73、OSIosn）_____________

4、

（1）将大小为n*n的下二角数组转换成以行为主的•维数组,第5题且不存储内容为的元素

（2）一维数组b的内容为（1,4,7,2,5,8,3,4,5,7,2,5,6,3,2容

5、

（1）该算法的功能是冒泡排序以

（2）flaq是标志变量若他为1,表示本次冒泡出现了记录交换，必须继续进行冒泡排序；区若flaq为0,表示本次冒泡没有出现记录交换，该次冒泡以前就已经达到了排序要求，因而堞中沿可结束排序第6题

二、应用题（1・6小题每题7分，第7小题8分，共50分）第1题鼎鑫宁徽第7题景第2题邂护三淞七第3题

三、算法设计题（每小题10分，共20分，将答案标号题号写在答题纸背面）““COCO。