大学学习资料：数据结构(c语言版)复习资料.doc

1、1数据结构数据结构(c(c 语言版语言版) )复习资料复习资料一、填空题一、填空题1.数据结构是一门研究非数值计算的程序设计问题中数据结构是一门研究非数值计算的程序设计问题中计算机的计算机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和运算等的学科。运算等的学科。2. 数据结构被形式地定义为数据结构被形式地定义为（D, R） ，其中其中 D 是是数据数据元素元素的有限集合，的有限集合，R 是是 D 上的上的关系关系有限集合有限集合。3. 数据结构包括数据的数据结构包括数据的逻辑结构逻辑结构、数据的数据的存储结构存储结构和数据的和数据的运算运算这三个方面的内容。这三个方面的内容。4.

2、数据结构按逻辑结构可分为两大类，它们分别是数据结构按逻辑结构可分为两大类，它们分别是线性结构线性结构和和非线性结构非线性结构。5. 线性结构中元素之间存在线性结构中元素之间存在一对一一对一关系关系， 树形结构中元树形结构中元素之间存在素之间存在一对多一对多关系关系，图形结构中元素之间存在图形结构中元素之间存在多对多对多多关系。关系。6 在线性结构中，第一个结点在线性结构中，第一个结点没有没有 前驱结点，其前驱结点，其余每个结点有且只有余每个结点有且只有 1 个前驱结点个前驱结点； 最后一个结点最后一个结点没没有有后续结点后续结点， 其余每个结点有且只其余每个结点有且只有有1 个后续结点个后续结

3、点。7. 在树形结构中，树根结点没有在树形结构中，树根结点没有 前驱前驱结点，其余每结点，其余每个结点有且只有个结点有且只有1个前驱结点；叶子结点没有个前驱结点；叶子结点没有后续后续结点结点，其余每个结点的后续结点数可以其余每个结点的后续结点数可以任意多任意多个个。8. 在图形结构中在图形结构中， 每个结点的前驱结点数和后续结点数每个结点的前驱结点数和后续结点数可以可以任意多个任意多个。9数据的存储结构可用四种基本的存储方法表示，它数据的存储结构可用四种基本的存储方法表示，它们分别是们分别是顺序顺序、 链式链式 、 索引索引和和散列散列。10. 数据的运算最常用的有数据的运算最常用的有 5 种

4、种，它们分别是它们分别是插入插入 、 删删除、修改、除、修改、 查找查找 、排序、排序。11. 一个算法的效率可分为一个算法的效率可分为时间时间效率和效率和空间空间效率。效率。12. 在顺序表中插入或删除一个元素在顺序表中插入或删除一个元素， 需要平均移动需要平均移动 表表中一半中一半元素，具体移动的元素个数与元素，具体移动的元素个数与 表长和该元素在表长和该元素在表中的位置表中的位置有关。有关。13. 线性表中结点的集合是线性表中结点的集合是 有限有限的的， 结点间的关系结点间的关系是是一对一一对一的。的。14. 向一个长度为向一个长度为 n 的向量的第的向量的第 i 个元素个元素(1in+

5、1)之之前插入一个元素时，需向后移动前插入一个元素时，需向后移动 n-i+1个元素。个元素。15. 向一个长度为向一个长度为 n 的向量中删除第的向量中删除第 i 个元素个元素(1in)时，需向前移动时，需向前移动 n-i个元素。个元素。16. 在顺序表中访问任意一结点的时间复杂度均为在顺序表中访问任意一结点的时间复杂度均为O(1)，因此因此，顺序表也称为顺序表也称为 随机存取随机存取的数据结构的数据结构。17. 顺序表中逻辑上相邻的元素的物理位置顺序表中逻辑上相邻的元素的物理位置 必定必定相邻相邻。单链表中逻辑上相邻的元素的物理位置单链表中逻辑上相邻的元素的物理位置 不一定不一定 相邻相邻。

6、18在单链表中在单链表中，除了首元结点外除了首元结点外，任一结点的存储位置由任一结点的存储位置由 其其直接前驱结点的链域的值直接前驱结点的链域的值指示。指示。19 在在 n 个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点*p，需找，需找到它的到它的前驱结点的地址前驱结点的地址，其时间复杂度为，其时间复杂度为 O（n） 。20.栈只能在栈只能在栈顶栈顶插入和删除元素插入和删除元素； 对于队列只能对于队列只能在在队尾队尾插入和插入和队首队首删除元素。删除元素。21. 栈是一种特殊的线性表，允许插入和删除运算的一栈是一种特殊的线性表，允许插入和删除运算的一端称为端称为栈顶栈顶。不允许插

7、入和删除运算的一端称。不允许插入和删除运算的一端称为为栈底栈底。22.队列队列是被限定为只能在表的一端进行插入运是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。算，在表的另一端进行删除运算的线性表。23.23.不包含任何字符不包含任何字符（长度为（长度为 0 0）的串的串称为空串；称为空串；由一个或多个空格由一个或多个空格（仅由空格符仅由空格符）组成的串组成的串称为空称为空白串。白串。24.24. 子串的定位运算称为串的模式匹配；子串的定位运算称为串的模式匹配； 被匹配的主被匹配的主串串称为目标串，称为目标串，子串子串称为模式。称为模式。25.25. 假设有二维数组假设

8、有二维数组 A A6 68 8，每个元素用相邻的，每个元素用相邻的 6 6 个字节个字节存储存储，存储器按字节编址存储器按字节编址。已知已知 A A 的起始存储位置的起始存储位置（基基地址）为地址）为 10001000，则数组，则数组 A A 的体积（存储量）为的体积（存储量）为288288B B；末尾元素末尾元素 A A5757的第一个字节地址为的第一个字节地址为12821282；若按行存储时若按行存储时，元素元素 A A1414的第一个字节地址为的第一个字节地址为(8+4)(8+4)6+1000=10726+1000=1072；若按列存储时若按列存储时，元素元素 A A4747的第一个字的

9、第一个字节地址为节地址为(6(67 74)4)6 610001000）12761276。26 由个结点所构成的二叉树有由个结点所构成的二叉树有5种形态。种形态。27.一棵深度为一棵深度为 6 的满二叉树有的满二叉树有n1+n2=0+ n2=n0-1=31个分支结点和个分支结点和 26-1=32个叶子。个叶子。注注：满二叉树没有度为满二叉树没有度为 1 的结点的结点，所以分支结点数就是所以分支结点数就是二度结点数。二度结点数。28 一棵具有个结点的完全二叉树，它的深度一棵具有个结点的完全二叉树，它的深度为为9。（ 注：用注：用 log2(n) +1= 8.xx +1=92929 设一棵完全二叉树

10、有设一棵完全二叉树有 700700 个结点个结点， 则共有则共有350个个叶子结点叶子结点。答：最快方法：用叶子数答：最快方法：用叶子数n/235030 设一棵完全二叉树具有设一棵完全二叉树具有 1000 个结点个结点，则此完全二则此完全二叉树有叉树有 500个叶子结点个叶子结点， 有有499个度个度为为 2 的结点的结点，有有1个结点只有非空左子树个结点只有非空左子树，有有0个结点只个结点只有非空右子树。有非空右子树。答：最快方法：用叶子数答：最快方法：用叶子数n/2500 ，n2=n0-1=499。另外另外，最后一结点为最后一结点为 2i 属于左叶子属于左叶子，右叶子是空的右叶子是空的，所

11、所以有以有 1 个非空左子树个非空左子树。完全二叉树的特点决定不可能有完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数左空右不空的情况，所以非空右子树数0.31在数据的存放无规律而言的线性表中进行检索的最在数据的存放无规律而言的线性表中进行检索的最佳方法是佳方法是顺序查找（线性查找）顺序查找（线性查找）。32. 线性有序表线性有序表（a1，a2，a3，a256)是从小到大排列是从小到大排列的，对一个给定的值的，对一个给定的值 k，用二分法检索表中与，用二分法检索表中与 k 相等的相等的元素元素， 在查找不成功的情况下在查找不成功的情况下， 最多需要检索最多需要检索8次次。设有设有

12、 100 个结点，用二分法查找时，最大比较次数是个结点，用二分法查找时，最大比较次数是7。33. 假设在有序线性表假设在有序线性表 a20上进行折半查找上进行折半查找， 则比较一则比较一次查找成功的结点数为次查找成功的结点数为 1；比较两次查找成功的结点数；比较两次查找成功的结点数为为2；比较四次查找成功的结点数为比较四次查找成功的结点数为8；平均平均查找长度为查找长度为3.7。解解：显然显然，平均查找长度平均查找长度O O（loglog2 2n n）5top0ST-top=0ST-topm0ST-top=m0（C ）18. 在一个图中在一个图中，所有顶点的度数之和等于图所有顶点的度数之和等于

13、图的边数的的边数的倍。倍。A1/2B.1C.2D.4（B）19. 在一个有向图中，所有顶点的入度之和在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的等于所有顶点的出度之和的倍。倍。A1/2B.1C.2D.4（B）20. 有有 8 个结点的无向图最多有个结点的无向图最多有条边条边。A14B.28C.56D.112（C）21. 有有 8 个结点的有向完全图有个结点的有向完全图有条边条边。A 14B.28C.56D.11 对矩阵进行压缩存储是为了D。A方便运算B 方便存储C提高运算速度D减少存储空间设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a1，1为第一个元素，其

14、存储地址为 1，每个元素占 1 个地址空间，则 a8，5的地址为B。A13B 33C18D40允许对队列进行的操作有D。A 对队列中的元素排序B 取出最近进队的元素C 在队头元素之前插入元素D 删除队头元素输入序列为 ABC，可以变为 CBA 时，经过的栈操作为B。Apush，pop，push，pop，push，popBpush，push，push，pop， pop， popCpush，push，pop， pop，push，popDpush，pop，push，push，pop， pop（B）22在表长为的链表中进行线性查找，它在表长为的链表中进行线性查找，它的平均查找长度为的平均查找长度为.

15、;. （） ;. n;. （）（A）23折半查找有序表（折半查找有序表（4，6，10，12，20，30，50，70，88，100） 。若查找表中元素若查找表中元素 58，则它将依则它将依次与表中次与表中比较大小，查找结果是失败。比较大小，查找结果是失败。A20，70，30，50B30，88，70，50C20，50D30，88，50（C）24对对 22 个记录的有序表作折半查找个记录的有序表作折半查找，当查当查4找失败时找失败时， 至少需要比较至少需要比较次关键次关键字。字。A3B4C5D 6（A）25. 链表适用于链表适用于查找查找A顺序顺序 B二分法二分法C顺序顺序，也能二分法也能二分法 D

16、随机随机四、简答题四、简答题1.数据结构和数据类型两个概念之间有区别吗？数据结构和数据类型两个概念之间有区别吗？答答：简单地说简单地说，数据结构定义了一组按某些关系结合在一起的数数据结构定义了一组按某些关系结合在一起的数组元素组元素。数据类型不仅定义了一组带结构的数据元素数据类型不仅定义了一组带结构的数据元素，而且还在而且还在其上定义了一组操作。其上定义了一组操作。2. 简述线性结构与非线性结构的不同点。简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构一对一的，非线性结构反映结点间的逻辑关系是多对多的。反映结点间的逻辑

17、关系是多对多的。3、分析下面各程序段的时间复杂度、分析下面各程序段的时间复杂度1.项基本原则4.设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。刘答：至少有 14 种。 全进之后再出情况，只有 1 种：4，3，2，1 进 3 个之后再出的情况，有 3 种，3,4,2,13,2,4,13,2,1,4 进 2 个之后再出的情况，有 5 种，2,4,3,12,3,4,12,1, 3,42,1,4,32,1,3,4 进 1 个之后再出的情况， 有 5 种， 1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,35.给定二叉

18、树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树 B，并简述由任意二叉树 B 的前序遍历序列和中序遍历序列求二叉树 B 的思想方法。解：方法是：由前序先确定解：方法是：由前序先确定 root，由中序可确定，由中序可确定 root的左的左、右子树右子树。然后由其左子树的元素集合和右子树的然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合集合对应前序遍历序列中的元素集合，可继续确定可继续确定 root的左右孩子的左右孩子。将他们分别作为新的将他们分别作为新的 root，不断递归不断递归，则则所

19、有元素都将被唯一确定，问题得解。所有元素都将被唯一确定，问题得解。DACFEGBHI6. 试写出如图所示的二叉树分别按先序试写出如图所示的二叉树分别按先序、中序中序、后序遍后序遍历时得到的结点序列。历时得到的结点序列。答：DLR：AB D F J G K C E H I L MLDR:B F J D G KAC H E L I MLRD：J F K G D B H L M I E C A数据结构的概念：数据之间的内在联系。要了解 3 种数据结构的概念：逻辑结构；物理结构；基本操作。例如：栈和队的逻辑结构都是线性的，但她们的基本操作不同，就是不同的数据结构。常见的数据结构的分类：线性关系；集合关

20、系；一对多；多对多（图） ；什么事物理结构（应该有印象） 。算法设计时要用类 PASCAL,类 C，不要用 C+.算法分析的常用方法：事前分析；事后统计。时间/空间复杂度的概念。 空间是算法运行时资源占用情况。时间复杂度：最坏，最好，平均。例如：归并排序都是 O（n*logn） ，最好，最怀，平均都是一样的插入排序：最好为 O(n) ,最坏为 O（n2）线性表：逻辑关系，各种基本操作，两个有序表的归并。线性表的顺序存储：线性表的操作在顺序表中的实现。例如：1。插入与删除和插入的位置与表长有关。2在一个长为 n 的表中插入一个元素的平均复杂度，要有插入位置的概率分布表达式，即给出此表达式，算平均

21、复杂度。线性表的链式存储：链表的基本操作：2 个有序表的归并。例如：1。把链表就地逆置：一个指针 P 指向当前逆置好的一系列节点的最后一个节点， 取 P 的 NEXT 插入队头。2三色问题：节点红黄蓝在链表上无序排列，把他们按红黄蓝的顺序排好。要求只能从头到尾搜索一遍。设当前指针 P， 头指针 S， S.NEXT 为 Q， S 后接红节点。若 P 为红，插入 S 后。若 P 为黄，插入 Q 后。若 P 为兰，不动。然后 P 向后移，求下个。注：要了解单链表的插入，删除在什么位置操作。静态链表（数组表示） ：不能象单链表那样不受限增加节点。循环链表：如果表示队列，用它最好。P 指向队尾。好处：用

22、于优先队列中。双向链表： 单链表中只有 P 指向当前节点， 不能删除 P。因为无法找到 P 的前驱。而双向链表可以。注意指针变化情况。栈：后进先出。基本操作：出入栈，取栈顶。在顺序表和链表上的实现；出栈序列是否合理？例如： 入栈序列是 1， 2， ， ， n， 则出栈序列有几种？（即n 个节点的二叉树的个数。因为树的先序是 1，2， ， ，n） 。栈与递归：见我给你寄过去的手写体。队列：先进现出。链队列，循环队列。例如：1。把从队头开始的第 i 个元素删除：队列 只有(1.)for (i=0;in; i+)for (j=0; jm; j+)Aij=0;答：O（m*n）(2.)x=0;for(i

23、=1; in; i+)for (j=1; jlchild;b-lchild = b-rchild;b-rchild = t;swap( b-lchild );swap( b-rchild );六、用两个栈模拟一个队列：algorithm 用两个栈模拟一个队列stack s1, s2; / 容量都为 n。void 元素入队int x;if( s1-top = n )printf( 队列上溢 );elsepush( s1, x );void 元素出队int x;s2-top = 0;while( !Empty( s1 ) )push( s2, pop( s1 ) );pop( s2, x );while( !Empty( s2 ) )push( s1, pop( s2 ) );void 判断队列是否为空if( isEmpty( s1 ) )return( 1 );elsereturn( 0 );