数据结构第三章考试题库[含答案].docVIP

第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，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(????)。 ????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.?一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（????）。 ???A. 2 3 4 1 5?????B. 5 4 1 3 2?????C. 2 3 1 4 5??????D. 1 5 4 3 2 【南开大学?2000?一、1】【山东大学?2001?二、4 (1分)】【北京理工大学?2000?一、2（2分）】 9.?设一个栈的输入序列是?1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（????）。 A. 5 1 2 3 4????????B. 4 5 1 3 2??????C. 4 3 1 2 5????????D. 3 2 1 5 4 【合肥工业大学?2001?一、1（2分）】 10.?某堆栈的输入序列为a, b，c?，d,下面的四个序列中，不可能是它的输出序列的是（????）。 ????A. a，c，b，d?????????B. b, c，d，a????C. c, d，b, a?????????D. d, c，a，b 【北京航空航天大学?2000?一、3（2分）】【北京邮电大学?1999?一、3（2分）】 11.?设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为 （????）。 A．fedcba???????B. bcafed????????C. dcefba????????D. cabdef 【南京理工大学?1996?一、9（2分）】 12.?设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是(?????)。 A．XYZ???????????B. YZX????????????C. ZXY??????