数据结构复习资料1

《数据结构复习资料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