2022年武汉纺织大学外经贸学院计算机科学与技术专业《数据结构与算法精品.pdf

2022年武汉纺织大学外经贸学院计算机科学与技术专业《数据结构与算法》 科目期末试卷A （有答案） 一、选择题 1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一 的关系，则选择好的（ ）方法是哈希文件的关键。 A.哈希函数 B.除余法中的质数 C.冲突处理 D.哈希函数和冲突处理 2、将两个各有 N个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A.N B.2N-1 C.2N D.N-1 3、线性表的顺序存储结构是一种（ ）。 A.随机存取的存储结构 顺序存取的存储结B. 构 C.索引存取的存储结构 存取的存储结D.Hash构 4、循环队列 A[0..m-1]存放其元素值，用 front和 rear分别表示队头和队尾，则当前队列中的元素 数是（ ）。 A. （rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 5、下面关于串的叙述中，不正确的是（ ）。 A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中， 每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。 Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅 Ⅰ、Ⅲ、Ⅳ ．仅BⅠ、Ⅱ、Ⅲ ．C仅Ⅱ、Ⅲ、Ⅳ ．仅DⅢ、Ⅳ、Ⅴ 7、下列叙述中，不符合 m 阶B树定义要求的是（ ）。 A．根结点最多有 m棵子树 ．所有叶B 结点都在同一层上 C．各结点内关键字均升序或降序排列 ．叶D 结点之间通过指针链接 8、设X是树T 中的一个非根结点，B是 T所对应的二叉树。在 B 中，X 是其双亲的右孩子，下列 结论正确的是（ ）。 A.在树T 中，X是其双亲的第一个孩子 B.在树T 中，X 一定无右兄弟 C.在树T 中，X 一定是叶结点 D.在树T 中，X 一定有左兄弟 9、下述二叉树中，哪一种满足性质 ：从任一结点出发到根的路径上所经过的结点序列按其关键字 有序（ ）。 A.二叉排序树 哈夫曼树 B. 树 堆 C.AVL D. 10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。 A. （100，80，90，60，120，110，130） B. （100，120，110，130，80，60，90） C. （100，60，80，90，20，110，130） D. （100，80，60，90，120，130，110） 二、填空题 11、顺序查找 n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视 哨时，若查找失败，则比较关键字的次数为______。 12、对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充 算法中标出的空白处，完成其功能。 13、如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算 法空格处填上正确的语句。设线索二叉树的结点数据结构为 （lflag ，left，data，right，rflag）， 其中：lflag=0，left 指向其左孩子，lflag=1，left 指向其前驱 ；rflag=0，right 指向其右孩子， rflag=1，right 指向其后继。 14、设有两个算法在同一机器上运行，其执行时闻分别为 100n2和2n，要使前者快于后者，n 至 少为______。 15、在一棵 m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有 的关键字的个数是______ ；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关 键字的个数是______。 16、模式串 P=‘abaabcac’的 next 函数值序列为______。