全国计算机等级考试二级教程公共基础知识数据结构与算法

全国计算机等级考试二级教程公共基础知识2018/1/52第一章数据结构与算法2018/1/5311算法111算法的基本概念算法是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法。一般说来，程序的编制不可能优于算法的设计。2018/1/5411算法1算法的基本特征可行性（EFFECTIVENESS）确定性（DEFINITENESS）有穷性（FINITENESS）拥有足够的情报2018/1/5511算法算法的定义是一组严禁地定义的运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下中止。2018/1/5611算法2算法的基本要素1算法中对数据的运算和操作算术运算逻辑运算关系运算数据传输2018/1/5711算法2算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具有传统流程图、NS结构化流程图、算法描述语言等。算法的基本控制结构顺序、选择、循环2018/1/5811算法3算法设计基本方法列举法归纳法递推递归减半递推技术回溯法2018/1/5911算法例题1设方程FX0在A,B上有实根，且FA与FB异号，利用二分法来该方程在区间A,B上的一个实根。ABCBC2018/1/51011算法112算法复杂度算法的复杂度包括时间复杂度和空间复杂度。1算法的时间复杂度算法的时间复杂度是指算法所需要的计算工作量。与问题有关与问题的规模有关与输入有关2018/1/511课后习题选择1算法的时间复杂度是指执行算法程序所需要的时间算法程序的长度算法执行过程中所需要的基本运算次数算法程序中的指令条数2018/1/5122005年9月试题填空算法复杂度主要包括时间复杂度和【2】复杂度。2018/1/51311算法算法工作量F（N）N是问题的规模2018/1/51411算法分析算法的工作量平均性态最坏情况复杂性2018/1/51511算法例题2采用顺序搜索法，在长度为N的一维数组中查找值为X的元素。即从数组的第一个元素开始，逐个与被查值X进行比较，基本运算为X与数组元素的比较。2018/1/51611算法平均性态分析设被查项X在数组中出现的概率为Q，则查找次数TITII1IN时TIN,IN1时假设X在每个位置上出现的概率一样，则在每个位置上出现的概率为Q/N，不出现的概率为1Q，则平均查找次数为AN1Q/N2Q/N3Q/NNQ/NN1Q最坏情况为N2018/1/51711算法2算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。算法程序所占用的空间输入的初始数据所占的空间算法执行过程中所需的额外空间压缩存储技术2018/1/518课后习题选择算法的空间复杂度是指算法程序的长度算法程序中的指令条数算法程序所占的存储空间算法执行过程中所需要的存储空间2018/1/5192006年9月试题选择下列叙述中正确的是_。A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂度必定小D）上述三种说法都不对2018/1/52012数据结构的基本概念数据结构所研究的问题数据的逻辑结构数据集合中各数据元素之间所固有的逻辑关系数据的存储结构在对数据进行处理时，各数据元素在计算机中存储关系对各种数据结构进行的运算2018/1/52112数据结构的基本概念121什么是数据结构数据结构是指相互有关联的数据元素的集合。数据元素现实世界中客观存在的一切个体都可以是数据元素。2018/1/52212数据结构的基本概念例题3无序表的顺序查找与有序表的对分查找35167885432933215446162129333543465478852018/1/52312数据结构的基本概念例题4查看学生情况登记表中的学生成绩总表分类表分等次表2018/1/52412数据结构的基本概念1数据的逻辑结构数据元素的集合，记为DD上关系的集合，记为R数据结构表示为BD,R数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构2018/1/52512数据结构的基本概念例题5一年四季的数据结构可以表示为BD,RD春，夏，秋，冬R春，夏，夏，秋，秋，冬2018/1/52612数据结构的基本概念例题6家庭成员数据结构表示为BD,RD父亲，儿子，女儿R父亲，儿子，父亲，女儿2018/1/52712数据结构的基本概念例题7N维向量的数据结构XX1,X2,X3,XNDX1,X2,X3,XNRX1,X2,X2,X3,XN1,XN2018/1/52812数据结构的基本概念2数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。不仅要存储数据的信息，还要存储数据元素关系的信息。常用存储结构顺序、链接、索引2018/1/529课后习题选择数据的存储结构是指数据所占的存储空间量数据的逻辑结构在计算机中的表示数据在计算机中的顺序存储方式存储在外存中的数据2018/1/5302007年9月试题选择6下列叙述中正确的是A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对2018/1/5312007年4月试题选择1下列叙述中正确的是。A）算法的效率只与问题的规模有关,而与数据的存储结构无关B）算法的时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的D）算法的时间复杂度与空间复杂度一定相关2018/1/5322005年4月试题选择4下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率2018/1/53312数据结构的基本概念122数据的图形表示例题8用图形表示数据结构BD,RDDI|1I7D1,D2,D3,D4,D5,D6,D7RD1,D3,D1,D7,D2,D4,D4,D5,D3,D6D1D3D7D6D2D4D52018/1/53412数据结构的基本概念122数据的图形表示根结点终端结点数据结构的运算插入、删除、查找、分类、合并、分解、复制、修改2018/1/53512数据结构的基本概念123线性结构与非线性结构分类依据数据结构中各数据元素之间前后件关系的复杂程度线性结构的特点有且只有一个根结点每一个结点最多只有一个前件，也最多只有一个后件。在一个线性结构中插入或删除任何一个结点后还应是线性结构。2018/1/536课后习题选择下列叙述中正确的是线性表是线性结构栈和队列是非线性结构线性链表是非线性结构二叉树是线性结构2018/1/53713线性表及其顺序存储结构131线性表的基本概念线性表是由N（N0）个数据元素A1，A2，A3，AN组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件，即线性表或是一个空表，或可以表示为（A1，A2，AI，AN）2018/1/53813线性表及其顺序存储结构非空线性表的结构特征有且只有一个根结点，它无前件有且只有一个终端结点，它无后件除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件线性表的长度N0时为空表2018/1/53913线性表及其顺序存储结构132线性表的顺序存储结构线性表的顺序存储结构的特点线性表中所有元素所占的存储空间时连续的。线性表中各数据元素在存储空间中是按照逻辑顺序依次存放的。2018/1/54013线性表及其顺序存储结构线性表中元素地址ADRAIADRA1I1KADRA1第一个数据元素的存储地址每个元素占K个字节2018/1/54113线性表及其顺序存储结构线性表的主要运算线性表的插入线性表的删除线性表的查找线性表的排序线性表的分解线性表的合并线性表的复制线性表的逆转2018/1/54213线性表及其顺序存储结构133顺序表的插入运算例题9一个长度为8的线性表顺序存储在长度为10的存储空间中，现在要求在第二个元素18之前插入一个新元素872018/1/54313线性表及其顺序存储结构例题9V11018295663352431471234567891087V110123456789108747312435635618292018/1/54413线性表及其顺序存储结构例题91829566335148724314712345678910V110V11018875663352924314712345678910142018/1/54513线性表及其顺序存储结构线性表（A1，A2，AI，AN）在第I个元素AI前插入一个新元素B，得（A1，A2，AJ，AJ1，AN，AN1）则插入前后两线性表的关系AJ1JI1AJBJIAJ1I1JN12018/1/54613线性表及其顺序存储结构134顺序表的删除运算例题10长度为8的线性表顺序存储在长度为10的存储空间中，要求删除第一个元素。2018/1/54713线性表及其顺序存储结构例题10V110291856633524314712345678910V1101234567891018566335243147123456789101856633524472018/1/54813线性表及其顺序存储结构例题10AJ1JI1AJAJ1IJN1线性表插入与删除的效率很低2018/1/54914栈和队列141栈及其基本运算1什么是栈栈（STACK）是限定在一端进行插入与删除的线性表。栈顶栈底先进后出（FILO）后进先出TOPBOTTOM2018/1/550课后习题选择下列关于栈的叙述中正确的是在栈中只能插入数据在栈中只能删除数据栈是先进先出的线性表栈是先进后出的线性表2018/1/5512006年9月试题填空4按“先进后出”原则组织数据的数据结构是【4】。2018/1/5522006年4月试题选择4按照“后进先出”原则组织数据的数据结构是A）队列B）栈C）双向链表D）二叉树2018/1/55314栈和队列2栈的顺序存储及其运算入栈操作TOPBOTTOMABC2018/1/55414栈和队列2栈的顺序存储及其运算退栈操作TOPBOTTOMABCX2018/1/55514栈和队列思考题入栈顺序为A、B、C，出栈顺序有哪些CBAABCACBBACBCA不可能有的顺序CAB2018/1/55614栈和队列思考题入栈顺序为A、B、C、D，出栈顺序有哪些ABCDABDCACBDACDBADCBBACDBADCBCADBCDABDCACBADCBDACDBADCBA不可能有的情况DABCDACBDBCADBACDCABCABDCDABCADBBDACADBC2018/1/55714栈和队列2栈的顺序存储及其运算读栈顶操作TOPBOTTOMABCX2018/1/5582005年9月试题选择3下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素2018/1/5592005年4月试题选择3下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素2018/1/56014栈和队列142队列及其基本运算1什么是队列队列（QUEUE）是指允许在一端进行插入、而在另一端进行删除的线性表。尾指针（REAR）排头指针（FRONT）先进先出（FIFO）2018/1/561课后习题选择下列关于队列的叙述中正确的是在队列中只能插入数据在队列中只能删除数据队列是先进先出的线性表队列是先进后出的线性表2018/1/56214栈和队列142队列及其基本运算1什么是队列入队FRONTREARABCD2018/1/56314栈和队列142队列及其基本运算1什么是队列退队FRONTREARABCDX2018/1/56414栈和队列2循环队列及其运算将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。REARFRONT2018/1/56514栈和队列2循环队列及其运算REARFRONTABCDEF2018/1/56614栈和队列2循环队列及其运算FRONTREARABCD2018/1/56714栈和队列2循环队列及其运算队列空的条件REARFRONTREARFRONTMS02018/1/56814栈和队列2循环队列及其运算队列满的条件FRONTREARREARFRONTMS12018/1/569课后习题填空在一个容量为15的循环队列中，若头指针FRONT6，尾指针REAR9，则该循环队列共有_个元素。REARFRONT个数REARFRONT2018/1/570FRONTREAR个数REARMFRONT个数REARMFRONTMODM对应记忆表盘2018/1/5712005年9月试题填空5数据结构分为逻辑结构和存储结构，循环队列属于【5】结构。2018/1/57214栈和队列2循环队列及其运算入队操作REARFRONT非满才能入队2018/1/57314栈和队列2循环队列及其运算退队操作REARFRONT非空才能退队X2018/1/5742007年9月试题填空3线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_【3】_存储结构。线性表、队列、栈不提链式存储即默认顺序存储结构2018/1/5752007年4月试题选择5下列对列的叙述正确的是。A）队列属于非线性表B）队列按”先进后出”的原则组织数据C）队列在队尾删除数据D）队列按先进先出原则组织数据2018/1/5762006年4月试题选择5下列叙述中正确的是A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构C）双向链表是非线性结构D）只有根结点的二叉树是线性结构2018/1/57715线性链表151线性链表的基本概念线性表的顺序存储结构存在的缺点插入或删除过程需移动大量的元素存储空间不便于扩充计算机存储空间得不到充分利用，不便于对存储空间的动态分配链式存储的结点的结构数据域指针域2018/1/57815线性链表1线式链表12IM存储序号数据域指针域2018/1/57915线性链表VINEXTI数据域指针域数据1数据2数据NHEAD2018/1/58015线性链表VINEXTI12345678910A13HEADA2A4A3A5191050HEADA2A1A3A4A502018/1/58115线性链表双向链表HEADA1A2AN002018/1/58215线性链表2带链的栈用来收集计算机存储空间所有空闲的存储结点TOPA1A2A302018/1/58315线性链表3带链的队列A1A2A3FRONTREAR2018/1/5842006年9月试题填空5数据结构分为线性结构和非线性结构，带链的队列属于【5】2018/1/58515线性链表152线性链表的基本运算线性链表的插入线性链表的删除线性链表的合并线性链表的分解线性链表的逆转线性链表的复制线性链表的排序线性链表的查找2018/1/58615线性链表152线性链表的基本运算1在线性链表中查找指定元素2018/1/58715线性链表152线性链表的基本运算插入A1A3A2FRONTREARA42018/1/58815线性链表152线性链表的基本运算删除A1A3A2FRONTREAR2018/1/58915线性链表153循环链表及其基本运算循环链表的两个特点表头结点、指针域、头指针最后一个结点2018/1/59016树与二叉树161树的基本概念RKPQDBENOTCHXYSWZAMFGL2018/1/591课后习题选择10设树的度为，其中度为，的结点个数分别为，则中的叶子结点数为A8B7C6D52018/1/5922018/1/5932018/1/5942018/1/5952018/1/596度个数叶子1402213124131共个2018/1/59716树与二叉树有关名词根结点父结点子结点叶子结点度树的深度2018/1/59816树与二叉树运算符单目运算符双目运算符三目运算符多目运算符用树表示运算表达式的原则2018/1/59916树与二叉树162二叉树及其基本性质1什么是二叉树非空二叉树只有一个根结点每一个结点最多有两棵子树，且分别被称为该结点的左子树和右子树。2018/1/510016树与二叉树162二叉树及其基本性质1什么是二叉树ATXBCPZY2018/1/510116树与二叉树2二叉树的基本性质性质1在二叉树的第K层上，最多有2K1K1个结点。ABCFGDEHIJKLMNQ2018/1/51022005年9月试题填空4一棵二叉树第六层（根结点为第一层）的结点数最多为【4】个。2018/1/510316树与二叉树2二叉树的基本性质性质2深度为M的二叉树最多有2M1个结点。ABCFGDEHIJKLMNQ2018/1/510416树与二叉树2二叉树的基本性质性质3在任意一棵二叉树中，度为0的结点（即子结点）总是比度为2的结点多一个。N0N1N2NN12N2N1N0N212018/1/51052007年9月试题选择8一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为A）219B）221C）229D）2312018/1/51062007年4月试题选择7某二叉树中有N个度为2的结点则该二叉树中的叶子结点数为A）N1B）N1C）2ND）N/22018/1/510716树与二叉树2二叉树的基本性质性质4具有N个结点的二叉树，其深度至少为LOG2N1，其中LOG2N表示取LOG2N的整数部分。ABCGDEHJKN2018/1/510816树与二叉树3满二叉树与完全二叉树满二叉树ABCFGDEHIJKLMNQ2018/1/5109课后习题选择8在深度为的满二叉树中，叶子结点的个数为A32B31C16D152018/1/51102007年4月试题填空在深度为7的满二叉树中，度为2的结点个数为【1】。2018/1/51112006年4月试题选择7在深度为7的满二叉树中，叶子结点的个数为A）32B）31C）64D）632018/1/511216树与二叉树3满二叉树与完全二叉树完全二叉树ALBCFGDEHIJKMN2018/1/5113课后习题填空2设一棵完全二叉树共有700个结点，则在该二叉树中有_个叶子结点。N0N21结点数N0N1N2700N10或N11N0、N1、N2都是整数2018/1/511416树与二叉树3满二叉树与完全二叉树性质5具有N个结点的完全二叉树的深度为LOG2N1ALBCFGDEHIJKMN2018/1/511516树与二叉树3满二叉树与完全二叉树性质611223674589101113142018/1/511616树与二叉树163二叉树的存储结构链式存储164二叉树的遍历前序遍历ATXBCPZYTBZAXCPYTBZACYXPTZBACYXP2018/1/511716树与二叉树164二叉树的遍历中序遍历ATXBCPZYTBZAXCPYTBZACYXPTZBACYXP2018/1/51182007年9月试题填空4对下列二叉树进行中序遍历的结果为_【4】_。2018/1/511916树与二叉树164二叉树的遍历后序遍历ATXBCPZYTBZAXCPYTBZACYXPTZBACYXP2018/1/5120课后习题选择设有下列二叉树，对此二叉树中序遍历的结果为AABCDEFBDBEAFCCABDECFDDEBFCAABCDEF2018/1/5121课后习题填空设一棵二叉树的中序遍历为DBEAFC，前序遍历结果为ABDECF，则其后序遍历结果为ADBEFCBCDEFDEBFCABDECF2018/1/51222007年4月试题选择6对下列二叉树进行前序遍历的结果为A）DYBEAFCZXB）YDEBFZXCAC）ABDYECFXZD）ABCDEFXYZ2018/1/51232006年9月试题选择10对下列二叉树进行中序遍历的结果是_。A）ACBDFEGB）ACBDFGEC）ABDCGEFD）FCADBEG2018/1/51242006年4月试题选择6对如下二叉树行后序遍历的结果为A）ABCDEFB）DBEAFCC）ABDECFD）DEBFCAABCDEF2018/1/512517查找技术171顺序查找只能使用顺序查找的情况无序表有序表链式存储1、N/2、N172二分法查找只能在有序的顺序存储时使用1、LOG2N2018/1/5126课后习题选择9对长度为的线性表进行顺序查找，在最坏的情况下所需要的比较次数为AN1BNCN1/2DN/22018/1/5127课后习题填空在长度为的有序线性表中进行二分查找，需要的比较次数为LOG2N1LOG2N2018/1/51282006年9月试题选择在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。A）63B）64C）6D）72018/1/51292005年9月试题选择2下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序线性链表2018/1/51302005年4月试题选择下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序线性链表2018/1/513118排序技术181交换类排序法冒泡排序法从前向后扫描，同时逐次比较相邻两元素大小，若前大后小则互换位置，最大数到最后。从后向前扫描，逐次比较相邻两元素大小，若后小前大则互换，最小数到最前。重复过程至有序。517316942862018/1/513218排序技术181交换类排序法冒泡排序法51731694286131674269115326746891