数据结构复习题

一、计算题

1.稀疏矩阵A如下，写出矩阵A的三元组表及矩阵A的转置矩阵的三元组表。

0 3 0 0 0 10 0 0 0 0 05 -1 0 0 0 0 0 0 0 0 4 0-3 0 0 0 0 0

2.一棵二叉树的前根遍历序列为ABCDEFG，中根遍历序列为CBDAEGF，试构造出该二叉树。

3.下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。

 1 12 5 101  8 9 12 8   25 9   410  2 4 

4.给定表（80，90，50，70，75，60，40，100），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

5.试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。

6．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）

7．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。

8．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉

排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。

9．如图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优先搜索顶点序列。

10．用冒泡排序法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。

11.

12．

13.

14.

15.

二、算法设计题

1.编写计算二叉树中叶子结点数目的算法。

2.开散列表的类型定义如下：

typedefstructtagnode {keytype key; structtagnode*next; }*pointer,node;

typedef pointer openhash［n］;

试写出开散列表上的查找算法。

3.试分别写出二叉树的先根遍历和中根遍历的递归算法。

void Preorder (BiTree T) //先序遍历二叉树 { if(T)

{

visit(T->data); // 访问根结点 Preorder(T->lchild); // 遍历左子树 Preorder(T->rchild);// 遍历右子树 } }

voidOrder (BiTree T) //中序遍历二叉树 { if(T)

{

Preorder(T->lchild); // 遍历左子树

visit(T->data); // 访问根结点 Preorder(T->rchild);// 遍历右子树 } }

4.试编写以单链表为存储结构实现直接选择排序的算法。 .

5.