数据结构李春葆习题与解析.docx
《数据结构李春葆习题与解析.docx》由会员分享，可在线阅读，更多相关《数据结构李春葆习题与解析.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构李春葆习题与解析
李春葆编著：
数据结构（C语言篇）――习题与解析（修订版）
清华大学出版社
五、数组与稀疏矩阵
单项选择题
1.常对数组进行的两种基本操作是 。
A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引
2.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从
0到8，列下标j的范围从1到10，则存放M至少需要 1 个字节；M的第8列和第5
行共占 2 个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先
方式存储时的 3 元素的起始地址一致。
1A.90 B.180C.240D.540
2A.108 B.114C.54D.60
3A.M[8][5] B.M[3][10]C.M[5][8]D.M[0][9]
3.二维数组M的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从
0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元
素的 元素的起始地址一致。
A.M[2][4] B.M[3][4]C.M[3][5]D.M[4][4]
4.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地
址SA开始连续存放在存储器内，存放该数组至少需要的单元素是 。
A.80 B.120 C.240 D.270
5.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地
址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为 。
A.SA+141 B.SA+144 C.SA+222 D.SA+225
6.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地
址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为 。
A.SA+141 B.SA+180 C.SA+222 D.SA+225
7.稀疏矩阵一般的压缩存储方法有两种，即 。
A.二维数组和三维数组 B.三元组与散列
C.三元组与十字链表 D.散列和十字链表
8.若用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 。
A. 正确 B. 不正确
9.设矩阵A是一个对称矩阵，为节省存储，将其下三角部分按行序存放在一信数组B[1,n（n-1）/2]中，对下三角部分中任一元素aij（i≥j），在一组数组B的下标位置k的值是 。
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
填空题
1.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A[0][0]），则A[i][j]的地址是 。
2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][10]的地址是 。
3.二维数组A[10..20][5..20]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是 。
4.有一个10阶对称矩阵A，采用压缩存储方式（以行为主存储，且LOC（A[0][0]）=1），则
A[8][5]的地址是 。
5.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*（n+1）/2]中，若按行序为主存储，则
A[i][j]对应的S中的存储位置是 。
6.一个稀疏矩阵如图所示，则对应的三元数组表示为 。
八、树形结构
单项选择题
1.如图所示的4棵二叉树中， 不是完全二叉树。
3.在线索化二叉树中，t所指结点没有左子树的充要条件是 。
A.t->left==NULL B.t->ltag==1C.t->ltag==1且t->left==NULLD.以上都不对
4.二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法 。
A.正确 B.错误
5.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 。
A.正确 B.错误
6.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 。
A.正确 B.错误
7.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少
为 。
A.2h B.2h-1 C.2h+1 D.h+1
8.如图所示二叉树的中序遍历序列是 。
A.abcdgef B.dfebagc C.dbaefcg D.defbagc
9.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是 。
A.acbed B.decab C.deabc D.cedba
10.如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的 。
A.前序B.中序 C.后序D.层次序
11.如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的 。
A.前序B.中序 C.后序D.层次序
12某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是 。
A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca
13.二叉树为二叉排序树的充分必要条件是任一结点的值均大于其左孩子的值、小于其右孩子的值，这种说法 。
A.正确 B.错误
14.按照二叉树的定义，具有3个结点的二叉树有 种。
A.3B.4 C.5D.6
15.如图所示二叉树的中序遍历序列是 。
A.abdgcefh B.dgbaechf C.gdbehfca D.abcdefgh
16.树的基本遍历策略可分为先根遍历和后根遍历；二叉树基本遍历策略可分为先序遍历、
中序遍历和后序遍历。
这时，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。
结论
是正确的。
A.树的先根遍历序列与二叉树的先序遍历序列相同
B.树的后根遍历序列与二叉树的后序遍历序列相同
C.树的先根遍历序列与二叉树的中序遍历序列相同
D.以上都不对
17.深度为5的二叉树至多有 个结点。
A.16 B.32 C.31 D.10
18.在一非空二叉树的中序遍历序列中，根结点的右边 。
A.只有右子树上的所有结点 B.只有右子树上的部分结点
C.只有左子树上的所有结点 D.只有左子树上的部分结点
19.树最适合用来表示 。
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
20任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序 。
A.不发生改变 B.发生改变 C.不能确定 D.以上都不对
21.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用
存储结构。
A.二叉链表 B.广义表存储结构 C.三叉链表 D.顺序存储结构
22.对于一个满二叉树，m个树叶，n个结点，深度为h，则 。
A.n=h+m B.h+m=2n C.m=h-1 D.n=2h-1
23.如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序 。
A.uwvts B.vwuts C.wuvts D.wutsv
25.如图所示的T2是由有序树T1转换而来的二叉树，那么树T1有 个叶结点。
A.4B.5C.6D.7
26.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 。
A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙
27.线索二叉树是一种 结构。
A.逻辑B.逻辑和存储C.物理D.线性
填空题
1.有一棵树如图所示，回答下面问题：
（1）这棵树的根结点是 ；
（2）这棵树的叶子结点是 ；
（3）结点c的度是 ；
（4）这棵树的度是 ；
（5）这棵树的深度是 ；
（6）结点c的子女是 ；
（7）结点c的父母结点是 。
2.指出树和二叉树的三个主要差别 、 、 。
3.从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本目的是 。
4.一棵二叉树的结点数据采用顺序存储结构，存储于数组T中，如图所示，则该二叉树的链接表示形式为 。
1 2 3456789101112131415161718192021
e
a
f
d
g
c
j
i
h
b
5.深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下、从左到右次序给结点编号（从1开始），则编最小的叶子结点的编号是 。
6.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=。
7.一棵二叉树的第k层最多有 个结点；一棵有n个结点的满二叉树共有个叶子和个非终端结点。
8.结点最少的树为 ，结点最少的二叉树为 。
9.现有按中序遍历二叉树的结果是abc，问有 种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是 。
10.根据二叉树的定义，具有三个结点的二叉树有 种不同的形态，它们分别是 。
11.由如图所示的二叉树，回答以下问题：
（1）其中序遍历序列 ；
（2）其前序遍历序列 ；
（3）其后序遍历序列 ；
（4）该二叉树的中序线索二叉树为 ；
（5）该二叉树的后序线索二叉树为 ；
（6）该二叉树对应的森林是 。
12.已知一棵树如图所示，其孩子兄弟表示为 。
13.以数据集｛4，5，6，7，10，12，18｝为结点权值所构造的哈夫曼树为 ，其带权路径长度为 。
九、图
1.在一个图中，所有顶点的度数之和等于所有边数的 倍。
A.1/2 B.1 C.2 D.4
2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度这和 倍。
A.1/2 B.1 C.2 D.4
3.一个有n个顶点的无向图最多有 条边。
A.n B.n（n-1） C.n（n-1）/2 D.2n
4.具有4个顶点的无向完全图有 条边。
A.6 B.12 C.16 D.20
5.具有6个顶点的无向图至少应有 条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
6.在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。
A.n B.n+1 C.n-1 D.n/2
7.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。
A.n B.（n-1）2 C.n-1 D.n2
8.对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则表头向量的大小是 1 ；所有邻接矩阵中的结点总数是2。
1A.n B.n+1 C.n-1 D.n+e
2A.e/2 B.e C.2e D.n+e
9.已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可得到顶点序列为 1 ；按宽度搜索法进行遍历，则可得到顶点序列为 2 。
1A.abecdf B.acfebd C.aebcfd D.aedfcb
2A.abcedf B.abcefd C.aebcfd D.acfdeb
10.已知一有向图的邻接表存储结构如图所示
（1）根据有向图的深度优先遍历算法，从v1顶点出发，所得到的顶点序列是 1 。
（2）根据有向图的宽度优先遍历算法，从v1顶点出发，所得到的顶点序列是 2 。
1A.v1,v2,v3,v5,v4 B.v1,v2,v3,v4,v5
C.v1,v3,v4,v5,v2 D.v1,v4,v3,v5,v2
2A.v1,v2,v3,v4,v5 B.v1,v3,v2,v4,v5
C.v1,v2,v3,v5,v4 D.v1,v4,v3,v5,v2
11.采用邻接表存储的图的深度优先遍历算法类似于二叉树的 。
A.先序遍历 B.中序遍历 C.后序遍历D.按层遍历
12.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的 。
A.先序遍历 B.中序遍历 C.后序遍历D.按层遍历
13.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用 。
A.求关键路径方法 B.求最短路径的Dijkstra方法
C.宽度优先遍历算法D.深度优先遍历算法
填空题
1.n个顶点的连通图至少 条边。
2.在无权图G的邻接矩阵中，若（vi,vj）或属于图G的边集，则对应元素A[i][j]等于 ，否则等于 。
3.在无权图G的邻接矩阵中，若A[i][j]等于1，则等于A[j][i]= 。
4.已知图G的邻接表如图所示，其从v1顶点出发的深度优先搜索序列为 ，其从v1顶点出发的宽度优先搜索序列为 。
5.已知一图的邻接矩阵表示，计算第i个结点的入度的方法是。
6.已知一图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是。
十、查找
单项选择题
1.顺序查找法适合于存储结构为 的线性表。
A.散列存储 B.顺序存储或链接存储
C.压缩存储 D.索引存储
2.对线性表进行二分查找时，要求线性表必须 。
A.以顺序方式存储 B.以顺序方式存储，且结点按关键字有序排列
C.以链接方式存储 D.以链接方式存储，且结点按关键字有序排列
3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 。
A.n B.n/2 C.（n+1）/2D.（n-1）/2
4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 。
A.O（n2） B.O（nlog2n） C.O（n）D.O（log2n）
5.二分查找和二叉排序树的时间性能 。
A.相同 B.不相同
6.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当二分查找值为82的结点时， 次比较后查找成功。
A.1 B.2 C.4D.8
7.设哈希表长m=14，哈希函数H（key）=key%11。
表中有4个结点：
addr（15）=4
addr（38）=5
addr（61）=6
addr（84）=7
其余地址为空
如用二次探测再散列处理冲突，关键字为49的结点的地址是 。
A.8 B.3 C.5D.9
8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为 。
A.35/12 B.37/12 C.39/12D.43/12
9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳地。
A.10 B.25 C.6D.625
10.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。
A.分块 B.顺序 C.二分D.散列
填空题
1.顺序查找法的平均查找长度为 ；二分查找法的平均查找长度为 ；分块查找法（以顺序查找确定块）的平均查找长度为 ；分块查找法（以二分查找确定块）的平均查找长度为 ；哈希表查找法采用链接法处理冲突时的平均查找长度为 。
2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。
3.二分查找的存储结构仅限于 ，且是 。
4.在分块查找方法中，首先查找 ，然后再查找相应的 。
5.长度为255的表，采用分块查找法，每块的最佳长度是 。
6.在散列函数H（key）=key%p中，p应取 。
7.假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为 ，则比较二次查找成功的结点数为 ，则比较三次查找成功的结点数为 ，则比较四次查找成功的结点数为 ，则比较五次查找成功的结点数为 ，平均查找长度为 。
8.对于长度为n的线性表，若进行顺序查找，则时间复杂度为；若采用二分法查找，则时间复杂度为 ；若采用分块查找（假设总块数和每块长度均接近n1/2），则时间复杂度为。
9.在散列存储中，装填因子α的值越大，则 ；α的值越小，则 。
十一、内排序
1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。
A.希尔排序 B.起泡排序 C.插入排序D.选择排序
2.设有1000个无序的元素，希望有最快的速度挑选出其中前10个最大的元素，最好采用
排序法。
A.起泡排序 B.快速排序 C.堆排序D.基数排序
3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。
A.插入排序 B.选择排序 C.快速排序D.归并排序
4.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为 。
A.79，46，56，38，40，80 B.84，79，56，38，40，46
C.84，79，56，46，40，38 D.84，56，79，40，46，38
5.一组记录的排序码为（46，79，56，38，40，84），则利用快速排序方法，以第一个记录为基准得到的一次划分结果为 。
A.38，40，46，56，79，84 B.40，38，46，79，56，84
C.40，38，46，56，79，84 D.40，38，46，84，56，79
6.一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为 。
A.16253548234079823672 B.16253548798223364072
C.16254835798223364072 D.16253548792336407282
7.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。
A.希尔排序 B.起泡排序 C.插入排序D.选择排序
8.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 。
A.希尔排序 B.归并排序 C.插入排序D.选择排序
9.用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
（1）25，84，21，47，15，27，68，35，20
（2）20，15，21，25，47，27，68，35，84
（3）15，20，21，25，35，27，47，68，84
（4）15，20，21，25，27，35，47，68，84
则采用的排序方法是 。
A.选择排序 B.希尔排序 C.归并排序D.快速排序
10.下列几种排序方法中，平均查找长度最小的是 。
A.插入排序 B.选择排序 C.快速排序D.归并排序
11.下列几种排序方法中，要求内存量最大的是 。
A.插入排序 B.选择排序 C.快速排序D.归并排序
12.快速排序方法在 情况下最不利于发挥其长处。
A.要排序的数据量太大 B.要排序的数据中含有多个值
C.要排序的数据已基本有序 D.要排序的数据个数为奇数
填空题
1.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第七个记录60插入到有序表时，为寻找插入位置需比较 次。
2.在利用快速排序方法对（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用而使用的栈的所能达到的最大深度为 ，共需递归调用的次数为 ，其中第二次递归调用是对 一组记录进行快速排序。
3.在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定性考虑，则应选取 方法；若只从平均情况下排序最快考虑，则应选取 方法；若从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。
4.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 。
5.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 ，需要内存量最多的是 。
6.在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ，若原始记录无序，则选用 。
7.在插入排序和选择排序中，若初始数据基本正序，则选用 ，若初始数据基本反序，则选用 ，
8.对n个元素的序列进行起泡排序时，最少的比较次数是 。
答案
一、绪论
选择题
升级会员 