作业3解答.doc

堆栈、队列和字符串 作业3 一、单项选择题 1．用单链表表示的链式队列的队头在链表的（　　　）位置。（北方名校经典试题） A）链头 B）链尾 C）链中 D）任意 【分析】队列的队头是对队列元素进行删除的一端。对于链队列在链头处进行删除，所以队头在链表的链头位置（不考虑不包含数据元素的头结点） 【答案：A】 2．栈应用的典型事例是（　　　）。 A）排队 B）查找 C）归并 D）用“算符优先法”进行表达式求值 【分析】排队、归并与查找一般都不用栈，而用“算符优先法”进行表达式求值必须用栈，是栈的典型应用。 【答案：B】 3．若用单链表来表示队列，则应该选用（　　　）。（北方名校经典试题） A）带尾指针的非循环链表 B）带尾指针的循环链表 C）带头指针的非循环链表 D）带头指针的循环链表 【分析】设尾指针为Tail，对于循环链表，tail-next为队头，所以应选用带尾指什的循环链表。 【答案：B】 4．设有循环队列cq，结构定义如下： #define MAXQSIZE 100 //最大队列长度 typedef struct QNode{ ElemType *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 【分析】队列入队时，元素应追加在队尾，也应是队尾发生变化，由于是循环队列，可知应在同余意义下取值。 【答案：B】 5．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（　　　）结构。（北方名校经典试题） A）堆栈 B）队列 C）数组 D）线性表 【分析】打印任务最好采用先来先服务，也就是说缓冲区此时实际上是一个等待打印队列。 【答案：B】 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） 【分析】入队时，队尾发生变化，出队时，队头发生变化，可知连续执行了3次入队后，（cq.front,cq.rear）的值为（12,17）；连续执行2次出队后，（cq.front,cq.rear）的值为（14,17）；连续执行了3次入队后，（cq.front,cq.rear）的值为（14,2）。 【】 B）DCBA C）ACDB D）DABC 【分析】由于栈的入栈与出栈操作都在栈顶进行，在答案D中D最先出栈，此时从栈顶到栈底的元素分别为D、C、B、A，可知出栈序列应为DCBA，而不可能为DABC，所以本题应选择D。 【答案：D】 8．设栈最大长度为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 【分析】由于栈的入栈和出栈操作都在栈顶进行，在答案D中首先出栈的元素为4，此时栈从栈底到栈顶的元素依次为1，2，3，4，这样要求栈长度至少为4，已超过材的最大长度。 【答案：D】 9．设TOP为链栈的栈顶指针，则空栈的条件是（　　　）。 A）n==0 B）TOP-next==0 C）TOP==NULL D）TOP-next==NULL 【分析】由于链栈不设立头结点，所以空链栈的条件是TOP==NULL。 【答案：C】 10．一般情况下，将递归算法转换成等价的非递归算法应该设置（　　　）。（北方名校经典试题） A）栈 B）队列 C）堆栈或队列 D）数组 【分析】栈的用途之一就是将递归转换为非递归。 【】 1．设栈的输入序列是1，2，…，n，若输出序列的第一个元素是n，则第i个输出元素是（　　　）。 A）n-i+1 B）i C）n-i D）前面都不正确 【分析】由栈的特点可知出栈序列应为：n，n-1，…，2，1。 【】 2．设S为一个长度为 n的字符串，其中的字符各不相同，则 S中的互异的非平凡