【2017年整理】数据结构期末考试复习提纲(专科).doc

数据结构复习提纲（专科） 一. 判断题（每题1分，共10分） 二. 填空题（每题1分，共20分） 三. 选择题（每题1分，共20分） 1-4章：20% 7-10章：80% 四．题0分） 五．程序填空（每空1分，共5分） 六．程序分析（每题5分） 七．编程（每题10分） （1）二叉树先序遍历 （2）二叉树层次遍历 （3）求二叉树中叶结点数 （4）求二叉树总结点数 （5）求二叉树高度 （6）顺序查找 （7）二分查找 （8）直接插入排序程序 （9）双向冒泡排序 （10）选择排序 （11）希尔排序 *（12）快速排序 四．题题 解： 2．P180五. 应用题 解： （1） 中序遍历序列：55 40 25 60 28 08 33 54 （2） 中序线索二叉树： 3．题图如下所示，画出邻接矩阵和邻接表 解（1）邻接矩阵 1 2 3 4 5 （2）邻接表 1 2 3 5 2 4 ∧ 3 5 ∧ 4 1 ∧ 5 4 ∧ 4． P204四. 应用题 （2）： 已知一个无向图有6个结点，9条边，这9条边依次为（a，b）,（a，c）,（a，e）,（a，f），（b，c），（c，e），（c，d），（d，e），（e，f）。试画出该无向图，并从顶点a出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。（5分） 解： 从顶点0出发的深度优先搜索遍历的结点序列：a b c d e f（答案不唯一） 从顶点0出发的广度优先搜索遍历的结点序列：a b c e f d（答案不唯一） 5． P204四. 应用题 （3）：已知一个无向图的顶点集为：{a，b，c，d，e}，其邻接矩阵如下，画出图，写出顶点a出发按深度优先搜索进行遍历的结点序列。（5分） 解： （1） （2）深度优先搜索： a b d c e （答案不唯一） 广度优先搜索： a b e d c （答案不唯一） 6． P204四. 应用题 （6）：已知如图所示的有向图，请给出该图的: 每个顶点的入度、出度； 邻接表； （3） 邻接矩阵。 解：（1） （2） （3） 7．无向图G如图所示，（1）试画出邻接矩阵；（2）写出从A出发的深度优先遍历的序列。 解：（1） 邻接矩阵 （2）从A出发的深度优先遍历的序列： A B D C E G F（不唯一） 8．P232四. 应用题 （6）： 对于给定结点的关键字集合K={4，8，2，9，1，3，6，7，5}， （1）试构造一棵二叉排序树； （2）求等概率情况下的平均查找长度ASL。 解： （1）构造二叉排序树 （2）ASL=（1*1+2*2+3*4+4*2）/ 9 =2.78 （或=25/9） 9．P233四. 应用题 （11）： 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为13，散列函数为：H（K）=K % 13。 试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。 解：（1） 线性探测再散列解决冲突时所构造的散列表： 0 1 2 3 4 5 6 7 8 9 10 11 12 14 1 68 27 55 19 20 84 79 23 11 10 ① ② ① ④ ③ ① ① ③ ⑨ ① ① ③ （2）平均查找长度ASL=（1*6+2*1+3*3+4*1+9*1）/12=30/3=3 （3）试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。 10． P261四. 排序过程分析 （2）： 已知数据序列{18，17，60，40，07，32，73，65}，写出采用直接插入算法排序时，每一趟排序的结果。 解：