数据结构应用题Word格式文档下载.docx
- 文档编号:3106907
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:15
- 大小:24.90KB
数据结构应用题Word格式文档下载.docx
《数据结构应用题Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构应用题Word格式文档下载.docx(15页珍藏版)》请在冰点文库上搜索。
data<
=pb->
data)
data=pa->
data;
pa=pa->
}
else
data=pb->
pb=pb->
if(!
pa)pa=pb;
while(pa)
pc->
next=NULL;
}
3、已知一棵非空二叉树,其按中序和后序遍历的结果分别为:
中序:
CGBAHEDJFI后序:
GBCHEJIFDA
请画出这棵二叉树,并写出其前序遍历的结果。
前序遍历结果:
ACBGDEHFJI
4、已知字符:
C1,C2,C3,C4,C5,C6的权分别为:
17,5,16,4,8,11,请构造相应的赫夫曼树,并给出相应字符的赫夫曼编码。
c1:
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,请构造出该二叉树。
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++)
%d"
kArr[i]);
\n\n"
8-1;
boolbFlag=false;
for(intj=8-1;
j>
i;
j--)
if(kArr[j]<
kArr[j-1])
intnTmp=kArr[j];
kArr[j]=kArr[j-1];
kArr[j-1]=nTmp;
bFlag=true;
bFlag)break;
第%d次排序:
i+1);
for(intk=0;
k<
k++)
kArr[k]);
\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中得到表中的最小整数。
注意,函数中可使用顺序表的如下两个公有函数:
intLength();
求表的长度;
intgetData(intk);
提取第k个元素的值。
#include“SeqList.h”
template<
classT>
voidFindMaxMin(SeqList<
int>
A,int&
Max,int&
Min);
#include
“SeqList.h”
template
<
class
T>
void
FindMaxMin(SeqList<
A,
int&
Max,
Min)
{
Max=Min=A.getData(0);
for(int
i=1;
A.Length(
i++)
if(A.getData(i)>
Max)
Max=A.getData(i);
else
if(A.getData(i)<
Min=A.geyData(i);
}
15.根据下面的字母/频率表构造一棵Huffman树,并给出各字母的Huffman编码。
A
B
C
D
F
G
H
25
10
36
4
5
6
11
3
#include<
iostream>
string>
#defineN8
usingnamespacestd;
classNode
public:
charc;
intweight;
intlchild;
intrchild;
intparent;
Node();
Node(charc,intw,intlc,intrc,intp);
};
classHuffmanTree
Nodedata[2*N-1];
intleafNum;
HuffmanTree(charc[N],intw[N]);
voidWriteHuffmanEncoding();
Node:
:
Node()
c='
'
;
weight=0;
lchild=-1;
rchild=-1;
parent=-1;
Node(charc,intw,intlc,intrc,intp)
this->
c=c;
weight=w;
lchild=lc;
rchild=rc;
parent=p;
HuffmanTree:
HuffmanTree(charc[N],intw[N])
{
leafNum=N;
for(inti=0;
i<
N;
i++)
data[i].c=c[i];
data[i].weight=w[i];
}
intmin;
intindex;
intmin2;
intindex2;
leafNum-1;
min=min2=INT_MAX;
index=index2=-1;
for(intj=0;
j<
leafNum+i;
j++)
if((data[j].parent==-1)&
(data[j].weight<
min))
min2=min;
index2=index;
min=data[j].weight;
index=j;
elseif((data[j].parent==-1)&
min2))
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;
leafNum;
stringh="
intp=i;
while(data[p].parent!
=-1)
if(p==data[data[p].parent].lchild)h="
0"
+h;
elseh="
1"
p=data[p].parent;
cout<
字母"
data[i].c<
的哈夫曼编码为:
h<
endl;
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.
sort(L,
n)
int
L,
n;
i,
x;
for(i=1;
{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)&
(!
rchild))
count++;
CountLeaf(T->
lchild,count);
rchild,count);
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;
\n二叉树的前序遍历结果<
非递归>
:
\t"
while(pt!
=NULL||top!
=NULL)/*未遍历完,或堆栈非空*/
=NULL)
if(SHOWCHAR)
%c"
pt->
data);
ps=(ABTStack*)malloc(sizeof(ABTStack));
ps->
ptree=pt;
link=top;
top=ps;
pt=pt->
lchild;
pCounter++;
if(top!
pt=top->
ptree;
ps=top;
top=top->
link;
free(ps);
rchild;
21.编写实现“起泡排序”的子函数,入口参数是整型数组L[]和数组长度n.
voidBubbleSort(intL[],intn)
inti,j,t;
for(i=0;
inthasChanged=0;
for(j=1;
j<
n-i;
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文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 应用题