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

2022年兰州大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。A.单链表B.双向链表C.单循环链表D.顺序表4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.46、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。A.1B.4C.3D.2二、填空题11、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d>三元组表示弧<a，b>及弧上的权d。E(G)为E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>｝，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。12、属于不稳定排序的有______。13、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。14、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有______检索和______检索。15、外排序的基本操作过程是______和______。16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。18、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、倒排文件是对次关键字建立索引。（）21、数组不适合作为任何二叉树的存储结构。（）22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）23、对于有n个结点的二叉树，其高度为log2n。（）24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）25、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（）26、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）28、B-树中所有结点的平衡因子都为零。（）四、简答题29、写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。30、调用下列C函数f（n），回答下列问题：（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。C函数：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、请用流程图或高级语言表示算法。已知有向图有n个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的<vi，vj>(以其中之一为0标志结束)，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点(其结点数值域从1到n)。33、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。34、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法（注：已知树中的结点数）。35、已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false。

参考答案一、选择题1、【答案】D2、【答案】A3、【答案】D4、【答案】C5、【答案】C6、【答案】A7、【答案】A8、【答案】A9、【答案】C10、【答案】B二、填空题11、【答案】50；412、【答案】希尔排序、简单选择排序、快速排序、堆排序等13、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。14、【答案】关键字；记录号；记录号；顺序；直接15、【答案】生成有序归并段（顺串）；归并16、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。17、【答案】O（m+n）18、【答案】93三、判断题19、【答案】×20、【答案】√21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】√26、【答案】√27、【答案】×28、【答案】√四、简答题29、答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：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，4730、答：（1）第一层for循环判断n+1次，往下执行n次，第二层for执行次数为（n+（n-1）+（n-2）+…+1），第三层循环体受第一层循环和第二层循环的控制，其执行次数如表1-1所示。执行次数为f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5对，f（5）=55，执行过程中，输出结果为：31、答：（1）算法的基本设计思想：先将n个数据由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再将数组R中的前n－P个数和后