数据结构c语言版复习资料

1、数据结构复习资料 一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后

2、一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。9数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。11. 一个算法的效率可分为 时间 效率和 空间 效率。12. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表

3、长和该元素在表中的位置 有关。13. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。14. 向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个元素。15. 向一个长度为n的向量中删除第i个元素(1in)时，需向前移动 n-i 个元素。16. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。17. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。18在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。19 在n个结点

4、的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。20. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。22. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。23. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为

5、目标串， 子串 称为模式。25. 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (674)61000）1276 。26 由个结点所构成的二叉树有 5 种形态。 27. 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。注：满二叉树没有度为1的结点，所以分支结点数就

6、是二度结点数。28 一棵具有个结点的完全二叉树，它的深度为 9 。（ 注：用 log2(n) +1= 8.xx +1=929设一棵完全二叉树有700个结点，则共有 350 个叶子结点。答：最快方法：用叶子数n/2350 30 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。答：最快方法：用叶子数n/2500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数0.31在数据的

7、存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。32. 线性有序表（a1，a2，a3，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。33. 假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。解：显然，平均查找长度O（log2n）top0 ST-top=0 ST-topm0 ST-top=m0（ C ）18. 在一个图中，所有顶点的

8、度数之和等于图的边数的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）19. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）20. 有8个结点的无向图最多有 条边。 A14 B. 28 C. 56 D. 112 （ C ）21. 有8个结点的有向完全图有 条边。 A14 B. 28 C. 56 D. 112 （ B ）22在表长为的链表中进行线性查找，它的平均查找长度为. ; . （）; . ; . （）（ A ）23折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则

9、它将依次与表中 比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）24对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。A3 B4 C5 D 6（ A ）25. 链表适用于 查找A顺序 B二分法 C顺序，也能二分法 D随机四、简答题1.数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。2. 简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结

10、点间的逻辑关系是多对多的。3、分析下面各程序段的时间复杂度(1.) for (i=0; in; i+)for (j=0; jm; j+)Aij=0;答：O（m*n）1. 项基本原则(2.) x=0;for(i=1; in; i+) for (j=1; j=0是DIJISTRU算法的适应范围）。对无向图，可看成2个方向权值一样。例子见手写版。问：DIJISTRU算法能否求图的最小生成树？不能。打印最短路径，时间O（n2），空间O（n），可以用DIJISTRU算法得到集合的同时，记录每个节点前面那个元素，一个一个向前找。二部图：一个图是否是二部图？时间是O（n）。用等价类：一个边的两点分属于不用等

11、价类（估计不会考太深）。伙伴系统，边界标识（要看）。无用单元收集不考。顺序查找时间（最坏，平均）。有序表查找，二分查找，折半查找（判定树，树的高度，平均检索长度（在成功和不成功时的不同情况）。静态树表不考，静态次优不考。索引顺序表：概念。动态查找：二叉排序树：中序遍历有序，先序无序。给出先（或后）序的次序，写出此树（因为中序是顺序的，已知）。他的插入和删除（删除不一定考）。给定树，求平均查找长度。查找长度的量级。平衡二叉树：一定是二叉排序树。树的所有子树都是平衡二叉树。反之不成立。若要执行4种旋转，至少7个节点。M阶B树：关键字个数的上下限。N个关键字构成树的节点数目层数。B树的概念。键树。哈

12、希表：解决冲突的方法。只有链地址法可以解决二次聚集。不是同义词不会竞争同一位置。链地址法是顺序结构和链结构的完美结合。查找长度：1。探测次数（包括最后一次比较为空的次数）。 2关键字比较次数（不包括最后一次为空的）。37内部排序：简单插入排序（稳定）；折半（不稳定）；希尔（不稳定）；冒泡（稳定）；快速（不稳定）；选择（不稳定）；堆（不稳定）；归并（稳定）。要记住她们的时间复杂度（最好，平均，最坏）。基数排序：给定N个数，范围在（0，n2-1），以O(n)时间排序。记ni=ai*n+bi，按(ai,bi)先以bi为基数排序，再以ai 排。基数排序利用关键字本身的值，而其他基于比较。找最大和最小值

13、的时间3/2n-2。见手写版。两两比较，小的方一个数组，大的放一个数组，再找。找最大和次大值：可以调整堆，也可以记下比较第一章一、数据结构的四类基本类型：1、集合2、线性结构3、树形结构4、图形结构或网状结构二、数据元素之间的物理结构有两种：顺序存储结构和链式储存结构三、算法中基本操作重复的次数是问题规模N的某个函数F（N）算法的时间量度记作T（N）O（F（N）它表示随问题规模N的增大，算法执行的时间的增长率和F（N）的增长率相同，称作算法的渐近时间复杂度简称时间复杂度。第二章线性表一、线性表的建立：1、建立一个线性链表：2、插入一个结点：在头部：在中间：在尾部：3、删除一个结点：头部中间尾部

14、二、线性链表原代码如下： include typedefstruct node int data; struct node *next;NODE1、建立一个线性链表：create_list( )NODE *head,*p; int i,j,k; scanf(“%d”,&i); /链表的结点个数 head=NULL; for(j=i;i!=0;i-) scanf(“%d”,&k); if(head=NULL) head-data=k; p=head;p-next-data=k;p=p-next;p-next=NULL;return(head); 2、插入一个结点： 在头部插入一个结点p ： in

15、sert(NODE*head) NODE *p ; scanf(“%d”,&p-data)； /要插入的结点 p-next=head; head=p; 在p与q之间插入结点k：insert(NODE * head) NODE *p,*q,*k; scanf(“%d”,&k-data)； /要插入的结点 k-next=q; p-next=k; 在尾部插入一个结点q ： insert(NODE *head) NODE *p,*q; scanf(“%d”,&q-data)； /要插入的结点 for(p=head;p-next!=NULL;p=p-next); /到链表的最后一个结点 p-next=q

16、; q-next=NULL; 3、删除一个结点：在头部删除一个结点p: delete(NODE*head)NODE *p;p=head; head=head-next;free(p); 在p与q之间删除结点k： delete(NODE*head) NODE *p,*q,*k; p-next=q; free(k); 在尾部删除一个结点p: delete(NODE*head) NODE *p,*q; for(q=p=head;p-next!=NULL;q=p,p=p-next); /到链表的最后一个结点 q-next=NULL; free(p);双向链表的操作与单向差不多。第三章栈和队列一、栈是一

17、种先进后出的线性表进栈相当于在线性链表的头部插一个结点，出栈相当于在线性链表的头部删除一个结点二、队列是一种和栈相反的线性表，它是先进先出线性表进队相当于是在线性表的尾部加一结点，出队相当于在线性链表的头部删除一个结点三、判断循环队列的空满可以用以下两种方法：一是另设一个标志位区别队列是空是满二是少用一个元素空间，约定头指针在队列尾指针的下一位置上作为队满第四章串一、串的机内表示：定长顺序存储表示和堆分配存储表示，两者的思想和区别二、定长顺序存储表示思想是类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。三、堆分配存储表示思想是仍以一组地址连续的存储单元存放串值字符序列，

18、但它们的存储空间是程序执行过程中动态分配而得。四、两者区别是：定长顺序存储是每个定义的串变量是分配一个固定的长度而堆分配存储是程序执行过程中动态分配而得。 串的模式匹配算法：P79第五章：数组和广义表一、疏矩阵的存储方法1、三元组顺序表： 压缩存储的概念就是只存储稀疏矩阵的非零元。所以一个三元组（i,j, aij）就可以唯一确定了矩阵的一个非零元。其中i 表示该非零元在稀疏矩阵中的第几行，j 表示非零元在稀疏矩阵中的第几列，aij表示非零元在稀疏矩阵中的值。快速转置的好处缺点原因二、十字链表：在链表中，每个非零元可以用一个含有五个域的结点表示，其是I,j,e三个域分别表示该非零元所在行、列、和

19、非元零的值，向 右域right用以链接同一行下个非零元，用down用以链接同列中下一个非零元，同一行非零元可以通过right域链成一个链表，同一列可以通过 down域链成一个链表，每个非零元既是某行链表中的结点，又是某个列链表的结点整个矩阵就成了一个十字交叉的链表故称十字链表，可以用两个分别存储行链 表的头指针的列链表的头指针的一维数组表示之：矩阵： 0 0 1 01312 0 0 4 0 3 5 03353232122441、广义表的存储结构广义表LS=（a1,a2,a3an）表头是第一个元素a1，其余元素组成的表（a2,a3,an）是LS的表尾第六章 树和二叉树一、二叉的性质：1、在二叉树

20、的第I层上至多有2I-1个结点（I1） 2、深度为K的二叉树至多有2K1个结点 3、对任何一棵二叉树T，如果其终端结点数不N0，度为2的结点数为N 2则N0N21 4、具有N个结点的完全二叉树的深度为LLOG2N1二、满二叉树的定义：一棵深度为k且有2k-1个结点的二叉树称为三、完全二叉树定义：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度k的满二叉树中编号从1到n的结点一一对应时称之为完全二叉树四、二叉树的存储结构：一、顺序存储结构二、链式存储结构五、遍历二叉树：1、前序：是先访问根结点，先序遍历左子树，先序遍历右子树2、中序：中序遍历左子树，访问根结点，中序遍历右子树3、后序

21、：后序遍历左子树，后序遍历右子树，访问根结点例：见书p129页六、建立一棵二叉树：p131七、线索二叉树：穿线方法：先按先、中或后序把二叉树遍历，八、树的存储结构：一、双亲表示法：就是用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲的结点在数组中位置。特点：找双亲容易，找孩子难（见p135 图6.13）二、孩子兄弟表示法（又称二叉树和二叉链表表示法）链表结构中的两个链域分别指向该结点的的第一个孩子结点和下一个兄弟结点。操作容易，破坏了树的层次（见p137 图6.15）九、森林的遍历：1、先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树2、后根（序）遍历：先依次

22、后根遍历每棵子树，然后访问根结点十、森林和二叉树的转换：十一、最优二叉树（赫夫曼树）是一类带权路径长度最短的树建立构造Huffman树的方法Huffman算法构造Huffman树步骤1、根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj2、在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和3、在森林中删除这两棵树，同时将新得到的二叉树加入森林中4、重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树第七章 图一、图的定义和术语：1、图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)

23、其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对2、有向图有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头3、无向图无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v），并且（v,w）=(w,v)4、有向完备图n个顶点的有向图最大边数是n(n-1)5、无向完备图n个顶点的无向图最大边数是n(n-1)/26、权与图的边或弧相关的数叫7、网带权的图叫8、

24、子图如果图G(V,E)和图G(V,E),满足：v则称G为G的子图9、顶点的度1、无向图中，顶点的度为与每个顶点相连的边数2、有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目10、路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1 V2-V4 - V8 -V5 -V3-V6-V72、广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图 中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未

25、被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为 止数据结构复习资料12010-01-06 10:43一、名词解释：1. 数据结构数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。2. 逻辑结构我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。3. 物理结构抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。二、问答题：1. 简述“软件工程”的工程化的思想。答：软件工程就是应用一些科

26、学理论和工程上的技术来指导软件开发。软件工程将研制软件的全过程分为六个阶段：问题说明，需求分析，系统设计，编写程序，测试工作，运行与维护。软件工程的基本原则是：划分软件生命期，运行计划评审，编制软件文档。2. 说明对程序进行评价时，“时间”与“空间”之间的关系。答：时间性和空间性是程序的效率问题。时间效率决定于：源程序转换为目标程序的时间和目标程序执行的时间。时间效率与编译质量有关，与算法的简化程度有关，还与用户对语言的熟练程度有关，其中，算法的效率起主要作用。空间效率一般指程序花费的内存空间的问题。对于同等复杂程度的程序：一般时间效率越高的程序，占用的内存就越大，空间效率就越低；一般时间效率

27、越低的程序，占用的内存就越小，空间效率就越高。两者具有一定的矛盾性。但是随着内存容量的不断增大，往往会牺牲空间性来提高时间性。3. 依照“软件工程”的思想，叙述软件生命周期的不同阶段及各阶段的主要工作内容。答：在软件工程中，把从软件的计划开始，经历问题的说明（定义），需求分析，设计代码，测试与维护，直到软件报废为止的整个期间，称为软件的生命周期。在软件生命周期中，除了最后的运行与维护属于运行期，其它都称为开发期。1） 问题说明：对研究的问题进行完整而且适当的说明。2） 需求分析：根据问题说明，确定软件必须具有的功能。不是具体解决问题，而是明确必须“做什么”。3） 系统设计：将反映用户要求的逻辑模型转换为一个具体的设计方案，使用伪码来描述算法。4） 编写程序：将伪码转换为高级语言的形式。5） 测试工作：检查程序和系统的其他部分是否满足设计要求。6） 运行与维护：将验收后的软件交付用户使用，通过实际运行环境的检验，对不适应的部分进行修改和扩充。4. 拓扑排序中使用了那些数据结构共使用了数组，链表，图和堆栈四种数据结构。三、求二叉树的叶节点的个数： algorithm countleaf( Tree *t, int count ) if( t != null ) if( t-lchild = null & t-rchild = null ) count+; co