发布时间 : 星期六 文章数据结构习题册更新完毕开始阅读2b2a7704e45c3b3567ec8b91
数据结构课后练习题
一、 选择题
1、在以下 讲述中，正确的是（ B ）。
A、线性表的现行存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出
2、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ B ）。
A、正确 B、错误
3、二维数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（ A ）。 A、SA+141 B、SA+180 C、SA+222 D、SA+225
4、数组SA中，每个元素的长度为3个字节，行下标I从0到7，列下标J从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（ C ）。 A、80 B、100 C、240 D、270
5、常对数组进行的两种基本操作是（ C ）。
A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6、将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A中元素A[6][5]在B数组中的位置K为（ D ）。 A、19 B、26 C、21 D、15
7、若广义表A满足Head(A)=Tail(A)，则A为（ B ）。 A、（） B、（（）） C、（（），（）） D、（（），（），（）） 8、广义表（（a）,a）的表头是（ C ），表尾是（ C ）。 A、a B、b C、(a) D、((a)) 9、广义表（（a,b）,c,d）的表头是（ C ），表尾是（ D ）。 A、a B、b C、(a,b) D、(c,d) 10、广义表（（a））的表头是（ B ），表尾是（ C ）。 A、a B、(a) C、() D、((a)) 11、广义表（a,b,c,d）的表头是（ A ），表尾是（ D ）。 A、a B、(a) C、(a,b) D、(b,c,d) 12、广义表（（a,b,c,d））的表头是（ C ），表尾是（ B ）。 A、a B、() C、(a,b,c,d) D、((a,b,c,d)) 13、下面结论正确的是（ BC ）。
A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表
C、广义表L=（（），（A，B））的表头为空表 D、广义表中原子个数即为广义表的长度 14、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=( D ) A、(G) B、(D) C、C D、 D
15、已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出原子项t的操作是（ D ）。
A、Head(Head(Tail(Tail(L)))) B、Tail(Head(Head(Tail(L)))) C、Head(Tail(Head(Tail(L)))) D、Head(Tail(Head(Tail(Tail(L)))))
16、设A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))=( C ) A. (g) B.(d) C.c D.d 17、对矩阵压缩存储是为了（ B ）
A、方便运算 B、节省空间 C、方便存储 D、提高运算速度 18、稀疏矩阵一般的压缩存储方法有两种，即（ C ）
1
A、二元数组和三元数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表
二、 判断题 A—对B—错 1． 数组是同类型值的集合。B
2． 数组的存储结构是一组连续的内存单元。A
3． 数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。B
4． 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。B 5． 使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。A
6． 广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。A
7． 线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。A 8． 广义表中原子个数即为广义表的长度。B 9． 广义表中元素的个数即为广义表的深度。B
三、 填空题
1、设a是含有N个分量的整数数组，则求该数组中最大整数的递归定义为（ f(k)=a[0](k=0时)||f(k)=max(f(k-1),a[k])(k>0时)），
最小整数的递归定义为（ f(k)=a[0](k=0时)||f(k)=min(f(k-1),a[k])(k>0时) ）。
2、二维数组A[10][5]采用行序为主方式存储，每个元素占4个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是（ ）。
3、二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是（ ）。
4、广义表的（ ）定义为广义表中括弧的重数。 5、设广义表L=（（），（）），则Head(L)=（ ）；Tail(L)=（ ）；L的长度是（ ）；L的深度是（ ）。 6、广义表中的元素可以是（ ），其描述宜采用程序设计语言中的（ ）表示。 7、广义表(((a)))的表头是（ ），表尾是（ ）。 8、广义表((a),((b),c),(((d))))的表头是（ ），表尾是（ ）。 9、设广义表A=(x,((a,b),c,d))，则Head(Head(Tail(A)))=（ ）。 10、设广义表A=(a,b,c),B=(A,(c,d)),C=(a,(B,A),(e,f))，则
（1）Head(A)=( ) (2) Tail(B)=( ) (3) Head(Head(Head(Tail(C))))=( )
11、下三角矩阵A[1..N,1..N]的下三角元素已压缩到一维数组S[1..N*（N+1）/2+1]中，若按行序为主序存储，则A[I,j]对应的S中的存储位置是 。
?0?312、已知一个稀疏矩阵为 ??0??002000?1000?0?? ，则对应的三元组表表示为 。 5??0?13、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为 。 14、三维数组A[c1..d1,c2..d2..,c3..d3]共有 个元素。
15、数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存储地址是 。
16、将一个下三角矩阵A[1..100,1..100]按行优先存入一维数组B[1..n]中，A中元素A[66,65]在B数组中的位置为 。 四、 计算题
1、 数组A[8][6][9]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，求元素A[2][4][5]
的存储地址。
2
2、 假设二维数组A6x8，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的基地址为1000，
计算：
（1） 数组A的体积（存储量） （2）A的最后一个元素第一个字节的地址
（3）按行存储时，a14的第一个字节的地址 （4）按列存储时，a47的第一个字节的地址。
3、 假设按低下标优先存储整数数组A9x3x5x8时，第一个元素的字节地址是100，每个整数占4个字节。
问下列元素的存储地址是什么？
（1）a0000 （2） a1111 （3） a3125 （4）a8247
4、 按行优先顺序和按列优先顺序分别列出四维数组A[2][2][2][2]所有元素在内存中的存储顺序。 5、 一个n阶对称矩阵A采用一维数组S按行序为主序存放其上三角各元素，写出S[k]与A[i,j]的关系公
式。设A[1，1]存于S[1]中。
6、 写出下面稀疏矩阵对应的三元组表示，并画出十字链表表示法。 A=〔（0，0，2，0），（3，0，0，0），（0，0，-1，5），（0，0，0，0）〕 五、 简答题
1、 什么是广义表，简述广义表与线性表的主要区别？
2、 利用广义表的Head和Tail运算把原子student从下列广义表中分离出来。
（1） L1=（soldier,teacher,student,worker,farmer） （2） L2=（soldier,(teacher,student),(worker,farmer)） 3、 画出下列广义表的存储结构图，并求它的深度。
（1）((( )),a,((b,c)),(((d)))) （2）((((a),(b))),((( ),d),(e,f)))
4、已知图4.4为广义表的存储结构图，写出各图的广义表。 （1） 1 1 ∧
1 1 ∧ 1 ∧ 1 1 ∧
0 x 1 ∧ 1 ∧ 1 ∧
0 y 1 ∧ ∧ 0 z （2） 1 1 1 ∧ ∧ 1 1 ∧ ∧ 1 1 ∧ 1 1 1 ∧ ∧ 0 a 1 ∧ 0 a 0 b 0 b
六、 设计题
1、 对于二维数组A[m][n]，分别编写相应函数实现如下功能：（1）求数组 A靠边元素之和；（2）求从
A[0][0]开始的互不相邻的各元素之和；（3）当m=n时分别求两条对角线上的元素之和，否则打印出m≠n的信息。
2、 如果矩阵A中的一个元素A[i][j]满足下列条件：A[i][j]是第I行中最小的元素，又是第j列中值最大
的元素，则称之为该矩阵的一个马鞍点。编写函数计算m×n的矩阵A的所有马鞍点，并分析算法的时间复杂度。
3
第六章：树和二叉树复习题
一、选择题
1、 有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据
结构是（ ）
A、向量 B、树 C、图 D、二叉树 2、树最适合用来表示（ ）
A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据
3、树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ ）
A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c)
4、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5、按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A、3 B、4 C、5 D、6
6、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则数的最大高度为（ ），其叶结点数为（ ）；树的最小高度为（ ），其叶结点数为（ ）；若采用链表存储结构，则有（ ）个空链域。
A、n/2 B、[ log2n]+1 C、log2n D、n E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1 K、n2 L、n1+1
7、对一棵满二叉树，m个树叶，n个结点，深度为h，则（ ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1
8、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），至多为（ ）。
A、2h B、2h-1 C、2h-1 D、2h-1
9、在一棵二叉树上第5层的结点数最多为（ ）（假设根结点的层数为1） A、8 B、16 C、15 D、32
10、深度为5的二叉树至多有（ ）个结点。 A、16 B、32 C、31 D、10
11、一棵有124个叶结点的完全二叉树，最多有（ ）个结点 A、247 B、248 C、249 D、250
12、含有129个叶子结点的完全二叉树，最少有（ ）个结点 A、254 B、255 C、256 D、257
13、假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。 A、15 B、16 C、17 D、47
16、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（ ）。
A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]
17、在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。
A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点
18、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ ）。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对
19、设n、m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙
4