级等级考试公共基础知识

《级等级考试公共基础知识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、公共基础知识1数据结构与算法程序设计基础软件工程基础数据库基础知识2第1章数据结构与算法一、算法的基本概念二、线形结构与非线形结构、栈和对列的定义三、二叉树的定义四、查找技术与排序技术3一、算法的基本概念：（1）算法的空间复杂度：是指算法在运行过程中需辅助存储空间的大小。（2）算法的时间复杂度：是指执行算法所需要的计算工作量（基本运算次数）。（3）算法的基本特征：确定性、可行性、有穷性、拥有足够的情报。（4）算法的有穷性：是指一个算法必须在执行有限的步骤以后结束。4例1：在下列选项中，不是一个算法一般应该具有的基本特征的是____。（5-1）(A

2、)确定性(B)可行性(C)无穷性(D)拥有足够的情报√√√例2：算法的时间复杂度是指____。（2-1）(A)执行算法程序所需的时间(B)算法程序的长度(C)算法执行过程中所需要的基本运算次数(D)算法程序中的指令条数例3：算法的空间复杂度是指____。（3-1）(A)算法程序的长度(B)算法程序中的指令条数(C)算法程序所占的存储空间(D)算法执行过程中所需要的存储空间5例4：下面叙述正确的是___。（1-1）(A)算法的执行效率与数据的存储结构无关(B)算法的空间复杂度是指算法程序中指令（或语句）的条数(C)算法的有穷性是指算法必须能在执行有

3、限个步骤之后终止(D)算法的时间复杂度是指执行算法程序所需要的时间√√例5：在计算机中，算法是指____。（6-1）(A)查询方法(B)加工方法(C)解题方案的准确而完整的描述(D)排序方法例6：算法分析的目的是________。（8-1）(A)找出数据结构的合理性(B)找出算法中输入和输出之间的关系(C)分析算法的易懂性和可靠性(D)分析算法的效率以求改进√6（7）下列叙述中正确的是________。(069)A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可

4、复杂度必定小D）上述三种说法都不对√7例9：算法的基本特征是可行性、确定性、_______和拥有足够的情报。（7-1）例7：算法的复杂度主要包括时间复杂度和_____复杂度。（1-1）空间例8：实现算法所需的存储单元多少和算法的工作量大小分别称为算法的_____________________。（6-1）空间复杂度和时间复杂有穷性（5）问题处理方案的正确而完整的描述称为【5】。(054)算法8二、线形结构与非线形结构、栈和对列的定义（1）数据结构的基本概念数据结构主要研究和讨论以下三个方面的问题：①数据集合中各数据元素之间所固有的逻辑关系，即数据

5、的逻辑结构。②在对数据进行处理时，各数据元素在计算机中的存储存储关系，即数据的存储结构。③对各种数据结构进行的运算。9（2）根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线形结构与非线形结构。如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线形结构，又称线形表。所以线形表、栈与队列、线形链表都是线形结构，而二叉树是非线形结构。10（3）栈是一种特殊的线性表：只能在固定的一端进行插入和删除操作，后进先出表。（4）队列可看作是插入在一端（队尾）进

6、行，删除在另一端（队头）进行的线性表，先进先出表。（5）线性单链表、双向链表与循环链表的结构及其基本运算：在链表的运算过程中，采用链接方式即循环链表的结构把空表与非空表的运算统一起来。11（6）循环链表具有两个特点：①在循环链表中增加了一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。②循环链表中最后一个结点的指针不是空，而是指向表头结点。（7）数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式。12例：以下数据结构属于非线性数据结构的是____。（1-2）(A)队列(B)线性

7、表(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)

8、都是先进后出(C)只允许在端点处插入和删除元素(D)没有共同点例：栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可