基础知识综合

《基础知识综合》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国计算机等级考试公共基础知识高恩婷编辑1笔试，与程序设计语言（C、VB、VF等）笔试部分合为一张试卷。2公共基础知识占笔试试卷的30分。310道选择题、5道填空题。考试方式主要内容基本数据结构与算法程序设计基础软件工程基础数据库设计基础一.基本数据结构与算法算法的基本概念：算法复杂度（时间、空间）数据结构的定义：数据的逻辑结构与存储结构；数据结构的图形表示；线性结构、非线性结构的概念线性表的定义：线性表的顺序存储结构及插入、删除运算栈和队列的定义：栈和队列的顺序存储结构及其基本运算线性单链表、双向链表与循环链表的

2、结构及其基本运算。树的基本概念：二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历顺序查找与二分法查找算法;基本排序算法(交换类排序，选择类排序，插入类排序)大纲要求例题：算法的有穷性是指A．算法程序的运行时间是有限的B．算法程序所处理的数据量是有限的C．算法程序的长度D．算法只能被有限的用户使用下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关算法的空间复杂

3、度是指A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句货指令条数D.算法在纸箱过程中所需要的临时工作单元数4.算法的时间复杂度是指A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数1.算法的基本概念2.数据结构的定义:数据的逻辑结构与存储结构；数据结构的图形表示；线性结构、非线性结构的概念根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性

4、表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图数据的逻辑结构——只抽象反映数据元素的逻辑关系数据的存储（物理）结构——数据的逻辑结构在计算机存储器中的实现数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：1.下列叙述中正确的是A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结

5、构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间2.下列数据结构中，属于非线性结构的是A.循环队列B.带链队列C.二叉树D.带链栈3.数据的存储结构是指______。A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据3.线性表例题：1.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的链式存储结构。2.下列叙述中正确的是A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B.线性表的链式存储结

6、构所需要的存储空间一般要多于顺序存储结构C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D.上述三种说法都不对3.线性表的顺序存储结构和线性表的链式存储结构分别是______。A.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构4.用链表表示线性表的优点是______。A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少D.便于随机存取4.栈和队列栈的

7、定义和特点：定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）队列的定义及特点：定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)栈中元素个数=bottom-top+1队列中元素个数=（rear-front+maxqsize）%maxqsize。其中maxqsize为队列的容量例题：1.如果进栈序列为e1，e2，

8、e3，e4，则可能的出栈序列是A．e3，e1，e4，e2B．e2，e4，e3，e1C．e3，e,4，e1，e2D．任意顺序2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后依次出栈，则元素出栈的顺序是A.12345ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA这一题注意与上一个例子区别！