2022年长春光华学院计算机科学与技术专业《数据结构与算法》科目期末试精品.pdf

2022年长春光华学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。A.head（tail（LS））（head（LS））B.tailC.head（tail（head（tail（LS））））（tail（tailD.head（head（LS））））2、下列排序算法中，占用辅助空间最多的是（）。A.归并排序快速排序B.希C.尔排序D.堆排序3、以下与数据的存储结构无关的术语是（）。A.循环队列链表B.哈希表C.栈D.4、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.45、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、循环队列放在一维数组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、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只有BⅡ．ⅠC和Ⅱ．ⅠD和Ⅲ8、一个具有1025个结点的二叉树的高h为（）。A.11B.10至1025之间C.11至1024之间D.109、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBA不定C.CBEDFAD.10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序起泡排序B.简单选择C.排序快速排序D.二、填空题11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。13、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子，rflag=1，right指向其后继。14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。18、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、数组不适合作为任何二叉树的存储结构。（）22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）25、为了很方便地插入和删除数据，可以使用双向链表存放数据。（）26、在任何情况下，归并排序都比简单插入排序。（快）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、无环有向图才能进行拓扑排序。（）