数据结构应用题.doc

数据结构应用题
北京语言大学网络教育学院
《数据结构》

【应用题】（
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、单链表结点的类型定义如下：
typedef struct LNode {
        int data;
        struct LNode *next;
} LNode, *Linklist;
写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。
（注:不破坏A和B的原有结构）
答：Merge(Linklist A, Linklist B, Linklist &C )
void Merge(Linklist A, Linklist B, 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
B C

D E F

答：前序：ABDECF、中序：DBEACF、后序：DEBFCA
6、已知某二叉树中序遍历的结果是ABC，试画出其可能的二叉树五种形态。
1、B 2、 C 3、 C 4、 A 5、A
/ \ / / \ \
A C B A B C
/ / \ /
A B C B
7、一个一维整数数组A[m]中有n (n≤m)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，在数组A[ ]中插入一个新的整数x ，并使得插入后仍保持非递减有序。要求x 插在值相等的整数后面。编写相应的函数实现。
答：void InsertSort (int A[ ], int m , int & n , int x)
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
B E
C F
D G
10、设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
答：按顺序逐个输入
46
/ \
25 78
/ \ /
12 37 62
/ \
29 70

11、已知一棵二叉树的先序序列是ABCDEFG，中序序列为CBEDAFG，请构造出该二叉树。
答： A
/ \
B F
/ \ \
C D G
/
E
12、有一组关键码序列（38，19，65，13，49，41，1，73），采用冒泡排序方法由小到大进行排序，请写出每趟排序的结果。
答：#include "stdio.h"

int _tmain(int argc, _TCHAR* argv[])
{
int kArr[]={38,19,65,13,49,41,1,73};
printf("原始数据：");
for(int i=0;i<8;i++)
printf("%d ",kArr[i]);
printf("\n\n");
for(int i=0;i<8-1;i++)
{
bool bFlag=false;
for(int j=8-1;j>i;j--)
if(kArr[j]<kArr[j-1])
{
int nTmp=kArr[j];
kArr[j]=kArr[j-1];
kArr[j-1]=nTmp;
bFlag=true;
}
if(!bFlag) break;
printf("第%d次排序：",i+1);
for(int k=0;k<8;k++)
printf("%d ",kArr[k]);
printf("\n");
}
return 0;
}
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中得到表中的最小整数。
注意，函数中可使用顺序表的如下两个公有函数：
int Length( ); 求表的长度；
int getData(int k); 提取第k个元素的值。

#include “SeqList.h”
template <class T>
void FindMaxMin(SeqList<int>& A, int& Max, int& Min);
答：#include “SeqList.h”     
template <class T>  

void FindMaxMin(SeqList<int>& A, int& Max, int& Min) {      
Max=Min=A.getData(0); 

for(int i=1; i<A.Length( ); i++) { 

if(A.getData(i)>Max) Max=A.getData(i); 

else if(A.getData(i)<Min) Min=A.geyData(i);     
}  
}
15．根据下面的字母/频率表构造一棵Huffman树, 并给出各字母的Huffman编码。
A
B
C
D
E
F
G
H
25
10
36
4
5
6
11
3
答：#include<iostream>
#include<string>
#define N 8
using namespace std;
class Node
{
public:
char c;
int weight;
int lchild;
int rchild;
int parent;
Node();
Node(char c,int w, int lc, int rc, int p);
};
class HuffmanTree
{
public:
Node data[2 * N - 1];
int leafNum;
HuffmanTree(char c[N],int w[N]);
void WriteHuffmanEncoding();
};
Node::Node()
{
c=' ';
weight = 0;
lchild = -1;
rchild = -1;
parent = -1;
}
Node::Node(char c,int w, int lc, int rc, int p)
{
this->c = c;
this->weight = w;
this->lchild = lc;
this->rchild = rc;
this->parent = p;
}
HuffmanTree::HuffmanTree(char c[N],int w[N])
{
leafNum = N;
for (int i = 0; i < N; i++)
{
data[i].c = c[i];
data[i].weight = w[i];
}
int min;
int index;
int min2;
int index2;
for (int i = 0; i < leafNum - 1; i++)
{
min = min2 = INT_MAX;
index = index2 = -1;
for (int j = 0; j < leafNum + i; j++)
{
if ((data[j].parent == -1) && (data[j].weight < min))
{
min2 = min;
index2 = index;
min = data[j].weight;
index = j;
}
else if ((data[j].parent == -1) && (data[j].weight < 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;
}
}
void HuffmanTree::WriteHuffmanEncoding()
{
for (int i = 0; i < leafNum; i++)
{
string h = "";
int p = i;
while (data[p].parent != -1)
{
if (p == data[data[p].parent].lchild) h = "0" + h;
else h = "1" + h;
p = data[p].parent;
}
cout<<"字母"<<data[i].c<<"的哈夫曼编码为："<<h<<endl;
}
}
int main()
{
char c[N] = {'A', 'B','C', 'D', 'E','F', 'G', 'H'};
int w[N] = {25, 10, 36, 4, 5,6.11，3};
HuffmanTree ht(c,w);
ht.WriteHuffmanEncoding();
}

16．设有一个关键码的输入序列{ 55， 88， 100， 120， 90， 150， 40， 20，95}，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。
答：345 636 434 648 484 465 253 845 244 699 009 845 623 135 347 658 757 242 153 467 254 363 212 426 769 551 985 247 623 8951
17．编写实现“直接插入排序”的子函数，入口参数是整型数组L[ ]和数组长度n.
答：void  sort(L, n)     
int  L, n; 
{ int  i, x; 
for(i=1; i<n; 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"
#define MAXNODE 20
#define ISIZE 8
#define NSIZE0 7
#define NSIZE1 8
#define NSIZE2 15
//SHOWCHAR = 1(显示字符) SHOWCHAR = 0(显示数字)
#define SHOWCHAR 1
struct BTNode
{
int data;
BTNode *rchild;
BTNode *lchild;
};
struct ABTStack
{
BTNode *ptree;
ABTStack *link;
};
static pCounter = 0;
/*
前序遍历函数pre_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void pre_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.
答：void BubbleSort(int L[],int n)
{
int i,j,t;
for(i=0;i<n;i++)
{
int hasChanged=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;
}
}

12 / 12