14、设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行折半搜索时的判定树（或扩充的二叉搜索树），并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 509 154 677 017 275 553 897 094 170 503 512 612 765 908 答：圆圈表示搜索不成功。 搜索成功的平均搜索长度：1/14（1+2*2+3*4+4*7）=45/14
搜索不成功的平均搜索长度：1/15（3*1+4*14）=59/15
15、已知一个无向网G如图所示，根据克鲁斯卡尔算法给出G的一棵最小生成树（要求给出生成过程的步骤）
1 3 4 2 9 6 4 5 7 2 7 5 3 6 5 3 6 8 5 4 6 6
16、已知有向图G=（V，E），其中
V={a,b,c,d,e,f,g},E={
17、设散列表为HT[13]，散列函数为H(key)=key % 13，用闭散列法解决冲突，对于下列关键码序列12，23，45，57，20，03，78，31，15，36构造表。若采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
18、已知二叉树的先序和中序序列如下，试构造出相应的二叉树。
21
先序：ABCDEFGHIJ 中序：CDBFEAIHGJ
19.有5个元素，其进栈次序为A,B,C,D,E,在各种可能的出栈次序中，以元素C,D最先出栈（即C第一个且D第二个出栈）的序列有哪些？
20、已知一个无向连通网络G，如下图所示，根据克鲁斯卡尔和普里姆算法画出一棵最小生成树（要求写出求解过程的步骤）。
1 21 19 5 33 16 11 4 18 2 6 14 6 5 3 7
21、设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需要记录的平均比较次数不超过2次。试问散列表需要设计多大？设a是散列表的装载因子，则有ASLsucc=(1/2)*[1+1/(1-a)]。
22、假定一组记录的排序码为(46，79，56，38，40，84，50，42)，若需利用堆排序方法将其排序为递增有序，请问应建立最小堆还是最大堆？并给出建立的初始堆。
23、设有一个10×10的对称矩阵A[10][10]，采取按行压缩存储的方式存放于一个一维数组B[]中，则数组B[]的容量应该有多大？若设A[0][0]为第一个元素，存放于B[0]，且数组A[][]的每一个数组元素在数组B[]中占一个数组元素位置，则A[8][5]在数组B[]中的地址是多少？
24、设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连接，每个页块可存放30个记录。若采用按桶散列，且要求搜索到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？
25、设有一个n×n的对称矩阵A，如图(a)所示。为了节约存储空间，可以只存储对角线及对角线以上的元素，或者只存储对角线和对角线以下的数据元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行优先方式存储于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：
（1）存放对称矩阵A上三角部分或下三角部分的一维数组B有多少个元素？
（2）若在一维数组B中从0号位置开始存储，则如图(a)所示的对称矩阵中的任意一个元素aij在只存储上三角部分的情况下（如图b所示）应存放于一维数组的什么下标位置？给出计算公式。
（3）若在一维数组B中从0号位置开始存储，则如图(a)所示的对称矩阵中的任意一个元素aij在只存储下三角部分的情况下（如图c所示）应存放于一维数组的什么下标位置？给出计算公式。
22
?a11?a?21????an1a12a22?an2?a1n??a2n??
????ann??a11?a?21????an1a12a22?an2?a1n??a2n??
????ann??a11?a?21????an1a12a22?an2?a1n??a2n??
????ann?(a)对称矩阵 (b)只存放上三角部分 (c)只存放下三角部分
26、设散列表为HT[13]，散列函数为H(key)=key % 13，用闭散列法解决冲突，对于下列关
键码序列12，23，45，57，20，03，78，31，15，36构造表。若采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
五、编程 题
1、假定数组A[n]中有多个零元素，试写出一个函数，将A中所有的非零元素依次移到数组A的前端。
2、设有一个线性表（e0，e1，?，en-2，en-1）存放在一个一维数组A[n]中的数据元素，请编写一个函数将这个线性表原地逆置，即将数组的这n个原址内容置换为（en-1，en-2，?，e1，e0），设数据元素ei为整型。
3、针对带表头结点的单链表，设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 函数首部为： ListNode* Max()
4、设二叉树的结点结构为（left，data，right）其中指针left和right分别指向结点的左右子女，请根据下面的函数声明编写出求一棵二叉树深度的算法，该深度由函数返回，参数BT指向一棵二叉树。
5、针对带表头结点的单链表，设计一个算法，通过一趟遍历在单链表中确定值最小的结点。 http://www.docin.com/p-57948594.html
template
Type tmp; for ( int i = 0; i <= ( n-1 ) / 2; i++ ) { tmp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = tmp; } }
23
6、假定二叉树采用二叉链表存储结构，试设计一个算法计算所有度为1的结点个数。 /*
设0度结点 1度结点 2度结点个数分别为x0 x1 x2 */
x0+x1+x2 = node_count; //三种结点数之和为总结点数
0*x0 + 1*x1 + 2*x2 = node_count - 1; //树枝数等于结点数减1（去掉根结点）
一式乘2减二式得
2*x0 + x1 = node_count + 1;
因此只要知道叶子数和总结点数就可得1度结点个数
7假设二叉树采用二叉链表存储结构存储，试设计一个算法，计算一棵给定二叉树的所有结点数。
typedef struct BiTNode { TElemType data; struct BiTNode *lchild ; //左孩子指针 struct BiTNode *rchild; // 右孩子指针 } BiTNode, *BiTree; void CountLeaf (BiTree T, int& count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } else return; } // CountLeaf 8设计一个算法，在带头结点的单链表head中删除一个data域值最小的结点。（假定该结点是唯一的）。
9、设顺序表A[1??m+n]中前m个元素递增有序，后n个元素递增有序，且这（m+n）个元素中没有重复元素，试设计一个迭代算法使得整个顺序表有序，要求算法时间尽可能少且空间复杂度为O(1)。
设有m+n个元素，前面m个有序，后n个有序，设计一个算法，使得整个顺序表有序 //算法 1 同 \顺序表示法及其练习.h\的 6 //算法 2，将顺序表A中较小的元素插入到B中 void merge2(SqList A,SqList&B) {
int i = 0,j = 0,k ; while(i < A.Length)
24
相关推荐：
loading