文档介绍：第三次作业一、选择题 1 、在按行优先顺序存储的三元组表中,下述陈述错误的是 D。 A. 同一行的非零元素,是按列号递增次序存储的 B. 同一列的非零元素,是按行号递增次序存储的 C. 三元组表中三元组行号是非递减的 D. 三元组表中三元组列号是非递减的 2 、在稀疏矩阵的三元组表示法中,每个三元组表示 D。 A. 矩阵中非零元素的值 B. 矩阵中数据元素的行号和列号 C. 矩阵中数据元素的行号、列号和值 D. 矩阵中非零数据元素的行号、列号和值 3 、对特殊矩阵采用压缩存储的目的主要是为了 D。 A. 表达变得简单 B. 对矩阵元素的存取变得简单 C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间 4 、广义表是线性表的推广,它们之间的区别在于 A。 A. 能否使用子表 B. 能否使用原子项 C. 表的长度 D. 是否能为空 5、已知广义表(a, b, c, d) 的表头是 A,则表尾是 D; B. () C. (a, b, c, d) D. (b, c, d) // 第一个元素为表头,其余元素组成的表为表尾 6 、下面说法不正确的是 A。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构表示 D. 广义表可以是一个多层次的结构 7 、若广义表 A 满足 Head(A)=Tail(A) ,则 A为B。 A.() B. (()) C. (( ),( )) D. (( ),( ),( )) 8、在一棵树中,如果结点 A有3 个兄弟, B是A的双亲,则 B 的度为 D // 双亲即父节点 9、深度为 h 的完全二叉树至少有 D 个结点,至多有 B 个结点 h h -1 h +1 h-1 // 满二叉树是完全二叉树结点最多的情况 10 、具有 n 个结点的满二叉树有个叶结点。 A. n/2 B. (n-1)/2 C. (n+1)/2 D. n/2+1 //n 个结点的满二叉树深度:( 2^h ) -1=n, 叶结点的个数: x=2^(h-1)=(2^h)/2 // 所以, x=(n+1)/2 11 、一棵具有 25 个叶结点的完全二叉树最多有个结点。 A. 48 B. 49 C. 50 D. 51 // 完全二叉树:结点最多时 k-1 层最右非终结结点只有一个左分支,此时,度为 0 的只有叶节点, 25 个,度为 1 的只有非终结结点 1 个,度为 2 的有 25-1 个,所以结点最多为 25+1+24=50 个 12 、已知二叉树的先根遍历序列是 ABCDEF ,中根遍历序列是 CBAEDF ,则后根遍历序列是A。 A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 13 、具有 10 个叶结点的二叉树中有 B 个度为 2 的结点。 C. 10 D. 11 14 、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足 D。 A. 所有非叶结点均无左孩子 B. 所有非叶结点均无右孩子 C. 只有一个叶子结点同时成立// 蜕化的二叉树,单链表, A 的时候成立, B 的时候也成立二、填空题 1 、稀疏矩阵一般压缩存储的方式有三种,分别是三原组存储、行指针链表和十字链表。 2、二维数组 M中每个元素的长度是 3 字节,行下标 i从 0~7 ,列下标 j从0~9 ,从首地址&M[0][0] 开始连续存放在存储器中。若按行优先的方式存放,元素 M[7][5] 的起始地址为 M[0][0]+22 5 ;若按列优先方式存放,元素 M[7][5] 的起始地址为 M[0][0]+14 1。//LOC(M[7][5])= LOC(M[0][0])+ (7*10+5 )* 3=LOC(M[0][0])+225 //LOC(M[7][5])=LOC(M[0][0])+(5*8+7)*3=LOC([0][0])+141 3 、广义表(a, (a, b), d, e, ((i, j), k)) 的长度是 5 ,深度是 3。 4 、设广义表 A((( ), (a, (b), c))) ,则 Cal(Cdr(Cal(Cdr(Cal(A))))= (b) //A 的头的尾的头的尾的头// 取头不加括号,取尾加括号 5 、一棵二叉树有 67 个结点, 结点的度是 0和2 。问这棵二叉树中度为 2 的结点有 33 个。// 度为 0 的结点是叶结点,因此度为 0 的结点比度为 2 的结点多 1 6、含 A, B,C 三个结点的不同形态的二叉树有 5 棵。// 只有高度为 3 和高度为 2 两种情况 7、含有 4 个度为 2 的结点和 5 个叶子结点的完全二叉树,有 1或0 个度