2022年吉林大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。A.5B.6C.8D.92、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modMB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modMD．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ．B仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、Ⅳ．D仅Ⅲ、Ⅳ、Ⅴ8、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。A.选择排序B.起泡排序C.插入排序D.堆排序二、填空题11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。12、在哈希函数H（key）=key%p中，p值最好取______。13、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。注：(1)图的顶点号从0开始计。(2)indegree是有n个分量的一维数组，放顶点的入度，(3)函数crein用于计算顶点入度。(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。14、数据结构中评价算法的两个重要指标是______。15、VSAM系统是由______、______、______构成的。16、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。17、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（S，t），LEN（t）+1））；ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。18、模式串P=‘abaabcac’的next函数值序列为______。三、判断题19、对磁带机而言，ISAM是一种方便的文件组织方法（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、广义表（（（a，b，c），d，e，f））的长度是4。（）22、稀疏矩阵压缩存储后，必会失去随机存取功能。（）23、树形结构中元素之间存在一对多的关系。（）24、二叉树是一般树的特殊情形。（）25、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，