全国二级考试公共基础部分重点与难点-Java程序设计.DOC

全国二级考试公共基础部分重点与难点 顺序存储结构与链式存储结构 图1 线性表的顺序存储示意 图2 线性单链表的存储结构示意 顺序存储结构 链式存储结构 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑，存储密度 =1 插入、删除操作不需要移动大量的元素，修改指针即可 存储空间动态分配，表容量容易扩充 存储空间可以不必连续 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 指针需要占用额外的存储空间，存储密度 1 链表只能顺序存取元素，不可以随机存取 入栈与出栈 栈：只允许在一端插入和删除的线性表叫栈，允许插入和删除的一端称为栈顶 (top)，另一端称为栈底(bottom)。 特点： 后进先出 (LIFO，Last In First Out) 或 先进后出（FILO） 顺序栈用一维数组S（1：m）实现，top=0表示栈空，top=m表示栈满。– bottom）+1 进栈（push）：也叫入栈，即在栈顶位置插入一个新元素，先将top +1，然后将新元素插入到top所指的位置；当top已指向栈存储空间的最后一个位置时，说明栈已满，若再进行进栈操作则出现“上溢”错误。 出栈（pop）：也叫退栈，即取出栈顶元素并赋给一个指定的变量，先将栈顶元素赋值给一个指定的变量，然后将top-1；当top为0时，说明栈已空，若再进行出栈操作则出现“下溢”错误。 读（get）栈顶元素：将栈顶元素赋值给一个指定的变量，top不变。 图 3 顺序栈的进栈、出栈运算示意 【常考题型】已知若干元素的入栈顺序，如A、B、C、D、E，问：哪些是不可能的出栈顺序？哪些是可能的出栈顺序？ 解题提示：可将栈想象成一个杯子，入栈就好比往杯子里放园球，先放进去的在下面，后放进去的在上面，取球的时候必须先取上面的，后取下面的。凡是出入次序不存在矛盾的元素序列就是可能的出栈顺序。比如本题可能的顺序有：1）依次将球A、B、C、D、E全都放进去后再取出来，则出栈顺序为EDCBA；2）先依次将A、B、C放进去，然后取出上面的2个，再将D、E放进去，然后都取出来，则出栈顺序为CBEDA；3）先依次将A、B放进去，然后取出上面的1个，再将C、D放进去，然后都取出来，最后将E放进去再取出来，这时出栈顺序是BDCAE。其它可能的顺序不再罗列。 思考：DBCAE、DEBAC是可能的出栈顺序吗？ （答：不是，因为D是第一个出栈的，说明其前面的A、B、C还没出栈，那么这3个元素再出栈时必须符合CBA的顺序） 循环队列中的元素个数 队列：只允许在一端插入、在另一段删除的顺序表叫队列，允许删除的一端称为队头 (front)，允许插入的一端称为队尾(rear)。队列用一维数组实现sq[M] 特点： 先进先出 (FIFO，First In First Out) 队列的进队、退队原则： 入队时队尾指针先进一， rear = rear + 1，再将新元素按 rear 指示位置加入。 退队时队头指针先进一，front = front + 1， 再将下标为 front 的元素取出。 队满时再入队将产生“溢出”错误； 队空时再退队将产生“下溢”错误。 图 4 队列的入队、退队运算示意 循环队列： 就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图 5所示。 循环队列的运算规则： 每进行一次入队运算，队尾指针就进一，当rear=m+1时，置rear=1； 每进行一次退队运算，队头指针就进一，当front=m+1时，置front=1； 循环队列的状态判断： 为了区分队列是满还是空，设立标志s，当s=1时表示队列非空，当s=0时表示队列空。 循环队列的初始状态为空，即s=0，且rear=front=m； 队列空的条件为s=0； 队列满的条件为s=1且front=rear。 m … 2 1 Q（1：m） 8 7 F 6 E 5 D 4 C 3 B 2 A 1 Q（1：8） 8 X 7 F 6 E 5 D 4 C 3 B 2 A 1 Y Q（1：8） 8 X 7 F 6 E 5 D 4 C 3 B 2 1 Y Q（1：8） 图 5 循环队列的运算示意 【常考题型】求循环队列中的元素个数 循环队列里面的个数计算方法： rear front 的时候， num = rear – front； rear front 的时候， num = rear + m – front；例： 循环队列的存储空间为Q（1:50），初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，则循环队列中的元素个数为？ 解题思路：起始时rear=front=