海量资源，欢迎共阅
《数据结构》期末考试题型及分值
（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）
数据结构试卷（一）
海量资源，欢迎共阅
三、计算题（每题6分，共24分）
1. 在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。 A01234567 data next ?0?1??1??1??01010110110100?1??1??1?0?? 60 50 78 90 34 40 3 5 7 2 0 4 1 111线性表为：（78，50，40，60，34，90） 2. 请画出下图的邻接矩阵和邻接表。 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 2 4 4 2 2 2 图12 2 4 4 5 4 5 4 5 图11
8 8 3 四、阅读算法（每题7分，共14分） 2 3 8 4 5 海量资源，欢迎共阅
1. LinkListmynote(LinkListL)
{//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； }
returnL； } 请回答下列问题： （1）说明语句S1的功能； 查询链表的尾结点 （2）说明语句组S2的功能； 将第一个结点链接到链表的尾部，作为新的尾结点 （3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。 返回的线性表为（a2,a3,…,an,a1） 2. voidABC(BTNode*BT) { ifBT{ ABC(BT->left); ABC(BT->right); cout<
boolFind(BTreeNode*BST,ElemType&item) {
if(BST==NULL)
returnfalse;//查找失败 else{
if(item==BST->data){
数据结构期末考试复习总结,DOC
