数据结构期末考试复习总结.docx

《数据结构期末考试复习总结.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试复习总结.docx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结数据结构期末考试题型及分值（1）简答题6题*5 分=30 分简要回答要点（2）分析题6题*5 分=30 分给出结果（3）设计题1题*10 分=10 分设计思想及结果（4）编程题1题*10 分=10 分完整代码（5）综合题1题*20 分=20 分抽象数据类型的定义、表示、实现、算法分析 定义=功能（ ADT） 表示=储备结构体实现 =算法（基本操作）算法分析=时间、空间复杂度考试概念有： 1. 数据结构 一、线性表（栈 - 队- 列- 串- 数组 - 广义表 - 规律结构 - 储备结构 - 运算结构） 二、非线性表（集合- 树- 图） 2.抽象数据类型数据对象 - 数据关系 -

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 ,试写出该线性表。A01234567data605078903440next3572041011101010111011101010

3、1110线性表为：（ 78, 50, 40, 60, 34, 90）2. 请画出下图的邻接矩阵和邻接表。可编辑资料 - - - 欢迎下载精品名师归纳总结3. 已知一个图的顶点集V 和边集 E 分别为： V=1,2,3,4,5,6,7; E=1,23,1,35,1,48,2,510,2,36,3,415,3,512,3,69,4,64,4,720,5,618,6,725;用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。用克鲁斯卡尔算法得到的最小生成树为：1,23,4,64,1,35,1,48,2,510,4,7204. 画出向小根堆中加入数据4, 2, 5, 8, 3 时,

4、每加入一个数据后堆的变化。见图12442222可编辑资料 - - - 欢迎下载精品名师归纳总结24454545可编辑资料 - - - 欢迎下载精品名师归纳总结图 122883可编辑资料 - - - 欢迎下载精品名师归纳总结3584图 11四、阅读算法（每题7 分,共 14 分）1. LinkList mynoteLinkList L/L 是不带头结点的单链表的头指针ifL&L-nextq=L 。 L=L next 。 p=L 。S1：whilep next p=p next 。 S2：p next=q 。 q next=NULL 。returnL。可编辑资料 - - - 欢迎下载精品名师归纳总

5、结性表。请回答以下问题：（ 1）说明语句 S1 的功能。 查询链表的尾结点（ 2）说明语句组 S2 的功能。将第一个结点链接到链表的尾部,作为新的尾结点（ 3）设链表表示的线性表为（a1,a2, ,an） ,写出算法执行后的返回值所表示的线可编辑资料 - - - 欢迎下载精品名师归纳总结返回的线性表为（ a2,a3, ,an,a1 ）2. void ABCBTNode * BTifBT ABC BT-left;ABC BT-right;可编辑资料 - - - 欢迎下载精品名师归纳总结coutdatadataitem=BST-data;/查找胜利return true; else ifitemd

6、ata可编辑资料 - - - 欢迎下载精品名师归纳总结return Find else return Find /ifBST-left _,item;_BST-right ,item;可编辑资料 - - - 欢迎下载精品名师归纳总结六、编写算法（共8 分）统计出单链表HL 中结点的值等于给定值X 的结点数。int CountXLNode* HL,ElemType x int CountXLNode* HL,ElemType xint i=0; LNode* p=HL;/i为计数器whilep.=NULL if P-data=x i+; p=p-next;/while,出循环时 i 中的值即为

7、x 结点个数return i;/CountX数据结构试卷（二） 三、应用题 36 分1. 设一组初始记录关键字序列为45 ,80,48,40,22,78 ,就分别给出第 4 趟简洁挑选排序和第 4 趟直接插入排序后的结果。22 , 40, 45,48, 80, 78 ,40 , 45, 48,80, 22, 782. 设指针变量 p 指向双向链表中结点A,指针变量 q 指向被插入结点B,要求给出在结点 A 的后面插入结点B 的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。q- llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rl

8、ink=q;3 设一组有序的记录关键字序列为13 ,18,24, 35,47,50,62,83,90 ,查找方法用二分查找,要求运算出查找关键字62 时的比较次数并运算出查找胜利时的平均查找长度。2,ASL=91*1+2*2+3*4+4*2=25/9可编辑资料 - - - 欢迎下载精品名师归纳总结4 设一棵树 T 中边的集合为 A ,B ,A ,C, A ,D ,B ,E ,C,F,C,G ,要求用孩子兄弟表示法（二叉链表）表示出该树的储备结构并将该树转化成对应的二叉树。树的链式储备结构略,二叉树略5. 设有无向图 G,要求给出用普里姆算法构造最小生成树所走过的边的集合。E=1 , 3, 1,

9、 2, 3, 5, 5, 6, 6, 46. 设有一组初始记录关键字为45 ,80,48,40,22,78 ,要求构造一棵二叉排序树并给出构造过程。四、算法设计题 16 分1. 设有一组初始记录关键字序列（K1, K2, Kn）,要求设计一个算法能够在On 的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki ,右半部分的每个关键字均大于等于Ki 。设有一组初始记录关键字序列（K1, K2, Kn ）,要求设计一个算法能够在On 的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki ,右半部分的每个关键字均大于等于 Ki 。void quickpassint

10、 r, int s, int tint i=s, j=t, x=rs; whileijwhile ix j=j-1; if ij ri=rj;i=i+1;while ij & rix i=i+1; if inextforq=hb;q.=0;q=q-next if q-data=p-data break;可编辑资料 - - - 欢迎下载精品名师归纳总结ifq.=0 t=lklist *mallocsizeoflklist; t-data=p-data;t-next=hc; hc=t;数据结构试卷（三）三、运算题 每题 10 分,共 30 分1.已知二叉树的前序遍历序列是AEFBGCDHIKJ ,

11、中序遍历序列是EFAGBCHKIJD ,画出此二叉树,并画出它的后序线索二叉树。可编辑资料 - - - 欢迎下载精品名师归纳总结NULLAEBFGCD可编辑资料 - - - 欢迎下载精品名师归纳总结HFKJ2已知待散列的线性表为（36, 15, 40, 63, 22）,散列用的一维的址空间为0 .6 ,假定选用的散列函数是H（ K ） = K mod 7 ,如发生冲突采纳线性探查法处理,试：H36=36 mod 7=1;H 22=1+1 mod 7=2; .冲突H15=15 mod 7=1; .冲突H 222=2+1 mod 7=3;H 15=1+1 mod 7=2;H40=40 mod 7=

12、5;H63=63 mod 7=0;H22=22 mod 7=1; .冲突（1） 运算出每一个元素的散列的址并在下图中填写出散列表：01234566336152240（2） 求出在查找每一个元素概率相等情形下的平均查找长度。可编辑资料 - - - 欢迎下载精品名师归纳总结1ASL=211351.6可编辑资料 - - - 欢迎下载精品名师归纳总结3已知序列（ 10,18,4,3,6,12,1,9, 18,8）请用快速排序写出每一趟排序的结果。8,9,4,3,6,1,10,12,18,181,6,4,3,8,9,10,12,18,181,3,4,6,8,9,10,12,18,181,3,4,6,8,

13、9,10,12,18,181,3, 4,6,8,9,10,12,18,18四、算法设计题 每题 15 分,共 30 分1. 设计在单链表中删除值相同的余外结点的算法。设计在单链表中删除值相同的余外结点的算法。typedef int datatype;可编辑资料 - - - 欢迎下载精品名师归纳总结typedef struct node datatype data; struct node *next;lklist; void delredundantlklist *&headlklist *p,*q,*s; forp=head;p.=0;p=p-nextforq=p-next,s=q;q.=0

14、; if q-data=p-data s-next=q-next; freeq;q=s-next; else s=q,q=q-next;2. 设计一个求结点 x 在二叉树中的双亲结点算法。设计一个求结点x 在二叉树中的双亲结点算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree; bitree *q20; int r=0,f=0,flag=0;void preorderbitree *bt, char xif bt.=0 & flag=0if bt-data=x flag=1; return;else

15、 r=r+1% 20; qr=bt; preorderbt-lchild,x; preorderbt-rchild,x; void parentbitree *bt,char xint i; preorderbt,x;fori=f+1; ilchild-data=x | qi-rchild-data break; if flag=0 printfnot found xn;else if idata; else printfnot parent;数据结构试卷（四）三、运算题 每题 10 分,共 30 分1、画出广义表 LS= , e , a , b , c , d 的头尾链表储备结构。1- 1-

16、1111-10 e0a1-1-10 b0c0 dLS2、下图所示的森林：(1) 求树（ a）的先根序列和后根序列。可编辑资料 - - - 欢迎下载精品名师归纳总结(1) ABCDEF;BDEFCA 。 2 ABCDEFGHIJK;BDEFCAIJKHG林转换为相应的二叉树。ABGCHDIEJFK(2) 求森林先序序列和中序序列。ABCDEF;BDEFCA 。（ 3）将此森林转换为相应的二叉树。可编辑资料 - - - 欢迎下载精品名师归纳总结ABCDEFG HIJK可编辑资料 - - - 欢迎下载精品名师归纳总结(a) b2 ABCDEFGHIJK;BDEFCAIJKHG林转换为相应的二叉树。A

17、BGCHDIEJFK23、设散列表的的址范畴是 0.9 ,散列函数为 H（ key ） = （ key+2） MOD 9,并采纳链表处理冲突,请画出元素7、4、5、3、6、 2、8、9 依次插入散列表的储备结构。H4=H5=0,H3=H6=H9=2,H8=3,H2=H7=6045123693845627789可编辑资料 - - - 欢迎下载精品名师归纳总结四、算法设计题 每题 10 分,共 30 分1. 设单链表中有仅三类字符的数据元素 大写字母、数字和其它字符 ,要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。设单链表中有仅三类字符的数据元素 大写字母、数字和其

18、它字符 ,要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist; void splitlklist *head,lklist *&ha,lklist *&hb,lklist *&hclklist *p; ha=0,hb=0,hc=0; forp=head;p.=0;p=headhead=p-next; p-next=0;if p-data=A & p-datanext=ha; ha=p;else if p-d

19、ata=0 & p-datanext=hb; hb=p; else p-next=hc; hc=p;2. 设计在链式储备结构上交换二叉树中全部结点左右子树的算法。设计在链式储备结构上交换二叉树中全部结点左右子树的算法。typedef struct node int data; struct node *lchild,*rchild; bitree;void swapbitreebitree *btbitree *p; ifbt=0 return;swapbitreebt-lchild; swapbitreebt-rchild; p=bt-lchild; bt-lchild=bt-rchild;

20、 bt-rchild=p;3. 在链式储备结构上建立一棵二叉排序树。在链式储备结构上建立一棵二叉排序树。#define n 10typedef struct nodeint key; struct node *lchild,*rchild;bitree; void bstinsertbitree *&bt,int keyif bt=0bt=bitree *mallocsizeofbitree; bt-key=key;bt-lchild=bt-rchild=0; else if bt-keykey bstinsertbt-lchild,key; else bstinsertbt-rchild,k

21、ey;void createbsttreebitree *&btint i;fori=1;idata.=bt2-data return0;else returnjudgebitreebt1-lchild,bt2-lchild*judgebitreebt1-rchild,bt2-rchild;2. 设计两个有序单链表的合并排序算法。设计两个有序单链表的合并排序算法。void mergelklistlklist *ha,lklist *hb,lklist *&hclklist *s=hc=0; whileha.=0 & hb.=0ifha-datadataifs=0 hc=s=ha; else s

22、-next=ha; s=ha;ha=ha-next; else ifs=0 hc=s=hb; else s-next=hb; s=hb;hb=hb-next;ifha=0 s-next=hb; else s-next=ha;数据结构试卷（六）四、算法设计题 20 分设计在次序有序表中实现二分查找的算法。可编辑资料 - - - 欢迎下载精品名师归纳总结设计在次序有序表中实现二分查找的算法。struct record int key; int others; int bisearchstruct record r , int kint low=0,mid,high=n-1; whilelowkhi

23、gh=mid-1;else low=mid+1;return0;设计判定二叉树是否为二叉排序树的算法。设计判定二叉树是否为二叉排序树的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node *lchild,*rchild;bitree; void inorderbitree *btifbt.=0inorderbt-lchild;ifminnumbt-keyflag=0; minnum=bt-key;inorderbt-rchild;3. 在链式储备结构上设计直接插入排序算法在链式储备结构上设计直接插入排序算法voi

24、d straightinsertsortlklist *&headlklist *s,*p,*q;int t;if head=0 | head-next=0 return;else forq=head,p=head-next;p.=0;p=q-nextfors=head;s.=q-next;s=s-next if s-datap-data break; ifs=q-nextq=p;elseq-next=p-next;p-next=s-next;s-next=p; t=p-data;p-data=s-data;s-data=t;数据结构试卷（七）四、算法设计题 20 分1. 设计在链式结构上实现

25、简洁挑选排序算法。设计在链式结构上实现简洁挑选排序算法。void simpleselectsorlklistlklist *&headlklist *p,*q,*s;int min,t;可编辑资料 - - - 欢迎下载精品名师归纳总结ifhead=0 |head-next=0 return; forq=head; q.=0;q=q-nextmin=q-data; s=q;forp=q-next; p.=0;p=p-next ifminp-datamin=p-data; s=p; ifs.=qt=s-data; s-data=q-data; q-data=t;2. 设计在次序储备结构上实现求子串

26、算法。设计在次序储备结构上实现求子串算法。void substringchar s , long start, long count, char t long i,j,length=strlens;if startlength printfThe copy position is wrong;else if start+count-1length printfToo characters to be copied; else fori=start-1,j=0; ikey=xreturn;elseifbt-keyxlevelbt-lchild,x;else levelbt-rchild,x;数据

27、结构试卷（八）四、算法设计题 20 分1. 设计一个在链式储备结构上统计二叉树中结点个数的算法。设计一个在链式储备结构上统计二叉树中结点个数的算法。void countnodebitree *bt,int &countifbt.=0count+; countnodebt-lchild,count; countnodebt-rchild,count;2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct int vertexm; int edgemm;gadjmatrix;typedef struct node1

28、int info;int adjvertex; struct node1 *nextarc;glinklistnode; typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode;可编辑资料 - - - 欢迎下载精品名师归纳总结void adjmatrixtoadjlistgadjmatrix g1 ,glinkheadnode g2 int i,j; glinklistnode *p; fori=0;i=n-1;i+ g2i.firstarc=0;fori=0;i=n-1;i+ forj=0;jadjve

29、rtex=j; p-nextarc=gi.firstarc; gi.firstarc=p;p=glinklistnode *mallocsizeofglinklistnode;p-adjvertex=i; p-nextarc=gj.firstarc; gj.firstarc=p;数据结构试卷（九）五、算法设计题 20 分1. 设计运算二叉树中全部结点值之和的算法。设计运算二叉树中全部结点值之和的算法。void sumbitree *bt,int &sifbt.=0 s=s+bt-data; sumbt-lchild,s; sumbt-rchild,s;2. 设计将全部奇数移到全部偶数之前的算法

30、。设计将全部奇数移到全部偶数之前的算法。void quickpassint r, int s, int tint i=s,j=t,x=rs; whileijwhile ij & rj%2=0 j=j-1;if ij ri=rj;i=i+1;while ij & ri%2=1 i=i+1;if inext=0 return1;elseforq=head,p=head-next; p.=0; q=p,p=p-nextifq-datap-data return0; return1;可编辑资料 - - - 欢迎下载精品名师归纳总结数据结构试卷（十）三、算法设计题 22 分1. 设计在链式储备结构上合并

31、排序的算法。设计在链式储备结构上合并排序的算法。void mergelklistlklist *ha,lklist *hb,lklist *&hclklist *s=hc=0; whileha.=0 & hb.=0ifha-datadataifs=0 hc=s=ha; else s-next=ha; s=ha;ha=ha-next; else ifs=0 hc=s=hb; else s-next=hb; s=hb;hb=hb-next;ifha=0 s-next=hb; else s-next=ha;2. 设计在二叉排序树上查找结点X 的算法。设计在二叉排序树上查找结点X 的算法。bitree

32、 *bstsearch1bitree *t, int keybitree *p=t;whilep.=0ifp-key=keyreturnp;elseifp-keykeyp=p-lchild;else p=p-rchild;return0;3. 设关键字序列 k 1, k 2, k n-1 是堆,设运算法将关键字序列k 1, k 2, k n-1 , x 调整为堆。设关键字序列 k 1 , k2, k n-1 是堆,设运算法将关键字序列k 1, k 2, k n-1 , x 调整为堆。void adjustheapint r ,int nint j=n,i=j/2,temp=rj-1;while

33、 i=1 if temp=ri-1break; elserj-1=ri-1; j=i; i=i/2; rj-1=temp;数据结构试卷（一）参考答案三、运算题（每题6 分,共 24 分）01110101011101110101011101.线性表为： （78, 50,40, 60,34, 90）2.邻接矩阵：邻接表如图 11 所示：可编辑资料 - - - 欢迎下载精品名师归纳总结图 113. 用克鲁斯卡尔算法得到的最小生成树为：1,23,4,64,1,35,1,48,2,510,4,7204. 见图 124422222445454588323584图 12四、读算法（每题7 分,共 14 分）1. （ 1）查询链表的尾结点（ 2）将第一个结点链接到链表的尾部,作为新的尾结点（ 3）返回的线性表为（ a2,a3, ,an,a1）2. 递归的后序遍历链式储备的二叉树。五、法填空（每空2 分,共 8 分） trueBST-leftBS