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

2023试卷A〔有答案〕一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为〔 〕。A.5B.6C.8D.92、下述文件中适合于磁带存储的是〔 〕。挨次文件索引文件C.哈希文件D.多关键字文件计时，存储单元的地址〔 〕。A.肯定连续B.肯定不连续C.不肯定D.局部连续，局部不连续4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行〔 〕。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，〔 〕。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、循环队列放在一维数A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进展入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，以下推断队空和队满的条件中，正确的选项是〔 〕。队空：end1＝＝end2；队满：end1＝＝〔end2＋1〕modM队空：end1＝＝end2；队满：end2＝＝〔end1＋1〕mod〔M－1〕队空：end2＝＝〔end1＋1〕modM；队满：end1＝＝〔end2＋1〕modM；队满：end2＝＝〔end1＋1〕mod〔M－1〕7、排序过程中，对尚未确定最终位置的全部元素进展一遍处理称为一趟排序。以下排序方法中，每一趟排序完毕时都至少能够确定一个元素最终位置的方法是〔〕。Ⅰ．简洁选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ81025个结点的二叉树的高h为〔〕。A.11B.10C.11 至1025之间D.10 至1024之间9、下述二叉树中，哪一种满足性质：从任一结点动身到根的路径上所经过的结点序列按其关键字有序〔〕。A.二叉排序树B. 哈夫曼树C.AVL 树D. 堆10、数据序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中的〔〕的两趟排序后的结果。A.选择排序B.起泡排序C.插入排序D. 堆排序二、填空题11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。12、假设用n表示图中顶点数目，则有 条边的无向图成为完全图。别是后序线索二叉树求给定结node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据构造为〔lflag，left，data，right，rflag〕，其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，rightrflag=1，right指向其后继。14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree〔T〕在对二叉排序树丁进展后序遍历时释放二又排序树T的全部结点；delete_subtree〔T，A〕，首先在二叉排序树T中查找A的结点，依据查找状况分别进展如下处理：〔1〕假设找不到值为A的结点，则返回根结点的地址〔2〕假设找到A的结点，则删除以此结点为根的子树，并释放此子树中的全部结点，假设值为A的结点是查找树的根结点，删除后变成空的二叉树，则null；否则返回根结点的地址。15、有序表为〔12，18，24，35，47，50，62，83，90，115，134〕当用二分法查找90时，需 次查找成功，查找47时 成功，查找100时，需 次才能确定不成功。16、一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是 。17、阅读以下程序说明和程序，填充程序中的 。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示〔编者略〕。本程序承受非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针tp。交换左、右子树的算法为：把根结点放入堆栈。当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。重复〔2〕直到堆栈为空时为止。经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是，而栈顶指针值是。设栈为挨次栈4个字节。三、推断题19、直接访问文件也能挨次访问，只是一般效率不高。〔 〕20、倒排文件是对次关键字建立索引。〔 〕21、在链队列中，即使不设置尾指针也能进展入队操作。〔 〕22、数组不适合作为任何二叉树的存储构造。〔 〕23、一棵树中的叶子数肯定等于与其对应的二叉树的叶子数。〔 〕24、树形构造中元素之间存在一对多的关系。〔 〕25、抽象数据类型与计算机内部表示和实现无关。〔 〕26、数据元素是数据的最小单位。〔 〕27、B-树中全部结点的平衡因子都为零。〔 〕28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。〔 〕四、简答题29、对于具有n个叶结点且全部非叶结点都有左、右孩子的二叉树。i试问这种二叉树的结点总数是多少?i1〕。

2-〔li-1〕=1。其中：li个叶结点所在的层号〔设根结点所在层号为30、假定对有序表：〔3，4，5，7，24，30，42，54，63，72，8795〕进展折半查找，试答复以下问题：查找过程的判定树。假设查54，需依次与哪些元素比较?假设查90，需依次与哪些元素比较?查找概率相等，求查找成功时的平均查找长度。A＝〔a

，a，…，a 〕，0≤a＜0 1 n0 1 n1 n〔0≤i≤n〕，假设存在a

＝a ＝…＝a ＝xm＞n/2〔0≤p≤n1≤k≤m〕，则xAp1 p2 pm kA＝〔0，5，5，3，5，7，55〕，则5为A＝〔0，5，5，3，5，1，5，7〕则A中没有主元素。假设An个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。假设存在主元素，则输出该元素；否则输出－1。要求：出算法的根本设计思想。依据设计思想，承受CCJava语言描述算法，关键之处给出注释。说明你所设计算法的时间简单度和空间简单度。五、算法设计题32、设二叉树用二指针构造存储〔可以是动态存储构造〕，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。33、按图的宽度优先搜寻法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vij到顶点V的路径(i≠j)j34、试编写在带头结点的单链表中删除〔一个〕最小值结点的〔高效〕算法delete〔Linklist&L〕。35、设键盘输入n个英语单词，输入格式为n，w1，w2，…，wn，其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：假设单词重复消灭，则只在链表上保存一个。除满足〔1〕的要求外。链表结点还应有一个计数域，记录该单词重复消灭的次数，然后输出消灭次数最多的前k〔k<=n〕个单词。参考答案一、选择题1、【答案】A2、【答案】A3、【答案】A4、【答案】D5、【答案】C6、【答案】A7、【答案】A8、【答案】C9、【答案】D10、【答案】C二、填空题11、【答案】p!=NULL//链表未到尾就始终进展q//将当前结点作为头结点后的第一元素结点插入12、【答案】n(n-1)/213、【答案】node->rflag==0；*x=bt；*x=node->right；prior〔t，x〕14、【答案】free〔T〕；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null15、【答案】2；4；3【解析】二分法查找元素次数列表查100115就停顿了。16、【答案】〔rear+1〕%〔n-m+1〕==frontstack[tp]=t；p=stack[tp--]；p；++tp【解析】此题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后推断栈是否为空，假设不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。18、【答案】23；100CH三、推断题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、答：〔1〕判定树如下图：假设查5430、63、42、54比较，查找成功。假设查9030、63、87、95比较，查找失败。〔4〕31、答：〔1〕算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重计数，确Num是否是主元素。算法可分为以下两步：①选取候选的主元素：依次扫描所给数组Num保存c中，Num的消灭次数1Num，则计1，否则计1；当计