数据结构应用题.docx

PAGE12/NUMPAGES12

北京语言大学网络教育学院

《数据结构》

【应用题】（

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,LinklistC)

voidMerge(LinklistA,LinklistB,LinklistC)

{C=(Linklist)malloc(sizeof(LNode));

pa=A-next;pb=B-next;pc=C;

while(papb)

{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,intn,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},试画出从空树起，逐个输入各个数据而生