全国计算机等级考试公共基础知识高恩婷编辑.ppt
《全国计算机等级考试公共基础知识高恩婷编辑.ppt》由会员分享,可在线阅读,更多相关《全国计算机等级考试公共基础知识高恩婷编辑.ppt(48页珍藏版)》请在三一文库上搜索。
1、全国计算机等级考试 公共基础知识 高恩婷 编辑,1 笔试,与程序设计语言(C、VB、VF等)笔试部分合为一张试卷。 2 公共基础知识占笔试试卷的30分。 3 10道选择题、5道填空题。,考试方式,主要内容,基本数据结构与算法,程序设计基础,软件工程基础,数据库设计基础,一.基本数据结构与算法,算法的基本概念:算法复杂度(时间、空间) 数据结构的定义:数据的逻辑结构与存储结构;数据结构的图形表示;线性结构、非线性结构的概念 线性表的定义:线性表的顺序存储结构及插入、删除运算 栈和队列的定义:栈和队列的顺序存储结构及其基本运算 线性单链表、双向链表与循环链表的结构及其基本运算。 树的基本概念:二叉
2、树的定义及其存储结构;二叉树的前序、中序和后序遍历 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序),大纲要求,例题: 算法的有穷性是指 A算法程序的运行时间是有限的 B算法程序所处理的数据量是有限的 C算法程序的长度 D算法只能被有限的用户使用 下列叙述中正确的是 A算法的效率只与问题的规模有关,而与数据的存储结构无关 B算法的时间复杂度是指执行算法所需要的计算工作量 C数据的逻辑结构与存储结构是一一对应的 D算法的时间复杂度与空间复杂度一定相关 算法的空间复杂度是指 A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量 C.算法程序中的语句货指令条
3、数 D.算法在纸箱过程中所需要的临时工作单元数 4.算法的时间复杂度是指 A.算法的执行时间 B.算法所处理的数据量 C.算法程序中的语句或指令条数 D.算法在执行过程中所需要的基本运算次数,1. 算法的基本概念,2. 数据结构的定义:数据的逻辑结构与存储结构;数据结构的图形表示;线性结构、非线性结构的概念,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储(物理)结构数据的逻辑结构在计算机存储器中的实现,1.下列叙述中正确的是 A.顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连续的 B.顺序存储结构只针对线性结构,链式存储结构只针对非线性结构 C.顺序存储结构能存储有序
4、表,链式存储结构不能存储有序表 D.链式存储结构比顺序存储结构节省存储空间 2.下列数据结构中,属于非线性结构的是 A.循环队列 B.带链队列 C.二叉树 D.带链栈 3.数据的存储结构是指_。 A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示 C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据,3. 线性表,例题: 1.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表,循环队列是队列的 链式 存储结构。 2.下列叙述中正确的是 A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B.线性表的链式存储结构所需要的存储空间一般要多于
5、顺序存储结构 C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D.上述三种说法都不对,3.线性表的顺序存储结构和线性表的链式存储结构分别是_。 A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构 4.用链表表示线性表的优点是_。 A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同 C. 花费的存储空间较顺序存储少 D. 便于随机存取,4. 栈和队列,栈的定义和特点: 定义:限定仅在表尾进行插入或删除操作的线性表,表尾栈顶,表头栈底,不
6、含元素的空表称空栈 特点:先进后出(FILO)或后进先出(LIFO),队列的定义及特点: 定义:队列是限定只能在表的一端进行插入,在表的另一端进行删除的线性表 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点:先进先出(FIFO),栈中元素个数=bottom-top+1 队列中元素个数=(rear-front+maxqsize)%maxqsize。其中maxqsize为队列的容量,例题: 1. 如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是 Ae3,e1,e4,e2 Be2,e4,e3,e1 Ce3,e,4,e1,e2 D任意顺序 2. 一个栈的初始状态为空
7、。现将元素1、2、3、4、5、A 、B、C、D、E依次入栈,然后依次出栈,则元素出栈的顺序是 A.12345ABCDE B.EDCBA54321 C.ABCDE12345 D.54321EDCBA 这一题注意与上一个例子区别! 3.一个队列的初始状态为空。现将元素1、2、3、4、5、A 、B、C、D、E依次入队,然后依次出队,则元素出队的顺序是 12345ABCDE 。 4. 下列关于栈的叙述正确的是 A.栈按“先进先出”的原则组织数据 B.栈按“先进后出”的原则组织数据 C.只能在栈底插入数据 D.不能删除数据 栈先进后出、栈顶可以插入删除、栈底不可以插入删除 5.支持子程序调用的数据结构是
8、 A.栈 B.树 C.队列 D.二叉树,例题: 6.假设用一个长度为50的数组(下标从0到49)作为栈的存储空间,栈底指针bottom指向栈底元素,栈顶指针top指向栈顶元素,如果bottom=49,top=30(数组下标),则栈中具有 20 个元素 7.设某循环队列的容量为50,如果头指针front=45(指向对头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有 15 个元素。 8.对于循环队列,下列叙述中正确的是 A.队头指针是固定不变的 B.队头指针一定大于队尾指针 C.队头指针一定小于队尾指针 D.队头指针可以大于队尾指针,也可以小于队尾指针 9.下列叙述中正
9、确的是 A.循环队列有队头和队尾两个指针,因此,循环队列是非线性结构 B.在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况 C.再循环队列中,只需要对为指针就能反映队列中元素的动态变化情况 D.循环队列中元素的个数是有队头指针和队尾指针共同决定的,5. 单链表、双向链表、循环链表,例题: 1. 设某循环队列的容量为50,头指针front=5(指向队头元素的前一位置),尾指针rear=29(指向队尾元素),则该循环队列中共有 24 个元素。 实现循环队列时,头指针指向第一个元素的前一个空间,尾指针指向最后一个元素。因此,此时队列中6、7、829这24个空间存有元素。 2.在单链表中,
10、增加头结点的目的是_。 A. 方便运算的实现 B. 使单链表至少有一个结点 C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现,6. 树、二叉树,二叉树的遍历: 前序:根左右 中序:左根右 后序:左右根 例题: 1. 对如图所示的二叉树进行前序遍历的结果是: A.DYBEAFCZX B.YDEBFZXCA C.ABDYECFXZ D.ABCDEFXYZ 上图所示二叉树进行中序遍历的结果是 DYBEAFCZX 上图所示二叉树进行后序遍历的结果是 YDEBFZXCA 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是_。 A. cedba B. a
11、cbed C. decab D. deabc,6. 树、二叉树,例题: 在树形结构中,树根节点没有 前件(前驱) 某二叉树中度为2的节点有18个,则该二叉树中有 19 个叶子节点。 因为:二叉树中,叶子节点数比度为2的节点数多1个,即n0=n2+1 在深度为7的满二叉树中,度为2的节点个数为 63 。 二叉树性质:一棵深度为k的满二叉树有2k-1个节点。 所以:该树中共有27-1=127个节点 又因为:叶子节点数比度为2的节点数多1个,即n0=n2+1 所以有:n0+n2=2n2+1=127n2=63 深度为5的满二叉树有 16 个叶子节点。 某二叉树中度为2的节点有18个,则该二叉树中有 1
12、9 个叶子节点。 因为:二叉树中,叶子节点数比度为2的节点数多1个,即n0=n2+1 一棵二叉树中共有70个叶子节点与80个度为1的节点,则该二叉树中的总节点数为 219 。(叶子节点数比度为2的节点数多1个),7. 在一棵二叉树上第5层的结点数最多是_。 2n-1 A. 8 B. 16 C. 32 D. 15 8.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为_。 A. 349 B. 350 C. 255 D. 351 根据完全二叉树的第二个性质可知:当一二叉树的总结点为n 时,其父结点的个数就为Int(n/2). 而我们不难可知道;在二叉树中,叶子结点就应该等于所有结点与父
13、结点之差。 故本题最简单的解法即为: 699 Int(699/2) = 699 349 = 350,7. 查找、排序,查找也叫检索,是根据给定的某个值,在表中确定一个关键字等于给定值的记录或数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值叫查找算法的,例题: 对长度为n的线性表排序,在最坏的情况下,比较次数不是n(n-1)/2的排序方法是 A快速排序 B冒泡排序 C直接插入排序 D堆排序 2. 在长度为n的有序线性表中进行二分查找,在最坏的情况
14、下需要比较的次数是 A.O(n) B.O(n2) C.O(log2n) D.O(nlog2n) 3.下列叙述中正确的是 A.对长度为n的有序链表进行查找,最坏情况下需要的比较次数为n B.对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为n/2 C.对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为log2n D.对长度为n的有序链表进行对分查找,最坏情况下需要的比较次数为nlog2n 4.在长度为n的线性表中,寻找最大项至少需要比较 1 次。 5. 希尔排序法属于哪一种类型的排序法_。 A. 交换类排序法 B. 插入类排序法 C. 选择类排序法 D. 建堆排序法,6.对长
15、度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为_。 A. N+1 B. N C. (N+1)/2 D. N/2 7.在下列几种排序方法中,要求内存量最大的是_。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序,二. 程序设计基础,程序设计方法与风格 结构化程序设计 面向对象的程序设计方法,对象、方法、属性及继承与多态性,大纲要求,例: 算法的有穷性是指 A算法程序的运行时间是有限的 B算法程序所处理的数据量是有限的 C算法程序的长度 D算法只能被有限的用户使用 下列叙述中正确的是 A算法的效率只与问题的规模有关,而与数据的存储结构无关 B算法的时间复杂度是指执行算法
16、所需要的计算工作量 C数据的逻辑结构与存储结构是一一对应的 D算法的时间复杂度与空间复杂度一定相关 下列叙述中,不符合良好程序设计风格要求的是 A.程序的效率第一,清晰第二 B.程序的可读性好 C.程序中要有必要的注释 D.输入数据前要有提示信息,1. 程序设计方法与风格,例: 在结构化程序设计中,模块划分的原则是 A各模块应包括尽量多的功能 B各模块的规模应尽量大 C各模块之间的联系应尽量紧密 D模块内具有高内聚度,模块间具有低耦合度 为了使模块尽可能独立,要求 A模块的内聚程度要尽量高,且各模块间的耦合程度要尽量强 B模块的内聚程度要尽量高,且各模块间的耦合程度要尽量弱 C模块的内聚程度要
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 计算机等级考试 公共 基础知识 高恩婷 编辑
链接地址:https://www.31doc.com/p-2582278.html