精品滨江学院计算机科学与技术专业《数据结构与算法》科目期末试卷精品.pdf

2022年浙江中医药大学滨江学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)3、算法的计算量的大小称为计算的（）。A.效率复杂性B.现实性C.难度D.4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、下面关于串的叙述中，不正确的是（）。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、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树．所有叶B结点都在同一层上C．各结点内关键字均升序或降序排列．叶D结点之间通过指针链接8、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log（n+1）+12C.log（n+1）2D.log（n-l）210、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。A.1B.4C.3D.2二、填空题11、在哈希函数H（key）=key%p中，p值最好取______。12、在有n个顶点的有向图中，每个顶点的度最大可达______。13、VSAM系统是由______、______、______构成的。14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。15、文件可按其记录的类型不同而分成两类，即______和______文件。16、阅读下列程序说明和程序，填充程序中的______。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。18、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、稀疏矩阵压缩存储后，必会失去随机存取功能。（）22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：ai>ai+1>…>an。（）23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（）25、在任何情况下，归并排序都比简单插入排序快。（）26、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以