《数据结构作业练习题3》由会员分享，可在线阅读，更多相关《数据结构作业练习题3（2页珍藏版）》请在金锄头文库上搜索。
1、堆 栈 、 队 列 和 字 符 串 作 业 3 一 、 单 项 选 择 题 1用单链表表示的链式队列的队头在链表的（ ）位置。 （北方名校经典试题） A）链头 B）链尾 C）链中 D）任意 2栈应用的典型事例是（ ）。 A）排队 B）查找 C）归并 D ）用“算符优先法”进行表达式求值 3若用单链表来表示队列，则应该选用（ ）。（北方名校经典试题） A）带尾指针的非循环链表 B）带尾指针的循环链表 C）带头指针的非循环链表 D ）带头指针的循环链表 4设有循环队列 cq，结构定义如下： #define MAXQSIZE 100 / 最大队列长度 typedef struct QNodeElem
2、Type *base; / 初始化的动态分配空间int front; / 头指针，如队列不空，指向队列头元素int rear; / 尾指针，如队列不空，指向队列尾元素的下一个位置 SqQueue; SqQueue:cq; 则当一个元素入队时指针变化为（ ）。 A）cq.rear= cq.rear+1 B）cq.rear=(cq.rear+1) % MAXQSIZE C）cq.front= cq.front+1 D ）cq.front=(cq.front+1) % MAXQSIZE 5在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲 区，这样主机将要输出的数据依次写入该缓冲区
3、，而打印机则从该缓冲区中取出数据 打印。该缓冲区应该是一个（ ）结构。（北方名校经典试题） A）堆栈 B）队列 C）数组 D）线性表 6设有循环队列 cq，类型描述如上题，已知 MAXQSIZE=18，cq.front=12，cq.rear=14 ，在连续执行了 3 次入队，2 次出队，3 次入 队操作之后，（cq.front,cq.rear）的值应为（ ）。 A）（13,0 ） B）（14,2 ） C）（13,17） D）（14,17） 7设一个栈的入栈序列是 ABCD，则借助于一个栈所得到的出栈序列不可能是（ ）。 A）ABCD B）DCBA C）ACDB D）DABC 2 数据结构 8设
4、栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（ ） 。 A）1、2、3、4、5、6 B）2、1、3、4、5、6 C）3、4、2、1、5、6 D ）4、3、2、1、5、6 9设 TOP 为链栈的栈顶指针，则空栈的条件是（ ）。 A）n=0 B）TOP-next=0 C ）TOP=NULL D）TOP- next=NULL 10一般情况下，将递归算法转换成等价的非递归算法应该设置（ ）。 （北方名校经典试题） A）栈 B）队列 C）堆栈或队列 D）数组 11设栈的输入序列是 1，2，n，若输出序列的第一个元素是 n，则第 i 个输 出元素是（ ）。 A）n-i+1 B）i
5、 C）n-i D）前面都不正 确 12设 S 为一个长度为 n 的字符串，其中的字符各不相同，则 S 中的互异的非平 凡子串（非空且不同于 S 本身）的个数为（ ）。（南方名校经典试题）A） B） C） D） n 2 2 n 2 2 2 n n 1 2 2 2 n n 二 、 综 合 题 1有 5 个元素，其入栈次序为：A 、B、C 、D、E ，在各种可能的出栈次序中， 以元素 C 第一个出栈，D 第二个出栈的次序有哪几个？ 本题选做 2已知一个栈 S 的输入序列为 abcd，下面两个序列能否通过栈的 Push 和 Pop 操 作输出；如果能，请写出操作序列；如果不能，清说明原因。 （1）dbca （2）cbda 本题选做 3已知 Ackerman 函数定义如下： 0 , 0 ) 1 , ( , 1 ( 0 , 0 ) 1 , 1 ( 0 1 ) , ( n m n m akm m akm n m m akm m n n m Akm （1）写出递归算法； *（2）写出非递归算法。 第 2 章 线性表 3注：（2）较难，选做。
