发布时间 : 星期四 文章数据结构习题更新完毕开始阅读144210a7195f312b3169a5d5
16.二叉平衡树要求任意结点的左右子树的高度必须相等。
四、应用题
1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 2. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63时的比较次数。
3.已知长度为 9 的表（48，65，32，81，12，25，50，04，56），若按表中元素的顺序依次插入到一棵初始为空的二叉排序树中：a.请画出此二叉排序树；b.若在表中再插入76和18，请画出新的二叉排序树。 4.已知如下所示长度为7的表（30，36，48，22，58，46，18），按表中元素的顺序插入一棵初始为空的二叉排序树，并求在等概率的情况下查找成功的平均查找长度。
5.设散列表的长度ｍ＝11；散列函数为Ｈ(Ｋ)＝Ｋ mod m，给定的关键码序列为19，14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功的平均搜索长度。
6.给定关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 },构造哈希表, 设定哈希函数 H(key) = key MOD 13 ( 表长=13 )。
(1)若采用线性探测再散列处理冲突(2)若采用二次探测再散列处理冲突(3)并计算等概率情况下查找成功的平均查找长度。
7.设散列表的长度为14, 待插入关键码序列为 { Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec }，散列函数为H (key) = ?i?2?，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。
字母 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 (1) 试画出相应的散列表；计算等概率下搜索成功的平均搜索长度；
8.设散列表HT[0..12],即表的大小为m=13。采用双散列法解决冲突。散列函数和再散列函数分别为：H0（key）=key% 13; 注：%是求余数运算（=mod）
Hi=(hi-1+REV(key+1)+1);ⅰ=1,2,3………,m-1其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37)=73, REV(7)=7等。若插入的关键码序列为｛2，8，31，20，19，18，53，27｝试画出插入这8个关键码后的散列表。
*9．一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？ 10.给定表{19,14,22,01,66,21,83,27,56,13,10} ①试按元素在表中的顺序构造一棵二叉排序树；
②判断该二叉排序树是否平衡，若不平衡，调整其为平衡二叉树。
49
11.已知一个长度为12的表（jan,feb,mar,apr,june,july,aug,sep,ocr,nov,dec），
①试按表中元素的次序依次插入一棵初始状态为空的二叉排序树。（以字符ASCII大小为序）画出相应的二叉排序树，并求出等概率情况下的查找成功的平均查找长度；
②若根据该二叉排序树对表中排序构成有序表，试求在等概率情况下查找成功的平均查找长度； ③按表中元素顺序构造出一棵平衡二叉树，并求出等概率情况下查找成功的平均查找长度。 12.设有一组关键字（17，13，14，153，29，35）需插入到表长为14的散列表中，请完成一下任务： ①设计一个适合该散列表的散列函数；
②用设计的散列函数将上述关键字插入到散列表中，画出其结构；并指出利用线性探测法②解决地址冲突时构造散列表的装填因子为多少。
13.现有线性表的关键字集合{33，41，20，24，30，13，01，67}共8个数据元素，已知散列函数为H(k)=(3k)，用开放定址法解决冲突，且d1=h(k)，di=(di-1+(7k)+1)(i=2,3,……)，
①试在0～10的散列地址空间中构造散列表，并计算出等概率情况下查找成功和查找失败的平均查找长度。
②采用链地址法解决地址冲突，构造哈希表，并求出等概率情况下查找成功的平均查找长度。 14.已知一个有序表（13，18，24，35，47，50，62，83，90，115，134），写出利用二分查找法查找90的过程。
15.将关键字序列26，38，12，45，73，64，30，56依次插入一棵空B-树中，从而构造一棵3阶B-树，请画出其构造过程。
16.含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？ 含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？
五、算法设计题
1.ST是一个采用顺序表存储的，且按关键字有序，试完成下列折半查找算法。 int Search_Bin(SSTable ST,KeyType key)
2. 试编写一个函数，在一个顺序表B中查找出具有最大值和最小值的整数。
函数的原型如下所示，原型的参数表中给出顺序表对象为B，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。注意，函数中可使用顺序表的如下两个公有函数： int Length( ); 求表的长度；
int getData(int k); 提取第k个元素的值。
void FindMaxMin(SeqList & B, int& Max, int& Min);
*3．设有一个关键码的输入序列{ 55， 31， 11， 37， 46， 73， 63， 02， 07 }
50