《数据结构复习资料1》由会员分享,可在线阅读,更多相关《数据结构复习资料1(7页珍藏版)》请在金锄头文库上搜索。
1、1数据结构复习数据结构复习第一章第一章 绪论绪论 复习内容: (1) 基本概念和术语 (2) 抽象数据类型的表示与实现 (3) 估算算法时间复杂度 复习题: 1.仿照三元组的抽象数据类型写出抽象数据类型有理数的定义(有理数是其分子、分母 均为自然数且分母不为零的分数)。 ADT Rational_Num 数据对象:D= |e1,e2n(n 为整数集合) 数据关系:R1=, e1 是有理数分子,e2 是有理数分母,且 e20 基本操作: InitRational_Num (k=0; while(i=y if(yz if(x=temp)y=temp; else y=x;x=temp; printf
2、(x,y,z); /Descending 第二章第二章 线性表线性表 复习内容: (1) 线性表的类型和定义 (2) 线性表的顺序表示和实现 (3) 线性表的链式存储和实现 (4) 一元多项式的表示及相加 线性表-顺序存储结构-顺序表 线性表-链式存储结构-链表 线性表在顺序存储结构上实现查找、插入和删除的算法 区分线性表的逻辑结构和存储结构 复习题: 1.(1) 在顺序表中插入或删除一个元素,需要平均移动【表中一半】元素,具体移动的元素 个数与【表长和该元素在表中的位置】有关。 (2) 顺序表中逻辑上相邻的元素的物理位置【必定】紧邻。单链表中逻辑上相邻的元素的 物理位置【不一定】紧邻。 2.
3、例 2-1 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即:线性表中 的数据元素即为集合中的成员。 现要求一个新的集合 AAB。 3.简述顺序表和单链表的优缺点。 顺序表-优点:逻辑相邻,物理相邻可随机存取任一元素存储空间使用紧凑。缺点: 插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配,利用不充分 表容量难以扩充。 单链表-优点它是一种动态结构,整个存储空间为多个链表共用不需预先分配空间 插入、删除操作方便。单链表的缺点指针占用额外存储空间不能随机存取,查找速 度慢。 4. 写出按正位序建立一个单链表的算法。 void CreateList_L(Link
4、List L-next = NULL; / 先建立一个带头结点的单链表for (i = 1; i data); / 输入元素值p-next = L-next; L-next = p; / 插入 / CreateList_L 5.已知 L 是带表头结点的非空单链表,且 P 结点既不是首元结点,也不是尾元结点,试从 下列提供的答案中选择合适的语句序列。 (1)删除 P 结点的语句序列是【JLGCN】。3(2)删除尾元结点的语句序列是【IKCN】。 (A) P=P-next; (B) P-next = P; (C) P-next= P-next -next; (D) P= P-next -next;
5、 (E) while(P!=NULL) P= P-next; (F) while(Q-next!=NULL) P=Q;Q= Q-next; (G) while(P-next !=Q) P= P-next; (H) while(P-next -next!=Q) P= P-next; (I) while(P-next -next!= NULL) P= P-next; (J) Q=P; (K) Q=P-next; (L) P=L; (M) L=L-next; (N) free(Q); 6. 指出以下算法中的错误和低效(即费时)之处,并将它改写为一个既正确又高效的算法。Status DeletK(Sq
6、List count=i+1;j-) La.elemj-1=La.elemj;La.length-; return ok; /DeleteK 第二个 for 语句中,元素前移的次序错误; 低效之处是每次删除一个元素的策略。 改正后的算法: Status DeletK(SqList Sub1len=Spospos+len-1;Sub0=len;return OK; / SubString 2.2.已知下列字符串 a=THIS,f=A SAMPLE,c=GOOD,d=NE,b=, s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2
7、), t=Replace(f,SubString(f,3,6),c), u=Concat(SubString(c,3,1),d), g=IS v=Concat(s,Concat(b,Concat(t,Concat(b,u), 请问:s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么? 答:s=THIS SAMPLE IS;t=A GOOD;v=THIS SAMPLE IS A GOOD ONE; StrLength(s)=14; Index(v,g)=3;Index(u,g)=0。 3.3. 第五章第五章 数组和广义表数组和广义表 复习内容: (1) 数组
8、的类型定义 (2) 数组的顺序表示和实现5(3) 矩阵的压缩存储 (4) 广义表的定义 (5) 广义表的存储结构 复习题: 1.1. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0 元素。 2.2. 稀疏矩阵的压缩存储方法:【三元组顺序表,行逻辑链接的顺序表,十字链 表】 3.3. 设有一个 10 阶的下三角矩阵 A(包括对角线) ,按照从上到下、从左到右的 顺序存储到连续的 55 个存储单元中,每个数组元素占 1 个字节的存储空间,则 A54地址与 A00的地址之差为( B ) 。(A) 10 (B) 19 (C) 28 (D) 55 4. Loc(Loc( aij)=aij)
9、=? 答案:Loc(Loc( aij)=Loc(a11)+aij)=Loc(a11)+ i*(i-1)/2i*(i-1)/2 +(j-1)*L+(j-1)*L 第六章第六章 树和二叉树树和二叉树 复习要求:掌握树和二叉树的概念、存储结构,基本运算及其遍历,掌握哈夫曼树的概念 和构造方法。 复习内容: (1) 树的定义和基本术语 (2) 二叉树 (3) 遍历二叉树和线索二叉树 (4) 树和森林 (5) 哈夫曼树及其应用 复习题: 1.1. 画出和下列已知序列对应的树 T树的先根次序访问序列为 GFKDAIEBCHJ 树的后根次序访问序列为 DIAEKFCJHBG2.2. 画出和下列已知序列对应的
10、森林 F森林的先序访问序列为 ABCDEFGHIJKL 森林的中序访问序列为 CBEFDGAJIKLH3.假设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10 试为这 8 个字母设计哈夫曼编码。使用 0-7 的二进制表示形式是另一种编码方案。对于上述实例,比较两种方案的优缺点。WPL1=2.61 WPL2=3 方案 1 优于方案 2 5. 一棵深度为 H 的满 k 叉树有如下性质:第 H 层上的结点都是叶子结点,其余各层上每个 结点都有 k 棵非空子树。如果按层次顺序从 1 开始对全部结点编号,问:
11、 (1)各层结点数目是多少?6(2)编号为 p 的结点的父结点(若存在)的编号是多少? (3)编号为 p 的结点的第 i 个儿子结点(若存在)的编号是多少? (4)编号为 p 的结点有有右兄弟的条件是什么?其右兄弟的编号是多少? 答案: (1)第 i 层有 ki-1个结点;(2)p=1 时,该结点为根,无父结点;否则其父结点编号为(k=2) kkp)2(3)其第 k-1 个儿子的编号为 pk。所以,如果他有儿子,则其第 i 个儿子的编号为 pk+(i-(k-1); (4)(p-1)%k0 时,该结点有右兄弟,其右兄弟的编号为 p+1。第七章第七章 图图 复习要求:掌握图的有关概念、存储结构、遍
12、历算法、生成树的求法以及拓扑排序的概念 及求法。 复习内容: (1) 图的定义和术语 (2) 图的存储结构 (3) 图的遍历 (4) 图的连通性问题 (5) 有向无回图及其应用 (6) 最短路径 复习题: 1. 对于一个具有 n 个顶点和 e 条边的有向图和无向图,在其对应的邻接表中, 所含边结点分别有_e_个和_2e_个。 2. 设有 6 个结点的无向图,该图至少应有( A )条边才能确保是一个连通图。A.5 B.6 C.7 D.8 3. 已知如右图所示的有向图,请给出该图的 (1) 每个顶点的入/出度; (2) 邻接矩阵 (3) 邻接表 (4) 逆邻接表 (5) 强连通分量答案: (1)
13、每个顶点的入/出度; 顶点123456 入度321122 出度022313 (2) 邻接矩阵 000000 100100 010001 001011 100000 1100101234567(3) 邻接表(4) 逆邻接表(5) 有 3 个强连通分量4.简述图的各种存储结构的适用类型? 答: 邻接矩阵:有向图和无向图 邻接表(逆邻接表):有向图和无向图 十字链表:有向图 邻接多重表:无向图 5. 已知一个图的顶点集 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 6. AOV 网是一种_有向无回路_的图。 7.请对下面的无向带权图,1523468(1) 写出它的邻接矩阵,并按普里姆算法求其最小生成树; (2) 写出它的邻接表,并按克鲁斯卡算法求其最小生成树。641246 3621357655 5