C 唯一性不确定。
D 唯一性与原因的边的权数有关。
14、将递归算法转换成对应的非递归算法时,通常需要使用__________。 A栈 B 队列 C 链表 D树 15 、设二维数组 A[m][n], 每个数组元素占用 K 个存储单元 , 第一个数组元素的存储地址是 Loc(a[0][0]),求按行优先顺序存放的数组元素 a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为______。 A,Loc(a[0][0]+[(i-1)*n+j-1]*k B,Loc(a[0][0])+[i*n+j]*k C,Loc(a[0][0])+[j*m+i]*k D,Loc(a[0][0])+[(j-1)*m+i-1]*k 16 、设二维数组 A[m][n], 每个数组元素占用 k 个存储单元 , 第一个数组元素的存储地址是 Loc(a[0][0]),求按列优先顺序存放的数组元素 a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为______。 A,Loc(a[0][0])+[(i-1)*n+j-1]*k B,Loc(a[0][0])+[i*n+j]*k C,Loc(a[0][0])+[j*m+i]*k D,Loc(a[0][0])+[(j-1)*m+i-1]*k 17 、设二维数组 A[6][10], 每个数组元素占用 4 个存储单元 , 若按行优先顺序存放的数组元 素,a[0][0]的存储地址为 860,则 a[3][5]的存储地址是______。 A,1000 B,860 C,1140 D,1200 18、设二维数组 A[6][10],每个数组元素占用 4 个存储单元,若按行优先顺序存放的数组元素 a[3][5]的存储地址为 1000,则 a[0][0]的存储地址是______。 A,872 B,860 C,868 D,864 19、若将 n 阶上三角矩阵 A 按列优先顺序压缩存放在一维数组 B[1..n(n+1)/2]中,第一个非零 元素 a1,1 存于 B[0]中,则应存放到 B[k]中的非零元素 ai,j(1<=i<=n,1<=j<=i)的下标 i、j 与 k 的对 应关系是______。 A,i(i+1)/2+j B,i(i-1)/2+j-1 C,j(j+1)/2+i D,j(j-1)/2+i-1 20、若将 n 阶下三角矩阵 A 按列优先顺序压缩存放在一维数组 B[1..n(n+1)/2]中,第一个非零 元素 a1,1 存于 B[0]中,则应存放到 B[k]中的非零元素 ai,j(1<=i<=n,1<=j<=i)的下标 i、j 与 k 的对 应关系是______。 A,j(2n-j+1)/2+i-j B,(j-1)(2n-j+1)/2+i-j C,i(2n-i+1)/2+j-i D,i(2n-i+2)/2 A 便于进行矩阵运算 B 便于输入和输出 C 节省存储空间 度 22、稀疏矩阵压缩后,必会失去______功能。 A 顺序存储 B 随机存取 C 输入输出 D 以上都不对
D 降低运算的时间复杂
23、一个 n*n 的对称矩阵 A,采用压缩方式存放到一维数组 B 中,则 B 的容量为______. A,n^2 B,(n^2)/2 C,(n*(n+1))/2 D,((n+1)^2)/2 24、 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树， 它的带权路径长度为_________。 A,24 B,48 C,72 D,53 25、在一棵深度为 h 的具有 n 个元素的二叉搜索树中，一个元素的最大搜索长度（即 比较的结点数） 为_________ A,n B,lbn C,h/2 D,h 经
26、根据集合{25,30,16,48}，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况 下成功查找一个元素的平均查找长度为_________。 A,2 B,2.5 C,3 D,4 27、利用 n 个值作为叶结点的权生成的霍夫曼树中共包含有_________个结点。 A,n B,n+1 C,2*n D,2*n-1 28、利用 n 个值作为叶结点的权生成的霍夫曼树中共包含有_________个双支结点。 A,n B,n-1 C,n+1 D,2*n-1 29、利用 3,6,8,12 这 4 个值作为叶子结点的权，生成一棵霍夫曼树，该树中所有叶子的最长 带权路径长度为_________。 A,18 B,16 C,12 D,30 30、在平衡二叉树中，每个结点的平衡因子的绝对值被限制为_________。 A,1 B,2 C,3 D,4 判断题 1、 由树转换成二叉树， 其根结点的右子树总是空的。 T 2、后序遍历树和中序遍历与该树对应的二叉树，其结果不同。 F 3、 有一个结点是某二叉树子树的中序遍历序列中的最后一个结点， 则它必是该子 树的前序 遍历序列中的最后一个结点。 F 4、 若一个树叶是某子树的中序遍历序列中的最后一个结点， 则它必是该子树的前序 遍历序 列中的最后一个结点。 T 5、 已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树， 因为不知道树 的根结 点是哪一个。 F
数据结构复习题：树和二叉树 单选题 1、假定在一棵二叉树中，双分支结点数为 15 个，单分支结点数为 32 个，则叶子结点 数为 _____。 A,15 B,16 C,17 D,47 2、假定一棵二叉树的结点数为 18 个，则它的最小高度_____。 A,4 B,5 C,6 D,18 3、在一棵二叉树中第五层上的结点数最多为_____。 A,8 B,15 C,16 D,32 4、在一棵具有五层的满二叉树中，结点总数为_____。 A,31 B,32 C,33 D,16 5、已知 8 个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生 成一棵二叉排序树后，最后两层上的结点总数为_____。 A,1 B,2 C,3 D,4 6、 由分别带权为 9、 2、 5、 7 的四个叶子结点构造一棵哈夫曼树， 该树的带权路径长度为_____。 A,23 B,37 C,44 D,46 7、在树中除根结点外，其余结点分成 m(m≥0)个_____的集合 T1,T2,T3...Tm,每个 集合又都 是树，此时结点 T 称为 Ti 的父结点，Ti 称为 T 的子结点(1≤i≤m)。 A,互不相交 B 可以相交 C 叶结点可以相交 D 树枝结点可以相交 8、下面答案_____是查找二叉树（又称二叉排序树） 。 A 二叉树中的每个结点的两棵子树的高度差的绝对值不大于１。 B 二叉树中的每个结点的两棵子树的高度差等于１。 C 二叉树中的每个结点的两棵子树是有序的。 D 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，且小于 其右子树（如果存在）所有结点的关键字值。 9、如果结点 A 有三个兄弟，而且 B 是 A 的双亲，则 B 的出度是_____。 A,3 B,4 C,5 D,1 10、 一个深度为 L 的满 K 叉树有如下性质： 第 L 层上的结点都是叶子结点， 其余各层上每 个 结点都有 K 棵非空子树。 如果按层次顺序从１开始对全部结点编号， 编号为 n 的有右兄弟的 条件是_____。 A,(n-1) % k= =0 B,(n-1) % k!=0 C,n % k= =0 D,n % k!=0
top--; } } //while } 填空题 1、对于一棵具有 n 个结点的树，则该树中所有结点的度之和为______。n-1 2 、在一棵二叉树中，度为 0 的结点的个数为 n0 ，度为 2 的结点的个数为 n2 ，则： n0=__________。n2+1 3、在二叉树的顺序存储中，对于下标为 5 的结点，它的双亲结点的下标为__________， 若 它存在左孩子，则左孩子结点的下标为__________，若它存在右孩子，则右孩子结点的下标 为___________。2|10|11 4、在一棵二叉排序树中，按__________遍历得到的结点序列是一个有序序列。中序 5 、 由分 别带 权为 3,9,6,2,5 的 共五 个叶 子结 点构 成 一棵 哈夫 曼树 ，则 带 权路 径长 度为 _________。 55 6、有如下递归函数: int dunno (int m) { int value; if (m==0) value=3; else value=dunno(m-1)+5; return (value); } 执行语句 printf("%d\n",dunno(3))；的结果是________。 18 7、所谓稀疏矩阵指的是______的矩阵。 非零元素很少且分布没有规律 8、 一个稀疏矩阵 Am*n 采用三元组表示后,若把三元组中有关行下标与列下标的值互换,并把 m 和 n 的值互换,则就完成了 Am*n 的转置运算。这句话______正确的。不是 9、 若稀疏矩阵采用三元组压缩方法存储,只要把每个元素的行下标和列下标互换,就成了对该 矩阵的转置运算,这种观点______(正确或错误). 错误 10、在一棵非空的二叉搜索树中，以每个分支结点为根的子树都是一棵____________。 二叉搜索树 11、对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个____________。有序序列 12、 从一棵二叉搜索树中查找一个元素时， 若元素的值等于根结点的值， 则表明____________， 若元素的值小于根结点的值，则继续向____________查找，若元素的值大于根结点的值，则 继续向____________查找。查找成功|左子树|右子树 13 、 在 一 个 堆 的 顺 序 存 储 中 ， 若 一 个 元 素 的 下 标 为 i ， 则 它 的 左 孩 子 元 素 的 下 标 为 ____________，右孩子元素的下标为____________。2i+1|2i+2 14、在一个小根堆中，堆顶结点的值是所有结点中的____________，在一个大根堆中，堆顶 结点的值是所有结点中的____________。最小值|最大值 15、当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层____________调整，直 到被调整到____________位置为止。向上|栈顶 16、 不管一棵哈夫曼树中有偶数或奇数个叶子结点， 则树中总结点的个数必为____________ 个。奇数