12 链队列
选择题
（1） 用不带头结点的单链表存储队列时，其队头指针指向队头结点，队尾指针指向
队尾结点，则执行删除操作时，（ ）。 A．仅修改队首指针 B．仅修改队尾指针 C．队首指针和队尾指针都需要修改 D．队首指针和队尾指针可能都需要修改
（2） 在链队列中，设指针f和r分别指向队首和队尾，则插入s所指结点的操作是
（ ）。 A．f->next=s; f=s; B．r->next=s; r=s; C．s->next=r; r=s; D．s->next=f; f=s;
（3） 设循环单链表表示的队列长度为n，若只设头指针，则进队操作的时间性能为
（ ）。 A．○(n) B．○(1) C．○(n2) D．○(nlog2n)
（4） 最不适合用作链队列的链表是（ ）。 A．只带队首指针的非循环双链表 B．只带队首指针的循环双链表 C．只带队尾指针的循环双链表 D．只带队尾指针的循环单链表
算法设计题
（5） 假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但
不设头指针。试设计相应的入队和出队算法。
26
13 栈和队列的应用
选择题
（1） 设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。 A．顺序表 B．栈 C．队列 D．链表
（2） 如果数据是在程序的运行过程中逐步产生的，并且要求先产生的数据后处理，
后产生的数据先处理，则最合适的数据结构是（ ）。 A．顺序表 B．顺序栈 C．顺序队列 D．堆
（3） 在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印缓冲区，
该缓冲区应该是一个（ ）结构。 A．栈 B．队列 C．数组 D．线性表
（4） 执行（ ）操作时，需要使用队列作为辅助数据结构。 A．深度优先遍历图 B．广度优先遍历图 C．散列查找 D．遍历二叉树
（5） 表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为
（ ），其中^表示乘幂。 A．3,2,4,1,1；#*^(+*- B．3,2,8；#*^- C．3,2,4,2,2；#*^(- D．3,2,8；#*^(-
（6） 利用栈计算表达式的值时，设置操作数栈OPND，设OPND只有存储单元，
计算下列表达式是不发生上溢的是（ ）。 A．a-b*(c-d) B．(a-b)*c-d C．(a-b*c)-d D．(a-b)*（c-d）
（7） 与中缀表达式a*b+c/d-e等价的前缀表达式是（ ）。 A．-+*ab/cde B．*+/-abcde C．+*ab-/cde D．*ab+cd/-e
（8） 解决hanoi塔问题的递归算法，其时间复杂度是（ ）。 A．○(n) B．○(n2) C．○(2n) D．○(n!)
（9） 4个圆盘的汉诺塔，总的移动次数为（ ）。 A．7 B．8 C．15 D．16
（10） 一个递归的求解过程可以用递归函数求解，也可以用非递归函数求解，从运行
时间上看，通常递归函数要比非递归函数（ ）。 A．快一些 B．慢一些 C．相同 D．无法比较
（11） 栈和队列的主要区别在于（ ）。 A．它们的逻辑结构不一样 B．它们的存储结构不一样 C．所包含的运算不一样 D．插入、删除运算的限定不一样
27
（12） 栈和队列的共同点是（ ）。 A．都是先进先出 B．都是先进后出 C．只允许在端点处插入和删除元素 D．没有共同点
（13） 栈和队列具有相同的（ ）。 A．逻辑结构 B．抽象数据类型 C．存储结构 D．运算
（14） 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈
S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。 A．6 B．4 C．3 D．2
算法设计题
（15） 假设一个算术表达式中可以包含三中括号：园括号“（”和“）”，方括号“[”
和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写算法判断表达式中所含括号是否配对出现。
（16） 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。
（17） 设计递归算法求解在n元集合A={1，2，?，n}中选取k（k≤n）个元素的所
有组合。例如，从集合{1，2，3，4}中选取2个元素的所有组合为：{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{3，4}。
（18） 已知Q是一个循环队列，S是一个顺序栈，设计算法实现将队列中所有元素逆
转。
（19） 设栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，?，a2，a1，
要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，?，a2，a2n-1，a2n-3，?，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为○(n)。
（20） 利用两个栈S1和S2模拟一个队列，已知栈的三个运算定义如下：PUSH(ST,x)
元素x入ST；POP(ST,x)ST栈顶元素出栈，赋给变量x；Sempty(ST)判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue插入一个元素入队列；dequeue删除一个元素出队列；queue_empty判断队列是否为空。
（21） 一个双端队列Q是限定在线性表的两端（LEFT端和RIGHT端）都可以进行
插入和删除操作的线性表，队列为空的条件是LEFT=RIGHT。若采用顺序存储结构存储双端队列，要求： ①定义双端队列的存储结构；
②给出在指定端L（表示左端）和R（表示右端）进行插入（QueueInsert）和删除（QueueDelete）操作的算法。
28
14 数组
选择题
（1） 数组通常具有的两种基本操作是（ ）。 A．查找和修改 B．查找和索引 C．索引和修改 D．建立和删除
（2） 将数组称为随机存取结构是因为（ ）。 A．数组元素是随机的 B．对数组任一元素的存取时间是相等的 C．随时可以对数组进行访问 D．数组的存储结构是不定的
（3） 下面说法中，不正确的是（ ）。 A．数组是一种线性结构
B．数组是一种定长的线性结构
C．除了插入和删除操作外，数组的基本操作还有存取、修改、检索和排序等 D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操作
（4） 二维数组SZ[-3..5，0..10]含有的元素个数是（ ）。 A．88 B．99 C．80 D．90
（5） 数组A[0..5，0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址
为1000的内存单元中，则元素A[5，5]的地址是（ ）。 A．1175 B．1180 C．1205 D．1210
（6） C语言中定义的整数一维数组a[50]和二维数组b[10][5]具有相同的首元素地
址，即&(a[0])=&(b[0][0])，在以列序为主序时，a[18]的地址和（ ）的地址相同。 A．b[1][7] B．b[1][8] C．b[8][1] D．b[7][1]
（7） 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0～8，列下
标的范围是0～9，则存放A至少需要（ ）个字节，A的第8列和第5行共占（ ）个字节，若A按行序优先方式存储，元素A[8][5]的起始地址与当A按列优先存储时的（ ）元素的起始地址一致。 A．90 B．180 C．240 D．540 E．108 F．114 G．54 H．A[8][5] I．A[3][10] J．A[5][8] K．A[4][9]
（8） 三维数组A[8,8,10]采用行序为主的方式从地址A[0，0，0]开始存放，假设每
个元素占用存储空间大小为L，则元素A[3，2，8]的存放位置是（ ）。 A．A[0，0，0]+198*L B．A[0，0，0]+108*L C．A[0，0，0]+268*L D．A[0，0，0]+13*L
算法设计题
（9） 若在矩阵A中存放一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元
素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求矩阵所有马鞍点的算法，并分析最坏情况下
29
的时间复杂度。
（10） 给定n×m矩阵A[a..b，c..d]满足A[i，j]≤A[i，j+1]（a≤i≤b，c≤j≤d-1）和
A[i，j]≤A[i+1，j]（a≤i≤b-1，c≤j≤d）。设计算法判定x是否在A中，要求时间复杂度为○(m+n)。
30