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

2022年广东海洋大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.45、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝27、循环队列放在一维数组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、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。12、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。13、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。14、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：______15、文件可按其记录的类型不同而分成两类，即______和______文件。16、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。17、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。18、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。三、判断题19、倒排文件是对次关键字建立索引。（）20、对磁带机而言，ISAM是一种方便的文件组织方法（）21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）22、循环队列也存在空间溢出问题。（）23、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）24、二叉树是一般树的特殊情形。（）25、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（）26、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）28、无环有向图才能进行拓扑排序。（）四、简答题29、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树。（2）若查找元素54，需依次与哪些元素比较?（3）若查找元素90，需依次与哪些元素比较?（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。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、若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。33、给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。34、在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。35、编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。

参考答案一、选择题1、【答案】A2、【答案】C3、【答案】A4、【答案】C5、【答案】A6、【答案】C7、【答案】A8、【答案】D9、【答案】D10、【答案】A二、填空题11、【答案】2(N-1)12、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@13、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p14、【答案】py->next=px->next；px->next=py15、【答案】操作系统文件；数据库16、【答案】【解析】最大的分支结点是最后一个叶子结点的父结点。17、【答案】9174；878818、【答案】0；n+1；top[1]+1=top[2]三、判断题19、【答案】√20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（1）判定树如图所示：（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。（3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。（4）30、答：森林转换为二叉树分以下三步：连线（将兄弟结点相连，各树的根看作兄弟）。切线（保留最左边子女为独生子女，将其他子女分支切掉）。旋转（以最左边树的根为轴，顺时针向下旋转45度）。所以由上面三棵树转换得到的二叉树如图所示：31、答：（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函数的时间复杂度分别为O（p/2）、