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

2023 年河北工程大学计算机科学与技术专业数据构造与算法科目期末试卷A有答案一、选择题1、用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为。A.5B.6C.8D.92、将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是。A.NB.2N-1C.2ND.N-13、单链表中，增加一个头结点是为了。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.便利运算的实现D.说明单链表是线性表的链式存储4、循环队列 A0.m-1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是。A.rear-front+m%m B.rear-front+1C.rear-front-1 D.rear-front5、在以下表述中，正确的选项是A. 含有一个或多个空格字符的串称为空格串B. 对 nn0个顶点的网，求出权最小的 n-1 条边便可构成其最小生成树C. 选择排序算法是不稳定的D. 平衡二叉树的左右子树的结点数之差确实定值不超过 l6、关键字序列 5，8，12，19，28，20，15，22 是小根堆最小堆，插入关键字3，调整后的小根堆是。A3，5，12，8，28，20，15，22，19 B3，5，12，19，20，15，22，8，28C3，8，12，5，20，15，22，28，19 D3，12，5，8，28，20，15，22，197、假设一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c ，d，e，a，则根结点的孩子结点。A只有 eB 有e、bC有e、cD无法确定8、在下述结论中，正确的有。只有一个结点的二叉树的度为 0。二叉树的度为 2。二叉树的左右子树可任意交换。深度为 K 的完全二叉树的结点个数小于或等于深度一样的满二叉树。A. B. C. D.9、每个结点的度或者为 0 或者为 2 的二叉树称为正则二叉树。n 个结点的正则二叉树中有个叶子。22A.log nB.n1/2C.logn+1D. n1/210、下面关于 B 和 B+树的表达中，不正确的选项是A.B 树和 B+树都是平衡的多叉树B.B树和 B+树都可用于文件的索引构造C.B 树和 B+树都能有效地支持挨次检索D.B树和 B+树都能有效地支持随机检索二、填空题11、挨次查找 n 个元素的挨次表，假设查找成功，则比较关键字的次数最多为次；当使用监视哨时，假设查找失败，则比较关键字的次数为。12、在有 n 个顶点的有向图中，每个顶点的度最大可达。13、数据构造是研讨数据的和以及它们之间的相互关系，并对与这种构造定义相应的，设计出相应的。14、n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注：(1)图的顶点号从 0 开头计。(2) indegree 是有n 个重量的一维数组，放顶点的入度，(3) 函数crein 用于计算顶点入度。(4) 有三个函数push(data)，pop，check其含义为数据 data 入栈，出栈和测试栈是否空 (不空返回l，否则 0)。15、在双向循环链表中，向 p 所指的结点之后插入指针 f 所指的结点，其操作是、 、。16、 U=xyxyxyxxyxy；t=xxy；ASSIGNS，U；ASSIGNV，SUBSTR S， INDEXS，t，LENt+1；ASSIGN m，ww，求 REPLACES，V，m=。17、在挨次存储的二叉树中，编号为 i 和j 的两个结点处在同一层的条件是。18、以下程序是快速排序的非递归算法，请填写适当的语句，完成该功能。三、推断题19、对处理大量数据的外存介质而言，索引挨次存取方法是一种便利的文件组织方法。20、倒排文件的目的是为了多关键字查找。21、一个广义表可以为其他广义表所共享。22、栈的输入序列是 1，2，n，输出序列是 a1，a2，an 假设ai=n 1in则有：aiai+1an。23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。24、对于有 n 个结点的二叉树，其高度为 log2n。25、线性表承受链表存储时，结点和结点内部的存储空间可以是不连续的。26、外部排序是把外存文件调入内存，可利用内部排序的方法进展排序，因此排序所花的时间取决于内部排序的时间。27、当转变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。28、承受线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，由于这会影响以后的查找。四、简答题29、对于具有 n 个叶结点且全部非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明1。2-li-1=1。其中：li 表示第 i 个叶结点所在的层号设根结点所在层号为30、将以下由三棵树组成的森林转换为二叉树只要求给出转换结果。31、一个带有表头结点的单链表，结点构造为假设该链表只给出了头指针 list。在不转变链表的前提下，请设计一个尽可能高效的算法， 查找链表中倒数第k 个位置上的结点k 为正整数。假设查找成功，算法输出该结点的data 域的值，并返回 1；否则，只返回 0。要求：（1） 描述算法的根本设计思想。（2） 描述算法的具体实现步骤。（3） 依据设计思想和实现步骤，承受程序设计语言描述算法使用C 或C或 JAVA 语言实现，关键之处请给出简要注释。五、算法设计题32、设 A1.100是一个记录构成的数组，B1.100是一个整数数组，其值介于 l100 之间，现要求按B1.100的内容调整 A 中记录的次序，比方当B1=11 时，则要求将 A1 的内容调整到 A11中去。规定可使用的附加空间为O1。33、请用流程图或高级语言表示算法。有向图有 n 个顶点，请写算法，依据用户输入的数对建立该有向图的邻接表。即承受用户输入的(以其中之一为 0 标志完毕)， 对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中全部边 处理完毕。提示：先产生邻接表的 n 个头结点(其结点数值域从 1 到 n)。34、设 A 和 B 均为下三角矩阵，每一个都有n 行 n 列。因此在下三角区域中各有nn+1/个元素。另设有一个二维数组 C，它有n 行 n+1 列。试设计一个方案，将两个矩阵 A 和 B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于 C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。ijij并给出计算 A 的矩阵元素a ，和B 的矩阵元素 b 在 C 中的存放位置下标的公式。35、以三元组表存储的稀疏矩阵 A，B 非零元个数分别为 m 和 n。试用类 PASCAL 语言编写时间简单度为 Om+n的算法将矩阵B 加到矩阵 A 上去。A 的空间足够大，不另加关心空间。要求描述所用构造。参考答案一、选择题1、【答案】A2、【答案】A3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】D10、【答案】C二、填空题11、【答案】n；n+112、【答案】2(n-1)13、【答案】规律构造；物理构造；操作运算；算法14、【答案】0；j；i；0；indegreei=0；vexi；k=l；indegreei=0【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的全部元素之和。拓扑排序过程：首先将入度为 0 的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其他顶点的入度减一，然后推断这些顶点的入度是否为零，假设为零，连续进栈，重复这些操作，完成拓扑排序。15、【答案】f-next=p-next；f-prior=p；p-next-prior=f；p-next=f。16、【答案】xyxyxywwy17、【答案】+a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。18、【答案】aj=ak；low=stacktop0；stacktop0=k+1【解析】快速排序(quick sort)的根本思想是，通过一趟排序将待排记录分割成独立的两局部，其中一局部记录的关键字均比另一局部记录的关键字小，则可分别对这两局部记录连续进展排序，以到达整个序列有序。三、推断题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） 连线将兄弟结点相连，各树的根看作兄弟。23切线保存最左边子女为独生子女，将其他子女分支切掉。旋转以最左边树的根为轴，顺时针向下旋转 45 度。所以由上面三棵树转换得到的二叉树如下图：31、答：1算法的根本设计思想定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点。p 指针沿链表移动；当 p 指针移动到第k 个结点时，q 指针开头与p 指针同步移动；当 p 指针移动到链表最终一个结点时，由于 p 和 q 相隔 k，故 q 指针所指元素为倒数第 k 个结点。以上过程对链表仅进展一遍扫描。（2） 算法的具体实现步骤 count0，p 和 q 指向链表表头结点的下一个结点。假设 p 为空，转。假设 count 等于 k，则 q 指向下一个结点；否则，countcount1。 p 指向下一个结点，转步骤。假设 count 等于 k，则查找成功，输出该结点的data 域的值，返回 1；否则，查找失败， 返回 0。算法完毕。（3） 算法实现五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：算法如下：