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

2022年北京工商大学嘉华学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。A.串树广B.义表栈C.D.2、下列排序算法中，占用辅助空间最多的是（）。A.归并排序快速排序B.希C.尔排序D.堆排序3、连续存储设计时，存储单元的地址（）。A.一定连续一定不B.连续C.不一定连续D.部分连续，部分不连续4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.46、循环队列放在一维数组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、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟9、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。A.选择排序起泡排序B.插入排序C.堆排序D.二、填空题11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。13、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。15、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。18、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、倒排文件是对次关键字建立索引。（）21、串是一种数据对象和操作都特殊的线性表。（）22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）25、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（）26、顺序存储结构的主要缺点是不利于插入或删除操作。（）27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）四、简答题29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’（1）计算模式p的nextval函数值。（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。30、写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。31、二叉树的带权路