数据结构应用题

数据结构应用题1/12北京语言大学网络教育学院《数据结构》【应用题】（1、已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。答：第1趟：4121710730第2趟：4717101230第3趟：4710171230第4趟：4710121730第5趟：47101217302、单链表结点的类型定义如下：typedefstructLNode{intdata;structLNode*next;}LNode,*Linklist;写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。（注:不破坏A和B的原有结构）答：Merge(LinklistA,LinklistB,Linklist&C)voidMerge(LinklistA,LinklistB,Linklist&C){C=(Linklist)malloc(sizeof(LNode));pa=A-next;pb=B-next;pc=C;while(pa&&pb){pc-next=(Linklist)malloc(sizeof(LNode));pc=pc-next;if(pa-data=pb-data){pc-data=pa-data;pa=pa-next;}else{pc-data=pb-data;pb=pb-next;}}if(!pa)pa=pb;while(pa){pc-next=(Linklist)malloc(sizeof(LNode));pc=pc-next;pc-data=pa-data;pa=pa-next;}pc-next=NULL；}3、已知一棵非空二叉树，其按中序和后序遍历的结果分别为：中序：CGBAHEDJFI后序：GBCHEJIFDA请画出这棵二叉树，并写出其前序遍历的结果。答：前序遍历结果:ACBGDEHFJI4、已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并数据结构应用题2/12给出相应字符的赫夫曼编码。答：c1:10c2:1111c3:01c4:1110c5:110c6:005、已知如下图所示二叉树，分别写出其前序、中序和后序序列。答：前序：ABDECF、中序：DBEACF、后序：DEBFCA6、已知某二叉树中序遍历的结果是ABC，试画出其可能的二叉树五种形态。1、B2、C3、C4、A5、A/\//\\ACBABC//\/ABCB7、一个一维整数数组A[m]中有n(n≤m)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，在数组A[]中插入一个新的整数x，并使得插入后仍保持非递减有序。要求x插在值相等的整数后面。编写相应的函数实现。答：voidInsertSort(intA[],intm,int&n,intx)8、假设字符A,B,C,D,E,F的使用频率分别是0.07,0.09,0.12,0.22,0.23,0.27，写出A,B,C,D,E,F的Huffman（哈夫曼）编码。答：A=1110、B=1111、C=110、D=00、E=01、F=109、一颗二叉树的中序序列和后序序列分别是DCBAEFG和DCBGFEA,请画出该二叉树并给出先序序列。答：先序为ABCDEFGABECFDG10、设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。答：按顺序逐个输入46/\2578/\/123762/\2970ABCDEF数据结构应用题3/1211、已知一棵二叉树的先序序列是ABCDEFG，中序序列为CBEDAFG，请构造出该二叉树。答：A/\BF/\\CDG/E12、有一组关键码序列（38，19，65，13，49，41，1，73），采用冒泡排序方法由小到大进行排序，请写出每趟排序的结果。答：#includestdio.hint_tmain(intargc,_TCHAR*argv[]){intkArr[]={38,19,65,13,49,41,1,73};printf(原始数据：);for(inti=0;i8;i++)printf(%d,kArr[i]);printf(\n\n);for(inti=0;i8-1;i++){boolbFlag=false;for(intj=8-1;ji;j--)if(kArr[j]kArr[j-1]){intnTmp=kArr[j];kArr[j]=kArr[j-1];kArr[j-1]=nTmp;bFlag=true;}if(!bFlag)break;printf(第%d次排序：,i+1);for(intk=0;k8;k++)printf(%d,kArr[k]);printf(\n);}return0;}13、设图G＝V，E，V＝{1，2，3，4，5，6}，E={1，2，1，3，2，5，3，6，6，5，5，4，6，4}。画出该图，并写出所有的拓扑序列。14、试编写一个函数，在一个顺序表A中查找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。数据结构应用题4/12注意，函数中可使用顺序表的如下两个公有函数：intLength();求表的长度；intgetData(intk);提取第k个元素的值。#include“SeqList.h”templateclassTvoidFindMaxMin(SeqListint&A,int&Max,int&Min);答：#include“SeqList.h”templateclassTvoidFindMaxMin(SeqListint&A,int&Max,int&Min){Max=Min=A.getData(0);for(inti=1;iA.Length();i++){if(A.getData(i)Max)Max=A.getData(i);elseif(A.getData(i)Min)Min=A.geyData(i);}}15．根据下面的字母/频率表构造一棵Huffman树,并给出各字母的Huffman编码。ABCDEFGH251036456113答：#includeiostream#includestring#defineN8usingnamespacestd;classNode{public:charc;intweight;intlchild;intrchild;数据结构应用题5/12intparent;Node();Node(charc,intw,intlc,intrc,intp);};classHuffmanTree{public:Nodedata[2*N-1];intleafNum;HuffmanTree(charc[N],intw[N]);voidWriteHuffmanEncoding();};Node::Node(){c='';weight=0;lchild=-1;rchild=-1;parent=-1;}Node::Node(charc,intw,intlc,intrc,intp){this-c=c;this-weight=w;数据结构应用题6/12this-lchild=lc;this-rchild=rc;this-parent=p;}HuffmanTree::HuffmanTree(charc[N],intw[N]){leafNum=N;for(inti=0;iN;i++){data[i].c=c[i];data[i].weight=w[i];}intmin;intindex;intmin2;intindex2;for(inti=0;ileafNum-1;i++){min=min2=INT_MAX;index=index2=-1;for(intj=0;jleafNum+i;j++){if((data[j].parent==-1)&&(data[j].weightmin)){数据结构应用题7/12min2=min;index2=index;min=data[j].weight;index=j;}elseif((data[j].parent==-1)&&(data[j].weightmin2)){min2=data[j].weight;index2=j;}}data[leafNum+i].weight=min+min2;data[leafNum+i].lchild=index;data[leafNum+i].rchild=index2;data[index].parent=data[index2].parent=leafNum+i;}}voidHuffmanTree::WriteHuffmanEncoding(){for(inti=0;ileafNum;i++){stringh=;intp=i;while(data[p].parent!=-1)数据结构应用题8/12{if(p==data[data[p].parent].lchild)h=0+h;elseh=1+h;p=data[p].parent;}cout字母data[i].c的哈夫曼编码为：hendl;}}intmain(){charc[N]={'A','B','C','D','E','F','G','H'};intw[N]={25,10,36,4,5,6.11，3};HuffmanTreeht(c,w);ht.WriteHuffmanEncoding();}16．设有一个关键码的输入序列{55，88，100，120，90，150，40，20，95}，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。答：345636434648484465253845244699009845623135347658757242153467254363212426769551985247623895117．编写实现“直接插入排序”的子函数，入口参数是整型数组L[]和数组长度n.答：voidsort(L,n)intL,n;{inti,x;for(i=1;in;i++){x=L[i];while(i0&&L[i-1]x){L[i]=L[i-1];i++;}L[i-1]=x;数据结构应用题9/12}}18．简述顺序表和链表存储方式的特点。答：顺序表的优点是可以随机访问数据元素；缺点是大小固定，不利于增删结点。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）；缺点是不能进行随机访问，另外，每个结点上增加指针域，造成额外存储空间增大。19．对链表设置头结点的作用是什么？（至少说出两条好处）答：(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。20．若用二叉链表作为二叉树的存储表示，试编写算法统计二叉树中叶结点的个数。答：,int&count){if(T){if((!T-lchild)&&(!T-rchild))count++;CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);}}#includestdlib.h#defineMAXNODE20#defineISIZE8#defineNSIZE07#defineNSIZE18#defineNSIZE215//SHOWCHAR=1(显示字符)SHOWCHAR=0(显示数字)数据结构应用题10/12#defin