计算机二级公共基础知识 (2)精选文档.ppt

计算机二级公共基础知识本讲稿第一页，共七十八页考试方式考试方式n公共基础知识占二十分左右。公共基础知识占二十分左右。n数据结构部分和软件工程部分是考核的重点，栈、队数据结构部分和软件工程部分是考核的重点，栈、队列、循环队列的特点、二叉树的遍历和求结点数需理列、循环队列的特点、二叉树的遍历和求结点数需理解掌握，其它部分以识记为主。解掌握，其它部分以识记为主。本讲稿第二页，共七十八页公共基础知识公共基础知识1 算法算法2 数据结构的基本概念数据结构的基本概念3 线性表及其顺序存储线性表及其顺序存储4 栈和队列栈和队列5 树与二叉树树与二叉树6 查找技术查找技术7 程序设计与软件工程程序设计与软件工程8 数据库设计数据库设计本讲稿第三页，共七十八页1 算法算法1、算法的概念、算法的概念n算法是指解题方案的准确而完整的描述。算法是指解题方案的准确而完整的描述。2、算法的特性、算法的特性n可行性、确定性、有穷性、有输入和输出可行性、确定性、有穷性、有输入和输出3、算法的时间复杂度、算法的时间复杂度n是指执行算法所需要的计算工作量，而是指执行算法所需要的计算工作量，而不是算法具体不是算法具体的执行时间的执行时间。4、算法的空间复杂度、算法的空间复杂度n指执行某个算法所需要的辅助内存空间。指执行某个算法所需要的辅助内存空间。本讲稿第四页，共七十八页二级真题二级真题1、问题处理方案的正确而完整的描述称为、问题处理方案的正确而完整的描述称为()。2、算法复杂度主要包括时间复杂度和、算法复杂度主要包括时间复杂度和()复杂度。复杂度。3、算法的有穷性是指、算法的有穷性是指()A)算法程序的运行时间是有限的算法程序的运行时间是有限的 B)算法程序所处理的数据量是有限的算法程序所处理的数据量是有限的 C)算法程序的长度是有限的算法程序的长度是有限的 D)算法只能被有限的用户使用算法只能被有限的用户使用4、算法的时间复杂度是指、算法的时间复杂度是指()A)算法的执行时间算法的执行时间 B)算法所处理的数据量算法所处理的数据量 C)算法程序中的语句或指令条数算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数算法在执行过程中所需要的基本运算次数算法算法空间空间AD本讲稿第五页，共七十八页二级真题二级真题5、下列叙述中正确的是、下列叙述中正确的是()A)一个算法的空间复杂度大，则其时间复杂度也必定大一个算法的空间复杂度大，则其时间复杂度也必定大B)一个算法的空间复杂度大，则其时间复杂度必定小一个算法的空间复杂度大，则其时间复杂度必定小C)一个算法的时间复杂度大，则其空间复杂度必定小一个算法的时间复杂度大，则其空间复杂度必定小D)上述三种说法都不对上述三种说法都不对6、算法的空间复杂度是指算法的空间复杂度是指()A)算法在执行过程中所需要的计算机存储空间算法在执行过程中所需要的计算机存储空间 B)算法所处理的数据量算法所处理的数据量C)算法程序中的语句或指令条数算法程序中的语句或指令条数 D)算法在执行过程中所需要的临时工作单元数算法在执行过程中所需要的临时工作单元数DA本讲稿第六页，共七十八页2 数据结构的基本概念数据结构的基本概念1、数据结构的概念、数据结构的概念n是指数据与数据之间的关系，包括逻辑结构和物理结构。是指数据与数据之间的关系，包括逻辑结构和物理结构。2、逻辑结构、逻辑结构n是指数据元素之间的逻辑关系，即数据元素之间的前后次序关系。是指数据元素之间的逻辑关系，即数据元素之间的前后次序关系。3、物理结构、物理结构n是数据在计算机存储空间中的存放形式。是数据在计算机存储空间中的存放形式。4、逻辑结构与物理结构的关系、逻辑结构与物理结构的关系n同一个逻辑结构可以用不同的物理结构来实现。同一个逻辑结构可以用不同的物理结构来实现。本讲稿第七页，共七十八页春春夏夏秋秋冬冬一年四季数据结构的图形表示一年四季数据结构的图形表示女儿女儿父亲父亲儿子儿子家庭成员间辈分关系数据结构的图形表示家庭成员间辈分关系数据结构的图形表示线线性性结结构构非非线线性性结结构构两类逻辑结构：两类逻辑结构：本讲稿第八页，共七十八页两类物理结构：两类物理结构：顺顺序序存存储储链链式式存存储储A1A2An-1AnHEAD数据数据1数据数据2数据数据nNULL数据域数据域指针域指针域数据元素存储在一片连续的数据元素存储在一片连续的区域中，按逻辑顺序依次存区域中，按逻辑顺序依次存储，找到第一个元素后按序储，找到第一个元素后按序即可找到其他的各个元素。即可找到其他的各个元素。数据元素存储分散，每一个元素（除了最数据元素存储分散，每一个元素（除了最后一个元素）均需记录下一个元素的存储后一个元素）均需记录下一个元素的存储位置（即指针，其中下一个元素所占用的位置（即指针，其中下一个元素所占用的存储空间可以在本存储空间可以在本元素之前也可以在本元元素之前也可以在本元素之后），使用这些指针来找到各个元素。素之后），使用这些指针来找到各个元素。本讲稿第九页，共七十八页二级真题二级真题1、数据的存储结构是指（、数据的存储结构是指（）。）。A）存储在外存中的数据）存储在外存中的数据B）数据所占的存储空间量）数据所占的存储空间量C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示2、下列对于线性链表的描述中正确的是（、下列对于线性链表的描述中正确的是（）。）。A）存储空间不一定连续，且各元素的存储顺序是任意的）存储空间不一定连续，且各元素的存储顺序是任意的B）存储空间不一定连续，且前件元素一定存储在后件元素的前面）存储空间不一定连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的）存储空间必须连续，且各元素的存储顺序是任意的DA本讲稿第十页，共七十八页二级真题二级真题3、下列描述中正确的是（、下列描述中正确的是（）。）。A）一个逻辑数据结构只能有一种存储结构）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率构影响数据处理的效率D本讲稿第十一页，共七十八页二级真题二级真题4、下列叙述中正确的是（下列叙述中正确的是（）。）。A)算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关5、下列叙述中正确的是（、下列叙述中正确的是（）。）。A)顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的续的B)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间BA本讲稿第十二页，共七十八页二级真题二级真题6、下列叙述中正确的是、下列叙述中正确的是()。A）数据的逻辑结构与存储结构必定是一一对应的）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此，数）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构据的存储结构一定是线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此，）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构利用数组只能处理线性结构 D）以上三种说法都不对）以上三种说法都不对 D本讲稿第十三页，共七十八页3 线性表及其顺序存储线性表及其顺序存储1、线性表的基本概念、线性表的基本概念n线性表是由线性表是由n(n0)个数据元素个数据元素a1,a2,an组成的一个有限序组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个列，表中的每一个数据元素，除了第一个外，有且只有一个前驱，除了最后一个外，有且只有一个后继。其中前驱，除了最后一个外，有且只有一个后继。其中ai（i=1,2,n）是属于数据对象的元素，通常也称其为线性表中的）是属于数据对象的元素，通常也称其为线性表中的一个结点。一个结点。2、顺序表的插入、顺序表的插入n在第在第i个元素之前插入一个新元素时，需要从最后一个元素开始个元素之前插入一个新元素时，需要从最后一个元素开始依次将依次将n-i+1个元素个元素向后向后移动一个位置。移动一个位置。3、顺序表的删除、顺序表的删除n删除第删除第i个元素时，需要将从第个元素时，需要将从第i+1个元素开始，直至第个元素开始，直至第n个个元素之间的元素之间的n-i个元素依次个元素依次向前向前移动一个位置。移动一个位置。本讲稿第十四页，共七十八页栈：限定栈：限定只能在一端只能在一端进行插入和删除运算的进行插入和删除运算的线性表线性表AnA2A1栈底栈底 bottom 栈顶栈顶 top入栈入栈退栈退栈入栈：入栈：将栈顶指针加将栈顶指针加1将新元素插入到栈顶指针指将新元素插入到栈顶指针指向的位置向的位置退栈：退栈：将栈顶元素赋给一个指定的将栈顶元素赋给一个指定的变量变量将栈顶指针减将栈顶指针减14栈和队列栈和队列栈按照栈按照先进后出先进后出的顺序组织数据！的顺序组织数据！本讲稿第十五页，共七十八页队列：限定在一端进行插入，在队列：限定在一端进行插入，在另另一端一端进行删除的进行删除的线性表线性表ABCD头指针头指针front尾指针尾指针rear一个队列一个队列4栈和队列栈和队列队列按照队列按照先进先出先进先出的顺序组织数据！的顺序组织数据！循环队列：将队列臆造成为一个环状循环队列：将队列臆造成为一个环状的空间，头、尾指针和队列元素之间的空间，头、尾指针和队列元素之间的关系不变。当头、尾指针指向相同的关系不变。当头、尾指针指向相同位置时表示队列为空或为满两种状态位置时表示队列为空或为满两种状态。本讲稿第十六页，共七十八页二级真题二级真题1、下列关于栈的描述中错误的是（、下列关于栈的描述中错误的是（）。）。A)栈是先进后出的线性表栈是先进后出的线性表B)栈只能顺序存储栈只能顺序存储C)栈具有记忆作用栈具有记忆作用D)对栈的插入与删除操作中，不需要改变栈底指针对栈的插入与删除操作中，不需要改变栈底指针 2、下列关于栈的描述中正确的是（、下列关于栈的描述中正确的是（）。）。A)在栈中只能插入元素而不能删除元素在栈中只能插入元素而不能删除元素B)在栈中只能删除元素而不能插入元素在栈中只能删除元素而不能插入元素C)栈是特殊的线性表，只能在一端插入或删除元素栈是特殊的线性表，只能在一端插入或删除元素D)栈是特殊的线性表，只能在一端插入元素，而在另一端删栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素除元素BC本讲稿第十七页，共七十八页二级真题二级真题3、按照、按照“后进先出后进先出”原则组织数据的数据结构是（原则组织数据的数据结构是（）。）。A)队列队列 B)栈栈 C)双向链表双向链表 D)二叉树二叉树4、下列数据结构中、下列数据结构中,能够按照能够按照”先进后出先进后出”原则存取数据的是（原则存取数据的是（）。）。A)循环队列循环队列 B)栈栈 C)队列队列 D)二叉树二叉树5、支持子程序调用的数据结构是（、支持子程序调用的数据结构是（）。）。A)栈栈 B)树树 C)队列队列 D)二叉树二叉树6、下列关于栈的叙述正确的是（、下列关于栈的叙述正确的是（）。）。A)栈按栈按“先进先出先进先出”组织数据组织数据 B)栈按栈按“先进后出先进后出”组织数据组织数据 C)只能在栈底插入数据只能在栈底插入数据 D)不能删除数据不能删除数据BBAB本讲稿第十八页，共七十八页二级真题二级真题7、一个栈的初始状态为空。现将元素、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（依次入栈，然后再依次出栈，则元素出栈的顺序是（）。）。A）12345ABCDE B）EDCBA54321C）ABCDE12345 D）54321EDCBA8、下列对队列的叙述正确的是（、下列对队列的叙述正确的是（）。）。A)队列属于非线性表队列属于非线性表 B)队列按队列按“先进后出先进后出”原则组织数据原则组织数据C)队列在队尾删除数据队列在队尾删除数据D)队列按队列按“先进先出先进先出”原则组织数据原则组织数据BD本讲稿第十九页，共七十八页二级真题二级真题9、下列叙述中正确的是（、下列叙述中正确的是（）。）。A)栈是栈是“先进先出先进先出”的线性表的线性表B)队列是队列是“先进后出先进后出”的线性表的线性表C)循环队列是非线性结构循环队列是非线性结构D)有序线性表既可以采用顺序存储结构，也可以采用链式有序线性表既可以采用顺序存储结构，也可以采用链式存储结构存储结构10、对于循环队列、对于循环队列,下列叙述中正确的是（下列叙述中正确的是（）。）。A)队头指针是固定不变的队头指针是固定不变的B)队头指针一定大于队尾指针队头指针一定大于队尾指针C)队头指针一定小于队尾指针队头指针一定小于队尾指针D)队头指针可以大于队尾指针，也可以小于队尾指针队头指针可以大于队尾指针，也可以小于队尾指针DD本讲稿第二十页，共七十八页二级真题二级真题11、下列叙述中正确的是（、下列叙述中正确的是（）。）。A）循环队列有队头和队尾两个指针，因此，循环队列是非）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构线性结构B）在循环队列中，只需要队头指针就能反映队列的中元）在循环队列中，只需要队头指针就能反映队列的中元素的动态变化情况素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列的中元素）在循环队列中，只需要队尾指针就能反映队列的中元素的动态变化情况的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同）循环队列中元素的个数是由队头指针和队尾指针共同决定决定D本讲稿第二十一页，共七十八页二级真题二级真题12、假设用一个长度为、假设用一个长度为50的数组（数组元素的下标从的数组（数组元素的下标从0到到49.作作为栈的存储空间，栈底指针为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针指向栈底元素，栈顶指针top指向栈顶元素，如果指向栈顶元素，如果bottom=49，top=30（数组下标）（数组下标），则栈中具有，则栈中具有()个元素。个元素。13、数据结构分为逻辑结构和存储结构，循环队列属于、数据结构分为逻辑结构和存储结构，循环队列属于()结构。结构。14、数据结构分为线性结构和非线性结构，带链的队列属于、数据结构分为线性结构和非线性结构，带链的队列属于()。15、线性表的存储结构主要分为顺序存储结构和链式存储结构。队列、线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的是一种特殊的线性表，循环队列是队列的()。20存储结构存储结构线性结构线性结构存储结构存储结构本讲稿第二十二页，共七十八页二级真题二级真题16、按、按“先进后出先进后出”原则组织数据的数据结构是原则组织数据的数据结构是()。17、设某循环队列的容量为、设某循环队列的容量为50，头指针，头指针front=5(指向队头元素的指向队头元素的前一位置前一位置)，尾指针，尾指针rear=29(指向对尾元素指向对尾元素)，则该循环队列中，则该循环队列中共有共有()个元素。个元素。18、一个队列的初始状态为空。现将元素、一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元依次入队，然后再依次退队，则元素退队的顺序为素退队的顺序为()。19、设某循环队列的容量为、设某循环队列的容量为50，如果头指针，如果头指针front=45(指向队指向队头元素的前一位置头元素的前一位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该，则该循环队列中共有循环队列中共有()个元素。个元素。栈栈24A,B,C,D,E,F,5,4,3,2,115本讲稿第二十三页，共七十八页5 树与二叉树树与二叉树1 1、树、树n树是一种树是一种非线性结构非线性结构。n树中每一个结点都有一个唯一的前驱，称为该结点的树中每一个结点都有一个唯一的前驱，称为该结点的父节点父节点（双亲结点双亲结点）。）。n没有前驱的结点没有前驱的结点(只有一个只有一个)称为树的称为树的根结点根结点。n每一个结点都可以有多个后继，称为该结点的每一个结点都可以有多个后继，称为该结点的孩子结点孩子结点。n没有后继的结点称为没有后继的结点称为叶子结点叶子结点。n一个结点拥有后继结点的个数称为该一个结点拥有后继结点的个数称为该结点的度结点的度,度数为零的结度数为零的结点就是叶子点就是叶子.所有结点的最大度数称为所有结点的最大度数称为树的度树的度。n层次层次:树的根结点在第一层树的根结点在第一层,它的子结点为第二层它的子结点为第二层.n树的最大层次称为树的最大层次称为树的深度树的深度本讲稿第二十四页，共七十八页ABCDEFGHIJKLM结点结点A的度：的度：结点结点B的度：的度：结点结点M的度：的度：叶子：叶子：结点结点A的孩子：的孩子：结点结点B的孩子：的孩子：结点结点I的双亲：的双亲：结点结点L的双亲：的双亲：树的度：树的度：结点结点A的层次：的层次：结点结点M的层次的层次:树的深度：树的深度：5 树与二叉树树与二叉树根节点：根节点：AK，L，F，G，M，I，J3203DEB，C，DE，F144本讲稿第二十五页，共七十八页二叉树：二叉树：（1）非空二叉树只有一个根结点）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树，且分别称为该结点的左子）每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树树和右子树DATXBCYZP只有一个根结点的二叉树只有一个根结点的二叉树深度为深度为4的二叉树的二叉树5 树与二叉树树与二叉树本讲稿第二十六页，共七十八页 二叉树的二叉树的基本形态基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空5 树与二叉树树与二叉树本讲稿第二十七页，共七十八页5 树与二叉树树与二叉树二叉树的基本性质二叉树的基本性质性质性质1 1：在二叉树第在二叉树第k k层上，最多有层上，最多有2 2k-1k-1个结点。个结点。性质性质2 2：深度为深度为m m的二叉树最多有的二叉树最多有2 2m m-1-1个结点。个结点。性质性质3 3：任意一个二叉树中，任意一个二叉树中，度为度为0 0的结点总的结点总比比 度为度为2 2的结点的结点多一个多一个。性质性质4 4：具有具有n n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为loglog2 2n+1n+1,其其中中loglog2 2nn表示取表示取loglog2 2n n整数部分。整数部分。本讲稿第二十八页，共七十八页满二叉树满二叉树 除最后一层外，每一层的结点都有两个子结点。即每一层的除最后一层外，每一层的结点都有两个子结点。即每一层的结点都达到最大值，即在满二叉树的第结点都达到最大值，即在满二叉树的第k k层上有层上有2 2k-1k-1个结点。个结点。完全二叉树完全二叉树 除最后一层外，每一层的结点数均达到最大值，即在除最后一层外，每一层的结点数均达到最大值，即在最后一层只能缺少右边的若干结点。最后一层只能缺少右边的若干结点。5 树与二叉树树与二叉树本讲稿第二十九页，共七十八页ABCABCDEFGABCDEFABCDEABCD满满二二叉叉树树完完全全二二叉叉树树深度为深度为2的满二叉树的满二叉树深度为深度为3的满二叉树的满二叉树深度为深度为3的完全二叉树的完全二叉树本讲稿第三十页，共七十八页前序（先根）遍历：根、左、右前序（先根）遍历：根、左、右中序（中根）遍历：左、根、右中序（中根）遍历：左、根、右后序（后跟）遍历：左、右、根后序（后跟）遍历：左、右、根ABCDEFGH二叉树的遍历：二叉树的遍历：5 树与二叉树树与二叉树前序遍历：前序遍历：中序遍历：中序遍历：后序遍历：后序遍历：A BDFGCEHFDGB A C H EFGDBHECA本讲稿第三十一页，共七十八页二级真题二级真题1、某二叉树中度为、某二叉树中度为2的结点有的结点有18个，则该二叉树中有（个，则该二叉树中有（）个）个叶子结点。叶子结点。2、一棵二叉树第六层（根结点为第一层）的结点数最多为（、一棵二叉树第六层（根结点为第一层）的结点数最多为（）个。）个。3、在深度为、在深度为7的满二叉树中，叶子结点的个数为（的满二叉树中，叶子结点的个数为（）。4、深度为、深度为5的满二叉树有（的满二叉树有（）个叶子结点。）个叶子结点。5、某二叉树有、某二叉树有5个度为个度为2的结点以及的结点以及3个度为个度为1的结点，则该的结点，则该二叉树中共有（二叉树中共有（）个结点。）个结点。6、在深度为在深度为7的满二叉树中，度为的满二叉树中，度为2的结点个数为（的结点个数为（）。）。7、某二叉树有、某二叉树有5个度为个度为2的结点，则该二叉树中的叶子结点的结点，则该二叉树中的叶子结点数是（数是（）。）。A.10 B.8 C.6 D.4193264161463C本讲稿第三十二页，共七十八页二级真题二级真题8、某二叉树中有、某二叉树中有n个度为个度为2的结点，则该二叉树中的叶子结的结点，则该二叉树中的叶子结点数为（点数为（）。）。A)n+1 B)n-1 C)2n D)n/29、一棵二叉树中共有、一棵二叉树中共有70个叶子结点与个叶子结点与80个度为个度为1的结点，则该的结点，则该二叉树中的总结点数为（二叉树中的总结点数为（）。）。A)219 B)221 C)229 D)23110、下列描述中正确的是（、下列描述中正确的是（）。）。A)线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构 B)栈与队列是非线性结构栈与队列是非线性结构 C)双向链表是非线性结构双向链表是非线性结构 D)只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构11、下列数据结构中，属于非线性结构的是（、下列数据结构中，属于非线性结构的是（）。）。A)循环队列循环队列 B)带链队列带链队列 C)二叉树二叉树 D)带链栈带链栈AAAC本讲稿第三十三页，共七十八页二级真题二级真题12、对下列二叉树进行中序遍历的结果是（、对下列二叉树进行中序遍历的结果是（）。）。A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEGA本讲稿第三十四页，共七十八页13、对如下二叉树进行后序遍历的结果为（、对如下二叉树进行后序遍历的结果为（）。）。A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA二级真题二级真题D本讲稿第三十五页，共七十八页n对如下二叉树进行前序遍历的结果为（对如下二叉树进行前序遍历的结果为（）。）。A)DYBEAFCZX B)YDEBFZXCA C)ABDYECFXZ D)ABCDEFXYZ 二级真题二级真题C本讲稿第三十六页，共七十八页n对下列二叉树进行中序遍历的结果对下列二叉树进行中序遍历的结果()。二级真题二级真题DBXEAYFZC 本讲稿第三十七页，共七十八页n设二叉树如下，对该二叉树进行后序遍历的结果为设二叉树如下，对该二叉树进行后序遍历的结果为()。二级真题二级真题EDBGHFCA本讲稿第三十八页，共七十八页查找技术查找技术:1.顺序查找：最坏情况下，需要比较顺序查找：最坏情况下，需要比较n次次2.二分法查找（二分法查找（只适用顺序存储的有序表只适用顺序存储的有序表）：最坏情况下，需要比）：最坏情况下，需要比较较log2n次次排序技术排序技术:1.冒泡排序法：最坏情况下，需要比较冒泡排序法：最坏情况下，需要比较n(n-1)/2次次2.简单插入排序法：最坏情况下，需要比较简单插入排序法：最坏情况下，需要比较n(n-1)/2次次3.简单选择排序法：最坏情况下，需要比较简单选择排序法：最坏情况下，需要比较n(n-1)/2次次4.快速排序法：最坏情况下，需要比较快速排序法：最坏情况下，需要比较n(n-1)/2次次5.堆排序法：最坏情况下，需要比较堆排序法：最坏情况下，需要比较nlog2n次次6.希尔排序法：最坏情况下，需要比较希尔排序法：最坏情况下，需要比较n1.5次次6查找技术查找技术本讲稿第三十九页，共七十八页1 1、下列数据结构中，能用二分法进行查找的是（、下列数据结构中，能用二分法进行查找的是（）。）。A）顺序存储的有序线性表）顺序存储的有序线性表 B）线性链表）线性链表C）二叉链表）二叉链表 D）有序线性链表）有序线性链表2 2、对于长度为、对于长度为n n的线性表，在最坏的情况下，下列各排序法所对应的的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是比较次数中正确的是（）。）。A)A)冒泡排序为冒泡排序为n/2 B)n/2 B)冒泡排序为冒泡排序为n nC)C)快速排序为快速排序为n D)n D)快速排序为快速排序为n(n-1)/2n(n-1)/23 3、对于长度为、对于长度为n n的线性表进行顺序查找，在最坏情况下所需要的比较次数为的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。）。A)log2n B)n/2 C)n D)n+1A)log2n B)n/2 C)n D)n+1二级真题二级真题ADC本讲稿第四十页，共七十八页二级真题二级真题4、在长度为、在长度为n的有序线性表中进行二分查找，最坏情况下需要比的有序线性表中进行二分查找，最坏情况下需要比较的次数是（较的次数是（）。）。A）O(n)B）O(n2)C）O(log2n)D）O(nlog2n)5、对长度为、对长度为10的线性表进行冒泡排序，最坏情况下需要比的线性表进行冒泡排序，最坏情况下需要比较的次数为（较的次数为（）。）。6、在长度为、在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的有序线性表中进行顺序查找，最坏情况下需要比较的次数为（的次数为（）。）。A)63 B)64 C)6 D)7 7、冒泡排序在最坏情况下的比较次数是（、冒泡排序在最坏情况下的比较次数是（）。）。A）（）（n1）/2 B）nlog2 n C）n（n1）/2 D）/2 C45BC本讲稿第四十一页，共七十八页二级真题二级真题8、对长度为、对长度为n的线性表排序，在最坏情况下，比较次数不是的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是（的排序方法是（）。）。A）快速排序）快速排序 B）冒泡排序）冒泡排序 C）直线插入排序）直线插入排序 D）堆排序）堆排序9、下列排序方法中，最坏情况下比较次数最少的是（、下列排序方法中，最坏情况下比较次数最少的是（）。）。A）冒泡排序）冒泡排序 B）简单选择排序）简单选择排序 C）直接插入排序）直接插入排序 D）堆排序）堆排序 DD本讲稿第四十二页，共七十八页二级真题二级真题10、下列叙述中正确的是、下列叙述中正确的是（）。）。A)对长度为对长度为n的有序链表进行查找，最坏情况下需要的的有序链表进行查找，最坏情况下需要的比较次数为比较次数为nB)对长度为对长度为n的有序链表进行对分查找，最坏情况下需要的有序链表进行对分查找，最坏情况下需要的比较次数为的比较次数为(n/2)C)对长度为对长度为n的有序链表进行对分查找，最坏情况下需要的有序链表进行对分查找，最坏情况下需要的比较次数为的比较次数为(log2n)D)对长度为对长度为n的有序链表进行对分查找，最坏情况下需要的比的有序链表进行对分查找，最坏情况下需要的比较次数为较次数为(n log2n)A本讲稿第四十三页，共七十八页1、结构化程序设计的原则：、结构化程序设计的原则：（1）源程序文档化。）源程序文档化。（2）数据说明的次序文档化。）数据说明的次序文档化。（3）程序编写要做到）程序编写要做到清晰第一，效率第二清晰第一，效率第二，要模块，要模块 化，并使模块功能尽可能单一。化，并使模块功能尽可能单一。（4）避免不必要的转移（避免）避免不必要的转移（避免goto语句的使用）。语句的使用）。（5）在结构化程序设计中仅使用）在结构化程序设计中仅使用顺序、选择和循环（重复）顺序、选择和循环（重复）三种三种基本控制结构。基本控制结构。（6）总体原则：）总体原则：自顶向下、模块化、逐步求精自顶向下、模块化、逐步求精7 程序设计与软件工程程序设计与软件工程本讲稿第四十四页，共七十八页7 程序设计与软件工程程序设计与软件工程2、面向对象程序设计：、面向对象程序设计：（1）基本概念：）基本概念：类：具有共同属性、共同方法的对象的集合，是对象的抽象。类：具有共同属性、共同方法的对象的集合，是对象的抽象。对象：是类的一个实例。对象：是类的一个实例。（2）面向对象的特点：）面向对象的特点：标识唯一性，分类性，封装，继承，标识唯一性，分类性，封装，继承，多态性多态性本讲稿第四十五页，共七十八页3 3、软件工程、软件工程 （1 1）软件是）软件是程序、数据及相关文档的集合。程序、数据及相关文档的集合。（2 2）软件按功能可以分为：应用软件、系统软件和支撑软）软件按功能可以分为：应用软件、系统软件和支撑软件（或工具软件）。件（或工具软件）。（3 3）软件工程的三要素包括：）软件工程的三要素包括：方法、工具和过程方法、工具和过程，其中，方，其中，方法是完成软件工程项目的技术手段；工具支持软件开发、法是完成软件工程项目的技术手段；工具支持软件开发、管理和文档的生产；管理和文档的生产；过程过程支持软件开发的各个环节的控制和管支持软件开发的各个环节的控制和管理。理。7 程序设计与软件工程程序设计与软件工程本讲稿第四十六页，共七十八页可行性研究可行性研究初步项目计划初步项目计划需求分析需求分析概要设计概要设计详细设计详细设计测试测试实现实现使用使用维护维护退役退役定义阶段定义阶段开发阶段开发阶段维护阶段维护阶段软软件件生生命命周周期期编写软件需求规格编写软件需求规格说明书说明书为发现错误而执行程序为发现错误而执行程序尽量做到尽量做到高内聚，低耦合高内聚，低耦合本讲稿第四十七页，共七十八页4、补充：、补充：（1 1）需求分析阶段的工具需求分析阶段的工具数据流图数据流图DFDDFD。（2 2）在数据流图中，椭圆表示加工，）在数据流图中，椭圆表示加工，带有箭头的带有箭头的线段表示数据流。线段表示数据流。（3 3）数据字典（）数据字典（DDDD）：是对数据流图中所有元素的）：是对数据流图中所有元素的定义的集合，是结构化分析的核心。定义的集合，是结构化分析的核心。（4 4）DDDD和和DFDDFD共同构成系统的逻辑模型。共同构成系统的逻辑模型。7 程序设计与软件工程程序设计与软件工程本讲稿第四十八页，共七十八页5、结构化设计、结构化设计（1）在过程设计中尽量做到）在过程设计中尽量做到高内聚、低耦合。高内聚、低耦合。（2）软件设计分类：）软件设计分类：n从技术观点：软件结构设计、数据设计、接口设计、过程设计从技术观点：软件结构设计、数据设计、接口设计、过程设计n从工程角度：概要设计、详细设计从工程角度：概要设计、详细设计（3）在结构化设计过程中，常见的过程）在结构化设计过程中，常见的过程设计工具有：设计工具有：n图形工具：程序流程图、图形工具：程序流程图、N-S、PAD、HIPO。n表格工具：判定表。表格工具：判定表。n语言工具：语言工具：PDL（伪码）（伪码）7 程序设计与软件工程程序设计与软件工程用带箭头的线段表示控制流用带箭头的线段表示控制流本讲稿第四十九页，共七十八页6、软件测试、软件测试（1 1）软件测试的目的是尽可能的）软件测试的目的是尽可能的发现发现软件设计过程中的错误软件设计过程中的错误而不是改而不是改正错误正错误。程序员应避免检查自己的程序。程序员应避免检查自己的程序。（2 2）软件测试与调试不同！软件测试与调试不同！调试是用来调试是用来诊断和改正程序错误，一般由程诊断和改正程序错误，一般由程序员来完成。序员来完成。（3 3）测试方法：）测试方法：n白盒测试白盒测试：所测试的每条路径至少执行一次。：所测试的每条路径至少执行一次。n黑盒测试黑盒测试：对功能是否满足需求进行测试和验证。：对功能是否满足需求进行测试和验证。（4 4）软件测试的过程一般按四个步骤进行，即软件测试的过程一般按四个步骤进行，即单元测试、集成测试、单元测试、集成测试、验收测试和系统测试验收测试和系统测试。n单元测试是对模块进行正确性检验。单元测试是对模块进行正确性检验。7 程序设计与软件工程程序设计与软件工程本讲稿第五十页，共七十八页7 程序设计与软件工程程序设计与软件工程7、软件维护、软件维护n软件维护是软件生命周期中的最后一个阶段，从软件交付软件维护是软件生命周期中的最后一个阶段，从软件交付使用开始到软件不再使用为止。使用开始到软件不再使用为止。n软件维护主要做的工作有改正程序错误、适应环境变化修软件维护主要做的工作有改正程序错误、适应环境变化修改软件、完善软件的功能。改软件、完善软件的功能。本讲稿第五十一页，共七十八页二级真题二级真题1、符合结构化原则的三种基本控制结构是：选择结构、循环结、符合结构化原则的三种基本控制结构是：选择结构、循环结构和（构和（）。）。2、软件是（、软件是（）、数据和文档的集合。、数据和文档的集合。3、下列描述中正确的是（、下列描述中正确的是（）。）。A）程序就是软件）程序就是软件B）软件开发不受计算机系统的限制）软件开发不受计算机系统的限制C）软件既是逻辑实体，又是物理实体）软件既是逻辑实体，又是物理实体D）软件是程序、数据与相关文档的集合）软件是程序、数据与相关文档的集合 顺序结构顺序结构程序程序D本讲稿第五十二页，共七十八页二级真题二级真题4、软件是指（）、软件是指（）A）程序）程序 B）程序和文档）程序和文档 C）算法加数据结构）算法加数据结构 D）程序、数据与相关文档的完整集合）程序、数据与相关文档的完整集合 5、下列叙述中，不符合良好程序设计风格要求的是（、下列叙述中，不符合良好程序设计风格要求的是（）A）程序的效率第一，）程序的效率第一，清晰第二清晰第二 B）程序的可读性好）程序的可读性好 C）程序中要有必要的注释）程序中要有必要的注释 D）输入数据前要有提示信息）输入数据前要有提示信息DA本讲稿第五十三页，共七十八页二级真题二级真题6、下列叙述中正确的是（）。、下列叙述中正确的是（）。A）程序执行的效率与数据的存储结构密切相关）程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量）程序执行的效率只取决于所处理的数据量 D）以上三种说法都不对）以上三种说法都不对7、下列关于软件工程的描述中正确的是（、下列关于软件工程的描述中正确的是（）。）。A）软件工程只是解决软件项目的管理问题）软件工程只是解决软件项目的管理问题 B）软件工程主要解决软件产品的生产率问题）软件工程主要解决软件产品的生产率问题 C）软件工程的主要思想是强调在软件开发过程中需要应）软件工程的主要思想是强调在软件开发过程中