资源描述：
《数据结构应用题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、北京语言大学网络教育学院《数据结构》【应用题】（1、已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。答：第1趟：4 12 17 10 7 30 第2趟：4 7 17 10 12 30 第3趟：4 7 10 17 12 30 第4趟：4 7 10 12 17 30 第5趟：4 7 10 12 17 302、单链表结点的类型定义如下：typedefstructLNode{ intdata; structLNode*ne
2、xt;}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(siz
3、eof(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、已知一棵非空二叉树，其
4、按中序和后序遍历的结果分别为：中序：CGBAHEDJFI后序：GBCHEJIFDA请画出这棵二叉树，并写出其前序遍历的结果。答：前序遍历结果:ACBGDEHFJI4、已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。答：c1:10 c2:1111 c3:01 c4:1110 c5:110 c6:005、已知如下图所示二叉树，分别写出其前序、中序和后序序列。ABCDEF答：前序：A
5、BDECF、中序：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,
6、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},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。答
7、：按顺序逐个输入46/2578//123762/297011、已知一棵二叉树的先序序列是ABCDEFG，中序序列为CBEDAFG，请构造出该二叉树。答：A/BF/\CDG/E12、有一组关键码序列（38，19，65，13，49，41，1，73），采用冒泡排序方法由小到大进行排序，请写出每趟排序的结果。答：#include"stdio.h"int_tmain(intargc,_TCHAR*argv[]){intkArr[]={38,19,65,13,49,41,1,73};printf(
8、"原始数据：");for(inti=0;i<8;i++)printf("%d",kArr[i]);printf("");for(inti=0;i<8-1;i++){boolbFlag=false;for(intj=8-1;j>i;j--)if(kArr[j]
