(4)：A．872 B．860 C．868 D．864
5．若将n阶上三角矩阵A，按列优先顺序压缩存放在一维数组F[n(n+1)／2]中，第1个非零元素a11存于F[0]中，则应存放到F[K]中的非零元素aij(1≤i≤n，1≤j≤i的下标i,j与K的对应关系是 (5) 。
(5)：A．i(i+1)/2+j B．i(i-1)/2+j-1 C．j(j+1)／2+j D．j(j-1)／2+i—1
6．若将n阶下三角矩阵A，按列优先顺序压缩存放在一维数组F[n(n+1)／2]中，第一个非零元素a11，存于F[0]中，则应存放到F[K]中的非零元素aij(1≤j≤n，1≤j≤i)的下标i，i与K的对应关系是 (6) 。
(6):A.(2n-j+1)j/2+I-j B.(2n-j+2)(j-1)/2+i-j C．(2n-i+1)i/2+j-I D．(2n-i+2)i／2+j-i
7．设有10阶矩阵A，其对角线以上的元素aij(1≤j≤10，1 (7)：A．45 B．46 C．55 D.56 8．设广义表L=(a，b，L)其深度是 (8) 。 (8)：A．3 B．? C．2 D．都不对 9．广义表B：(d)，则其表尾是 (9) ，表头是 (10) 。 (9)—(10)：A．d B．() C．(d) D．(()) 10．下列广义表是线性表的有 （11） 。 (11)：A．Ls=(a，(b，c)) B．Ls=(a，Ls) C．Ls=(a，b) D．Ls=(a，(())) 11.一个非空广义表的表尾 (12) 。 (12)：A．只能是子表 B．不能是子表 C．只能是原子元素 D．可以是原子元素或子表 12．已知广义表A=((a，(b，c))，(a，(b，c)，d))，则运算head (head(tail(A)))的结果是 (13) 。 (13)：A．a B．(b，c) C．(a，(b，c)) D．d 二、填空题 1．两个串相等的充分必要条件是 (1) 。 2．空串是 (2) ，其长度等于 (3) 。 3．设有串S=”good”，T=”morning”，求： (1)concat(S，T)= (4) ； (2)substr(T，4，3)= (5) ； (3)index(T，”n”)= (6) ； (4)replace(S，3，2，”to”)= (7) 。 4．若n为主串长，m为子串长，则用简单模式匹配算法最好情况下，需要比较字符总数是 (8) ，最坏情况下，需要比较字符总数是 (9) 。 6 5．设二维数组A[8][10]中，每个数组元素占4个存储单元，数组元素a[2][2]按行优先顺序存放的存储地址是1000，则数组元素a[0][0]的存储地址是 (10) 。 6．设有矩阵 8 -3 -3 -3 4 2 -3 -3 A= 6 5 7 -3 1 3 9 11 F[m]中，则m为 (11) ，-3应存放到F[k1]中，k1为(12)，元素aij(1压缩存储到一维数组 ≤i≤4，1≤j≤i)按行优先顺序存放到F[k2]中，k2为 (13) ，按列优先顺序存放到F[k3]中，k3为 (14) 。 7．广义表Ls=(a，(b)，((c，(d))))的长度是 (15) ，深度是 (16) ，表头是 (17) ，表尾是 (18) 。 8．稀疏矩阵的压缩存储方法通常有两种，分别是 (19) 和 (20) 。 9．任意一个非空广义表的表头可以是原子元素，也可以是 (21) ，而表尾必定是 (22) 。 三、应用题 1．已知S=”(xyz)+*”试利用联接(concat(S，T))，取子串(substr(S，i，j))和置换(replace(S，i，j，T))基本操作将S转化为T=”(x+2)*y”。 2．设串S的长度为n，其中的字符各不相同，求S中互异的非平凡子串(非空且不同于S本身)的个数。 3．设模式串T=”abcaaccbaca”，请给出它的next函数及next函数的修正值nextval之值。 4．特殊矩阵和稀疏矩阵哪一种压缩存储会失去随机存储功能? 5．设n阶对称矩阵A压缩存储于一维数组F[m]中，矩阵元素aij(1≤i≤n，1≤j≤n)，存于F[k](0≤k 第五章 树和二叉树 一、单项选择题 1．关于二叉树的下列说法正确的是 (1)。 (1)：A．二叉树的度为2 B．二叉树的度可以小于2 C．每一个结点的度都为2 D．至少有一个结点的度为 2．设深度为h(h>0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为 （2）。 (2)A．2h B．2h-1 C．2h+1 D．h+1 3．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。 (3)：A．3 B．4 C．5 D．6 4．若一棵完全二叉树中某结点无左孩子，则该结点一定是 (4) 。 7 (4)：A.度为1的结点 B．度为2的结点 C．分支结点 D．叶子结点 5．深度为k的完全二叉树至多有 (5) 个结点，至少有 (6) 个结点。 (5)-(6)：A．2-1 B．2 k-1 k-1 C．2-1 D．2 kk 6．前序序列为ABC的不同二叉树有 (7) 种不同形态。 (7)：A．3 B．4 C．5 D．6 7．若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为 (8) ，层次序列为 (9) 。 (8)-(9)：A．BCAGFED B．DAEBCFG C．ABCDEFG D．BCAEFGD 8．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为 (10) ，右孩子结点的层次编号为 (11) ，双亲结点的层次编号为 (12)。 (10)-(12)：A．30 B．60 C．120 D．121 9．遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序 (13) 。 (13)：A.都不相同 B．完全相同 C．前序和中序相同 D．中序与后序相同 10．在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为 （14） ，根结点的右子树中结点个数为 (15) 。 (14)—(15)：A．20 B．29 C．30 D．35 11.具有n个结点(n>1)的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 (16) 。 (16)：A.仅有左孩子 B．仅有右孩子 C．仅有一个孩子 D．都有左、右孩子 12．判断线索二叉树中p结点有右孩子的条件是 (17) 。 (17)：A.p!=NULL B．p->rchild!=NULL C．p->rtag=0 D．p->rtag=1 13．将一棵树转换成二叉树，树的前根序列与其对应的二叉树的 (18) 相等。树的后根序列与其对应的二叉树的 (19)相同。 (18)—(19)：A．前序序列 B．中序序列 C．后序序列 D．层次序列 14．设数据结构(D，R)，D={dl，d2，d3，d4，d5，d6}，R={ (20)：A．线性表 B．二叉树C．队列 D．栈 (21)：人前序 B．中序 C．后序 D．层次 15．对于树中任一结点x，在前根序列中序号为pre(x)，在后根序列中序号为post(x)，若树中结点x是结点y的祖先，下列 （22） 条件是正确的。 (22)：A.pre(x) 8 D．pre(x)>pre(y)且post(x)>post(y) 16．每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的 (23) ，而结点N的右孩子是它在原树里对应结点的 (24) 。 (23)—(24)：A．最左孩子 B．最右孩子 C．右邻兄弟 D．左邻兄弟 17．二叉树在线索化后，仍不能有效求解的问题是 (25) 。 (25)：A．前序线索树中求前序直接后继结点 B．中序线索树中求中序直接前驱结点 C．中序线索树中求中序直接后继结点 D．后序线索树中求后序直接后继结点 18．一棵具有124个叶子结点的完全二叉树，最多有 (26)个结点。 (26)：A．247 B．248 C．249 D．250 。 19．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用 （27） 。 (27)：A. 二叉链表 B．孩子链表 C．三叉链表 D．顺序表 二、填空题 1.树中任意结点允许有 （1）孩子结点，除根结点外，其余结点 （2） 双亲结点。 2.若一棵树的广义表表示为A(B(E，F)，C(C(H，I，J，K)，L)，D(M(N)))。则该树的度为 (3) ，树的深度为 (4) ，树中叶子结点个数为 (5) 。 3．若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数是 (6) 。 4．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是 (7) 。 5．深度为k(k>0)的二叉树至多有 (8) 个结点，第i层上至多有 (9) 个结点。 6．已知二叉树有52个叶子结点，度为1的结点个数为30则总结点个数为 (10) 。 7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是 （11） 。 8．高度为6的完全二叉树至少有 (12) 个结点。 9．一个含有68个结点的完全二叉树，它的高度是 (13) 。 10．已知一棵完全二叉树的第6层上有6个结点(根结点的层数为1)，则总的结点个数至少是 (14) ，其中叶子结点个数是 （15） 。 11．已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是 （16） 。 12．一棵树转换成二叉树后，这棵二叉树的根结点一定没有 (17) 孩子，若树中有m个分支结点，则与其对应的二叉树中无右孩子的结点个数为 （18） 。 13．若用二叉链表示具有n个结点的二叉树，则有 （19） 个空链域。 14．具有m个叶子结点的哈夫曼树，共有 （20）个结点。 15．树的后根遍历序列与其对应的二叉树的 （21） 遍历序列相同。 16．线索二叉树的左线索指向其 （22） ，右线索指向其 （23） 。 三、应用题 9 1．具有n个结点的满二叉树的叶子结点个数是多少? 2．列出前序遍历序列是ABC的所有不同的二叉树。 3．已知二叉树的层次遍历序列为ABCDEFGHIJK，中序序列为DBGEHJACIKF，请构造一棵二叉树。 4．已知二叉树的中序遍历序列是ACBDGHFE，后序遍历序列是ABDCFHEG，请构造一棵二叉树。 5．已知二叉树的前序、中序和后序遍历序列如下，其中有一些看不清的字母用*表示，请先填写*处的字母，再构造一棵符合条件的二叉树，最后画出带头结点的中序线索链表。 (1)前序遍历序列是：*BC***G* (2)中序遍历序列是：CB*EAGH* (3)后序遍历序列是：*EDB**FA 6．将下图所示的森林转换成一棵二叉树，并画出这棵二叉树的顺序存储结构。 7．将下图所示的二叉树还原成森林。 8．对于给定的一组权值{3，5，6，7，9}，请构造相应的哈夫曼树，并计算其带权路径长度。 四、算法设计题 1．请设计一个算法，求以孩子兄弟链表表示的树中叶子结点个数。 2．请编写一个算法，实现将以二叉链表存储的二叉树中所有结点的左、右孩子进行交换。 3．请编写一个算法，将以二叉链表存储的二叉树输出其广义表表示形式。 4．请编写一个算法，判断以二叉链表存储的二叉树是否为完全二叉树。 5．假设二叉树采用链接存储方式存储，编写一个二叉树先序遍历和后序遍历的非递归算法。.. 6．已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。请编写一个 10