《2023年中国计量大学现代科技学院计算机科学与技术专业《数据结构与算法》科目期末试卷(含答案).docx》由会员分享，可在线阅读，更多相关《2023年中国计量大学现代科技学院计算机科学与技术专业《数据结构与算法》科目期末试卷(含答案).docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2023 年中国计量大学现代科技学院计算机科学与技术专业数据构造与算法科目期末试卷A有答案一、选择题1、有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是。A.60B.66C.18000D.332、假设需在Onlog2n的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是。A.快速排序B. 堆排序C.归并排序D.直接插入排序3、静态链表中指针表示的是。A. 下一元素的地址B. 内存储器的地址C. 下一元素在数组中的位置D. 左链或右链指向的元素的地址4、循环队列 A0.m-1存放其元素值，用 front 和
2、 rear 分别表示队头和队尾，则当前队列中的元素数是。A.rear-front+m%m B.rear-front+1C.rear-front-1 D.rear-front5、在以下表述中，正确的选项是A. 含有一个或多个空格字符的串称为空格串B. 对 nn0个顶点的网，求出权最小的 n-1 条边便可构成其最小生成树C. 选择排序算法是不稳定的D. 平衡二叉树的左右子树的结点数之差确实定值不超过 l6、排序过程中，对尚未确定最终位置的全部元素进展一遍处理称为一趟排序。以下排序 方法中，每一趟排序完毕时都至少能够确定一个元素最终位置的方法是。简洁选择排序希尔排序快速排序堆排二路归并排序A仅、B仅
3、、C 仅、D仅、7、假设元素a，b，c，d，e，f 依次进栈，允许进栈、退栈操作交替进展，但不允许连续三次进展退栈操作，则不行能得到的出栈序列是。8、有关二叉树以下说法正确的选项是。A. 二叉树的度为 2B. 一棵二叉树的度可以小于 2C. 二叉树中至少有一个结点的度为 2D. 二叉树中任何一个结点的度都为 29、一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历结果为。A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、分别以以下序列构造二叉排序树，与用其他三个序列所构造的结果不同的是。A.100，80，90，60，120，110，130 B.100
4、，120，110，130，80，60，90 C.100，60，80，90，20，110，130 D.100，80，60，90，120，130，110二、填空题11、对 n个记录的表 r1.n进展简洁选择排序，所需进展的关键字间的比较次数为。12、有向图 G=(V，E)，其中 V(G)=0，1，2，3，4，5，用 三元组表示弧及弧上的权 d。E(G)为 E(G)=，则从源点 0 到顶点 3 的最短路径长度是，经过的中间顶点是。13、在单链表 L 中，指针 P 所指结点有后继结点的条件是。14、建立索引文件的目的是。15、对于一个具有 n 个结点的单链表，在的结点半 p 后插入一个结点的时间简洁度
5、为，在给定值为x 的结点后插入一个结点的时间简洁度为。16、设 T 和 P 是两个给定的串，在T 中查找等于P 的子串的过程称为，又称P 为 。17、在挨次存储的二叉树中，编号为 i 和j 的两个结点处在同一层的条件是。18、每一棵树都能唯一地转换为它所对应的二叉树。假设一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是。设上述二叉树是由某棵树转换而成，则该树的前序序列是。三、推断题19、倒排序文件的优点是维护简洁。20、倒排文件是对次关键字建立索引。21、数组不适合作为任何二叉树的存储构造。22、队列和栈都是运算受限的线性表，只允许在表的两端进展运算。23、一棵
6、树中的叶子数确定等于与其对应的二叉树的叶子数。24、任何二叉树的后序线索树进展后序遍历时都必需用栈。25、线性表承受链表存储时，结点和结点内部的存储空间可以是不连续的。26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最终一个元素的操作与链表的长度无关。27、对大小均为 n 的有序表和无序表分别进展挨次查找，在等概率查找的状况下，对于查找成功，它们的平均查找长度是一样的，而对于查找失败，它们的平均查找长度是不同的。 28、平衡二叉树中，假设某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子确定 是零。 四、简答题29、三维数组 A1.10，-2.6，2.8的每个元素的长度为 4
7、个字节，试问该数组要占多少个字节的存储空间?假设数组元素以行优先的挨次存储，设第一个元素的首地址是 100，试求元素 A5，0，7的存储首地址。30、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按以下各种排序方法进展排序时的变化过程：（1） 归并排序，每归并一次书写一个次序。（2） 快速排序，每划分一次书写一个次序。（3） 堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。31、设二叉树 BT 的存储构造如表：其中 BT 为树根结点的指针，其值为 6，Lchild、Rchild 分别为结点的左、右孩子指针域data 为结点的数据域。试完成以下各题：（1
8、） 画出二叉树 BT 规律构造。（2） 写出按前序、中序、后序遍历该二叉树所得到的结点序列。（3） 画出二叉树的后序线索树。五、算法设计题32、二叉树丁的结点形式为llink，data，count，rlink，在树中查找值为 X 的结点，假设找到，则记数count加 1；否则，作为一个结点插入树中，插入后仍为二叉排序树，写出其非递归算法。33、元素集合已存入整型数组 A1.n中，试写出依次取A 中各值 Ai1in构造一棵二叉排序树T 的非递归算法：CSBTr，A34、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要
9、求利用原来两个单链表的结点存放归并后的单链表。35、编写算法打印出由指针 Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。留意：行、列及总表头结点的形式为：它们已用 val 域链接成循环链表。非零元的结点形式也同上，每一行列的非零元由rightdown域把它们链接成循环链表，该行列的表头结点即为该行列循环链表的表头。参考答案一、选择题1、【答案】B2、【答案】C3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】D8、【答案】B9、【答案】A10、【答案】C二、填空题11、【答案】nn-1/212、【答案】50；413、【答案】P-next!=NULL14
10、、【答案】提高查找速度15、【答案】O1；On16、【答案】模式匹配；模式串17、【答案】【解析】用挨次存储构造存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为 i 和j 的结点在挨次存储中的下标为 s 和 t，则结点 i 和j 在同一层上的条件是18、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。三、推断题19、【答案】20、【答案】21、【答案】22、【答案】23、【答案】24、【答案】25、【答案】26、【答案】27、【答案】28、【答案】四、简答题29、答：数组占的存储
11、字节数=10*9*7*4=2520；A5，0，7的存储地址=100+4*9*7+2*7+5*4=1184。30、答：12 一路归并第一趟：18，29，25，47，12，58，10，51。其次趟：18，25，29，47，10，12，51，58。第三趟：10，12，18，25，29，47，51，58。2快速排序第一趟：10，18，25，12，29，58，51，47。其次趟：10，18，25，12，29，47，51，88。第三趟：10，12，18，25，29，47，51，88。3堆排序建大堆：58，47，51，29，18，12，25，10。 51，47，25，29，18，12，10，58。 47，2
12、9，25，10，18，12，51，58。 29，18，25，10，12，47，51，58。 25，18，12，10，29，47，51，58。 18，10，12，25，29，47，51，58。 12，10，18，25，29，47，51，58。 10，12，18，25，29，47，51，58。31、答：1二叉树的规律构造如以以下图：（2） 前序序列：A B C E D F H G I J中序序列：E C B H F D J I G A后序序列：E C H F J I G D B A（3） 二叉树的后序线索树如以以下图：五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：算法如下：