发布时间 : 星期四 文章数据结构各章作业题目更新完毕开始阅读
第四章作业
11. 串是一种特殊的线性表，其特殊性体现在( )
A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个字符
12. 设有两个串T和P，求P在T中首次出现的位置的运算叫做( )。
A. 求子串 B. 模式匹配 C. 串替换 D. 串连接 13. 下面关于串的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 14. 串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数 15. 两个串相等的充分必要条件是（）
A．串中所含的字符相同 B．串中所含字符的个数相同，且对应位置上的字符也相同 C．串中所含的字符个数相同 D．串中对应位置上的字符相同 6. 已知p=”abcaabbabcabaacbacb”，求出next函数值。
5
第五章作业
一、选择题
16. 数组通常具有的操作是( )
A. 顺序存取 B. 直接存取 C. 散列存取 D. 索引存取 17. 多维数组实际上是由( )实现的。
A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量
18. 在二维数组A[8][10]中，每一个数组元素A[i][j]占用3个存储空间，所有数组元素相继存放于一个
连续的存储空间中，则存放该数组至少需要的存储空间是( )。 A. 80 B. 100 C. 240 D. 270
19. 一个二维数组A[10][20]按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组
元素占1个存储字，则A[6][2]的地址为( ) A. 226 B. 322 C. 341 D. 342 20. 一个二维数组A[10][20]按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为( ) A. 226 B. 322 C. 341 D. 342 21. 在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行连续存放，在这种情况下，元素A[8][5]的起始地址为( ) A. SA+141 B. SA+144 C. SA+222 D. SA+255
22. 将一个n?n的对称矩阵A的下三角部分按存放在一个一维数组B中，A[0][0]存放在B[0]中，那么
第i行的对角元素A[i][i]在B中的存放位置是( ) A. (i?3)i/2 B. (i?1)i/2 C. (2n?i?1)i/2 D. (2n?i?1)i/2 23. 将一个n?n的对称矩阵A的上三角部分按存放在一个一维数组B中，A[0][0]存放在B[0]中，那么第i行的对角元素A[i][i]在B中的存放位置是( ) A. (i?3)i/2 B. (i?1)i/2 C. (2n?i?1)i/2 D. (2n?i?1)i/2 24. 设A是一个n?n的对称矩阵，将A的对角线及对角线上方的元素以列优先(以列为主序)的方式存
放在一维数组B[n(n?1)/2]中，则矩阵中任一元素aij(0?i,j?n,i?j)在B中的存放位置是( ) A. j(j?1)/2?i
B. j(j?1)/2?i?1
C. i(i?1)/2?j
D. i(i?1)/2?j?1
25. 设n阶三对角矩阵A的三条对角线上的元素被按行压缩存储到一维数组B中，A[0][0]存放于B[0]。若某矩阵元素在B中存放的位置在k，那么该元素在原始矩阵中的行号i是( ) A. ?(k?1)/3? B. ?k/3? C. ?(k?1)/3? D. ?(k?1)/3? 二、简答题
26. 设有一个3维数组A[10][20][15]，按行优先存放于一个连续的存储空间中，每个数组元素占4个
存储字，首元素A[0][0][0]的存储地址是1000，则A[7][8][9]存放于什么地方。
27. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放在676(10)，每个元
素占1个存储单元，问A[3][3](10)存放在什么位置？脚注(10)表示用十进制表示。
28. 对于一个n?n矩阵A的任一元素a[i][j]，按行存储和按列存储时的地址之差是多少？(假设两种存
储的开始存储地址LOC(0,0)以及元素所占存储单元数d相同)
29. 设有n阶三对角矩阵A，将其3条对角线上的元素逐行存储到数组B[0:3n?3]中，使得
B[k]?A[i][j]，且B[0]?A[0][0]，求
(1) 用i，j表示k的下标变换公式。 (2) 用k表示i，j的下表变换公式。
6
30. 设有一个n?n的对称矩阵A，将其下三角部分按行压缩存放于一个一维数组B中，A[0][0]存放
于B[0]，试问：(1) 一维数组B有多少个元素？(2) A中的任意一个元素A[i][j]应存于一维数组B的什么下标位置？
31. 设有一个n?n的对称矩阵A，将其上三角部分按列压缩存放于一个一维数组B中，A[0][0]存放
于B[0]，试问：(1) 一维数组B有多少个元素？(2) A中的任意一个元素A[i][j]应存于一维数组B的什么下标位置？
7
第六章作业 一、选择题
32. 一颗有n个结点的树的所有结点的度数之和为( )。
A.n-1 B. n C. n?1
33. 设一颗高度为h的满二叉树有n个结点，其中有m个叶结点，则( ) A.n?h?m B. h?m?2n C. m?h?1 34. 一颗有124个叶结点的完全二叉树最多有( )个结点。
A. 247 B. 248 C. 249 35. 一颗有129个叶结点的完全二叉树最少有( )个结点。
A. 254 B. 255 C. 257
36. 设完全二叉树的第6层有24个叶结点，则此树最多有( )个结点。
A. 55 B. 79 C. 81
37. 具有1000个结点的完全二叉树的次底层的叶结点个数为( )。
A. 11 B. 12 C. 24
D. 2n D. n?2h?1 D. 250 D. 258 D. 127 D. 36
38. 用顺序存储的方法将n个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组R[n]中，当
编号为0的根结点存放于R[0]时，若结点R[i]有左孩子，则左孩子是( )。 A.R[2i?1]
B. R[2i]
C. R[2i?1]
D. R[2i?2]
39. 用顺序存储的方法将n个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组R[n]中，当
编号为0的根结点存放于R[0]时，若结点R[i]有右孩子，则右孩子是( )。
A.R[2i?1] B. R[2i] C. R[2i?1] D. R[2i?2] 40. 二叉树的叶结点在前序、中序和后序遍历过程中的相对顺序( )。
A. 发生改变 B. 不发生变化 C. 无法确定 D. 以上均不对
41. 设n，m为一颗二叉树上的两个结点，在该二叉树的中序遍历序列中n在m前的条件是( )。
A. n在m右方 B. n是m的祖先 C. n在m左方 D. n是m的子孙 42. 设一颗二叉树的前序序列为abdec，中序序列为dbeac，则该二叉树的后序遍历顺序是( )。
A. abdec B. debac C. debca D. abedc
43. 设一颗二叉树的中序序列为badce，后序序列为bdeca，则该二叉树的前序遍历顺序是( )。
A. adbec B. decab C. debac D. abcde
44. 对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的
左、右孩子中，其左孩子编号小于其右孩子编号，则可采用( )遍历实现二叉树的结点编号。 A. 先序 B. 中序 C. 后序 D. 层次序
45. 如果T2是由有序树T转换成的二叉树，那么T中结点的先根遍历顺序对应T2中结点的( )遍历
顺序。 A. 前序 B. 中序 C. 后序 D. 层次序
46. 如果T2是由有序树T转换成的二叉树，那么T中结点的后根遍历顺序对应T2中结点的( )遍历
顺序。 A. 前序 B. 中序 C. 后序 D. 层次序 47. 用n个权值构造出来的Huffman树共有( )个结点。
A. 2n?1 B. 2n C. 2n?1 D. n?1 48. 由权值为8,4,5,7的4个叶结点构造一颗Huffman树，该树的带权路径长度为( )。 A. 24 B. 36 C. 48 D. 72 二、简答题
49. 设二叉树根结点所在层次为1，树的深度d为距离根最远的叶结点所在的层次，试回答以下问题：
(1) 试精确给出深度为d的完全二叉树的不同二叉树的棵数；(2) 试精确给出深度为d的满二叉树
8