第二单元(栈和队列)(答案).doc

第二单元　课后练习题 知识点范围：第3章　栈和队列 一、选择题（每小题1分，共28分） 1．栈的特点是 B ，简称　C　的线性表；队列的特点是 A ，简称　D　的线性表。 A．先进先出 　B．后进先出 C．LIFO 　　　D．FIFO 2．栈和队列的共同点是 C 。 A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点 3．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。 A．edcba B．decba C．dceab D．abcde 4．设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列 B 是可能的出栈序列。 A．D,B,C,A,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,A,B 5．以下 B 不是队列的基本运算？ A．从队尾插入一个新元素 B．从队列中删除第i个元素 C．判断一个队列是否为空 D．读取队头元素的值 6．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1＝n，则pi为 C 。 A．i B．n－i C．n－i＋1 D．不确定 7．设计一个判别表达式中左、右括号是否配对出现的算法，采用 　D　 数据结构最佳。 A．线性表的顺序存储结构 　B．队列 　　C．线性表的链式存储结构 　　D．栈 8．判定一个顺序栈st（最多元素为MaxSize）为满的条件是 D 。 A．st-top != -1 B．st-top == -1 C．st-top != MaxSize D．st-top == MaxSize 9．一个队列的入队序列是1，2，3，4，则队列的输出序列是 B 。 A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 10．判定一个循环队列qu（最多元素为MaxSize）为空的条件是 C 。 A．qu-rear – qu-front ==MaxSize B．qu-rear – qu-front -1==MaxSize C．qu-rear ==qu-front D． qu-rear =qu-front -1 11．若用一个循环队列空间大小为6，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为　 B　 。 A．1和5　　　 B．2和4 　　　　C．4和2 　　　D．5和1 12．向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行 D 操作。 A．h-next=s?; B．s-next=h?; C．s-next=h?;h =s?; D．s-next=h-next?;h-next=s?; 13．输入序列为ABC，若用S表示入栈，X表示出栈操作，则得到CBA输出序列要经过的栈操作序列为 B 。 A． SXSXSX 　 B． SSSXXX　　　C． SSXSX 　　D． SXSSXX 14．和顺序栈相比，链栈有一个比较明显的优势是　 A 　。 A．通常不会出现栈满的情况　　　　 B． 通常不会出现栈空的情况 C．插入操作更容易实现 　　　　　　D．删除操作更容易实现 15．若一个顺序栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为( B )。 A. n-1 　　 B. n C. n+1 D. n/2 16．允许对队列进行的操作有 D 。 A．对队列中的元素排序 B．取出最近进队的元素 C．在队头元素之前插入元素 D．删除队头元素 17．对于循环队列 D 。 A．无法判断队列是否为空 B．无法判断队列是否为满 C．队列不可能满 D．以上说法都不对 18．若一个带头结点的链栈的栈顶指针用top表示，当p指向的结点进栈时，执行的操作是 C 。 A．p-next=top?;top=top-next; B．top=p-p; p-next=top; C．p-next=top-next; top-next=p; D．p-next=top; top=p; 19．队列的“先进先出”特性是指 D 。 A．最早插入队列