2023年汉江师范学院网络工程专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2023年汉江师范学院网络工程专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 2、下述文件中适合于磁带存储的是（　　）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 3、线性表的顺序存储结构是一种（　　）。 A.随机存取的存储结构 B.顺序存取的存储结构 C.索引存取的存储结构 D.Hash存取的存储结构 4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（　　）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。 7、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（　　）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（　　）。 A.每次分区后，先处理较短的部分 B.每次分区后，先处理较长的部分 C.与算法每次分区后的处理顺序无关 D.以上三者都不对 二、填空题 11、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 12、阅读下列程序，指出其功能，并写出空格处应填上的语句。 13、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。 14、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 15、建立索引文件的目的是______。 16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （1） 存放该数组至少需要的单元数是______。 （2） 存放数组的第8列的所有元素至少需要的单元数______。 （3） 数组按列存储时，元素A[5，8]的起始地址是______。 17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B 中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始） 18、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 三、判断题 19、倒排文件是对次关键字建立索引。（　　） 20、倒排文件的目的是为了多关键字查找。（　　） 21、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　） 22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（　　） 23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　） 24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（　　） 25、抽象数据类型与计算机内部表示和实现无关。（　　） 26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（　　） 27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们