《数据结构应用题new》由会员分享，可在线阅读，更多相关《数据结构应用题new（10页珍藏版）》请在金锄头文库上搜索。
1、 一、应用题1. 已知关键字序列为：（74,33,52,41,13,88,66,59）哈希表长为9，哈希函数为：H (k)k %9，解决冲突用线性补偿探测法（取Q=5），试构造哈希表，并求出等概率下查找成功的平均查找长度。【答案】（1）哈希表: 0 1 2 3 4 5 6 7 8 597488134133526621211112(2) ASL=（5*1+3*2）/8=11/8 2. 已知一个AOV网如图所示。(1)试画出它的邻接链表。（顶点号递减出现在各邻接表中）(2)试写出按照拓扑排序算法得到的拓扑序列。【答案】(1)(2)v4,v6,v1,v3,v5,v23. 已知线性表的存储结构为顺序表
2、，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；（2）简述算法f30的功能。void f30 (SeqList *L) int i,j;for (i=j=0;ilength; i+)if(L-datai=0)if(i!=j)L-dataj=L-datai;j+；L-length=j;【答案】（1）L=(21,19,0,34,30)(2) 删除顺序表中小于0的数。4. 已知关键字序列34,26,47,12,63,41,22,59,利用堆排序的方法对其排序。（1）写出在构成初始堆后关键字的排列情况。（2）写
3、出在堆排序的过程中输出前4个记录时,每次调整后关键字的排列情况。【答案】（1）初始堆：12,26,22,34,63,41,47,59（2）输出12后：22，26，41，34，63，59，47 输出22后：26，34，41，47，63，59 输出26后：34，47，41，59，63 输出34后：41，47，63，595. 请用克鲁斯卡尔算法构造下图所示网络的最小生成树。【答案】最小生成树如下图所示：6. 给出一组关键字K=14,28,17,9,7,21,13,4,11,写出用下列方法排序时,第一趟结束时关键字的排列状态。 (1)快速排序(2)希尔排序(d1=4) (3)归并排序【答案】给出一组关
4、键字K=14,28,17,9,7,21,13,4,11,写出用下列方法排序时,第一趟结束时关键字的排列状态。 (1)快速排序：11,4,13,9,71421,17,28 (2)希尔排序(d1=4) ： 7,21,13,4,11,28,17,9,14(3)归并排序：11，28 9，17 7，21 4，13 117. 假设一棵二叉树的先根遍历序列为ABCDEFGHI，中根遍历序列为ADCEBFHIG。(1)画出该二叉树；（2）写出后根遍历序列。【答案】（1）二叉树：（2）后根遍历序列： DECIHGFBA8. 已知关键字序列为：（93,42,79,131,12,102,27），哈希表长为9，哈希函
5、数为：H (k)k %9，解决冲突用线性探测再散列法，试构造哈希表，并求出等概率下查找成功的平均查找长度。【答案】(1)哈希表: 0 1 2 3 4 5 6 7 8 2793121314279102(2) ASL=（5*1+1*2+1*6）/7=13/79. 设网络如图所示，试用普里姆算法按照并入最小生成树中边的次序填写下表(从顶点A开始)，并画出对应的最小生成树。 1 23 45始 点终 点权 值【答案】1 23 45始 点ARCCE终 点RCDEF权 值2223110. 依次读入给定的整数序列7，16，4，8，20，9，6，18，5，完成下列操作：1)构造一棵二叉排序树,计算在等概率情况下
6、该二叉排序树的平均查找长度ASL; 2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。【答案】（1）ASL=(1+2*2+3*3+3*4)/9=26/9（2）811. （1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。【答案】（1）如图所示.（2）4次12. 已知二叉树如右图所示。（1）画出该二叉树的二叉链表；（2）分别写出该二叉树的先根、中根和后根遍历序列。【答案】(1)（2）先
7、根遍历序列：ABDCEGF中根遍历序列: DBAEGCF后根遍历序列: DBGEFCA13. 已知关键字序列为：（70,31,52,41, 88,12,27,66）哈希表长为9，哈希函数为：H (k)k %9，解决冲突用线性探测再散列法，试构造哈希表，并求等概率下查找成功的平均查找长度。【答案】(1)哈希表: 0 1 2 3 4 5 6 7 8 8827123141667052(2) ASL=（4*1+2*2+1*3+1*4）/8 = 15/814. 设一段文字中七个常用汉字为的，地，得，和，个，在，是，每个字符的使用频率分别为26，6，4，7，9，8，18。请画出对应的哈夫曼编码树（按照每个
8、结点的左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。【答案】哈夫曼树：哈夫曼编码的地得和个在是11101110100001000010115. 假设以数组seqnm存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式；(3)设m=40,rear=13,quelen=19,求队头元素的位置；(4)写出一般情况下队头元素位置的表达式。【答案】(1)quelen=m(2)quelen=0(3)35(4)(rear-quelen+1+m)%m16. 下列是一棵五阶B-树,
9、依次执行以下两步操作,画出每一步执行后所得到的B-树形。(1)插入n;(2)删除e 。【答案】(1)插入n: (2)删除e:17. 选取哈希函数为H(K)=K % 13，用链地址法处理冲突。试在012的散列地址空间中对关键字序列87，25，310，08，27，132，68，95，187，123，70，63，47构造哈希表，并求出等概率下查找成功的平均查找长度。【答案】 H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(8)= 8 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)=68 % 13
10、=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11 H(47)=47 % 13=8 ASL=(1*10+2*3)/13=16/1318. 已知一组数据元素为（57，24，96，73，18，45，30，40，82），要求：（1）试从空树开始画出按元素排列顺序输入而生成的一棵二叉排序树；（2）画出删除结点57后的二叉排序树。【答案】(1) 二叉排序树:（2）删除结点57后的二叉排序树:或：19. 假设有一个如下图的88矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。若将
11、上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：(1)B数组的体积至少是多少?(2)若a18存储在B0中，a56存储在Bk中，则k值为多少?(1) (2)【答案】（1）36 （2）1320. 已知有向图的邻接表如图所示,(1)写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;(2)画出该有向图的逆邻接表。【答案】（1）ABDCE(2)21. 假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题:(1)设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f30后的线性表；(2)简述算法f30的功能。 void f
12、30(LinkList L)/L为带头结点单链表的头指针LinkList p,q;P =L;while (p &p-next)q = p-next;p-next =q-next;p =q-next;free(q); 【答案】（1）(a2,a4,a6)(2) 删除单链表中数据结点序号为奇数的那些结点。22. 已知有向图的邻接表如图所示,(1)写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;(2)画出该有向图的逆邻接表。【答案】（1）ABDCE(2) 23. 依次读入给定的整数序列7，16，4，8，20，9，6，18，5，完成下列操作：1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树
13、的平均查找长度ASL; 2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。【答案】（1）ASL=(1+2*2+3*3+3*4)/9=26/9（2）824. 假设通信电文使用的字符集为a,b,c,d,e,f,g，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。 (1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符； (2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。【答案】(1)25. 由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。【答案】前序序列:GHIJ 后序序列:HJIG26. 假设一棵树的先根序列为ABCEFIJGHKD，后根序列为BEIJFGKHCDA。请画出该树。【答案】（1）因为树的先根和后根遍历序列分别与其转换后对应的二叉树的
