2011年计算机二级考试公共基础知识冲刺复习笔记（17）

文章作者 100test 发表时间 2011:03:18 18:47:58
来源 100Test.Com百考试题网

　　Point3：栈、队列和循环队列

　　出题趋势

考试日期	05-4	05-9	06-4	06-9	07-3	07-9	08-4	08-9	09-3	09-9	10-3	10-9
出题次数	1	1	1	1	1	1	2	2	2	2	2	2

　　考点精讲

　　1、栈（Stack）又称堆栈。

　　(1)栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。

　　(2)由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表（LastInFirstOut，简称LIFO）；先进栈的元素必定后出栈，所以又把栈称为先进后出表（FirstInLastOut，简称FILO）。

　　2、队列（Queue）简称队。

　　(1)队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。我们把允许插入的一端称作队尾（rear），允许删除的一端称作队首（front）。

　　(2)向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除队首元素称为离队或出队，该元素离队后，其后继元素就成为新的队首元素。(3)由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进队的次序离队，所以又把队列称为先进先出表（FirstInFirstOut，简称FIFO）。3、循环队列。就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。

真题分析

　　【真题1】对于循环队列，下列叙述中正确的是________。（2009年9月）

　　A)队头指针一定小于队尾指针

　　B)队头指针可以大于队尾指针，也可以小于队尾指针

　　C)队头指针是固定不变的

　　D)队头指针一定大于队尾指针

　　解析：循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追

　　赶尾指针。所以队头指针可以大于队尾指针，也可以小于队尾指针。

　　答案：B

　　【真题2】下列叙述中正确的是________。（2008年9月）

　　A)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

　　B)循环队列中元素的个数是由队头指针和队尾指针共同决定

　　C)循环队列有队头和队尾两个指针，因此循环队列是非线性结构

　　D)在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

　　解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。

　　答案：B

　　【真题3】设某循环队列的容量为50，头指针front=5(指向队头元素)，尾指针rear=29(指向队尾元素)，则该循环队列中共有__【3】__个元素。（2008年4月）

　　解析：在循环队列中因为头指针指向的是队头元素的前一个位置，所以是从第6个位置开始有数据元素，即计算从6到29之间有多少个元素，所以队列中的数据元素的个数为：29-6 1=29-5=24。

　　答案：24

　　【真题4】线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的__【3】__存储结构。（2007年9月）

　　解析：队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。

　　答案：顺序

　　【真题5】下列对队列的叙述正确的是________。（2007年3月）

　　A)队列在队尾删除数据

　　B)队列按“先进先出”原则组织数据

　　C)队列属于非线性表

　　D)队列按“先进后出”原则组织数据

　　解析：队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾；允许删除的一端称为队头。在队列这种数据结构中，最先插入的元素将最先能够被删除；反之，最后插入的元素将最后才能被删除。因此，队列又称“先进先出”或“后进后出”的线性表。

　　答案：B

　　【真题6】一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为__【1】__。（2010年3月）

　　解析：对于队列来讲，是先进先出。

　　答案：A,B,C,D,E,F,5,4,3,2,1

　　【真题7】设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有__【2】__个元素。（2010年3月）

　　解析：这次头指针在尾指针之后，因为是循环队列，所以应该是从46到50，再从1到10构成了这个队列。

　　答案：15

　　【真题8】下列数据结构中，能够按照“先进后出”原则存取数据的是________。（2009年9月）

　　A)队列

　　B)二叉树

　　C)循环队列

　　D)栈

　　解析：由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以栈被称为后进先出表(LastInFirstOut,简称LIFO)；先进栈的元素必定后出栈，所以又把栈称为先进后出表(FirstInLastOut,简称FILO)。

　　答案：D

　　#ff0000>