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

2022年上海海洋大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。A.串B.树C.广义表D.栈2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.NB.2N-1C.2ND.N-13、单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、下列关于AOE网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A．只有eB．有e、bC．有e、cD．无法确定7、循环队列放在一维数组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）8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.21510、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）C.（40，38，46，56，79，84）D.（40，38，46，84，56，79）二、填空题11、在哈希函数H（key）=key%p中，p值最好取______。12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。13、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：______14、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。15、数据结构中评价算法的两个重要指标是______。16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。17、模式串P=‘abaabcac’的next函数值序列为______。18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、倒排文件是对次关键字建立索引。（）21、循环队列也存在空间溢出问题。（）22、在链队列中，即使不设置尾指针也能进行入队操作。（）23、任何二叉树的后序线索树进行后序遍历时都必须用栈。（）24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）25、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（）26、算法的优劣与算法描述语言无关，但与所用计算机有关。（）27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）28、无环有向图才能进行拓扑排序。（）四、简答题29、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。其中：li表示第i个叶结点所在的层号（设根结点所在层号为1）。30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。31、设二叉树BT的存储结构如表：其中BT为树根结点的指针，其值为6，Lchild、Rchild分别为结点的左、右孩子指针域data为结点的数据域。试完成下列各题：（1）画出二叉树BT逻辑结构。（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列。（3）画出二叉树的后序线索树。五、算法设计题32、设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于l～100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=11时，则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O（1）。33、已知二叉树丁的结点形式为（llink，data，count，rlink），在树中查找值为X的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。34、按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)35、在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，35，42．滤掉3个元素。

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】C4、【答案】B5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】B10、【答案】C二、填空题11、【答案】小于等于表长的最大素数或不包含小于20的质因子的合数12、【答案】起泡；快速13、【答案】py->next=px->next；px->next=py14、【答案】归并；堆15、【答案】算法的时间复杂度和空间复杂度16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。17、【答案】0112231218、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。三、判断题19、【答案】√20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。（2）证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。证毕。30、答：森林转换为二叉树分以下三步：连线（将兄弟结点相连，各树的根看作兄弟）。切线（保留最左边子女为独生子女，将其他子女分支切掉）。旋转（以最左边树的根为