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

2022年南京航空航天大学金城学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序堆排序B.归并排序C.直接插入排序D.3、单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点标识表结点中首结B.点的位置C.方便运算的实现说明单链表是线性表的链式存D.储4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只有BⅡ．ⅠC和Ⅱ．ⅠD和Ⅲ8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。A.二叉排序树哈夫曼树B.树堆C.AVLD.9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.logn（nB.－1）/2C.logn+1（D.n＋1）/22210、下列二叉排序树中查找效率最高的是（）。A.平衡二叉树B.二叉查找树C.没有左子树的二叉排序树D.没有右子树的二叉排序树二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。12、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。13、VSAM系统是由______、______、______构成的。14、在单链表L中，指针P所指结点有后继结点的条件是______。15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。17、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（S，t），LEN（t）+1））；ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、倒排文件是对次关键字建立索引。（）21、数组不适合作为任何二叉树的存储结构。（）22、二维以上的数组其实是一种特殊的广义表。（）23、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（）24、对于有n个结点的二叉树，其高度为log2n。（）25、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）26、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）27、B-树中所有结点的平衡因子都为零。（）28、当改变网上一关某键路径上任一关键活动后，必将产生不同的关键路径。（）四、简答题29、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。30、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。（）排序的结果为：12，13，15，18，20，60（）