2022年浙大城市学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年浙大城市学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.403、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341566、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A．只有eB．有e、bC．有e、cD．无法确定7、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序B.起泡排序C.简单选择排序D.快速排序二、填空题11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。13、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输出。14、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。15、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）21、数组不适合作为任何二叉树的存储结构。（）22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：ai>ai+1>…>an。（）23、树形结构中元素之间存在一对多的关系。（）24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）25、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（）26、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）27、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（）28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（）四、简答题29、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。30、写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。31、设将n（n＞1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中存有的序列循左移P（0＜P＜n）个位置，即将R中的数据由（X0，X1，…，Xn－1）变换为（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 给出算法的基本设计思想。（2） 根据设计思想，采用C或C＋＋或JAVA语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。五、算法设计题32、假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。33、用邻接多重表存储结构，编写FIRST-ADJ(G，V)函数，函数返回值为第一个邻接点，若V没有邻接点，返回零。34、已知指针p指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的父亲结点q。设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG，LLINK，INFO，RLlNK，RTAG），且规定线索树的最左下结点的LLINK域和最右下结点的RLINKt域指向表头。35、编程：假设以数组Q[m]存放循环队列中的元素，同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化（initqueue），插入（enqueue）和删除（dequeue）元素的操作。

参考答案一、选择题1、【答案】D2、【答案】B3、【答案】B4、【答案】B5、【答案】C6、【答案】A7、【答案】A8、【答案】A9、【答案】D10、【答案】A二、填空题11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】n(n-1)/213、【答案】有穷性；确定性；可行性14、【答案】稳定15、【答案】【解析】m阶B-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少16、【答案】9174；878817、【答案】O（m+n）18、【答案】33三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】×23、【答案】√24、【答案】√25、【答案】×26、【答案】√27、【答案】×28、【答案】√四、简答题29、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：30、答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：12，23，35，16，25，36，19，21，16，47第二趟：12，16，23，35，16，25，36，19，21，47第三趟：12，16，23，16，25，35，19，21，36，47第四趟：12，16，16，23，19，25，35，21，36，47第五趟：12，16，16，19，23，25，21，35，36，47第六趟：12，16，16，19，21，23，25，35，36，47第七趟：12，16，16，19，21，23，25，35，36，4731、答：（1）算法的基本设计思想：先将n个数据由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再将数组R中的前n－P个数和后P个数分别原地逆置，最终得到结果xp，xp＋1，…，xn－1，x0，x1，…，xp－1。（2）用C语言算法描述如下：（3）说明算法的复杂性：上述算法中3个Reverse函数