资源描述：
《数据结构期末考试复习总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1204班学委精心整理数据结构期末复习《数据结构》期末考试题型及分值（1）简答题6题*5分=30分简要回答要点（2）分析题6题*5分=30分给出结果（3）设计题1题*10分=10分设计思想及结果（4）编程题1题*10分=10分完整代码（5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度}考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构）二、非线性表（集合-树-图）}2.抽象数据类型数据对象-数据关系-基本操作3.算
2、法性质-要求（设计）-效率（度量）4.实例查找：高效查找算法排序：高效的排序算法分析题考试题目参考（1）1-2-3-4-5-6顺序建BBST（2）6-5-4-3-2-1顺序建BBST241204班学委精心整理数据结构期末复习简答题实例241204班学委精心整理数据结构期末复习设计题：（1）（2）数据结构试卷（一）三、计算题（每题6分，共24分）241204班学委精心整理数据结构期末复习1.在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data605078903440next3572041线性表为：（78，50，4
3、0，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)204.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数
4、据后堆的变化。见图124444422255285283452843图12图11四、阅读算法（每题7分，共14分）1.LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L－>next；p=L；241204班学委精心整理数据结构期末复习S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；查询链表的尾结点（2）说明语句组S2的功能；将第一个结点链接到链表的尾部，作为新的尾结点（3）
5、设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。返回的线性表为（a2,a3,…,an,a1）1.voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<data<<'';}}该算法的功能是：递归地后序遍历链式存储的二叉树五、算法填空（共8分）二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){ite
6、m=BST->data;//查找成功return __true__;}elseif(itemdata)returnFind(___BST->left__,item);elsereturnFind(____BST->right__,item);}//if}六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data=
7、=x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;}//CountX数据结构试卷（二）241204班学委精心整理数据结构期末复习三、应用题(36分)1．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。(22，40，45，48，80，78)，(40，45，48，80，22，78)2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink
