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

2023期末试卷A〔有答案〕一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为〔 〕。A.5B.6C.8D.92、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是〔 〕。A.NB.2N-1C.2ND.N-1表中，增加一个头结点是为了〔 〕。A.使单链表至少有一个结点B. 标识表结点中首结点的位置C.便利运算的实现D. 说明单链表是线性表的链式存储4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是〔 〕。A.〔rear-front+m〕%mB.rear-front+1C.rear-front-1D.rear-front5、在以下表述中，正确的选项是〔 〕含有一个或多个空格字符的串称为空格串对n〔n>0〕个顶点的网，求出权最小的n-1条边便可构成其最小生成树选择排序算法是不稳定的平衡二叉树的左右子树的结点数之差确实定值不超l6、关键5，8，12，19，28，20，15，22是小根堆〔最小堆〕，插入关键字3，调整后的小根堆是〔 〕。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，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个结点的正则二叉树中有〔 〕个叶子。2 nB. 〔n－1〕/2C.log n+1D.〔n＋1〕2 10、下面关于B和B+树的表达中，不正确的选项是〔 〕A.B树和B+树都是平衡的多叉树B.B 树和B+树都可用于文件的索引构造C.B树和B+树都能有效地支持挨次检索D.B 树和B+树都能有效地支持随机检索二、填空题11、挨次查找n个元素的挨次表，假设查找成功，则比较关键字的次数最多为 次；当使用监视哨时，假设查找失败，则比较关键字的次数为 。12、在有n个顶点的有向图中，每个顶点的度最大可达 。13、数据构造是研讨数据的 和 对与这种构造定义相应的 ，设计出相应的 。14、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。注：(1)图的顶0开头计。indegree是有n个重量的一维数组，放顶点的入度，函数crein用于计算顶点入度。有三个函数push(data)，pop，check其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否0)。15、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是 、 、 、 。〔S，〔m，’ww’〕，REPLACE〔S，V，m〕= 。17、在挨次存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。18、以下程序是快速排序的非递归算法，请填写适当的语句，完成该功能。三、推断题19、对处理大量数据的外存介质而言，索引挨次存取方法是一种便利的文件组织方法。〔 〕键字查找。〔 〕他广义表所共享。〔 〕22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an假设ai=n〔1≤i≤n〕则有：ai>ai+1>…>an。〔 〕23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。〔 〕24、对于有n个结点的二叉树，其高度为log2n。〔 〕25、线性表承受链表存储时，结点和结点内部的存储空间可以是不连续的。〔 〕26、外部排序是把外存文件调入内存，可利用内部排序的方法进展排序，因此排序所花的。〔 〕27、当转变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。〔 〕28、承受线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，由于这会影响以后的查找。〔 〕四、简答题29、对于具有n个叶结点且全部非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?试证明1〕。

2〔li-〕=1。其中：li表示第i结层号设结层号为30、将以下由三棵树组成的森林转换为二叉树〔只要求给出转换结果〕。31、一个带有表头结点的单链表，结点构造为假设该链表只给出了头指针list。在不转变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点〔k为正整数〕。假设查找成功，算法输出该结点的data域的值1；否则0。要求：描述算法的根本设计思想。具体实现步骤。依据设计思想和实现步骤，承受程序设计语言描述算法〔使用C或CJAVA语言实现〕，关键之处请给出简要注释。五、算法设计题32、设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于l～100之间，现要求按B[1..100]的内容调A中记录的次序，比方当B[1]=11时，则要求将A[1]的内容调A[11]中去。规定可使用的附加空间为O〔1〕。33、请用流程图或高级语言表示算法。有向图有n个顶点，请写算法，依据用户输入的数对建立该有向图的邻接表。即承受用户输入的<vi，vj>(以其中之一为0标志完毕)，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中全部边处理完毕。提示：先产生邻n个头结点(其结点数值1n)。34、设A和B均为下三角矩阵，每一个都有n行n列。因此在下三角区域中各有nn+1/设数组，它有n行n+1一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。ijij并给出计算A的矩阵元素a，和B的矩阵元素b在C中的存放位置下标的公式。ijij35、以三元组表存储的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言写简单为〔m+〕阵B阵AA足够大，不另加关心空间。要求描述所用构造。参考答案一、选择题1、【答案】A2、【答案】A3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】D10、【答案】C二、填空题11、【答案】n；n+112、【答案】2(n-1)13、【答案】规律构造；物理构造；操作〔运算〕；算法14、【答案】0；j；i；0；indegree[i]=0；[vex][i]；k==l；indegree[i]=0【解析】有向图用邻接矩阵表示时，顶点i的入度等于第i列的全部元素之和。拓扑排序过程：首先将入度0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的顶点的入度减一，然后推断这些顶点的入度是否为零，假设为零，连续进栈，重复这些操作，完成拓扑排序。。16、【答案】’xyxyxywwy’17、【答案】++a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。18、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的根本思想是，通过一趟排序将待排记录分割成独立的两局部，其中一局部记录的关键字均比另一局部记录的关键字小，则可分别对这两局部记录连续进展排序，以到达整个序列有序。三、推断题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、答：森林转换为二叉树分以下三步：连线〔将兄弟结点相连，各树的根看作兄弟〕。〔2〕〔3〕

切线〔保存最左边子女为独生子女，将其他子女分支切掉〕。旋转〔以最左边树的根为轴，顺时针向下旋45度〕。所以由上面三棵树转换得到的二叉树如下图：31、答：〔1〕算法的根本设计思想定义两个指针变pq，初始时均指向头结点的下一个结点。p指针沿链表移动p指针移动到第k个结点时，q指针开头与p指针同步移动p指针移动到链表最终一个结点时，由于pqkq指针所指元素为倒k个