数据结构第三章考试题库(含答案)[精品].pdf

第3章 栈和队列 一 选择题 1. 对于栈操作数据的原则是（ ）。【青岛大学 2001 五、2 （2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否 ( ② )。当栈中元素为n 个,作进栈运算时发生上溢,则说明该栈的最大容量为 ( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间 时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产 生上溢。 ①, ② : A. 空 B. 满 C. 上 溢 D. 下溢 ③ : A. n-1 B. n C. n+1 D. n/2 ④ : A. 长度 B. 深度 C. 栈 顶 D. 栈底 ⑤:A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1 （5分）】【上海海运学院 1999 二、1 （5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1=i=n）个 元素是（ ）。 A. 不 确 定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是 i，则第j个输出元素是 （ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p,p,p，…，p,若p 是n，则 1 2 3 N N p 是( )。 i A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1 （1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？ （ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3 （2分）】 7. 设栈的输入序列是1，2，3，4,则 （ ）不可能是其出栈序列。【中科院计算所2000 一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一