2023年潮汕职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年潮汕职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、下述文件中适合于磁带存储的是（　　）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 3、链表不具有的特点是（　　）。 A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比 4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛V1，V2，V1，V3，V1，V4，V2，V5，V3，V5， V3，V6，V4，V6，V5，V7，V6，V7｝，G的拓扑序列是（　　）。 A.V1，V3，V4，V6，V2，V5，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7 5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 6、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1） 8、在下述结论中，正确的有（　　）。 ①只有一个结点的二叉树的度为0。 ②二叉树的度为2。 ③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.⑦③④ C.②④ D.①④ 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、下面关于B和B+树的叙述中，不正确的是（　　） A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构 C.B树和B+树都能有效地支持顺序检索 D.B树和B+树都能有效地支持随机检索 二、填空题 11、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用a，b，d 三元组表示弧a，b及弧上的权d。E(G)为E(G)=｛0，5，100，0， 2，10，1，2，5，0，4，30，4，5，60，3，5，10，2， 3，50，4，3，20｝，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。 13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。 14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。 15、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子，