一．判断题（每题1分）
（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。
（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（7）数据的存储结构是数据的逻辑结构的存储映像。
（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。
（ㄨ）（9）数据的逻辑结构是依赖于计算机的。
（√）（10）算法是对解题方法和步骤的描述。
二．填空题（每题1分）
1．数据有逻辑结构和存储结构两种结构。
2．数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。
3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
4．树形结构和图形结构合称为非线性结构。
5.在树形结构中，除了树根结点以外，其余每个结点只有1个前趋结点。
6.在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。
7．数据的存储结构又叫物理结构。
8．数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。
9．线性结构中的元素之间存在一对一的关系。
10．树形结构结构中的元素之间存在一对多的关系，
11．图形结构的元素之间存在多对多的关系。
12．数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。13．数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。14．算法是一个有穷指令的集合。
15．算法效率的度量可以分为事先估算法和事后统计法。
16．一个算法的时间复杂性是算法输入规模的函数。
17．一个算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。18．若一个算法中的语句频度之和为T（n）=6n+3n l o g2n，则算法的时间复杂度为O（n l o g2n）。19．若一个算法中的语句频度之和为T（n）=3n+n l o g2n+n2，则算法的时间复杂度为O（n2）。
20.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。
三．选择题（每题1分）
1．数据结构通常是研究数据的（A）及它们之间的相互联系。
A.存储结构和逻辑结构
B.存储和抽象
C.联系和抽象
D.联系与逻辑
2．数据结构中，在逻辑上可以把数据结构分成：（C）。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
3．数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。
A.存储结构
B.逻辑结构
C.顺序存储结构
D.链式存储结构
4．非线性结构中的每个结点（D）
1.无直接前趋结点
2.无直接后继结点
3.只有一个直接前趋结点和一个直接后继结点
4.可能有多个直接前趋结点和多个直接后继结点
5．链接存储的存储结构所占存储空间（A）。
A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元素
6．算法的计算量大小称为计算的（C）
A.现实性
B.难度
C.时间复杂性
D.效率
7．数据的基本单位是（B）
A.数据结构
B.数据元素
C.数据项
D.文件
8．每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（A）结构。
A.顺序存储
B.链式存储
C.索引存储
D.散列存储
9．每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）存储方式A.顺序 B.链式 C.索引 D.散列
10．以下任何两个结点之间都没有逻辑关系的是（D）
A.图形结构
B.线性结构
C.树形结构
D.集合
11．在数据结构中，与所使用的计算机无关的是（C）
A.物理结构
B.存储结构
C.逻辑结构
D.逻辑和存储结构
12．下列四种基本逻辑结构中，数据元素之间关系最弱的是（A）
A.集合
B.线性结构
C.树形结构
D.图形结构
13．与数据元素本身的形式、内容、相对位置、个数无关的是数据的（A）
A.逻辑结构
B.存储结构
C.逻辑实现
D.存储实现
14．每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C）存储方式
A.顺序
B.链式
C.索引
D.散列
15．算法能正确的实现预定功能的特性称为（A）
A.正确性
B.易读性
C.健壮性
D.高效性
16．算法在发生非法操作时可以作出处理的特性称为（C）
A.正确性
B.易读性
C.健壮性
D.高效性
17．下列时间复杂度中最坏的是（D）
A.O（1）
B.O（n）
C.O（l o g2n）
D.O（n2）
18．下列算法的实际复杂度是（D）
f o r(i=0;i f o r(j=0;i c[i][j]=i+j; A.O（1） B.O（n） C.O（l o g2n） D.O（n2） 19.算法分析的两个主要方面是（A）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 20．计算机算法必须具备输入、输出和（C） A.计算方法 B.排序方法 C.解决问题的有限运算步骤 D.程序设计方法 四．分析下面各程序段的时间复杂度(每小题5分，共20分) 1.f o r(i=0;i f o r(j=0;j A[i][j] 解：O（n*m） （2）s=0; f o r(i=0;i f o r(j=0;j s+=B[i][j]; s u m=s; 解：O（n2） （3）T=A； A=B； B=T； 解：O（1） （4）x=0;y=o; f o r(k=1;k<=n;k++) x++; f o r(i=1;i<=n;i++) f o r(j=1;j<=n;j++ y++; 解：O（n2） 五．根据二元组关系，指出它们属于何种数据结构。 (每小题10分，共30分) 1．A=（D，R），其中： D={a，b，c，d，e，f}，R={r} R={ （上式中尖括号表示括号内的结点之间关系是有向的） 解：线性结构 2．B=（D，R），其中： D={1，2，3，4，5，6}， R={（1,2）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（4,6）}解：属于图结构 3．C=（D，R），其中： D={a，b，c，d，e，f，g，h}， R={ 解：属于树结构 第一章绪论 一、判断题 (1）数据的逻辑结构与数据元素本身的内容和形式无关。 (2）数据元素是数据的最小单位。 (3）算法是对解题方法和步骤的描述。 (4）程序和算法原则上没有区别，在讨论数据结构时可以通用。 (5）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 (6）数据的存储结构是数据的逻辑结构的存储映像。 二、填空题 (1）数据逻辑结构包括：______、______、______、______四种类型，树形结构和图形结构合称为：_______。(2）数据的存储结构形式包括：_______、______、______、______。 (3) 数据元素是数据的基本单位，在某些情况下也可以称为和。 (4）线性结构中的元素之间存在______________的关系，树形结构中的元素之间存在__________的关系，图形结构的元素之间存在_____________的关系。 (5）算法的五个重要特性是：_______、_______、_______、_______、_______。 (6）数据结构被定义为（D,R) ，其中D是_______的有限集合，R是D上的_________的有限集合。 (7）数据结构主要研究数据的_________、___________和___________。 (8）算法是一个_______的集合；算法效率的度量可以分为_______和________。 (9) 以下程序段的时间复杂度 T ( n ) = 。 sum=0； for(i=0;i for(j=0;j sum=sum+a[i][j]; printf(“%d\n”,sum); (10) 以下计算 2 个 n 阶矩阵乘积的算法的时间复杂度是。 for ( i = l ; i < = n ; i + + ) { for(j=1; j < = n ; j + + ) { c[i][j]=0; for ( k = l ; k < = n ; k + + ) c[i][j]=c[i][j] + a [i][k] * b[k][j]; } } 三、选择题 (l）数据结构通常是研究数据的（）及它们之间的相互联系。 A．存储结构和逻辑结构 B．存储和抽象 C．联系和抽象 D．联系与逻辑 (2) 下列与数据元素有关的叙述中错误的是（）。 A．数据元素是有独立含义的数据最小单位 B．数据元素是描述数据的基本单位 C．数据元素可以称做结点 D．数据元素可以称做记录 (3）数据结构中，在逻辑上可以把数据结构分成：( ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 (4）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 ( ）。 A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构 (5）非线性结构的数据元素之间存在（）。 A．一对一关系 B．一对多关系 C．多对多关系 D. B 或 C (6）在非线性结构中，每个结点（）。 A. 无直接前驱 B．只有一个直接前驱和个数不受限制的直接后继 C．只有一个直接前驱和直接后继 D．有个数不受限制的直接前驱和直接后继 (7）除了考虑存储数据结构本身所占用的空间外，实现算法所用的辅助空间的多少称为算法的（）。 A．时间效率 B．空间效率 C．硬件效率 D．软件效率 (8)以下属于顺序存储结构优点的是（）。 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 (9)数据结构研究的内容是（）。 A．数据的逻辑结构 B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面 (10)链式存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 (11)一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。 A．确定性、可行性、有穷性 B．易读性、确定性、有效性 C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性 (12)以下关于数据的逻辑结构的叙述中正确的是（）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 (13)设问题的规模为 n ，分析以下程序段： k = n ; /* n > l */ m = 0 ; while ( k > = ( m + l ) * ( m - l ) ) m ++； 以上程序段的算法时间复杂度是( ) A. O( n ) B. O(1) C. O(n) D. O( n2 ) (14)设问题的规模为n ，分析以下程序段： a = 10 ; b = l00 ; while （b＞ 0 ) { a + + ; b ――；} 以上程序段的算法时间复杂度是（）。 A.O( n ) B. O(1) C. O(n) D. O( n2 ) (15)设语句 s=s+i 的时间是单位时间，则语句： s=0; for (i=l;i<=n;i++) s=s+i; 的时间复杂度为：( ）。 A. O(l) B. O(n) C. O(n2) D. O(n3) (16)算法分析的主要任务是（）。 A．探讨算法的正确性和可读性 B．探讨数据组织方式的合理性 C．为给定问题寻找一种性能良好的解决方案 D．研究数据之间的逻辑关系 (17)以下叙述中正确的是（）。 A．顺序存储方式只能用于存储线性结构 B．链式存储方式只能用于存储线性结构,探讨数据组织方式的合理性,研究数据之间的逻辑关系C．顺序存储和链式存储都可以用于线性和非线性结构 D．以上三种都不对 (18)以下叙述中正确的是（）。 A．数据元素是数据处理的最小单位 B．数据项是数据处理的基本单位 C．关键字是能够惟一标识一个数据元素的数据项 D．数据结构和数据类型的概念是等价的 四、简答题 (1)分别描述数据、数据元素、数据项、数据结构、逻辑结构、存储结构、算法的概念。 (2)试分析下列程序段的时间复杂度 五、算法设计题 （1）设有一个以“ ! ”为结束标志的字符串 S ，试设计一个算法，确定第 1 次出现的大写字母 A 在字符串中的位置（位置号从 0 开始）。 （2）已知判断闰年的条件是：①能被 4 整除，但不能被 100 整除的年份是闰年；②能被 100 整除，同时又能被 400 整除的年份是闰年。不满足上述条件之一的年份不是闰年。试设计一个算法，输出 2000 一 2050 年中的所有闰年。 （3）设计一个算法，用以求两个正整数 m 和 n 的最大公约数和最小公倍数。 第一章绪论 一、判断题 (1）√ (2）× (3）√ (4）× (5）√ (6）√三、选择题 (1） A (2） A (3） C (4） C (5） D (6） D (7) B (8) A (9) D (10) A (11) A (12) A (13) A (14) A (15) B (16) C (17) C (18) C 数据结构设计与技巧讲义 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）气泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 【知识点解析】 1.线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 2.栈、队列和数组 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。 .. ;.. 第一章 概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K ）以及这些数据之间的 一组二元关系（关系集合R ）来表示：(K, R) 结点集K 是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R 是定义在集合K 上的一组关系，其中每个关系r （r ∈R ）都是K ×K 上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char ）、指针类型（pointer ） b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a ．大Ο分析法：上限，表明最坏情况 b ．Ω分析法：下限，表明最好情况 c ．Θ分析法：当上限和下限相同时，表明平均情况 第二章 线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L （设每个元素需占用L 个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e .插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n ）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n ）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head 和tail 指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n ）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n ）】 e.不足：next 仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head 和tail 指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相 比其比例较大时，应该慎重选择 第三章 栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch ： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项> <项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ? <常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp 为中缀表达式，PostfixExp 为后缀表达式 初始化操作数栈OP ，运算符栈OPND ；OPND.push('#'); 读取InfixExp 表达式的一项 操作数：直接输出到PostfixExp 中； 操作符： 当‘（’：入OPND; 当‘）’：OPND 此时若空，则出错；OPND 若非空，栈中元 素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若 为‘（’，弹出即可 当‘四则运算符’：循环（当栈非空且栈顶不是‘（’&& 当前运算符优先级>栈顶运算符优先级），反复弹出栈顶运 算符并输入到PostfixExp 中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP ； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP ； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear ；队满：(rear+1)%n==front 第五章 二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数 d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树 e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶组成扩充二叉树，扩充二叉树是满二叉树 外部路径长度E ：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和 内部路径长度I ：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i 层（根为第0层，i ≥0）最多有2^i 个结点 b. 深度为k 的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1 f. 有n 个结点（n>0）的完全二叉树的高度为?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n 个结点的完全二叉树，结点按层次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点编号是 (i-1)/2 2) 当2i+1 《数据结构(C语言版)》复习重点 重点在二、三、六、七、九、十章，考试内容两大类：概念，算法 第1章、绪论 1.数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2.数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构 4.逻辑结构：是数据元素之间的逻辑关系的描述。 5.物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。 其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构6.算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 其5个重要特性：有穷性、确定性、可行性、输入、输出 7.时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n))；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如：(a){++x;s=0;} (b)for(i=1;i<=n;++i){++x;s += x;} (c)for(j=1;j<=n;++j) for(k=1;k<=n;++k){++x;s += x;} 含基本操作“x增1”的语句的频度分别为1、n和n2，则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n2)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(log n)、指数阶O(2的n次方)等。 8.空间复杂度：算法所需存储空间的度量记作，S(n)=O(f(n))。 第2章、线性表 1.线性表：是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。 2. 线性表的顺序存储结构：是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。 存储位置计算：假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，线性表的第i个数据元素ai的存储位置为LOC(ai)=LOC(a1)+(i-1)*L式中LOC(a1)是线性表第一个元素a1的存储位置，通常称做线性表的起始位置或基地址。 3. 线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。 第九章查找 一、基本概念（共40分，每题4分） 1、具有12个关键字的有序表，折半查找的平均查找长度________. A、3.1 B、4 C、2.5 D、5 2、下面关于折半查找的叙述正确的是________ A、表必须有序，表可以顺序方式存储，也可以链表方式存储 B、表必须有序，而且只能从小到大排列 C、表必须有序且表中数据必须是整型，实型或字符型 D、表必须有序，且表只能以顺序方式存储 3、与其他查找方法相比，散列查找法的特点是_______。 A．通过关键字的比较进行查找B．通过关键字计算元素的存储地址进行查找 C．通过关键字计算元素的存储地址并进行一定的比较进行查找D．以上都不是 4、适用于折半查找的表的存储方式及元素排列要求为______________。 A.链式方式存储，元素无序 B.链式方式存储，元素有序 C.顺序方式存储，元素无序 D.顺序方式存储，元素有序 5、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则折半查找元素55需要比较______次。 A．1 B．2 C．3 D．4 6、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较______次。 A．3 B．4 C．5 7、 D．6 7、若对数据集{23,44,48,36,52,73,64,58}建立散列表，采用H(k)=k MOD 13计算散列地址，并采用链地址法处理冲突，则元素64的散列地址为。 8、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中。这种方式主要适合于_______。 A．静态查找表B．动态查找表 C．静态查找表与动态查找表D．两种表都不适合 9、在线性表的哈希存储中，处理冲突有________________和________________两种； 装填因子的值越大，存取元素时发生冲突的可能性就________________， 装填因子的值越小，存取元素时发生冲突的可能性就________________。 10、已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则比较次数最多是______________。 二、综合计算（每题15分，共60分） 数据结构以及C语言常问与难点 1.序言 2.常问与难点，为避免重复发帖，特设此帖并置顶，以供浏览查阅。 3.内容主要是将本版的好帖子收集起来，并加以整理，仅给出知识点分析与问题解答，并不给出原帖链接，致歉。 4.本版中的好东西会慢慢添加进来（各位版主齐心协力，每天添加一个知识点，用不了多久就会很强大），本帖观点只 是各位版主和我个人的分析，不一定尽善尽美，但一定是尽心尽力。各位热心研友如有修正和补充，请在回复中说明。 5.特代表研友感谢各位版主的辛勤奉献，代表版主感谢热心研友对王道的支持（呵呵）。特别地，祝备考10的研友们一 切顺利，考上理想的学校。珍惜时间，努力才是王道。 1.目录，共占用一个代码区 2. 3. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。 4.typedef struct LNode{ 5. ElemType data; 6. struct LNode *next; 7.} LNode, *LinkList; 8. 9. 2.符号&的含义，指针进阶。涉及知识点：引用机制，实参与形参，C语言中地址与指针（以及指向指针的指针），指 针的传递（暂不涉及数组与指针的知识，将在以后介绍）。 10. 11. 3.如下方式动态分配内存的全部细节解释。涉及知识点：动态分配内存，define，强制类型转换，malloc()，顺序 表存储结构，顺序表与数组，链表结点的内存分配，指针细节，附完整程序。 12.L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 复制代码 1.正文，每个问题占用一个代码区 复制代码 1. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。 2.typedef struct LNode{ 3. ElemType data; 4. struct LNode *next; 5.} LNode, *LinkList; 6. 7.如下是一个最简单的结构体定义： 一、是非题 1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发，都能访问到所有结点........( F ) 7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中，队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是（ D ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址（B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A．O(n) B．O(1) C．O(n2) D．O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点 的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B ) A．s一>1ink=p一>1ink；p一>1ink＝s B．q一>1ink＝s；s一>link=p C．p一>link＝s一>1ink；s一>1ink＝p 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 2018考研计算机：数据结构重难点及 复习建议 新东方在线推荐： 一、重难点解析和复习建议 数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。 当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。 下面我们来解析一下知识点： 线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。 栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。 树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二 数据结构复习重点归纳 （适于清华严版教材） 一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。 栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。 多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。 树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。 二、数据结构各章节重点勾划： 第0章概述本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。 第一章线性表作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。 总体来说，线性表一章可供考查的重要考点有以下几个方面： 1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。 2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。 3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。 4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双 向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。 在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。 5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储 结构的各自好处。 第二章栈与队列栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。 学习此章前，你可以问一下自己是不是已经知道了以下几点： 1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。 2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问 题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。 3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。 4.循环队列中判队空、队满条件，循环队列中入队与出队算法。 如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。 第三章串经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。数据结构设计与技巧
大学数据结构期末知识点重点总结(考试专用)
数据结构复习重点要点
深圳大学 数据结构 查找作业
数据结构以及C语言常问与难点
2010级数据结构期末复习题(E)
数据结构复习要点(整理版).docx
2018考研计算机：数据结构重难点及复习建议
数据结构复习重点归纳
相关主题
文本预览