下载文档原格式
计算机二级公共基础知识计算机二级公共基础知识计算机二级公共基础知识是计算机相关专业的考试科目之一，涵盖了计算机的基础概念、硬件和软件知识、网络与互联网等方面的内容。
本文将从计算机的基本原理、计算机硬件、计算机软件和网络与互联网等四个方面介绍计算机二级公共基础知识。
一、计算机的基本原理计算机是一台按照一定的程序运行的机器，它能够接收、处理、存储和输出数据。
其基本原理包括数据的输入和输出、数据的运算处理、程序的控制和数据的存储等。
1. 数据的输入和输出：计算机通过输入设备（键盘、鼠标等）接收用户输入的数据，经过处理后通过输出设备（显示器、打印机等）将结果输出给用户。
2. 数据的运算处理：计算机可以执行各种算术和逻辑运算操作，包括加减乘除、比较、逻辑运算等。
3. 程序的控制：计算机按照事先编写好的程序来执行任务，程序由一系列指令组成，计算机按照指令的顺序依次执行。
4. 数据的存储：计算机内部有各种存储器件，包括内存、硬盘、光盘等，用于存储数据、程序和中间结果。
二、计算机硬件计算机硬件是计算机体系结构的物理实现，包括中央处理器（CPU）、内存、输入输出设备等。
1. 中央处理器（CPU）：是计算机的核心部件，负责执行指令、控制和协调各个硬件设备的工作。
2. 内存（RAM）：用于存储正在运行的程序和数据，是计算机的临时存储器，其大小决定了计算机可以同时处理的数据量。
3. 输入输出设备：包括键盘、鼠标、打印机、显示器等，用于与计算机进行交互。
4. 存储设备：包括硬盘、光盘、U盘等，用于长期存储数据和程序。
三、计算机软件计算机软件是计算机能够运行的程序和数据的集合，分为系统软件和应用软件两类。
1. 系统软件：包括操作系统（如Windows、Mac OS）和一些常用的工具软件（如浏览器、图像处理软件），用于管理计算机的硬件资源和提供基本的功能。
2. 应用软件：包括办公软件、设计软件、编程软件等，用于满足用户特定的需求。
第一章数据构造与算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的根本特征：是一组严谨地定义运算顺序的规那么，每一个规那么都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：〔1〕可行性；〔2〕确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；〔3〕有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；〔4〕拥有足够的情报。
算法的根本要素：一是对数据对象的运算和操作；二是算法的控制构造。
根本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制构造：顺序构造、选择构造、循环构造。
算法根本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
一般来说，算法的工作量用其执行的根本运算次数来度量，而算法执行的根本运算次数是问题规模的函数。
在同一个问题规模下，用平均性态和最坏情况复杂性来分析。
一般情况下，用最坏情况复杂性来分析算法的时间复杂度。
算法空间复杂度是指执行这个算法所需要的内存空间。
数据构造研究的三个方面：〔1〕数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑构造；〔2〕在对数据进展处理时，各数据元素在计算机中的存储关系，即数据的存储构造；〔3〕对各种数据构造进展的运算。
数据构造是指相互有关联的数据元素的集合。
数据构造是反映数据元素之间关系的数据元素集合的表示。
数据的逻辑构造包含：〔1〕表示数据元素的信息；〔2〕表示各数据元素之间的前后件关系。
〔逻辑关系，与在计算机内的存储位置无关〕一个数据构造中的各数据元素在计算机存储空间中的位置关系与逻辑关系有可能不同。
数据的存储构造是数据的逻辑构造在计算机存储空间中的存放形式。
常用的存储构造有顺序、链接、索引等。
二级公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
全国计算机等级考试二级教程——公共基础知识一、计算机的基本组成部分。
计算机由硬件和软件两部分组成，硬件包括中央处理器（CPU）、存储器、输入输出设备等；软件包括操作系统、应用软件等。
1.中央处理器（CPU）：计算机的核心部件，执行所有指令。
2.存储器：存储数据和程序。
3.输入设备：把数据从外部输入到计算机中，如键盘、鼠标、扫描仪等。
4.输出设备：把计算机处理的数据输出到外部，如打印机、显示器、音响等。
二、计算机的工作原理。
计算机的工作原理可以分为5个部分：输入、存储、处理、输出和控制。
1.输入：把数据或指令输入到计算机中，通过输入设备进行输入。
2.存储：将输入的数据或指令存储在内存中。
3.处理：根据指令执行相应的操作，如计算、比较、排序等。
4.输出：将处理后的结果输出到外部，通过输出设备进行输出。
5.控制：计算机通过控制器控制各个部件的运行，以完成整个计算过程。
三、计算机的分类。
计算机按其用途和规模可以分为大型机、中型机、小型机和微型计算机。
1.大型机：主要用于大型企业和政府机关，可以同时处理多个用户的请求，性能强劲。
2.中型机：主要用于中小型企业，相对于大型机规模和性能较小。
3.小型机：主要针对个体户、小企业和办公室等，处理能力比微型计算机强。
4.微型计算机：用于一般個人用戶和小型企业，具有价格低廉、体积小及易操作的特点，性能相对其他计算机较弱。
四、操作系统。
操作系统是管理计算机硬件和软件资源的程序，它在计算机的各个层次上进行控制和管理，包括处理器的管理、内存的管理、文件系统的管理等等。
常见的操作系统有：Windows、Linux、Unix、Android等。
五、计算机网络。
计算机网络是指把分布在不同地点的计算机集成在一起，实现资源共享和信息传输的系统。
计算机网络的分层体系结构一般被分为7层，分别是物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
其中物理层和数据链路层主要负责数据传输的物理和链路层面的工作；网络层和传输层负责数据传输的网络和传输方面的工作；会话层、表示层和应用层则负责数据传输的高层次工作。
二级公共根底知识总结第一章数据结构与算法1.1也不等计算机方法，程序的编制不可能优于算法的设计。
算法的全然特征：是一组严谨地定义运算顺序的规那么，每一个规那么根基上有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：〔1〕可行性；〔2〕确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不准许有多义性；〔3〕有穷性，算法必须能在有限的时刻内做完，即能在执行有限个步骤后终止，包括合理的执行时刻的含义；〔4〕拥有足够的情报。
算法的全然要素：一是对数据对象的运算和操作；二是算法的操纵结构。
指令系统：一个计算机系统能执行的所有指令的集合。
计算工作量。
算法空间复杂度是指执行那个算法所需要的内存空间。
1.2数据结构的全然全然概念数据结构研究的三个方面：〔1〔2〔3〕对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：〔1〕表示数据元素的信息；〔2〕表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：〔1〕有且只有一个根结点；〔2〕每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3线性表及其前件；〔2〕有且只有一个终端结点an，它无后件；〔3〕除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
结点个数n n=0。
线性表的顺序存储结构具有以下两个全然特点：〔1〕线性表中所有元素的所占的存储空间是连续的；〔2〕线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。
用bottom表示栈底。
栈的全然运算：〔1〕插进元素称为进栈运算；〔2〕删除元素称为退栈运算；〔3端〔队尾〕进进插进，而在另一端〔队头〕进行删除的线性表。
Rear指针指向队尾，front指〔1〕进队运算：从队尾插进一个元素；〔2〕退队运算：从队头删除一个元素。
最新全国计算机二级考试公共基础知识考点梳理1.全国计算机二级考试公共基础知识考点梳理篇一算法的基本要素：（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。
在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。
（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。
2.全国计算机二级考试公共基础知识考点梳理篇二算法的空间复杂度：算法的空间复杂度是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。
如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。
在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
3.全国计算机二级考试公共基础知识考点梳理篇三算法的时间复杂度：算法的时间复杂度是指执行算法所需要的计算工作量。
同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。
这表明使用绝对的时间单位衡量算法的效率是不合适的。
撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依赖于问题的规模（通常用整数n表示），它是问题规模的函数。
即算法的工作量=f（n）。
二级公共基础知识总结(30分：10选择+5填空)复习及应试建议：1.考生的复习必须遵守：“ 80/20的原则”二级考试的公共知识部分的覆盖面广，至少涵盖了计算机应用专业的四门核心课程：算法及数据结构、程序设计基础、软件工程基础和数据库。
事实上，这些课程本身的涉及面就很广，难度系数较大。
因此，这些课程甚至也是计算机专业学生最头疼的课程，对大多数考生来说其难度之大不言而喻。
所以，考生应把80%的时间用在20%勺重点知识点上，争取用20%勺重点知识点来答对 80%勺考题，这是考生复习二级考试的公共知识部分的总体思路。
2.复习的关键是考生必须准确判断和掌握常见考点考生必须能够准确判断和掌握常见考点，例如：算法部分主要考查算法的概念及算法的复杂度；数据结构部分主要考查最基本的概念、最典型的数据结构和最常见的操作；程序设计部分主要考查程序设计风格的基本要求、结构化程序设计的最基本知识和面向对象程序设计的最常见概念；软件工程基础部分主要考查软件工程的基本概念及软件生命周期的各个阶段的基础知识；数据库基础部分主要考查数据库基本概念、数据模型、关系代数基础知识、数据库设计方法和步骤。
对常见考点的准确把握会使考生避免盲目学习，从而能够轻松面对考试。
二级考试中要求的知识点都是最基本的、最简单的，真正需要“灵活”掌握的考点极少。
很多考生在考试过程中可能已经发现，该部分的题目“会做就是不懂”。
所以建议在复习过程中不要急于“灵活”，其实等到把基本的知识点掌握后自然就“灵活”了。
公共知识部分仅占30%分，题目相对简单。
因此，在答题过程中，这部分要争取速度快、准确度高。
总的原则是如果一道题在两分钟没有任何思路，就应该跳过此题，把时间给后面的题目。
记住：二级考试是一种合格考试，不是竞赛，及格就行了。
公共基础的复习没有技巧，就是背诵、背诵、再背诵，就是要把这10页纸背下来。
划线字体是至关重要的部分，框起来的字体为填空题的常考词汇，一定要背熟牢记，这里面有100分里30分的原题。
目录第1章数据结构与算法1.1算法1.2数据结构的基本概念1.3栈及线性链表1.4树与二叉树1.5查找技术1.6排序技术1.7 例题详解第2章程序设计基础2.1结构化程序设计2.2面向对象的程序设计2.3 例题详解第3章软件工程基础3.1软件工程基本概念3.2结构化设计方法3.3软件测试3.4软件的调试3.5 例题详解第4章数据库设计基础4.1数据库系统的基本概念4.2数据模型4.3关系代数4.4数据库设计与管理4.5 例题详解第1章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。
详细重点学习知识点：1．算法的概念、算法时间复杂度及空间复杂度的概念2．数据结构的定义、数据逻辑结构及物理结构的定义3．栈的定义及其运算、线性链表的存储方式4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历5．二分查找法6．冒泡排序法1.1算法考点1 算法的基本概念考试链接：考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。
计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。
1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。
2．算法的基本要素：（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。
在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。
（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。
考点2 算法复杂度考试链接：考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。
二级公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
计算机二级公共基础知识在当今数字化的时代，掌握一定的计算机知识已经成为了必备的技能。
而计算机二级考试中的公共基础知识部分，更是为我们构建了扎实的计算机理论基础。
接下来，就让我们一起深入了解一下这部分重要的内容。
首先，我们来谈谈数据结构与算法。
数据结构就像是计算机存储和组织数据的方式，而算法则是解决问题的步骤和方法。
比如，我们常见的数组，它就像是一排整齐的盒子，每个盒子里都能存放数据。
而链表呢，则像是一串珠子，通过指针相连。
在算法方面，排序算法是非常重要的一部分。
像冒泡排序，它通过不断比较相邻的元素，把较大的元素逐步“浮”到数组的末尾。
还有快速排序，它选择一个基准元素，把数组分成小于和大于基准的两部分，然后分别对这两部分进行排序。
接着，程序设计基础也是必不可少的一部分。
程序设计语言有很多种，比如 C、C+＋、Java 等。
了解程序设计的基本概念，比如变量、常量、数据类型等，是编写程序的基础。
变量就像是一个可以变化的盒子，我们可以把不同的数据放进去。
常量则是固定不变的值。
而数据类型则决定了这个盒子能装什么样的数据，是整数、小数还是字符。
然后是软件工程基础。
软件工程就像是盖房子的蓝图，它指导着软件开发的全过程。
从软件的需求分析，到设计、编码、测试，再到最后的维护，每个阶段都有其重要性。
需求分析要搞清楚用户到底需要什么样的软件，设计阶段要规划好软件的架构，编码就是把设计变成实际的代码，测试则是检查软件有没有问题，维护是在软件使用过程中对其进行修改和完善。
数据库设计基础也是公共基础知识中的重点。
数据库就像是一个大型的仓库，用来存储和管理数据。
关系数据库是我们常见的一种，其中的表、字段、主键等概念都需要我们掌握。
通过建立合适的表结构，设置正确的关系，可以让我们高效地存储和查询数据。
在操作系统知识方面，操作系统就像是计算机的大管家，负责管理计算机的资源和任务。
进程管理让多个程序能够同时运行而不互相干扰，内存管理确保程序有足够的内存空间，文件管理则让我们能够方便地存储和读取文件。
全国计算机等级考试二级公共基础知识总结-第一章数据结构与算法1.1 算法1．算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。
，2．确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；3．算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
4的设计方法。
5．算法时间复杂度是指执行算法所需要的计算工作量。
可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
6．算法时间复杂度取决于问题的规模和待处理的数据的初态。
7．如果算法P调用另一个算法Q，而算法Q又调用算法P，8．工程上常用的分治法是减半递推技术910．如果查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。
也就是说，在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，在平均的情况下需要检查数组中一半的元素。
如果已知需要查找的x有一半机会在数组中，此时q=1/2。
则A(n)=[(n+1)/4]+n/2=3n/4。
x不在数组中时，A(n)=n。
. 11．下面程序段的时间复杂度是for(int i=0;i<n;i++)for(int j=1;j<=m;j++)A[i][j]=0;语句的频度指的是该语句重复执行的次数，一个算法中所有语句的频度之和构成了该算法的运行时间。
本例中语句:A[i][j]=0;的频度是n*m，所以该程序段的时间复杂度是：O(m*n).1213．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程较慢。
141.2 数据结构的基本基本概念1．数据结构研究的三个方面：；数据运算。
2．逻辑结构是数据元素间关系的描述，与所用的计算机无关3．数据的逻辑关系是指数据元素的关联。
4．数据的不可分割的基本单位是数据项。
56．一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、7。
索引等存储结构。
而采用不同的存储结构，其数据处理的效率是不同的。
8．数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式，与所使用的计算机密切相关9．根据数据结构中各数据元素之间前后件关系的复杂度，一般将数据结构分为10．在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元11．插入和删除是对数据结构的两种基本运算。
除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。
12．在数据结构中，用一组地址连续的存储单元依次存储数据元素的方式是线性结构。
131．3 线性表及其顺序存储结构12．线性表是由n个数据元素组成的一个有限序列。
删除一个元素，平均移动的元素的个数为(n-1+n-2+......+0)/n=(n-1)/2；插入一个元素，平均移动元素个数为(n+n-1+n-2+......+1)/n=(n+1)/234．线性表可以是空表。
5．非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
结点个数n称为线性表的长度，当n=0时，称为空表。
6．线性表的顺序存储结构具有以下两个基本特点：7．ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。
例：一个矢量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是108数据元素的存储位置均取决于第一个数据元素的存储位置，即：。
ADR(ai)=ADR(a1)+(i-1)k第5个元素的地址：ADR(a5)=100+(5-1)X2=1088．在线性表的顺序存储结构下，可以对线性表进行各种处理。
主要的运算有：线性表的合并、线性表的复制、线性表的逆转等9合适的，因为顺序存储的结构比较简单。
10．采用顺序存储的线性表，顺序存储结构必须占用一片连续的存储单元，当对其进行插入和删除操作时需要移动大量的元素，优点是存储密度大，由于数组的存储方式是采用顺序存储的，即占用连续的存储空间，所以可以用数组的下标直接存取。
11．查找第i-1个结点和第i个结点，在顺序表中查找的时间复杂度为O(1)速度最快。
由于链表结构在空间存储上的不连续性，在查找某个结点时，需要从当前结点开始向前或者向后逐个比较查找，浪费时间，查找结果的时间复杂度均为O(n)，12．链接存储不是占用一片连续的存储空间，所以便于进行插入和删除操作。
13．线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点，此类存储方式属于顺序存储。
1．4 栈和队列1．栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
2FILO LIFOtop表示栈顶位置，用bottom表示栈底。
3．当一个栈ST （最多元素为MaxSize）时，ST->top= -1是判断顺序栈为空的条件。
ST->top=MaxSize-1是判断顺序栈为满的条件。
4．栈的基本运算：（12（3本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。
5元素。
67．队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。
Rear指针指向队尾，front指针指向队头。
8．在一个容量为25的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有9FIFO LILO）的线性表。
10．队列运算包括（12队头删除一个元素。
循环队列：s=0表示队列空，s=1且front=rear表示队列满1112．栈的基本操作。
一个栈的入栈序列是1,2,3,...,n,其输出序列为P1，P2，P3，。
，Pn，若P1=n，则Pi为n-i+1当p1=n，即n是最先出栈的，根据栈的运算原理，n必定是最后入栈的，那么输入顺序必定是1,2,3,...,n,则出栈的序列是n,n-1,n-2,...,113．设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列B序列是不可能通过栈产生的由于栈的压入和退出只能在栈顶进行，所以要使出栈的第一个数是序列的最后一个数5，只能先把序列所有元素都压入栈，但这时出栈序列只能是（A 5，4，3，2，1），所以（B 5，3，4，1，2）选项的出栈序列是错误的，应选（B）。
当初始序列压入一个时，就退出一个元素，这样就得到（A）选项的出栈序列1，2，3，4，5；先压入1，2，3，4四个元素，再退出所有元素，最后压入5，并退栈这时得到（C）选项的出栈序列4，3，2，1，5；压入1，2后对后面的元素3，4，5分别压入一个退出一个，这时便得到（D）选项的出栈序列3，4，5，2，1。
1．5 线性链表12．数据结构中的每一个结点对应于一个存储单元，这种存储单元（一个一个小3．结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存4．在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
因此，链式存储结构是散列存储5．带头结点的双向循环链表L为空的条件是：只有该头结点，即L->next==L 或者 L->prior==L6．对于链式队列结构，插入元素是在队尾进行的，只需修改队尾指针，不需修改队头指针。
向链式队列中插入一个结点就是在单链表表尾插入一个结点，同时新插入的结点成为表尾结点。
例：在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是r->next=s;r=s;7．向链式栈中插入一个结点，就是在单链表的表头插入一个结点，同时将新结点的位置赋予栈顶指针。
例：向一个栈顶指针为HS的链式栈中插入一个s所指的结点时，则执行s->next=HS;HS=s;8．线性链表的基本操作9．双向链表每个结点有两个指针域，这两个指针分别指向它的10．单链表中，每个结点都含有一个指针域，这个指针指向它的下一个结点。
因11．由于双向链表比单链表结构复杂，所以在插入和删除元素时，要修改更多的指针域，相对比较复杂，单向链表和双向链表在空间存储上的不连续性决定了两者都不可以随机访问，在双向链表中由于每个结点包括两个指针域，其中一个指向该结点的前驱结点，另一个指向该结点的后继结点，因此它既可以直接访问前驱结点，又可以直接访问后继结点，而单链表每个结点只有一个指针域，指向它的后继结点，所以它只能直接访问它的下一个结点，而无法直接访问它的前一个结点。
所以双向链表顺序访问相邻结点更加灵活。
12．链表的特点：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。
链表结构是一些逻辑上相邻，而空间上并不一定相邻的数据元素的集合，相邻的结点之间通过指针相互联系，在插入和删除元素时，只需修改结点指针即可，不需要移动数据元素。
当存储空间不足时，可以动态为其分配内存空间，所以不必事先估计存储空间的大小。
所需空间与其长度成正比。
13．用带头结点的链表表示线性表时，空表和非空表的插入、删除是相同的。
当往空链表插入元素时，只要把待插入元素的指针域指向头结点的指针域，把头结点的指针域指向新增元素即可，当往非空链表插入元素时只要找到插入的位置，执行同样的操作即可完成插入。
当链表只有一个元素时，删除操作只要修改指针指向下一个元素的指针所指的元素即可，跟一般的链表删除操作是一样的。
带头结点的链表并不能加快对链表的遍历，带头结点的链表反而要增加一个用于存储头结点的空间，并不能节省存储空间，用带头结点的链表跟存取元素的速度无关。
14．忽略了最后结点或头结点的指针，在n个结点的单向链表（无表头结点）中，每个结点都有一个指针单元（即指针域），加上头指针，至少需要n+1个指针单元。
1．6 树与二叉树1．树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
栈和队列都是线性结构。
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。
每一个结点可以有多个后件，称为该结点的子结点。
没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。
树的最大层次称为树的深度。
二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
2．树的结点不能为空，结点最少的树为只有一个结点的树；二叉树的结点数可以为03．设树T的度为4，其中度为1，2，3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数为应的结点个数乘积之和为1。
