二级公共基础知识培训.ppt

第一页，共100页。
全国计算机等级考试 之
二级公共基础知识
第二页，共100页。
二级公共基础知识分值10分,全部为选择题。
包括内容：
数据结构与算法（40%）
程序设计基础（20%）
软件工程基础（20%）
数据
在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。栈具有记忆作用，支持子过程调用。
栈的基本运算：1）插入元素称为入栈运算；2）删除元素称为退栈运算；3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
栈的存储方式和线性表类似，也有两种，即顺序栈和链式栈。
栈及其基本运算（演示）
第十三页，共100页。
一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
A）12345ABCDE B）EDCBA54321
C）ABCDE12345 D）54321EDCBA
答案：B
假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指间栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有_______个元素
答案：20
真题示例
第十四页，共100页。
下列关于栈的叙述正确的是（ ）。
A）栈按“先进先出”组织数据
B）栈按“先进后出”组织数据
C）只能在栈底插入数据
D）不能删除数据
一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后
退栈一次，再将元素 A,B,C,D依次入栈，之后将所有元素全部退
栈，则所有元素退栈（包括中间退栈的元素）的顺序为______（）
真题示例
答案： 1DCBA2345
第十五页，共100页。
下列关于栈的叙述中，正确的是（ ）
A)栈底元素一定是最后入栈的元素
B）栈操作遵循先进后出的原则
C)栈顶元素一定是最先入栈的元素
D)以上三种说法都不对
设栈的存储空间为S（1:40），初始状态为bottom=0, top=0。现经过一系列入栈与出栈运算后，top=20，则当前栈中有___________个元素
答案：20
真题示例()
第十六页，共100页。
是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。尾指针（Rear）指向队尾元素，头指针（front）指向排头元素的前一个位置（队头）。
队列是“先进先出”或“后进后出”的线性表。
队列运算包括：1）入队运算：从队尾插入一个元素；2）退队运算：从队头删除一个元素。
队列及其基本运算（演示）
第十七页，共100页。
循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素均为队列中的元素。
循环队列一般用顺序存储。
循环队列（演示）
循环队列中元素的个数是由队头指针和队尾指针共同决定
第十八页，共100页。
（1）循环队列元素的个数为（rear-front+m）%m，其中
m为循环队列容量。
（2）如果rear-front>0,则循环队列元素个数为rear-front;
如果rear-front<0,则循环队列元素个数为rear-front+m;
真题示例：
（1）设某循环列队的容量为50，如果头指针front =45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有______ 个元素。
答案：15 （）
（2）对于循环队列，下列叙述中正确的是（ ）
A)队头指针是固定不变的
B)队头指针是一定大于队尾指针
C)队头指针一定小于队尾指针
D)队头指针可以大于队尾指针，也可以小于队尾指针
计算循环队列个数两种方法：
第十九页，共100页。
真题示例：
（3）下列叙述中正确的是：（ ） （）
A)循环队列是队列的一种顺序存储结构
B)循环队列是队列的一种链式存储结构
C)循环队列是非线性结构 D)循环队列是一直逻辑结构
（4）设循环队列的存储空间为Q(1:30),初始状态为front=rear
= 30。现经过一系列入队与退队运算后，fro