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

精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -数据结构期末考试题型及分值（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 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -简答题实例可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -设计题：（1）（2）数据结构试卷（一）三、运算题（每题6 分，共 24 分）1. 在如下数组A 中链接储备了一个线性表，表头指针为A 0.next ，试写出该线性表。A01234567data605078903440next35720410111010101110111010101110线性表为：（ 78， 50， 40， 60， 34， 90 ）2. 请画出下图的邻接矩阵和邻接表。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -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 时，每加入一个数据后堆的变化。见图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。可编辑资料 - - - 欢迎下载精品名师归纳总结性表。请回答以下问题：（ 1）说明语句S1 的功能。查询链表的尾结点（ 2）说明语句组S2 的功能。将第一个结点链接到链表的尾部，作为新的尾结点（ 3）设链表表示的线性表为（a1,a2,an） ,写出算法执行后的返回值所表示的线可编辑资料 - - - 欢迎下载精品名师归纳总结返回的线性表为（a2,a3,an,a1 ）2. void ABCBTNode * BTifBT ABC BT->left;ABC BT->right;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -cout<<BT->data<<' '该算法的功能是：递归的后序遍历链式储备的二叉树五、算法填空（共8 分）二叉搜寻树的查找递归算法 :bool FindBTreeNode* BST,ElemType& itemif BST=NULLreturn false; /查找失败else if item=BST->dataitem=BST->data;/查找胜利return true ; else ifitem<BST->data可编辑资料 - - - 欢迎下载精品名师归纳总结return Find else return Find /ifBST->left _,item;_BST->right ,item;可编辑资料 - - - 欢迎下载精品名师归纳总结六、编写算法（共8 分）统计出单链表HL 中结点的值等于给定值X 的结点数。int CountXLNode* HL,ElemType xint CountXLNode* HL,ElemType xint i=0; LNode* p=HL;/i为计数器whilep.=NULL if P->data=x i+; p=p->next;/while,出循环时i 中的值即为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->rlink=q;3 设一组有序的记录关键字序列为13 ，18，24， 35，47，50，62，83，90 ，查找方法用二分查找，要求运算出查找关键字62 时的比较次数并运算出查找胜利时的平均查找长度。2,ASL=91*1+2*2+3*4+4*2=25/9可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -4 设一棵树T 中边的集合为A ，B ，A ，C， A ，D ，B ，E ，C，F，C，G ，要求用孩子兄弟表示法（二叉链表）表示出该树的储备结构并将该树转化成对应的二叉树。树的链式储备结构略，二叉树略5 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。E=1 ， 3， 1， 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 r, int s, int tint i=s, j=t, x=rs; whilei<jwhile i<j && rj>x j=j-1; if i<j ri=rj;i=i+1;while i<j && ri<x i=i+1; if i<j rj=ri;j=j-1;ri=x;2 设有两个集合A 和集合 B，要求设计生成集合C=AB 的算法， 其中集合A、B 和 C 用链式储备结构表示。设有两个集合A和集合 B，要求设计生成集合C=A B 的算法，其中集合A、B 和 C用链式储备结构表示。typedef struct node int data; struct node *next;lklist; void intersectionlklist *ha,lklist *hb,lklist *&hclklist *p,*q,*t; forp=ha,hc=0;p.=0;p=p->nextforq=hb;q.=0;q=q->next if q->data=p->data break;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -ifq.=0 t=lklist *mallocsizeoflklist; t->data=p->data;t->next=hc; hc=t;数据结构试卷（三）三、运算题 每题 10 分，共 30 分1.已知二叉树的前序遍历序列是AEFBGCDHIKJ ，中序遍历序列是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=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,9,10,12,18,181,3, 4,6,8,9,10,12,18,18四、算法设计题 每题 15 分，共 30 分 1 设计在单链表中删除值相同的余外结点的算法。设计在单链表中删除值相同的余外结点的算法。typedef int datatype;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -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; 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 r=r+1% 20; qr=bt; preorderbt->lchild,x; preorderbt->rchild,x; void parentbitree *bt,char xint i; preorderbt,x;fori=f+1; i<=r; i+ if qi->lchild->data=x | qi->rchild->data break; if flag=0 printf"not found xn"else if i<=r printf"%c",bt->data; else printf"not parent"数据结构试卷（四）三、运算题 每题 10 分，共 30 分1、画出广义表LS= , e , a , b , c , d 的头尾链表储备结构。可编辑资料 - - - 欢迎下载精品名师归纳总结LS1->1->110 e11->0a11->0 b1->10c0 d可编辑资料 - - - 欢迎下载精品名师归纳总结2、下图所示的森林：(1) 求树（ a）的先根序列和后根序列。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -(1) ABCDEF;BDEFCA 。 2 ABCDEFGHIJK;BDEFCAIJKHG林转换为相应的二叉树。ABGCHDIEJFK(2) 求森林先序序列和中序序列。ABCDEF;BDEFCA 。（ 3）将此森林转换为相应的二叉树。可编辑资料 - - - 欢迎下载精品名师归纳总结ABCDEFG HIJK可编辑资料 - - - 欢迎下载精品名师归纳总结(a) b2 ABCDEFGHIJK;BDEFCAIJKHG林转换为相应的二叉树。ABGCHDIEJFK23、设散列表的的址范畴是 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可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 9 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -四、算法设计题 每题 10 分，共 30 分 1设单链表中有仅三类字符的数据元素 大写字母、数字和其它字符 ，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。设单链表中有仅三类字符的数据元素 大写字母、数字和其它字符 ，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。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->data<='Z' p->next=ha; ha=p;else if p->data>='0' && p->data<='9' p->next=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; 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->key>key bstinsertbt->lchild,key; else bstinsertbt->rchild,key;void createbsttreebitree *&btint i;fori=1;i<=n;i+ bstinsertbt,random100;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -数据结构试卷（五） 三、应用题 32 分1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。DEBCA2. 设无向图G（如右图所示） ，给出该图的最小生成树上边的集合并运算最小生成树各边上的权值之和。E=1,5,5,2,5,3,3,4,W=103. 设一组初始记录关键字序列为15 ，17，18，22，35，51，60 ，要求运算出胜利查找时的平均查找长度。ASL=1*1+2*2+3*4/7=17/74. 设散列表的长度为8，散列函数Hk=kmod7，初始记录关键字序列为25 ，31，8，27，13，68 ，要求分别运算出用线性探测法和链的址法作为解决冲突方法的平均查找长度。ASL1=7/6 ， ASL2=4/3四、算法设计题28 分 1 设计判定两个二叉树是否相同的算法。设计判定两个二叉树是否相同的算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree; int judgebitreebitree *bt1,bitree *bt2if bt1=0 && bt2=0 return1;else if bt1=0 | bt2=0 |bt1->data.=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->data<hb->dataifs=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;数据结构试卷（六）四、算法设计题20 分 设计在次序有序表中实现二分查找的算法。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 11 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -设计在次序有序表中实现二分查找的算法。struct record int key; int others; int bisearchstruct record r , int kint low=0,mid,high=n-1; whilelow<=highmid=low+high/2;ifrmid.key=kreturnmid+1;elseifrmid.key>khigh=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;ifminnum>bt->keyflag=0; minnum=bt->key;inorderbt->rchild;3. 在链式储备结构上设计直接插入排序算法在链式储备结构上设计直接插入排序算法void 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->data>p->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. 设计在链式结构上实现简洁挑选排序算法。设计在链式结构上实现简洁挑选排序算法。void simpleselectsorlklistlklist *&headlklist *p,*q,*s;int min,t;可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 12 页，共 24 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -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 ifmin>p->datamin=p->data; s=p; ifs.=qt=s->data; s->data=q->data; q->data=t;2. 设计在次序储备结构上实现求子串算法。设计在次序储备结构上实现求子串算法。void substringchar s , long start, long count, char t long i,j,length=strlens;if start<1 | start>length printf"The copy position is wrong"else if start+count-1>length printf"Too characters to be copied" else fori=start-1,j=0; i<start+count-1;i+,j+ tj=si; tj= '0'3. 设计求结点在二叉排序树中层次的算法。设计求结点在二叉排序树中层次的算法。int lev=0;typedef struct nodeint key; struct node *lchild,*rchild;bitree; void levelbitree *bt,int xif bt.=0lev+;ifbt->key=xreturn;elseifbt->key>xlevelbt->lchild,x;else levelbt->rchild,x;数据结构试卷（八）四、算法设计题20 分 1. 设计一个在链式储备结构上统计二叉树中结点个数的算法。设计一个在链式储备结构上统计二叉树中结点个数的算法。void countnodebitree *bt,int &countifbt.=0count+; countnodebt->lchild,count; countnodebt->rchild,count;2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct int vertexm; int edgemm;gadjmatrix;typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode; typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode;可编辑资料 - - - 欢迎下载精品名师归纳总结