发布时间 : 星期二 文章数据结构习题更新完毕开始阅读144210a7195f312b3169a5d5
{ ;
for (w=FirstAdjVex(G,u));w>=0;w= ) if (!visited[w])
{ visited[w]=TRUE; Visit(w); ; } } } }
2．已知有向图G用邻接矩阵存储，设计算法以分别求解顶点vi的入度、出度和度。
3．已知图G用邻接矩阵存储，设计算法以分别实现函数firstadj（G，v）和nextadj(G,v,w)。 4．设图G用邻接矩阵A[n+1,n+1]表示，设计算法以判断G是否是无向图。
5．已知图G用邻接表存储，设计算法以输出其所有边或弧。（假设各表头指针在数组A[n+1]中） 6．设计算法以判断顶点vi到vj之间是否存在路径？若存在，则返回TRUE，否则返回FALSE。 7．设计算法以判断无向图G是否是连通的，若连通，返回TRUE，否则返回FALSE；
8．设G是无向图，设计算法求出G中的边数。（假设图G分别采用邻接矩阵、邻接表以及不考虑具体存储形式，而是通过调用前面所述函数来求邻接点）
9．设G是无向图，设计算法以判断G是否是一棵树，若是树，则返回TRUE，否则返回FALSE； 10．设G是有向图，设计算法以判断G是否是一棵以v0为根的有向树，若是返回TRUE，否则返回FALSE； 11．设连通图用邻接表A表示，设计算法以产生dfs（1）的dfs生成树，并存储到邻接矩阵B中。 12．设计算法以求解从vi到vj之间的最短路径。（每条边的长度为1） 13．设计算法以求解距离v0最远的一个顶点。
六、简答题
4．一个强连通图中各顶点的度有什么特点？
23．在图分别采用邻接矩阵和邻接表存储时，prim算法的时间复杂度是否一致？为什么？ 24．在实现Kruskal算法时，如何判断某边和已选边是否构成回路？
45
第八章 查找
一、单项选择题
1.设有100个数据元素，采用折半搜索时，最大比较次数为( ) A.6 B.7 C.8 D.10
2．含有n各结点的二叉排序树在最坏情况下查找成功时的平均查找长度为（设每个纪录的查找概率相等）（ ）
A.n B.(n-1)/2 C.(n+1)/2D.n-1
3.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。
A. 20 B. 18 C. 25
D. 22
4.5阶B树中，每个结点最多有（ ）个关键码。
A．2 B．3 C．4 D．5
5.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（ ）个表项。（设搜索成功的平均搜索长度为S=(n+1/(1-a))/2,其中a 为装填因子） A.400 B.526 C.624 D.676
6．适于对动态查找表进行高效率查找的组织结构是（ ）
A．有序表 B．分块有序表 C．三叉排序树 D．线性链表 7.采用顺序查找法检索长度为n的线性表，则检索每个元素的平均比较次数为_____。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 8.适于对动态查找表进行高效率查找的组织结构是_____。 A.有序表 B.分块有序表 C.二叉排序树 D.线性链表
9.如果要求一个线性表既能快速查找，又能适应动态变化的要求，则宜采用的检索方法是_____。 A.分块检索 B.顺序检索 C.二分检索 D.基于属性检索 10.对线性表进行二分查找时，要求线性表必须_____。
A.键值有序的链接表 B.键值有序的顺序表 C.链接表但键值不一定有序 D. 顺序但键值不一定有序
11.有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当用二分查找法查找键值为84的结点时，经_____比较后查找成功。
A. 2 B. 3 C. 4 D. 12
12.顺序检索一个具有n个数据元素的线性表，其时间复杂度为_____，二分检索一个具有n个数据元素的线性表，其时间复杂度为_____。
46
A. O(n) B. O(log2n) C. O(n2) D. O(nlog2n) 13.在一棵3阶B-树上，每个结点包括的子树相同，最多为_____，最少为_____。 A. 1 B. 2 C. 3 D. 4
14.设散列表长度为m，散列函数为H（key）=key%p，为了减少发生冲突的可能性，p应取_____。
A.小于m的最大奇数 B.小于m的最大素数 C.小于m的最大偶数 D.小于m的最大合数
二、填空题
1.查找算法中的两种最基本的操作是比较和 。
2．在分块查找中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成 块最好；若分成25块，其平均查找长度为 。
3. 在一棵AVL树(高度平衡的二叉搜索树)中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。
4. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_____上。 5.具有n条记录的顺序表中，在查找概率相等的情况下顺序查找平均查找长度为 。 6．影响哈希表关键字比较次数的因素有三个： 、 、 。 7．利用关键码分别为10， 20， 30， 40的四个结点，能构造出 种不同的二叉搜索树。
8．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为_____。 9.采用二分法进行查找的查找表，应选择____________________方式的存储结构。 10.在各种查找法中，平均查找长度与结点个数n无关的查找方法是____________________。 11.在分块查找法中，首先查找___________________，然后再查找相应的_______________。
12.假设在有序表A[0……9]中进行二分查找，比较一次查找成功的结点数为_________，比较二次查找成功的结点数为______，比较三次查找成功的结点数为________，比较四次查找成功的结点数为________，比较五次查找成功的结点数为__________，平均查找长度为__________________。
13.查找有序表R[0……11]中每个数据元素，假设查找在等概率情况下进行，则进行顺序查找的平均查找长度为_____________，进行二次查找的平均查找长度为____________。
14.假设在线性表R[0……59]中进行分块查找，共分10块，每块长度为6，若利用顺序查找法对索引表和子块进行查找，则查找每个元素的平均查找长度为_________________。
15.在散列存储中，装填因子a的值越大，存取数据元素时发生冲突的可能性就______，装填因子a的值越小，存取数据元素时发生冲突的可能性就____________________。
16.在一个10阶B-树中，每个根结点所含关键字的数目最多允许为_________，最少允许为__________。
47
17.一棵深度为h的B-树上，任一个叶子结点所处的层数为_____________，当向该B-树插入一个新结点时，为了检索插入位置需读取_________________个结点。
18.当向B-树中插入关键字时，可能引起结点___________，最终可能导致该B-树的高度___________，当从B-树中删除关键字时，可能引起结点___________，最终可能导致该B-树的高度___________。 19.排序是将一组任意排列的数据元素按__________的值从小到大或从大到小重新排列成有序的序列。 20.在排序前，关键字值相等的不同记录间的前后相对位置保持________的排序方法称为稳定的排序方法。 21.在排序前，关键字值相等的不同记录间的前后相对位置_________的排序方法称为不稳定的排序方法。 22.外部排序是指在排序前被排序的全部数据都存储在计算机的_____________储器中。 23.当数据已经有序时，不再进行排序的方法是_________________排序方法。
24.在堆排序中，首先要使数据成堆，在堆中所有的____________都不比其孩子结点小（或大）。 25.在直接插入排序的方法中，当需要将第i个数据插入时，此时前i-1个数据是___________的。 26.对一个基本有序的数据进行排序___________________排序方法运算次数最少。
三、判断题
1.折半搜索只适用于有序表，包括有序的顺序表和有序的链表。 2．分块查找比折半查找的查找效率高。
3. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。 4. 中序遍历一棵二叉排序树德结点就可以得到排好序的结点序列。 5.一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。
6.当3阶B 树中有255个关键码时，其最大高度（包括失败结点层）不超过8。 7.一棵3阶B 树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B 树。 8. 在对哈希表的查找中只需要函数的计算，不需要关键字的比较。 9.闭散列法通常比开散列法时间效率更高。
10.在用散列表存储关键码集合时，可以用再散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小m互质。
11.哈希表中装填因子越小，查找时发生冲突的可能性就越小。 12.装载因子是散列表的一个重要参数，它反映了散列表的装满程度。
13.在等概率情况下实现分块查找，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。
14.删除一个排序二叉树中的一个结点，在重新插入上去，一定能得到原来的二叉排序树。 15.只要采用顺序存储结构存放的数据元素，都可以利用折半查找法进行查找。
48