数据结构练习试题和答案解析.docx

:..完美WORD格式81413调整方法:根结点不平衡:根左子树高>右子树高+1:根的中序序列8,11,13,14,15,20中根的前一点14上移为根**********根左子树高<右子树高+1:(快速排序)对数据序列(49,38,65,97,76,134,27,49)进行排序,写出排序过程。并说明冒泡排序是否为稳定排序。冒泡排序法稳定快速排序不稳定49,38,65,97,76,134,27,4949,38,65,97,76,134,27,4949,65,97,76,134,38,49,2749,38,27,49,76,134,97,65,65,97,76,134,49,49,38,2727,38,49,49,65,76,97,13497,76,134,65,49,49,38,2727,38,49,49,65,76,97,13497,134,76,65,49,49,38,27134,97,76,65,49,49,38,-树如图所示,(1)画出将关键字6插入之后的B-树;(2)画出在(1)所得树中插入关键字2之后的B-树。,(1)写出其邻接矩阵;(2)写出三种以顶点A为起点的深度优先搜索顶点序列。{a,b,c,d,e,f,g,h}各字符在电文中出现的频度分别为:7,26,2,28,13,10,3,11,试为这8个字符设计哈夫曼编码。要求:(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值);(2)按左分支为0和右分支为1的规则,分别写出与每个字符对应的编码。1004654212526b28d10f11h1213e57a2c3gA:0101b:10c:01000d:00e:011f:000g:01001h:001专业整理知识分享完美WORD格式四、算法阅读题(本大题共4小题,每小题5分,共20分)四、算法阅读题(本大题共4小题,每小题5分,共20分),阅读下列算法f30,并回答问题:(1)设线性表为(a1,a2,a3,a4,a5,a6,a7),写出执行算法f30后的线性表;(2)简述算法f30的功能。voidf30(LinkListL){//L为带头结点单链表的头指针LinkListp,q;P=L;while(p&&p–>next){q=p–>next;//q指向第一个点p–>next=q–>next;//p的下一个指向第二个点,删除了第一个点p=q–>next;//p指向第二个点free(q);//回收q}}专业整理知识分享完美WORD格式(1)(a2,a3,a4,a5,a6,a7),(2)删除了链表第一个点(不是头结点),阅读算法并回答问题:(1)画出n为十进制的1348时算法执行过程中栈的动态变化情况;(2)说明算法中while循环完成的操作。voidf31(intn)//n为非负的十进制整数{inte;SeqStackS;InitStack(&S);do{Push(&S,n%8);n=n/8;}while(n);while(!StackEmpty(&S)){e=Pop(&S);printf(〞%ld〞,e);}}(1)4,0,52专业整理知识分享完美WORD格式(2),阅读算法f32,并回答问题:(1)设二叉树T如图所示,写出执行f32(T)的返回值;(2)简述算法f32的功能。intf32(BinTreeT){intm,n;if(!T)return0;else{m=f32(T–>lchild);n=f32(T–>rchild);if(m>n)returnm+1;elsereturnn+1;}专业整理知识分享完美WORD格式(2),阅读算法f32,并回答问题:(1)设二叉树T如图所示,写出执行f32(T)的返回值;(2)简述算法f32的功能。intf32(BinTreeT){intm,n;if(!T)return0;el