2022年南京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第1页
2022年南京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第2页
2022年南京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第3页
2022年南京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第4页
2022年南京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第5页
已阅读5页,还剩5页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2022年南京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)一、选择题1、下述文件中适合于磁带存储的是()。A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、下列排序算法中,占用辅助空间最多的是()。A.归并排序B.快速排序C.希尔排序D.堆排序3、单链表中,增加一个头结点是为了()。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、循环队列A[0..m-1]存放其元素值,用front和rear分别表示队头和队尾,则当前队列中的元素数是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中,正确的是()A.含有一个或多个空格字符的串称为空格串B.对n(n>0)个顶点的网,求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中,不能构成折半查找中关键字比较序列的是()。A.500,200,450,180B.500,450,200,180C.180,500,200,450D.180,200,500,4507、已知关键字序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后的小根堆是()。A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,198、一个具有1025个结点的二叉树的高h为()。A.11B.10C.11至1025之间D.10至1024之间9、设X是树T中的一个非根结点,B是T所对应的二叉树。在B中,X是其双亲的右孩子,下列结论正确的是()。A.在树T中,X是其双亲的第一个孩子B.在树T中,X一定无右兄弟C.在树T中,X一定是叶结点D.在树T中,X一定有左兄弟10、对序列{15,9,7,8,20,-1,4}用希尔排序方法排序,经一趟后序列变为{15,-1,4,8,20,9,7}则该次采用的增量是()。A.1B.4C.3D.2二、填空题11、在有n个顶点的有向图中,每个顶点的度最大可达______。12、N个顶点的连通图用邻接矩阵表示时,该矩阵至少有______个非零元素。13、在单链表L中,指针P所指结点有后继结点的条件是______。14、关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),要按照关键码值递增的次序进行排序,若采用初始步长为4的希尔排序法,则一趟扫描的结果是______;若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是______。15、设有两个算法在同一机器上运行,其执行时闻分别为100n2和2n,要使前者快于后者,n至少为______。16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支(非终端)结点和______个叶子,该满二叉树的深度为______。17、设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位,从首地址2000开始连续存放在主内存里,主内存字长为16位,那么(1) 存放该数组至少需要的单元数是______。(2) 存放数组的第8列的所有元素至少需要的单元数______。(3) 数组按列存储时,元素A[5,8]的起始地址是______。18、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中,则非零元素A9.9在B中的存储位置k=______。(注:矩阵元素下标从1开始)三、判断题19、对磁带机而言,ISAM是一种方便的文件组织方法()20、直接访问文件也能顺序访问,只是一般效率不高。()21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。()22、一个广义表可以为其他广义表所共享。()23、深度为k的二叉树中结点总数小于等于2k-1。()24、树形结构中元素之间存在一对多的关系。()25、外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。()26、快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。()27、连通图上各边权值均不相同,则该图的最小生成树是唯一的。()28、对两棵具有相同关键字集合的而形状不同的二叉排序树,按中序遍历它们得到的序列的顺序却是一致的。()四、简答题29、写出下列排序算法的基本思想,并写出对序列(23,12,35,47,16,25,36,19,21,16)进行排序时每一趟的结果。30、阅读下面的算法,说明算法实现的功能。31、已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)(1)画出这六大城市的交通网络图。(2)画出该图的邻接表表示法。(3)画出该图按权值递增的顺序来构造的最小(代价)生成树。五、算法设计题32、以顺序存储结构表示串,设计算法。求串s中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。33、试编写一算法对二叉树按前序线索化。34、编写递归算法,从大到小输出给定二叉排序树中所有关踺字不小于x的数据元素。要求你的算法的时间复杂度为O(log2(x+m)),其中,2为排序树中所含结点数,m为输出的关键字个数。35、编写一算法,利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表,算法返回头结点的地址。

参考答案一、选择题1、【答案】A2、【答案】A3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】C9、【答案】D10、【答案】B二、填空题11、【答案】2(n-1)12、【答案】2(N-1)13、【答案】P->next!=NULL14、【答案】(Q,A,C,S,Q,D,F,X,R,H,M,Y);(F,H,C,D,a,A,M,Q,R,S,Y,X)15、【答案】1516、【答案】【解析】满二叉树没有度为1的结点,度为0的结点等于度为2的结点个数+1。17、【答案】270;27;220418、【答案】93三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√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、答:本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2,head2最后一个结点的链域指向head1,head1为结果循环链表的指针。31、答:(1)这六大城市的交通网络图如图所示:(2)该图的邻接表表示法如图所示:

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论