数据结构第3章特殊线表习题解析(答).doc

第三章特殊线表习题一、选择题1、若用单链表来表示队列， 则应该选用 。A、带尾指针的非循环链表 B、带尾指针的循环链表C、带头指针的非循环链表 D、带头指针的循环链表 2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear 和front的值分别是 。A、1和5 B、2和4 C、4和2 D、5和1 3、设栈的输入序列为1、2、3、4，则 不可能是其出栈序列。A、1243 B、2134 C、1432 D、4312 E、3214 4、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为 。A、-A+B*C/DE B、-A+B*CD/E C、-+*ABC/DE D、-+A*BC/DE 5、设栈的输入序列是1、2、n，若输出序列的第一个元素是n，则第i个输出元素是 。 A、不确定 B、n-i+1 C、i D、n-i 6、假定一个顺序循环队列的队首和队尾指针分别用front 和rear表示，则判队空的条件是 。A、front+1=rear B、front=rear+1C、front=0 D、front=rear 7、假定一个顺序循环队列存储于数组An中，其队首和队尾指针分别用front 和rear表示，则判断队满的条件是 。A、(rear-1)%n=front B、(rear+1)%n=frontC、rear=(front-1)%n D、rear=(front+1)%n 8、一个栈的的输入序列为12345，则下列序列中不可能是栈的输出序列的是 。 A、23415 B、54132 C、23145 D、15432 9、若一个栈的输入序列是1、2、3、n，输出序列的第一个元素是i，则第i个输出元素是 。 A、i-j-1 B、i-j C、j-i+1 D、不确定 10、用单链表表示的链式队列的队头在链表的 位置。 A、链头 B、链尾 C、链中 11、设计一个判别表达式中左、右括号是否配对出现的算法，采用 数据结构最佳。A、线性表的顺序存储结构 B、队列C、线性表的链式存储结构 D、栈 12、在下列算法描述中，涉及到队运算的算法是 D 。A、表达式求值算法 B、深度优先搜索C、二叉树遍历 D、广度优先搜索 13、栈的插入和删除操作在 进行。A、栈顶 B、栈底 C、任意位置 D、指定位置 14、在一个顺序循环队列中，队首指针指向队首元素的 位置。A、前一个 B、后一个 C、当前 D、最后 15、当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为 。A、N-2 B、N-1 C、N D、N+1 16、如果以链表作为栈的存储结构，则退栈操作时 。A、必须判别栈是否满 B、判别栈元素的类型C、必须判别栈是否空 D、对栈不作任何判别 17、链栈与顺序栈相比有一个明显的优点，即 。A、插入操作更加方便 B、通常不会出现栈满的情况C、不会出现栈空的情况 D、删除操作更加方便二、填空题 1、中缀式a+b*3+4*(c-d)对应的前缀式为 +ab34-cd ，若a=1,b=2,c=3,d=4,则后缀式db/cc*a-b*+的运算结果为 18 。 2、用下标0开始的N元数组实现循环队列时，为实现下标变量m加1后在数组有效下标范围内循环，可采用的表达式是m= （m+1）% n 。 3、表达式求值是 栈 应用的一个典型例子。 4、队列是特殊的线性表，其特殊性在于 只允许在表的一端进行元素的插入而在另一端进行元素的删除 。 5、一个循环队列存于AM中，假定队首和队尾指针分别为front和rear，则判断队空的条件为 front=rear ，判断队满的条件为 (rear+1) % M=front 。 6、向一个循环队列存入新元素时，需要首先移动 队尾指针 ，然后再向它所指位置 存入 新元素。 7、 队列 又称为先进先出表。 8、栈是特殊的线性表，其特殊性在于 只允许在栈顶加入或删除元素 。 9、栈又称为 后进先出 表，队列又成为 先进先出 表。 10、在一个