2022年汕头大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、算法的计算量的大小称为计算的（）。A.效率复B.杂性现实C.性D.难度4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341565、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ．B仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、Ⅳ．D仅Ⅲ、Ⅳ、Ⅴ7、循环队列放在一维数组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）8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.lognB.（n－1）/2C.logn+1D.（n＋1）/2229、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log（n+1）+12C.log（n+1）2D.log（n-l）210、下面关于B和B+树的叙述中，不正确的是（）A.B树和B+树都是平衡的多叉树树B.B和B+树都可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索二、填空题11、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。12、在有n个顶点的有向图中，每个顶点的度最大可达______。13、外排序的基本操作过程是______和______。14、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输出。15、VSAM系统是由______、______、______构成的。16、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。17、阅读下列程序说明和程序，填充程序中的______。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。18、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。三、判断题19、倒排文件是对次关键字建立索引。（）20、对磁带机而言，ISAM是一种方便的文件组织方法（）21、数组不适合作为任何二叉树的存储结构。（）22、循环队列也存在空间溢出问题。（）23、树形结构中元素之间存在一对多的关系。（）24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（）25、为了很方便地插入和删除数据，可以使用双向链表存放数据。（）26、在任何情况下，归并排序都比简单插入排序快。（）27、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）28、若一个有向图的邻接矩阵对角线以下元素