2023年金陵科技学院数据科学与大数据技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2023年金陵科技学院数据科学与大数据技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、下列排序算法中，占用辅助空间最多的是（　　）。 A.归并排序 B.快速排序 C.希尔排序D.堆排序 2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（　　）。 A.a，b，e，c，d，f B.a，c，f,e，b，d C.a，e，b，c，f, d D.a，e，d，f，c，b 3、静态链表中指针表示的是（　　）。 A.下一元素的地址 B.内存储器的地址 C.下一元素在数组中的位置 D.左链或右链指向的元素的地址 4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（　　）。 A.h-next=s B.s-next=h C.s-next=h;h-next=s D.s-next=h-next;h-next=s 5、在用邻接表表示图时，拓扑排序算法时间复杂度为（　　）。 A.O(n) B.O(n+e) C.O(n*n) D.O(n*n*n) 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（　　）。 A．只有e B．有e、b C．有e、c D．无法确定 8、一个具有1025个结点的二叉树的高h为（　　）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（　　）。 A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 10、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（　　）。 A.选择排序法 B.插入排序法 C.快速排序法 D.堆排序法 二、填空题 11、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 12、在有n个顶点的有向图中，每个顶点的度最大可达______。 13、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete_subtree（T，A），首先在二叉排序树 T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。 15、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：(1)图的顶点号从0开始计。 (2)indegree是有n个分量的一维数组，放顶点的入度， (3)函数crein用于计算顶点入度。 (4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。 16、模式串P=‘abaabcac’的next函数值序列为______。 17、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时， top[2]为______，栈满时为______。 18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。 三、判断题 19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（　　） 20、倒排文件是对次关键字建立索引。（　　） 21