数据结构导论2010年10月真题及答案解析（02142）

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

typedef struct tagnode

{ keytype key;

  struct tagnode*next;}

*pointer,node;

typedef pointer openhash[n];

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

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

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

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

如题32图所示无向图，(1)写出其邻接矩阵;(2)写出三种以顶点A为起点的深度优先搜索顶点序列。

题32图

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

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

一个具有n个顶点的有向完全图的弧数是_______。

n个顶点的无向图G用邻接矩阵A[n][n]存储，其中第i列的所有元素之和等于顶点Vi的_______。

选择排序的平均时间复杂度为_______。