2022年中国民航大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2022年中国民航大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、n个结点的完全有向图含有边的数目（　　）。 A.n*n B.n(n+1) C.n/2 D.n*(n-1) 2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（　　）。 A.60 B.66 C.18000 D.33 3、以下数据结构中，（　　）是非线性数据结构。 A.树 B.字符串 C.队 D.栈 4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（　　）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（　　）。 A.543612 B.453126 C.346521 D.234156 6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（　　）。 A．只有e B．有e、b C．有e、c D．无法确定 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。 Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（　　）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（　　）。 A.（38，40，46，56，79，84） B.（40，38，46，79，56，84） C.（40，38，46，56，79，84） D.（40，38，46，84，56，79） 二、填空题 11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 13、在单链表L中，指针P所指结点有后继结点的条件是______。 14、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。 15、一个算法具有5个特性： ______、______、______、有零个或多个输入、有一个或多个输出。 16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 17、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。 18、模式串P=‘abaabcac’的next函数值序列为______。 三、判断题 19、倒排文件的目的是为了多关键字查找。（　　） 20、倒排文件是对次关键字建立索引。（　　） 21、广义表（（（a，b，c），d，e，f））的长度是4。（　　） 22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（　　） 23、二叉树是一般树的特殊情形。（　　） 24、对于有n个结点的二叉树，其高度为log2n。（　　） 25、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （　　） 26、在任何情况下，归并排序都比简单插入排序快。（　　） 27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（　　） 28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（　　） 四、简答题 29、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。 30、下面程序段的时间复杂度是什么？ 31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。 要求： （1）写出图G的邻接矩阵A。 （2）画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。 五、算法设计题 32、在一个循环链队中只有尾指