2022年江南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).docx
《2022年江南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).docx》由会员分享,可在线阅读,更多相关《2022年江南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).docx(11页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、2022年江南大学计算机科学与技术专业数据结构与算法科目期末试卷人(有答案)一、选择题1、若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是()。A. 快速排序堆排序归并排序直接插入排序2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为()排序法。A.插入选择希尔二路归并D.3、单链表中,增加一个头结点是为了()。A.使单链表至少有一个结点标识表结点中首结点的位置C.方便运算的实现说明单链表是线座表的链式存储4、下列关于AOE网的叙述中,不正确的是()。A. 关键活动不按期完成就会影响整个
2、工程的完成时间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、排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列
3、排序方法中,每一趟排序结束时都至少能够确定一个元素最终位置的方法是()。i.简单选择排序n.希尔排序ill.快速排序w.堆排V.二路归并排序.仅III、W、V)。A,仅I、III、W.仅BI、II、III.仅II、III、W8、有n(n0)个分支结点的满二叉树的深度是(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,则应作
4、()型调整以使其平衡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)表示,两栈顶指针为top1与top2,贝U当栈1空时,top1为,栈2空时,top为,栈满时为
5、。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、二维以上的数组其实是一种特殊的广义表。
6、()23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。()24、用一维数组存储二叉树时,总是以前序遍历顺序存储结点。()25、若中序遍历平衡的二叉排序树,可得到排好序的关键码序列。()26、数据元素是数据的最小单位。()27、B-树中所有结点的平衡因子都为零。()28、对两棵具有相同关键字集合的而形状不同的二叉排序树,按中序遍历它们得到的序列的顺序却是一致的。()四、简答题29、写出下列排序算法的基本思想,并写出对序列(23,12,35,47,16,25,36,19,21,16)进行排序时每一趟的结果。PROCbbsort(VARr:sequence;n:integer);(展-个职
7、心d:=l;pos(-1;=1;pos11i;exchanged:*true:WHILEexchangedDOgchmged;、felse;whileipos(dJDO|IF(ri-ri+dl)*d0THENri与ri+d交换;exchanged:=true;i:=i+d;pos(d):=posd-d;i:=pos(d;d:=-d;ENDP;30、设有n个元素采用起泡排序法进行排序,通常需要进行多少趟排序?对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件,有可能使起泡趟数可以减少并且能完成排序。weight给定设计31、二叉树的带权路径长度(WPL)是二叉树中所有叶结点
8、的带权路径长度之和,一棵二叉树T,采用二叉链表存储,节点结构为:right其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针,求T的WPL的算法。要求:(1)给出算法的基本设计思想。(2)使用C或C+语言,给出二叉树结点的数据类型定义。(3)根据设计思想,采用C或C+语言描述算法,关键之处给出注释。五、算法设计题32、编写程序,统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为AZ这26个字母和09这10个数字)。33、对给定关键字序号j(1jn),要求在无序记录A1.n中找到关键字从小到大排在第j位上的记录,写一个算法利用快速排序的划
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法 2022 江南 大学计算机 科学 技术 专业 数据结构 算法 科目 期末试卷 答案
限制150内