数据结构
- 格式：doc
- 大小：60.44 KB
- 文档页数：3
1.二叉树的第1、2个性质的证明。
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明：用数学归纳法证明：
归纳基础：i=1时，有2i-1=20=1。
因为第1层上只有一个根结点，所以命题成立。
归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。
由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。
即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。
性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。
因此利用性质1可得，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故命题正确。
2.一颗二叉树改造为完全二叉树和满二叉树。
（画图）
3.插入排序的基本过程。
基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。
4.希尔排序的基本过程。
基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。
如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。
5.实现堆排序需要解决那两个问题。
（1）怎样由一个无序的序列建立一个堆；
（2）如何在输出堆顶元素之后，调整剩余元素成为一个新的堆.
6.常见的线性查找有几种。
顺序检索
二分查找
分块查找亦称索引顺序查找
7.数组存储10个元素，请画出对应二叉判定树。
12345678910 136791214171921
8.图的遍历操作的复杂，主要表现在以下四个方面。
①在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
②在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
图的遍历通常有深度优先搜索和广度优先搜索两种方式
二、填空题
1、K个顶点的连通图至少有K-1条边。
2、在索引表中，每个索引项至少包含有关键码和地址两项。
3、栈的运算在栈顶进行。
4、求解带权连通图最小生成树的P r i m算法合适于稠密图的情形，而K r u s k a l算法适用于稀疏图。
5、在用K r u s k a l算法求解带权连通图的最小生成树时，选择权值最小的边的原则是该功能在图中构成回路。
6、深度优先生成树的高度比广度优先生成树的高度高。
7、先序遍历一棵树，根没有前驱结点。
8、n（n>0）个顶点的无向图中得顶点的度的最大值为n-1.
9、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于n+1。
10、迷宫是回溯控制问题，可使用递归方法来解决。
11、设有两个串t和p，求p在t中首次出现的位置的运算叫做模式匹配。
12、若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为（n+1）/2。
13、链表对于数据元素的插入和删除不需要移动结点，只需改变指针结点。
14、队列的插入操作在队尾进行，删除操作在队头进行。
15、下列排序算法中，算法最不稳定的是堆排序。
16、平衡因子的取值范围是-1~1。
17、假定一个链式列队的队头和队尾的指针分别为f r o n t和r e a r，则判断队空的条件为
f r o n t==r e a r。
18、利用2、3、4、9这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带全路径长度为32。
19、若让元素A,B,C依次进栈，则出栈次序不可能出现C,A,B的情况。
20、对于具有J条边的无向图，它的邻接表中有2J个边结点。
21、循环列队中，队头指针指向队头元素的位置。
22、在链表存储结构中进行删除操作的效率比在顺序存储结构中进行相同操作的效率高。
23、队列的插入操作在队尾进行，删除操作在队头进行。
24、如果一个过程或间接地调用自己，则称这个过程是一个递归过程。
25、对于一棵具有n个结点的树，该树中得所有结点的度数之和为n-1。
26、假定一棵树的广义表示为A(B(C,D(E,F,G),H(I,J))),则该书的高度为3。
27、以折半搜索方法从长度为n的有序表中搜索一个元素为时，时间复杂度为0(n l o g2)。
28、对n个数据对象进行堆排序，总时间长度为0(n l o g2）。
29、算法和程序原则上有没有区别？
算法是抽象的，程序是具体的。
算法是程序的理论基础，程序是算法的具体实现。
三、判断题
1、线索化二叉树中的每个结点通常包含5个数据成员。
（√）
2、进行折半搜索的表必须是顺序存储的有序表。
（√）
3、对二叉搜索树进行前序遍历得到的结点序列是一个有序序列。
（×）
4、有回路的有向图不能完成拓扑排序。
（√）
5、在链式存储表中存取表中得数据元素时，不一定要循链顺序访问。
（×）
6、二叉树中，序号为i 的结点，它的左孩子结点如存在，序号为i *2+1。
（×）
7、在用单链表表示的链式列队中，队头在链表的链尾位置。
（×）
8、有序树是二叉树的一种。
（√）
9、冒泡排序法是稳定的。
（√）
1.有序表（12,18,30,43,56,78,82,95）中折半搜索元素56时，其搜索长度为：3
2.向一棵A V L 树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为4中旋转类型。
3.若3个顶点的图G 的邻接矩阵为010001
010
，则图G 一定是有向图。
4.设有一个连通网络如图所示，试按如下格式，应用K r u s k a l 算法给出在构造最小生成树过程中顺序选出的各条边。
( 始顶点号，终顶点号， 权值
) ( 0 ,3,1)
( 2 ,5,2)
( 1, 4,3)
( 3, 5,4)
( 3,4,5 )
5.判断以下序列是否是最小堆，如果不是，将它调整为最小堆。
（1）{100,86,48,73,35,39,42,57,66,21}
不是最小堆，为最大堆，调整后为：{21,35,39,57,86,48,42,73,66,100} 0
1 2 3 4 5 6 6 1 8 7 5 3 4 2 6。
