2022年江南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年江南大学计算机科学与技术专业《数据结构与算法》科目期末

试卷人（有答案）一、选择题1、 若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。快速排序堆排序归并排序直接插入排序2、 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入 选择希尔 二路归并 D.3、 单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点 标识表结点中首结点的位置C.方便运算的实现 说明单链表是线座表的链式存储4、 下列关于AOE网的叙述中，不正确的是（）。关键活动不按期完成就会影响整个工程的完成时间任何一个关键活动提前完成，那么整个工程将会提前完成所有的关键活动提前完成，那么整个工程将会提前完成某些关键活动若提前完成，那么整个工程将会提前完成5、 动态存储管理系统中，通常可有（）种不同的分配策略。A.1 B.2 C.3 D.46、 已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!=t）时，i=j=5,则下次开始匹配时，i和j的值分别（）。A. i=1，j=0 . i=5，j=0. i=C5， j=2 . i=D6，j=27、 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。i.简单选择排序n.希尔排序ill.快速排序w.堆排V.二路归并排序

.仅III、W、V)。A,仅I、III、W.仅BI、II、III..仅III、W、V)。8、有n(n>0)个分支结点的满二叉树的深度是(n2-1log2(n+1)+1log2(n+1)log2(n-l)9、 一个具有1025个结点的二叉树的高h为()。A.11 B.1C至1025之间C.11至1024之间D.1010、 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为l,则应作()型调整以使其平衡A.LL B.LR C.RLD.RR二、填空题11、 N个顶点的连通图用邻接矩阵表示时，该矩阵至少有个非零元素。12、 设用希尔排序对数组｛98,36,-9,0,47,23,1,8,10,7｝进行排序，给出的步长(也称增量序列)依次是4,2,1则排序需 趟，写出第一趟结束后，数组中数据的排列次序。13、建立索引文件的目的是。14、一个算法具有5个特性：有零个或多个输入、有一个或多个输出。15、 索引顺序文件既可以顺序存取，也可以存取。16、当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2],贝U当栈1空时，top[1]为,栈2空时，top[为,栈满时为。17、已知U=‘xyxyxyxxyxy,;t='xxy';ASSIGN(S,U);ASSIGN(V, SUBST(S,INDEX(S, t), LEN (t) +1)); ASSIGN(m, 'ww')，求REPLACE(S, V, m)18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列是。设上述二叉树是由某棵树转换而成，则该树的前序序列是。

三、 判断题19、倒排序文件的优点是维护简单。（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、 广义表（（（a，b,c），d,e,f））的长度是4。（）22、二维以上的数组其实是一种特殊的广义表。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）25、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）26、数据元素是数据的最小单位。（）27、B-树中所有结点的平衡因子都为零。（）28、 对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（）四、 简答题29、写出下列排序算法的基本思想，并写出对序列（23，12，35,47，16,25,36，19,21,16）进行排序时每一趟的结果。PROCbbsort（VARr:sequence;n:integer）;（展-•个职心d:=l;pos（-1];=1;pos[11i;exchanged：*true:WHILEexchangedDO[gchmged;、felse;whilei<>pos（dJDO|IF（r[i]-r[i+dl）*d>0THEN[r[i]与r[i+d]交换；exchanged:=true;];i:=i+d;pos（d）:=pos[d]--d;i:=pos（d];d:=-d;ENDP;30、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序？对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。weight给定设计31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，一棵二叉树T，采用二叉链表存储，节点结构为：weight给定设计right其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针,求T的WPL的算法。要求：（1） 给出算法的基本设计思想。（2） 使用C或C++语言，给出二叉树结点的数据类型定义。（3） 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。五、算法设计题32、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A〜Z这26个字母和0〜9这10个数字）。33、对给定关键字序号j（1<j<n），要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找（要求用最少的时

间和最少的空间）。例如：给定无序关键字{7,5,1,6,2,8,9,3},当j=4时，找到的关键字应是5。34、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法（注：已知树中的结点数）。35、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注：向量d可视为循环表），其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分二路插入。编写实现2-路插入排序算法。参考答案一、选择题1、 【答案】C2、 【答案】A3、 【答案】C4、 【答案】B5、 【答案】C6、 【答案】C7、 【答案】A8、 【答案】C9、 【答案】C10、 【答案】C二、 填空题11、 【答案】2(N-1)12、 【答案】3;(10,7,-9,0,47,23,1,8,98,36)@13、 【答案】提高查找速度14、 【答案】有穷性；确定性；可行性15、 【答案】随机16、 【答案】0;n+1;top[1]+1=top[2]17、 【答案】’xyxyxywwy'18、 【答案】FEGHDCB;BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。三、 判断题

19、【答案】X20、【答案】X21、【答案】X22、【答案】/23、【答案】/24、【答案】X25、【答案】/26、【答案】X27、【答案】/28、【答案】/四、简答题29、 答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：12,23,35,16,25,36,19, 21, 16, 47第二趟：12,16, 23,35, 16, 25, 36, 19, 21, 47第三趟：12,16,23, 16, 25, 35,19,21,36,47 第四趟：12, 16, 16, 23, 19, 25,35,21,36,47第五趟：12, 16,16, 19, 23, 25, 21,35, 36, 47 第六趟：12, 16, 16, 19, 21,23,25,35, 36, 47 第七趟：12, 16, 16, 19, 21,23, 25, 35, 36, 4730、 答：n个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j趟起泡排序要进行n-j次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记flag的使用。int 〃£lag用作控制标记while(j<n&&flag)〃j是起泡排序靖览，景多n-1趣{flag=O; 〃设标记，若本超不发生交换，本靖起泡排序后，集法结束for(i=l;i<=n-j;i++)if(r(i]>r(i+l]) r[i]<—>r(i+l] 了交换舟要.进行卜'趟31、答：(1)算法的基本思路是利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。

(2)typedefstructBiNodeintweight;部值structBiNode*left:左孩子指针structBiNode*right;右孩子指针}BiNode,*BiTree:具体算法实现如下：intCalc^?L(BiTreeBTintheight){jf(BT=NJLL)如果当前节点为空节点return0;如果当前节点的左右孩子节点都为空，即当前节点为叶子节点；直接返回当前节点的WPL!BT->right)returnBT.weight*height;•如果当前节点不是叶子节点，则对当前节点的左右子树遂行递归，返回左右子树WPL之和elsereturnCalcVTLfBT^left,height-1)十CakWPL(BT>righLheight-1);五、算法设计题32、答：算法如下：voidcount()//统计输入宇停串中数字宇符和字母宇符的个数{intlfnun[36];ch^rch；for(i-0?i<36；i++)num[i]=0?//初始化while((ch=getchar())!='#')〃'#'强示输入字符串结束if(ch>=F0'4.ich<='9')-(i=ch-48;nunn(iJ++;}' 〃数字字待elseif(ch.>=*A'&&ch<='z'){L=ch-65+10;num[i]++;)//字母字符for(i=0;i<10；i++) //输出数字字符的个数printf("数字％<1的个?4=%d\n",i,nuni[i]);for(i=10;i<36;i++)//米出字母字符的个数printf("字母字符％c的个数=%d\n",i+55,nuni[i]);)//算法结束。3333、答：算法如下：intpartition(ReeTypeA[]rintlrn){inti=l,j=n；x=A(i).key;i°l;while(i<j){while(i<j&&A[j].key>=x)j--:if(i<j)A[i++]=A(jj;while(i<j&&A[i].key<»x)i++;if(i<j)A[j—]=A[i];returni;voidFind_j(RecTypeA(),intn,intj);(i=partition(A,1fn);while(i!)if(i<j)i=quicksart(Ari+lrn);//花后■部分继绒进行划分61sei=guicksart(Rf 〃花前半部分继续进彳i■划分34、答：算法如下：intPepth(PTreet) 〃求以双亲表示法作为存储结构的树的深度(intmaxdepth^O;for(i=l;i<at.n.；!+■♦-)(teinp=0:f=i;while(f>0}(tempi;f=t.nodes(f] }//深度加L并取新的双亲if(temp>maxdepth)maxdepth»temp; //破大深度更新return(maxdepth);,/返回树的深度}//结束Depth35、答：算法如下：voidBilnsertsortfRecTypeR[),intn)〃二路插入排序的算法{intd[n+l]; //辅助存牌d[1;first=»l;final'l^for(i=2;i<an;i++).key>=d(lj.key)//播人后部(low=l;high^final;while(low<»high) 〃折半查找插入位置low+higb)/2;if(R(i].key<d(m].key)high=m-l;elselow-m+l?}//whilefor(j-final;j>=high+l;j—)d[j+l]=d[j];//移动元素d(high+l]=R(i];final++;//插入有序位置}〃ifelse〃播入前部{if(firs