数据结构期末复习
1.完全二叉树的第5层有9个节点，该完全二叉树总计有多少个节点( B ).
A.41 B.24 C.40 D.25
2.具有21个顶点的无向图至少有多少条边才能形成连通图 ( B ).
A.21 B.20 C.22 D.210
3.假设以行序为主序存储二维数组A=array[1..40，1..80]，设每个数据元素占2个存储单元，基地址LOC[1,1]为8900，则LOC[21，14]的存储位置为( B ).
A.12288 B.12126 C.12286 D.12128
二维数组A[1..m，1..n]若按行优先存储，那么A的任意一个元素A[i][j]的存储首地址Loc(i，j)可由下式确定：Loc(i,j)=Loc(1，1)+[n×(i-1)+j-1]×b，其中，Loc(1，1)是第一个元素A[1][1]的首地址，b是每个元素占用的存储单元个数。代入数据便得Loc(21，14)=8900+[80×(21-1)+14-1]×2=12126。
4.完全二叉树顺序存储，结点X的编号为27，则其右孩子结点的编号是( A)
A.55 B.54 C.28 D.26
2N+1
5.具有11个结点的二叉树使用二叉链表进行存储，其中空指针的数目是( B ).
A.22 B.12 C.10 D.55
n个结点的二叉链表中，有2n个链域，每一条非空链域对应一条树枝，而树支的个数为n-1，空节点个数为2n-(n-1)=n+1
6.一棵二叉树，度为2结点数为174，度为1结点数为186，则叶子结点数为( C ).
A.187 B.173 C.175 D.185
7.已知序列3,16,33,37,57,65,66,83,85,100,112，则用折半查找法查找3需要进行( B )次比较.
A.1 B.3 C.2 D.4
①定义3个用来记录索引值的变量，变量min记录当前范围最小索引值，初始值为0；变量max记录当前范围最大索引值，初始值为数组长度-1；变量mid记录当前当前范围最中间元素的索引值，初始值为(min+max) / 2
②使用循环，判断当前范围下，最中间元素值与指定查找的数值是否相等
若相等，结束循环，返回当前范围最中间元素的索引值mid
若不相等，根据比较结果，缩小查询范围为上一次查询范围的一般
中间元素值比要查询的数值大，说明要查询的数值在当前范围的最小索引位置与中间索引位置之间，此时，更新查询范围为:
范围最大索引值 = 上一次中间索引位置 -1；
中间元素值比要查询的数值小，说明要查询的数值在当前范围的最大索引位置与中间索引位置之间，此时，更新查询范围为:
范围最小索引值 = 上一次中间索引位置 +1；
在新的查询范围中，更新中间元素值的位置，再次使用最中间元素值与指定查找的数值是否相等。
中间索引值 = (范围最小索引值 +范围最大索引值) / 2;
③每次查询范围缩小一半后，使用if语句判断，查询范围是否小于0个元素，若小于0个元素，则说明指定数值没有查询到，返回索引值-1。
mid分别指向65,33,3
8.有28个叶子的哈夫曼树的结点总数为 ( A ).
A.55 B.56 C.57 D.783
哈夫曼树，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。
9.具有47个顶点,1309条边的有向图，所有顶点度的和为( B ).
A.1081 B.2618 C.94 D.1309
无向图和有向图中每个顶点的度等于该顶点的入度与出度之和
总度数(D)等于边数(e)的两倍。D=2e
1.假设一颗二叉树的先序序列为ABDFHEGC,中序序列为DFHBGEAC,请画出该二叉树。
2.给定关键字查找序列：8,96,82,33,36,56,58,58,73 ，请构造二叉排序树。
3.有向图如下所示,画出其邻接矩阵存储(包括顶点存储和索引).
4.对如下图所示的AOE网络，计算各事件（顶点）的最早开始时间和最迟开始时间。
整个活动的完成时间是AOE图中从始点到终点的最长路径的长度，这条路径称为关键路径。关键路径上的活动称作关键活动。
注意：关键路径不一定只有一条。
1.最早发生时间：从前往后，前驱结点到当前结点所需时间，取最大值。
如上图中的节点D有两个前驱结点（节点B和C），节点B到节点D的最早发生时间是4+15也就是19，节点C到节点D的最早发生时间是4+12也就是16，因为19>16，所以节点D的最早发生时间是19.
结束节点（10）的最早发生时间和最迟发生时间相同。
2.最迟发生时间：从后往前，后继结点的最迟发生时间-边权值，取最小值。
如上图中的节点I的最迟发生时间为其后继节点J（只有一个）的最迟发生时间减去(I->j)的权值8即68-8=60.
看的博客链接：https://blog.****.net/qq_38071429/article/details/80407544
5.已知一个无向图如下图所示，要求用普里姆算法构造最小生成树（从顶点A开始），画出构造过程。
6.已知一组关键字{19,84,57,18,92,68,73,39}，请画出由该组关键字创建的大顶堆（画出结果即可。
7.设给定关键字输入序列为{93,44,56,90,123,112,112,96}，用散列法散列0-10的地址区。散列函数为H（k）=（k）MOD 11，发生冲突时使用二次探测再散列。请构造哈希表，并将结果填入下表。
8.设用于通信的电文由a、b、c、d、e、f、g、h 等8个字母组成, 字母在电文中出现的频率分别为:20,8,8,1,10,3,5,14。请构造哈夫曼树，并给每出每个字母的哈夫曼编码。