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

《2023年南京林业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(含答案).docx》由会员分享，可在线阅读，更多相关《2023年南京林业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(含答案).docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023 年南京林业大学计算机科学与技术专业数据构造与算法科目期末试卷A有答案一、选择题1、用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使j 沿链移动的操作为。A.j=rj.nextB.j=j+lC.j=j-nextD.j=rj-next 2、以下说法不正确的选项是。A.图的遍历是从给定的源点动身每个顶点仅被访问一次B.遍历的根本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、某线性表中最常用的操作是在最终一个元素之后插入一个元素和删除第一个元素，则承受存储方式最节约运算时间。A.单链表B.仅有头指针的单循环

2、链表C.双链表D.仅有尾指针的单循环链表4、最大容量为 n 的循环队列，队尾指针是 rear，队头：front，则队空的条件是。A.rear+1MODn=front B.rear=front C.rear+1=frontD.rear-1MODn=front5、在用邻接表表示图时，拓扑排序算法时间简单度为。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、字符串S 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”，承受 KMP 算法进展匹配，第一次消灭“失配”s!t时，ij5，则下次开头匹配时，i 和 j 的值分别。Ai1，j0B i5，j0Ci5

3、，j2Di6，j27、以下选项中，不能构成折半查找中关键字比较序列的是。A500，200，450，180B500，450，200，180 C180，500，200，450D180，200，500，4508、有关二叉树以下说法正确的选项是。A. 二叉树的度为 2B. 一棵二叉树的度可以小于 2C. 二叉树中至少有一个结点的度为 2 D.二叉树中任何一个结点的度都为 29、下述二叉树中，哪一种满足性质：从任一结点动身到根的路径上所经过的结点序列按 其关键字有序。A.二叉排序树B.哈夫曼树C.AVL树D.堆10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并A的左孩子的平衡因

4、子为 0，右孩子的平衡因子为l，则应作型调整以使其平衡A.LLB.LRC.RLD.RR二、填空题11、起始地址为 480，大小为 8 的块，其伙伴块的起始地址是；假设块大小为 32，则其伙伴块的起始地址为。12、对 n个记录的表 r1.n进展简洁选择排序，所需进展的关键字间的比较次数为。13、VSAM 系统是由、构成的。14、应用 Prim 算法求解连通网络的最小生成树问题。1针对如下图的连通网络，试按如下格式给出在构造最小生成树过程中挨次选出的各条边。2下面是 Prim 算法的实现，中间有 5 个地方缺失，请阅读程序后将它们补上。15、有序表为12，18，24，35，47，50，62，83，

5、90，115， 134当用二分法查找 90 时，需次查找成功，查找 47 时成功，查找 100 时，需次才能确定不成功。16、设数组 a1.50，1.80的基地址为 2023，每个元素占 2 个存储单元，假设以行序为主序 挨次存储，则元素 a45，68的存储地址为；假设以列序为主序挨次存储，则元素 a45， 68的存储地址为。17、在挨次存储的二叉树中，编号为 i 和j 的两个结点处在同一层的条件是。18、一棵有 n 个结点的满二叉树有个度为 1 的结点、有个分支非终端结点和个叶子，该满二叉树的深度为。三、推断题19、倒排序文件的优点是维护简洁。20、哈希表与哈希文件的唯一区分是哈希文件引入了

6、“桶”的概念。21、栈的输入序列是 1，2，n，输出序列是 a1，a2，an 假设ai=n 1in则有：aiai+1an。22、广义表a，b，c，d，e，f的长度是 4。23、哈夫曼树度为 1 的结点数等于度为 2 和 0 的结点数之差。24、假设从二叉树的任一结点动身，到根的路径上所经过的结点序列按其关键字有序，则该二叉树肯定是哈夫曼树。25、在外部排序过程中，对长度为 n 的初始序列进展“置换-选择”排序时，可以得到的最大初始有序段的长度不超过 n/2。26、为了很便利地插入和删除数据，可以使用双向链表存放数据。27、假设一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存

7、在。28、有向图中顶点 V 度等于其邻接矩阵中第 V 行中的 1 的个数。四、简答题29、对于具有 n 个叶结点且全部非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明1。2-li-1=1。其中：li 表示第 i 个叶结点所在的层号设根结点所在层号为30、设目标为 t=abcaabbabcabaacbacba，模式为 P=abcabaa（1） 计算模式 p 的 nextval 函数值。（2） 不写出算法，只画出利用 KMP 算法进展模式匹配时每一趟的匹配过程。31、图的邻接矩阵为：当用邻接表作为图的存储构造，且邻接点都按序号从大到小排列时，试写出：(1) 以顶点

8、V1 为动身点的唯一的深度优先遍历序列。当用邻接表作为图的存储构造，且邻接点都按序号从大到小排列时，试写出：(1) 以顶点V1 为动身点的唯一的深度优先遍历序列。(2)以顶点V1 为动身点的唯一的广度优先遍历序列。(3)该图唯一的拓扑有序序列。五、算法设计题32、指针 p 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFAp， q，该算法查找结点 p 的父亲结点 q。设线索二叉树的结点构造、表头结点构造和空树构造分别为LTAG，LLINK，INFO， RLlNK，RTAG，且规定线索树的最左下结点的 LLINK 域和最右下结点的 RLINKt 域指向表头。33、字符串 s1 中存放一段

9、英文，写出算法formats1，s2，s3，n，将其按给定的长度 n 格式化成两端对齐的字符串s2，其多余的字符送s3。34、元素集合已存入整型数组 A1.n中，试写出依次取A 中各值 Ai1in构造一棵二叉排序树T 的非递归算法：CSBTr，A35、设在 4 地(A，B，C，D)之间架设有 6 座桥，如下图。要求从某一地动身，经过每座桥恰巧一次，最终仍回到原地。（1） 试就以上图形说明：此问题有解的条件是什么?（2） 设图中的顶点数为n，试用 C 或 PASCAL 语言描述与求解此问题有关的数据构造并编写一个算法，找出满足要求的一条回路。参考答案一、选择题1、【答案】A2、【答案】C3、【答

10、案】D4、【答案】B5、【答案】B6、【答案】C7、【答案】A8、【答案】B9、【答案】D10、【答案】C二、填空题11、【答案】480+8=488；480-32=44812、【答案】nn-1/213、【答案】索引集；挨次集；数据集14、【答案】(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)(2) Tk；toVex=i min=MaxInt; mispos=i exit(0) Ti； fromVex=v【解析】Prim 算法的执行类似于查找图的最短路径的Dijkstra 算法。假设N=V，E是连通图，E 是 N 上最小生成树边的集合。算法从V =u ， E

11、开头，重复执行下述操作：TT0T在全部 u 属于V ，v 属于 V-V 的边u， v属于 E 中找一条代价最小的边u，v 加入集合 ET，同时将 v并入 VT，直到V00=V 为止。T0TT15、【答案】2；4；3【解析】二分法查找元素次数列表查找 100 是找到 115 就停顿了。16、【答案】9174；878817、【答案】【解析】用挨次存储构造存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为 i 和j 的结点在挨次存储中的下标为 s 和 t，则结点 i 和j 在同一层上的条件是18、【答案】【解析】满二叉树没有度为 1 的结点，度为 0 的结点等于度为

12、 2 的结点个数+1。三、推断题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，对于公式的变化，是削减了一个原来的叶结点，增加了两个叶结点，

13、反映到公式中，由于 2-t-1=2-t+1-1+2-t+1-1，所以结果不变，这就证明当i=n 时公式仍成立。证毕。30、答：1p 的nextval 函数值为 0110132p 的 next 函数值为 0111232。2利用KMP改进的 nextval算法，每趟匹配过程如下：31、答：(1)V1，V4，V9，V10，V7，V6，V8，V3，V2，V5 (2)V1，V4，V3，V2，V9，V7，V6，V5，V10，V8 (3)V1，V2，V5，V3，V4，V6，V8，V7，V9，V10五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：(1) 只有全部的顶点的度都是偶数，才能有解。(2)算法如下：修改常规访问标志数组 visited 的含义：当元素值为l 时表示该边已访问；当元素值为 0 时表示该边尚未访问。