数据结构应用题.docx
- 文档编号:1660805
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:15
- 大小:24.90KB
数据结构应用题.docx
《数据结构应用题.docx》由会员分享,可在线阅读,更多相关《数据结构应用题.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构应用题
北京语言大学网络教育学院
《数据结构》
【应用题】(
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 30
2、单链表结点的类型定义如下:
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
请画出这棵二叉树,并写出其前序遍历的结果。
答:
前序遍历结果:
ACBGDEHFJI
4、已知字符:
C1,C2,C3,C4,C5,C6的权分别为:
17,5,16,4,8,11,请构造相应的赫夫曼树,并给出相应字符的赫夫曼编码。
答:
c1:
10 c2:
1111 c3:
01 c4:
1110 c5:
110 c6:
00
5、已知如下图所示二叉树,分别写出其前序、中序和后序序列。
A
BC
DEF
答:
前序:
ABDECF、中序:
DBEACF、后序:
DEBFCA
6、已知某二叉树中序遍历的结果是ABC,试画出其可能的二叉树五种形态。
1、B2、C3、C4、A5、A
/\//\\
ACBABC
//\/
ABCB
7、一个一维整数数组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=10
9、一颗二叉树的中序序列和后序序列分别是DCBAEFG和DCBGFEA,请画出该二叉树并给出先序序列。
答:
先序为ABCDEFG
A
BE
CF
DG
10、设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起,逐个输入各个数据而生成的二叉搜索树。
答:
按顺序逐个输入
46
/\
2578
/\/
123762
/\
2970
11、已知一棵二叉树的先序序列是ABCDEFG,中序序列为CBEDAFG,请构造出该二叉树。
答:
A
/\
BF
/\\
CDG
/
E
12、有一组关键码序列(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("原始数据:
");
for(inti=0;i<8;i++)
printf("%d",kArr[i]);
printf("\n\n");
for(inti=0;i<8-1;i++)
{
boolbFlag=false;
for(intj=8-1;j>i;j--)
if(kArr[j] { intnTmp=kArr[j]; kArr[j]=kArr[j-1]; kArr[j-1]=nTmp; bFlag=true; } if(! bFlag)break; printf("第%d次排序: ",i+1); for(intk=0;k<8;k++) printf("%d",kArr[k]); printf("\n"); } return0; } 13、设图G= 画出该图,并写出所有的拓扑序列。 14、试编写一个函数,在一个顺序表A中查找出具有最大值和最小值的整数。 函数的原型如下所示,原型的参数表中给出顺序表对象为A,通过算法执行,从参数表中的引用参数Max中得到表中的最大整数,Min中得到表中的最小整数。 注意,函数中可使用顺序表的如下两个公有函数: intLength();求表的长度; intgetData(intk);提取第k个元素的值。 #include“SeqList.h” template voidFindMaxMin(SeqList 答: #include “SeqList.h” template void FindMaxMin(SeqList Max=Min=A.getData(0); for(int i=1; i if(A.getData(i)>Max) Max=A.getData(i); else if(A.getData(i) } } 15.根据下面的字母/频率表构造一棵Huffman树,并给出各字母的Huffman编码。 A B C D E F G H 25 10 36 4 5 6 11 3 答: #include #include #defineN8 usingnamespacestd; classNode { public: charc; intweight; intlchild; intrchild; intparent; 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; this->lchild=lc; this->rchild=rc; this->parent=p; } HuffmanTree: : HuffmanTree(charc[N],intw[N]) { leafNum=N; for(inti=0;i { data[i].c=c[i]; data[i].weight=w[i]; } intmin; intindex; intmin2; intindex2; for(inti=0;i { min=min2=INT_MAX; index=index2=-1; for(intj=0;j { if((data[j].parent==-1)&&(data[j].weight { min2=min; index2=index; min=data[j].weight; index=j; } elseif((data[j].parent==-1)&&(data[j].weight { 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;i { stringh=""; intp=i; while(data[p].parent! =-1) { if(p==data[data[p].parent].lchild)h="0"+h; elseh="1"+h; p=data[p].parent; } cout<<"字母"< "< } } 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},从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。 若发生不平衡,指明需做的平衡旋转的类型及平衡旋转的结果。 答: 3456364346484844652538452446990098456231353476587572421534672543632124267695519852476238951 17.编写实现“直接插入排序”的子函数,入口参数是整型数组L[]和数组长度n. 答: void sort(L, n) int L, n; { int i, x; for(i=1; i {x=L[i]; while(i>0 && L[i-1]>x) {L[i]=L[i-1]; i++; } L[i-1]=x; } } 18.简述顺序表和链表存储方式的特点。 答: 顺序表的优点是可以随机访问数据元素;缺点是大小固定,不利于增删结点。 链表的优点是采用指针方式增减结点,非常方便(只需要改变指针指向,不移动结点);缺点是不能进行随机访问,另外,每个结点上增加指针域,造成额外存储空间增大。 19.对链表设置头结点的作用是什么? (至少说出两条好处) 答: (1)对带头结点的链表,在表的任何结点之前插入结点或删除表中任何结点,所要做的都是修改前一结点的指针域,因为任何元素结点都有前驱结点。 若链表没有头结点,则首元素结点没有前驱结点,在其前插入结点或删除该结点时操作会复杂些。 (2)对带头结点的链表,表头指针是指向头结点的非空指针,因此空表与非空表的处理是一样的。 20.若用二叉链表作为二叉树的存储表示,试编写算法统计二叉树中叶结点的个数。 答: int&count) { if(T) { if((! T->lchild)&&(! T->rchild)) count++; CountLeaf(T->lchild,count); CountLeaf(T->rchild,count); } } #include"stdlib.h" #defineMAXNODE20 #defineISIZE8 #defineNSIZE07 #defineNSIZE18 #defineNSIZE215 //SHOWCHAR=1(显示字符)SHOWCHAR=0(显示数字) #defineSHOWCHAR1 structBTNode { intdata; BTNode*rchild; BTNode*lchild; }; structABTStack { BTNode*ptree; ABTStack*link; }; staticpCounter=0; /* 前序遍历函数pre_Order_Access()<非递归算法> 参数描述: BTNode*head: 根节点指针 */ voidpre_Order_Access(BTNode*head) { BTNode*pt; ABTStack*ps,*top; pt=head; top=NULL; printf("\n二叉树的前序遍历结果<非递归>: \t"); while(pt! =NULL||top! =NULL)/*未遍历完,或堆栈非空*/ { while(pt! =NULL) { if(SHOWCHAR) printf("%c",pt->data); else printf("%d",pt->data); ps=(ABTStack*)malloc(sizeof(ABTStack)); ps->ptree=pt; ps->link=top; top=ps; pt=pt->lchild; pCounter++; } if(top! =NULL) { pt=top->ptree; ps=top; top=top->link; free(ps); pt=pt->rchild; } } } 21.编写实现“起泡排序”的子函数,入口参数是整型数组L[]和数组长度n. 答: voidBubbleSort(intL[],intn) { inti,j,t; for(i=0;i { inthasChanged=0; for(j=1;j if(L[j-1]>L[j])t=L[j],L[j]=L[j-1],L[j-1]=t,hasChanged=1; if(hasChanged==0)break; } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 应用题