2022年江南大学计算机科学与技术专业《数据结构与算法》科目期末试卷人（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序堆排序归并排序直接插入排序2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入选择希尔二路归并D.3、单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点标识表结点中首结点的位置C.方便运算的实现说明单链表是线座表的链式存储4、下列关于AOE网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.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.二路归并排序A,仅I、III、W.仅BI、II、III.仅II、III、W8、有n(n>0)个分支结点的满二叉树的深度是(A.n2-1B.log2(n+1)+1C.log2(n+1)D.log2(n-l)9、一个具有1025个结点的二叉树的高h为()。A.11B.1C至1025之间C.11至1024之间D.1010、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为l,则应作()型调整以使其平衡A.LLB.LRC.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,则它的后序序列是。设上述二叉树是由某棵树转换而成，则该树的前序序列是。)。.仅III、W、V三、判断题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个元素采用起泡排序法进行排序，通常需要进行多少趟排...
