1 2 0 4 班 学委精心整理 数据结构期末复习 1 《数据结构》期末考试题型及分值 （1）简答题 6 题*5 分=30 分 简要回答要点 （2）分析题 6 题*5 分=30 分 给出结果 （3）设计题 1 题*10 分=10 分 设计思想及结果 （4）编程题 1 题*10 分=10 分 完整代码 （5）综合题 1 题*20 分=20 分 抽象数据类型的定义、表示、实现、算法分析 {定义=功能（ADT） 表示=存储结构体 实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构 {一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型 数据对象-数据关系-基本操作 3.算法 性质-要求（设计）-效率（度量） 4.实例 查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6 顺序建 BBST （2）6-5-4-3-2-1 顺序建 BBST 1 2 0 4 班 学委精心整理 数据结构期末复习 2 简答题实例 1204 班 学委精心整理 数据结构期末复习 3 设计题： （1） （2） 数据结构试卷（一） 三、计算题（每题 6 分，共 2 4 分） 1. 在如下数组 A 中链接存储了一个线性表，表头指针为 A [0].nex t，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 线性表为：（7 8 ，5 0 ，4 0 ，6 0 ，3 4 ，9 0 ）0111010101110111010101110 2. 请画出下图的邻接矩阵和邻接表。 1204 班 学委精心整理 数据结构期末复习 4 3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4.画出向小根堆中加入数据4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。见图12 图12 图11 四、阅读算法（每题7 分，共14 分） 1. LinkList mynote(LinkList L) {//L 是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下...
