发布时间 : 星期六 文章14-15-2数据结构练习题及答案0603更新完毕开始阅读8c5c062bb8f67c1cfbd6b87f
A. 相同 B. 不相同 C. 可能相同 D. 无法确定
4、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ B ）。
A. ‘ijing’ B. ‘jing&’ C. ‘ingNa’ D. ‘ing&N’
第五章 数组和广义表
一、选择题
1、设广义表L=((a，b，c))，则L的长度和深度分别为（ C ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3 2、广义表((a),a)的表尾是（ B ）。
A. a B. (a) C. () D. ((a)) 3、稀疏矩阵的常见压缩存储方法有（ C ）两种。
A. 二维数组和三维数组 B. 三元组和散列表 C. 三元组和十字链表 D. 散列表和十字链表 4、一个非空广义表中的数据元素（ D ）。
A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子 6、广义表G=(a, (b,c,d,(e,f)),g)的长度是（ A ）。 A. 3 B. 4 C. 7 D. 8
7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ B ）。
A. 正确 B. 错误 C. 无法确定 D. 以上均不对 8、广义表(a,b,c)的表尾是（ B ）。
A. b,c B. (b,c) C. c D. (c) 9、常对数组进行两种基本操作是（ C ）。
A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 查找与索引 10、对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）。
A. 表达变得简单 B. 对矩阵元素的存取变得简单 C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间的开销
11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11 为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40
12、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ B ）。
A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 13、广义表A=((a),a)的表头是（ B ）。
A. a B. (a) C. b D. ((a)) 14、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。
A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表
15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B ）。
?0?8060??0?8060?????7000070003????A. ? B. ??50400? 00000???????50400??0?0000????
9
?0?8060??0?8060?????0000370000????C. ? D. ??50403? 70000???????50400??00000?????16、以下有关广义表的表述中，正确的是（ A ）。
A. 由0个或多个原子或子表构成的有限序列 B. 至少有一个元素是子表 C. 不能递归定义 D. 不能为空表
17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（ ）。
A. d B. e C. (e) D. （e,f）
二、判断题
（错 ）1、广义表中原子个数即为广义表的长度。
（错）2、一个稀疏矩阵采用三元组表示，若把三元组中有关行下标与列下标的值互换，并把mu和nu的值进行互换，则完成了矩阵转置。
（错）3、广义表的长度是指广义表中括号嵌套的层数。 （√）4、广义表的深度是指广义表中括号嵌套的层数。
（√ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。
三、填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。
2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： (x,y,z) 。 3、稀疏矩阵的压缩存储方式有： 三元组 和 十字链表 。
四、综合题
1、现有一个稀疏矩阵，请给出它的三元组表。
?0?1??0??0i1123340?000?? 210??0?20?j231233v31121-231答案：
10
第六章 树
一、选择题
1、二叉树的深度为k，则二叉树最多有（ C ）个结点。
A. 2k B. 2k-1 C. 2k-1 D. 2k-1
2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。
A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。
A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙
4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（ ）。
A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（A）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。
A. 能 B. 不能
7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5
8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70
9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。
A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd
11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。
A. 有序数据元素 B. 无序数据元素
C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据
16、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（ ）个。 A. 15 B. 16 C. 17 D. 47
18、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中，若结点R[i]有左孩子，则其左孩子是（ ）。
A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 20、树的先根序列等同于与该树对应的二叉树的（ ）。
A. 先序序列 B. 中序序列 C. 后序序列 D. 层序序列 21、按照二叉树的定义，具有3个结点的二叉树有（ C ）种。 A. 3 B. 4 C. 5 D. 6
22、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ A ）。 A. 51 B. 23 C. 53 D. 74
二、判断题
（ 对）1、存在这样的二叉树，对它采用任何次序的遍历，结果相同。 （对）2、中序遍历一棵二叉排序树的结点，可得到排好序的结点序列。
11
（√ ）3、一个含有n个结点的完全二叉树，它的高度是?log2n?＋1。 （√ ）4、完全二叉树的某结点若无左孩子，则它必是叶结点。 （√ ）5、完全二叉树某结点有右子树，则必然有左子树。
三、填空题
1、具有n个结点的完全二叉树的深度是 ?log2n?+1 。 2、哈夫曼树是其树的带权路径长度 最小 的二叉树。
3、在一棵二叉树中，度为0的结点的个数是n0，度为2的结点的个数为n2，则有n0= N2+1 。
4、树内各结点度的 最大值 称为树的度。
四、代码填空题
1、函数InOrderTraverse(Bitree bt)实现二叉树的中序遍历，请在空格处将算法补充完整。 void InOrderTraverse(BiTree bt){ if( bt ){ InOrderTraverse(bt->lchild); printf(“%c”,bt->data); InOrderTraverse(bt->rchild); } }
五、综合题
1、假设以有序对
{
（1）哪个结点是根结点？a
（2）哪些结点是叶子结点？b,d,i,j,f,k,h （3）哪些结点是k的祖先？a,c,g （4）哪些结点是j的兄弟？i （5）树的深度是多少？4
2、假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 3、假设用于通讯的电文仅由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。请为这8个字母设计哈夫曼编码。
12