2023年甘肃畜牧工程职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷B(有答案).docx

2023年甘肃畜牧工程职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷B(有答案).docx

  1. 1、本文档共13页,可阅读全部内容。
  2. 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2023年甘肃畜牧工程职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷B(有答案) 一、选择题 1、若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是(  )。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 2、用有向无环图描述表达式(A+B)*((A+B)//A),至少需要顶点的数目为(  )。 A.5 B.6 C.8 D.9 3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值,为节省时间应采用的存储方式(  )。 A.单链表 B.双向链表 C.单循环链表 D.顺序表 4、已知串S=aaab,其next数组值为(  )。 A.0123 B.1123 C.1231 D.1211 5、在用邻接表表示图时,拓扑排序算法时间复杂度为(  )。 A.O(n) B.O(n+e) C.O(n*n) D.O(n*n*n) 6、若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则不可能得到的出栈序列是(  )。 7、下列叙述中,不符合m阶B树定义要求的是(  )。 A.根结点最多有m棵子树 B.所有叶结点都在同一层上 C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 8、一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足(  )。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 9、有n(n0)个分支结点的满二叉树的深度是(  )。 A.n2-1 B.log2(n+1)+1 C.log2(n+1) D.log2(n-l) 10、在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是(  )。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.快速排序 二、填空题 11、在有n个顶点的有向图中,每个顶点的度最大可达______。 12、设m、n均为自然数,m可表示为一些不超过n的自然数之和,f(m, n)为这种表示方式的数目。例f(5,3)=5,有5种表示方式:3+2, 3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。 ①以下是该函数的程序段,请将未完成的部分填入,使之完整。 ②执行程序,f(6,4)=______。 13、在单链表L中,指针P所指结点有后继结点的条件是______。 14、文件由______组成;记录由______组成。 15、VSAM(虚拟存储存取方法)文件的优点是:动态地______,不需要文件进行______,并能较快地______进行查找。 16、设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位,从首地址2000开始连续存放在主内存里,主内存字长为16位,那么 (1) 存放该数组至少需要的单元数是______。 (2) 存放数组的第8列的所有元素至少需要的单元数______。 (3) 数组按列存储时,元素A[5,8]的起始地址是______。 17、设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储: a11=1),则a85的地址为______。 18、设T和P是两个给定的串,在T中寻找等于P的子串的过程称为______,又称P为______。 三、判断题 19、倒排序文件的优点是维护简单。(  ) 20、直接访问文件也能顺序访问,只是一般效率不高。(  ) 21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。(  ) 22、队列和栈都是运算受限的线性表,只允许在表的两端进行运算。(  ) 23、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。(  ) 24、任何二叉树的后序线索树进行后序遍历时都必须用栈。(  ) 25、在外部排序过程中,对长度为n的初始序列进行“置换-选择”排序时,可以得到的最大初始有序段的长度不超过n/2。(  ) 26、顺序存储方式的优点是存储密度大,且插入、删除运算效率高。 (  ) 27、B-树中所有结点的平衡因子都为零。(  ) 28、在动态存储管理系统中做空间分配时,最佳适配法与最先适配法相比,前者容易增加闲置空间的碎片。(  ) 四、简答题 29、给出一组关键字:29,18,25,47,58,12,51,10,分别写出按下列各种排序方法进行排序时的变化过程: (1) 归并排序,每归并一次书写一个次序。 (2) 快速排序,每划分一次书写一个次序。 (3) 堆排序,先建成一个堆,然后每从堆顶取下一个元素后,将堆调整一次。 30、请写出应填入下列叙述中(  )内的正确

您可能关注的文档

文档评论(0)

xx_zk + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档