全国自学考试数据结构导论试题及答案(4套)

高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考

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

27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的_______。 28．选择排序的平均时间复杂度为_______。 三、应用题(本大题共5小题，每小题6分，共30分)

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

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

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

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

题32图

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

四、算法设计题(本大题共2小题，每小题7分，共14分) 34.编写计算二叉树中叶子结点数目的算法。 35.开散列表的类型定义如下：

typedef struct tagnode {keytype key; struct tagnode*next; }*pointer,node;

typedef pointer openhash［n］; 试写出开散列表上的查找算法。

第 9 页

高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考

2010年10月自考数据结构导论参考答案

第 10 页

高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考

第 11 页

高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考

2005年10月自考试卷数据结构导论

第 12 页