《二级等级考试公共基础知识4讲解材料》由会员分享，可在线阅读，更多相关《二级等级考试公共基础知识4讲解材料（102页珍藏版）》请在金锄头文库上搜索。
1、1数据结构与算法数据结构与算法程序设计基础程序设计基础软件工程基础软件工程基础数据库基础知识数据库基础知识2第第 11章章 数据结构与算法数据结构与算法一、一、 算法的基本概念算法的基本概念二、二、 线形结构与非线形结构、栈和对列的定义线形结构与非线形结构、栈和对列的定义三、三、 二叉树的定义二叉树的定义四、四、 查找技术与排序技术查找技术与排序技术3例1：在下列选项中，不是一个算法一般应该具有的基本特征的是_。（5-1）(A)确定性(B)可行性(C)无穷性(D)拥有足够的情报例2：算法的时间复杂度是指_。（2-1）(A)执行算法程序所需的时间(B)算法程序的长度(C)算法执行过程中所需要的基
2、本运算次数(D)算法程序中的指令条数例3：算法的空间复杂度是指_。（3-1）(A)算法程序的长度(B)算法程序中的指令条数(C)算法程序所占的存储空间(D)算法执行过程中所需要的存储空间5例4：下面叙述正确的是_。（1-1）(A)算法的执行效率与数据的存储结构无关(B)算法的空间复杂度是指算法程序中指令（或语句）的条数(C)算法的有穷性是指算法必须能在执行有限个步骤之后终止(D)算法的时间复杂度是指执行算法程序所需要的时间例5：在计算机中，算法是指_。（6-1）(A)查询方法(B)加工方法(C)解题方案的准确而完整的描述(D)排序方法例6：算法分析的目的是_。（8-1）(A)找出数据结构的合理
3、性(B)找出算法中输入和输出之间的关系(C)分析算法的易懂性和可靠性(D)分析算法的效率以求改进6（7）下列叙述中正确的是_。(069)A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂度必定小D）上述三种说法都不对7例9：算法的基本特征是可行性、确定性、_和拥有足够的情报。（7-1）例7：算法的复杂度主要包括时间复杂度和_复杂度。（1-1）空间例8：实现算法所需的存储单元多少和算法的工作量大小分别称为算法的_。（6-1）空间复杂度和时间复杂有穷性（5）问题处理方案的正确而完整的描述称为【5】。(054)
4、算法8二、线形结构与非线形结构、栈和对列的定义（1）数据结构的基本概念数据结构主要研究和讨论以下三个方面的问题：数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。在对数据进行处理时，各数据元素在计算机中的存储存储关系，即数据的存储结构。 对各种数据结构进行的运算。9（2）根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线形结构与非线形结构。如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线形结构，又称线形表。所以线形表、栈与队列、线形链表都是线形结构，而二叉树是非线形结构。10（3）栈
5、是一种特殊的线性表：只能在固定的一端进行插入和删除操作，后进先出表。（4）队列可看作是插入在一端（队尾）进行，删除在另一端（队头）进行的线性表，先进先出表。（5）线性单链表、双向链表与循环链表的结构及其基本运算：在链表的运算过程中，采用链接方式即循环链表的结构把空表与非空表的运算统一起来。11（6）循环链表具有两个特点：在循环链表中增加了一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。循环链表中最后一个结点的指针不是空，而是指向表头结点。（7）数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式。12例：以下数据结构属于非线
6、性数据结构的是_。（1-2）(A)队列(B)线性表(C)二叉树(D)栈例：下列叙述中正确的是_。（2-2）(A)线形表是线形结构(B)栈与队列是非线形结构(C)线形链表是非线形结构(D)二叉树是线形结构例：下列关于栈的叙述中正确的是_。（3-2）(A)在栈中只能插入数据(B)在栈中只能删除数据(C)栈是先进先出的线性表(D)栈是先进后出的线性表例：下列关于队列的叙述中正确的是_。（5-3）(A)在队列中只能插入数据(B)在队列中只能删除数据(C)队列是先进先出的线性表(D)队列是先进后出的线性表13例：栈和队列的共同点是_。（6-2）(A)都是先进后出(B)都是先进后出(C)只允许在端点处插入
7、和删除元素(D)没有共同点例：栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。（7-2）(A)ABCED(B)DBCEA(C)CDABE(D)DCBEA例：用链表表示线性表的优点是_。（8-4）(A)便于插入和删除操作(B)数据元素的物理顺序与逻辑顺序相同(C)花费的存储空间较顺序存储少(D)便于随机存取14例：线性表的顺序存储结构和线性表的链式存储结构分别是_。（7-3）(A)顺序存取的存储结构、顺序存取的存储结构(B)随机存取的存储结构、顺序存取的存储结构(C)随机存取的存储结构、随机存取的存储结构(D)任意存取的存储结构、任意存取的存储结
8、构例：在单链表中，增加头结点的目的是_。（7-4）(A)方便运算的实现(B)使单链表至少有一个结点(C)标识表结点中首结点的位置(D)说明单链表是线性表的链式存储实现15例：数据的存储结构是指_。（4-2）(054)(A)数据所占的存储空间量(B)数据的逻辑结构在计算机中的表示(C)数据在计算机中的顺序存储方式(D)存储在外存中的数据例：数据结构中，与所使用的计算机无关的是数据的_。（7-1）(A)存储结构(B)物理结构(C)逻辑结构(D)物理和存储结构（2）下列关于栈的描述中错误的是_。(054)A)栈是先进后出的线性表B)栈只能顺序存储C)栈具有记忆作用 D)对栈的插入与删除操作中，不需要
9、改变栈底指针16例：在运算过程中，能够使空表与非空表的运算统一的结构是_。（4-1）例：栈的基本运算有三种：入栈、退栈和_。（5-1）读栈顶元素循环链表 例：数据结构包括数据的逻辑结构、数据的_以及对数据的操作运算。（6-2）例：顺序存储方法是把逻辑上相邻的结点存储在物理位置_存储单元。（7-2）存储结构相邻例：数据结构包括数据的逻辑结构、数据的_以及对数据的操作运算。（6-2）存储结构17（5）数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为【5】。(064)逻辑独立性 （4）下列叙述中正确的是(059) A）一个逻
10、辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率（4）按“先进后出”原则组织数据的数据结构是【4】。(069)栈（5）数据结构分为线性结构和非线性结构，带链的队列属于【5】(069)线性结构18三、二叉树的定义（1）满二叉树指除最后一层外每一层上所有结点都有两个子结点的二叉树。（2）完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干子结点（叶子结点）的二叉树。由定义可知，满二叉
11、树肯定是完全二叉树，而完全二叉树一般不是满二叉树。（3）具有n个结点的完全二叉树，其父结点数为int(n/2)，而叶子结点数等于总结点数减去父结点数。19（4）二叉树第i（i1）层上至多有2i-1个结点。（5）二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先根结点左子树右子树。中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先左子树根结点右子树。 20后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先左子树右子树根结点。21例
12、：在一棵二叉树上第8层的结点数最多的是_。（1-3）(A)8(B)16(C)128(D)256例：在深度为5的满二叉树中，叶子结点的个数为_。（3-3）(A)32(B)31(C)16(D)15例：下面关于完全二叉树的叙述中，错误的是_。（2-3）(A)除了最后一层外，每一层的结点数均达到最大值(B)可能缺少若干个左右叶子结点(C)完全二叉树一般不是满二叉树(D)具有结点的完全二叉树的深度为log2n+122例：对对下列二叉树树中中序遍历历的结结果是_。（4-3） BACDEF(A) ABCDEF (B) DBEAFC (C) ABDECF (D) DEBFCA23（10）对下列二叉树进行中序遍
13、历的结果是_。(069)A）ACBDFEGB）ACBDFGEC）ABDCGEFD）FCADBEG24例：在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、_遍历和后序遍历。（2-1）中序例：设一棵完全二叉树共有500个结点，则在该二叉树中有_个叶子结点。（3-1）25025（4）按照“后进先出”原则组织数据的数据结构是(064)A）队列B）栈C）双向链表D）二叉树（5）下列叙述中正确的是(064)A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构C）双向链表是非线性结构D）只有根结点的二叉树是线性结构（6）对如下二叉树(064)进行后序遍历的结果为A）ABC
14、DEFB）DBEAFCC）ABDECFD）DEBFCA（7）在深度为7的满二叉树中，叶子结点的个数为(064)A）32B）31C）64D）6326四、查找技术与排序技术（1）顺序查找：无序表或链式存储结构线性表。方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到。若线性表中所有元素都与被查元素进行比较但都不相等，则表示线性表中没有要找的元素。顺序查找的效率是很低的。对于长度为n的线性表，在最坏的情况下，需要比较n次；在平均情况下，需要比较n/2次。27（2）二分法查找：必须是有序表。方法：将被查元素X与线性表的中间项的值进行比较，若相等则表示找到。若X小于
15、中间项的值，则在线性表的前半部分以相同的方法进行查找；若X大于中间项的值，则在线性表的后半部分以相同的方法进行查找。二分法的效率要比顺序查找高的多。对于长度为n的有序线性表，在最坏的情况下，只需要比较log2n次。28（3）交换类排序：冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2次。快速排序法也是一种交换类的排序方法。它是从线性表中选取一个元素T，将表中元素与T比较，小者在前，大者在后，分成两个子表；然后在不断地
16、进行同样的分割。直到所有子表为空。在最坏的情况下，需要的比较次数为n次。29（4）插入类排序：所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。简单插入排序法是从线性表的第2个元素开始直到最后一个元素，逐次将其中的每个元素插入到前面已经有序的子表中。在最坏的情况下，需要的比较次数为n(n-1)/2次。希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。在最坏的情况下，需要的比较次数为n1.5次。30（5）选择类排序：简单选择排序法是扫描整个线性表，从中选出最小元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表为空。假设线性表的长度为n，则在最坏的情况下，简单选择排序需要的比较次数为n(n-1)/2次。堆排序法属于选择类排序法。在最坏的情况下，需要的比较次数为nlog2n次。（6）归并排序是将两个或两个以上的有序表组合成一个新的有序表。因此在排序过程中需要内存容量最大。31例：希尔排序法属于哪一种类型的排序法_。（5-2）(A)交换类排序法(B)插入类排序法(C)选择类排序法(D)建堆排序
