《1093编号数据结构期末考试复习总结》由会员分享，可在线阅读，更多相关《1093编号数据结构期末考试复习总结（24页珍藏版）》请在金锄头文库上搜索。
1、1204 班 学委精心整理 数据结构期末复习 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 1204 班 学委精心整理 数据结构期末复习 2 简答题实例 1204 班 学委精心整理 数据结构期末复习 3 设计题： （1） （2） 数据结构试卷（一）数据结构试卷（一） 三、计算题（每题三、计算题（每题 6 分，共分，共 24 分）分） 1204 班 学委精心整理 数据结构期末复习 4 1.在如下数组 A 中链接存储了一个线性表，表
3、头指针为 A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440 next3572041 线性表为：（线性表为：（78，50，40，60，34，90） 01110 10101 11011 10101 01110 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; 用克鲁斯卡尔算法得到最小生成树，试
4、写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为：用克鲁斯卡尔算法得到的最小生成树为： (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 ABC (BT-right); coutdatadata) item=BST-data;/查
5、找成功 return _ true _ true _; else if(itemdata) return Find(_BST-left _BST-left _,item); else return Find(_BST-right_BST-right _,item); /if 六、编写算法（共六、编写算法（共 8 分）分） 统计出单链表 HL 中结点的值等于给定值 X 的结点数。 int CountX(LNode* HL,ElemType x) int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i 为计数器为计数器 while(p!=N
6、ULL) if (P-data=x) i+; p=p-next; /while, 出循环时出循环时 i 中的值即为中的值即为 x 结点个数结点个数 return i; /CountX 数据结构试卷（二）数据结构试卷（二） 1204 班 学委精心整理 数据结构期末复习 6 三、应用题(36 分)三、应用题(36 分) 1 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第 4 趟简单选择 排序和第 4 趟直接插入排序后的结果。 (22，40，45，48，80，78)，(40，45，48，80，22，78)(22，40，45，48，80，78)，(40，45，48，80
7、，22，78) 2 设指针变量 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/92,ASL=91*1+
8、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，2)，(3，5)，(5，6)，(6，4) 6 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给 出构造过程。 四、算法设计题(16 分) 四、算法设计题(16 分) 1 设有一组初
9、始记录关键字序列（K1，K2，Kn） ，要求设计一个算法能够在 O(n)的时 间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 Ki，右半部分 的每个关键字均大于等于 Ki。 设有一组初始记录关键字序列（K设有一组初始记录关键字序列（K1 1，K，K2 2，K，Kn n） ，要求设计一个算法能够在 O(n)的时间复 杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 K ） ，要求设计一个算法能够在 O(n)的时间复 杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 Ki i，右半部分的每个关 键字均大于等于 K ，右半部分的每个关 键字均大于等于 Ki i。
10、void quickpass(int r, int s, int t) int i=s, j=t, x=rs; while(ij) 1204 班 学委精心整理 数据结构期末复习 7 while (ix) j=j-1; if (ij) ri=rj;i=i+1; while (ij if (inext) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break; if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-data=p-data;t-next=hc; hc=t; 数据结构试卷（三）数据结构试卷（三） 三、计算题
11、(每题 10 分，共 30 分)三、计算题(每题 10 分，共 30 分) 1.已知二叉树的前序遍历序列是 AEFBGCDHIKJ，中序遍历序列是 EFAGBCHKIJD，画出 此二叉树，并画出它的后序线索二叉树。 A E B FG C D H F KJ NULL 2已知待散列的线性表为（36，15，40，63，22） ，散列用的一维地址空间为0.6，假定 选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试： H(36)=36 mod 7=1; H (22)=(1+1) mod 7=2; .冲突 冲突 H(15)=15 mod 7=1;.冲突冲突 H2(22)=(2
12、+1) mod 7=3; H (15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1; .冲突冲突 （1）计算出每一个元素的散列地址并在下图中填写出散列表： 1204 班 学委精心整理 数据结构期末复习 8 0 1 2 3 4 5 6 6336152240 （2）求出在查找每一个元素概率相等情况下的平均查找长度。 ASL=6 . 1 5 31121 3已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 (8,9,4,3,6,1),10,(12,18,18) (1,
13、6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 四、算法设计题(每题 15 分，共 30 分)四、算法设计题(每题 15 分，共 30 分) 1 设计在单链表中删除值相同的多余结点的算法。 设计在单链表中删除值相同的多余结点的算法。设计在单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node datatype data; struct node *next;lklis
14、t; void delredundant(lklist * for(p=head;p!=0;p=p-next) for(q=p-next,s=q;q!=0; ) if (q-data=p-data) s-next=q-next; free(q);q=s-next; else s=q,q=q-next; 2 设计一个求结点 x 在二叉树中的双亲结点算法。 设计一个求结点 x 在二叉树中的双亲结点算法。设计一个求结点 x 在二叉树中的双亲结点算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree; bit
15、ree *q20; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) if (bt!=0 return; else r=(r+1)% 20; qr=bt; preorder(bt-lchild,x); preorder(bt-rchild,x); void parent(bitree *bt,char x) int i; preorder(bt,x); for(i=f+1; ilchild-data=x | qi-rchild-data) break; if (flag=0) printf(not found xn); 1204 班 学委精心整理 数据结构期末复习 9 else if (idata); else printf(not parent); 数据结构
