期中考试讲解教程.pptx

期中考试讲解;考试人数;一、填空题; 1、单循环链表表示的队列长度为 n,若只设头指针,则进队的时间复杂度为____________。 答:O(n) ; 2、设元素 p1p2...pn 依次进栈,出栈序列为 q1q2...qn,如果 q1==pn-1,那么 q2 所有的可能为 ____________。 答:pn-2 或 pn ;3、已知广义表 LS=(a, (b, c, d), e),假设求表头操作为 Head,求表尾操作为 Tail,则 b=_____________。答:Head(Head(Tail(LS)));4、假设字符串下标从 1 开始,模式串 P=“abaabcac”的 next 函数值(未优化)序列为答:-1, 0, 0, 1, 1, 2, 0, 1 或者 0, 1, 1, 2, 2, 3, 1, 2;5、已知三对角矩阵 A[1..9, 1..9]的每个元素占用 2 个单元,现将其三条对角线上的元素逐行存储 在起始地址为 1000 的连续内存单元中,则元素 A[7][8]的存储地址为____________;如按列 优先顺序进行存储,则 A[7][8]的存储地址为____________。答:(1) 1038;(2) 1040 ;6、一棵有 100 个结点的完全二叉树从根结点开始,每一层从左到右依次对结点编号,根结点编 号为 1,则编号最小的叶子结点其编号为____________。答:51;7、将一个有 n 个结点的森林用左孩子-右兄弟链表示时,其中空链域的个数为____________。 答:n+1; 8、一棵二叉树的中序遍历序列为 ABCDEFG,后序遍历序列为 GFEDCBA,则这棵二叉树根结点左子树中的结点数目为____________。答:0;9、试判断下面的关键码序列中哪一个是堆____________。 1 {94, 31,53, 23, 16, 72} 2 {94, 53, 31, 72, 16, 23} 3 {16, 31, 23, 94, 53, 72} 4 {16, 53, 23, 94, 31, 72} 5 {16, 72, 31, 23, 94, 53} 答:3 ;二、问答题; 1、某算法时间复杂度的递推关系如下,其中 n 为求解问题的规模,设 n 是 3 的正整数幂。请给出该算法时间复杂度的大 O 表示法及推导过程。(6 分) ; 2、设目标串 T=“xxyxxxyxxxxyxyx”,模式串 P=“xxyxy”。如何用最少的比较次数找到 P 在 T 中第一 次出现的位置?相应的比较次数是多少?请给出具体的分析过程。(6 分)) ;思路：证明产生的输出序列是输入序列的任意排列组合即可。;A;A;CF;CF;CF;CF;CF;CF;CF;;什么是中序线索化二叉树 中序线索化二叉树的特点 如何解题;CBDAFHGIE;特点：对于中序线索化二叉树，一个节点的前驱是往右上回溯到第一个拐点 一个节点的后继是往左上回溯到第一个拐点;CBDAFHGIE;;;Y的前驱线索不为空 Y的前驱线索为空;1. P沿着右孩子一直找直到最右边节点Y’ ;Y’的后继线索不为空 Y’的后继线索为空;Y’的后继线索不为空 Y’的后继线索为空;;由前序和中序遍历建立二叉;;第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 ?第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。 第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下： 1 确定根,确定左子树，确定右子树。 2 在左子树中递归。 3 在右??树中递归。 4 打印当前根。 ;;;有序矩阵查找;;;基本设计思想： 利用递归和回溯，用一个int值统计到达当前结点时遍历过的结点的数值总和，用一个数组记录遍历过的所有结点。当到达叶节点且统计总和等于目标值，