1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 4 及答案解析(总分：60.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.当字符序列工作为下图输入时，输出长度为 3 的，且可用作 C 语言标识符的序列的有( )。【浙江大学2004 二(5 分)】 （分数：2.00）A.4 个B.5 个C.3 个D.6 个2.和顺序栈相比，链栈有一个比较明显的优势是( )。【北京理工大学 2006 五、6(1 分)（分数：2.00）A.通常不会出现栈满的情况B.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现3.若一个栈以向量 V1,n存储，初始栈顶指
2、针 top 为 n+1，则下面 x 进栈的正确操作是( )【南京理工大学 1998 一、13(2 分)】（分数：2.00）A.top=top+1； Vtop=xB.Vtop=x；top=top+1C.top=top1； Vtop=xD.Vtop=x；top=top 一 14.若栈采用顺序存储方式存储，现两栈共享空间 V1，m，topi代表第 i 个栈(i=1，2)栈顶栈 1 的底在V1，栈 2 的底在 Vm，则栈满的条件是( )。【南京理工大学 1999 一、14(1 分)】【江苏大学 2005 一、2(2 分)】（分数：2.00）A.1top2一 top11=0B.top1+1=top2C.
3、top1+top2=mD.top1=top25.栈在( )中应用。【中山大学 1998 二、3(2 分)】（分数：2.00）A.递归调用B.子程序调用C.表达式求值D.A，B，C6.向一个栈顶指针为 h 的带头结点的链栈中插入指针 S 所指的结点时，应执行( )。【北京理工大学 2005十一、6(1 分)】（分数：2.00）A.h-next=s；B.s 一next=h；C.s 一next=h；h 一next=s；D.s 一next=-h 一next；h 一next=s；7.一个递归算法必须包括( )。【武汉大学 2000 二、21（分数：2.00）A.递归部分B.终止条件和递归部分C.迭代部分
4、D.终止条件和迭代部分8.function calc(x，y：integer)：integer； begin if y=1 then calc：=x else calc：=calc(x，y一 1)+x end；a、b 均为正整数，则 cale(a，b)=( )。【中国科学技术大学 1995 十四、14(6 分)】（分数：2.00）A.a*(b 一 1)B.a*bC.a+bD.a+a9.执行完下列语句段后，i 值为( )。【浙江大学 2000 一、6(3 分)】 i1It f(int x1 (return(x0)?x*f(x-1)：2)；) int i； i =f(f(1);（分数：2.00）A
5、.2B.4C.8D.无限递归10.设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。【西安电子科技大学1996 一、6(2 分)】（分数：2.00）A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈11.递归过程或函数调用时，处理参数及返回地址，要用一种称为( )的数据结构。【福州大学。1998 一、1(2 分)】（分数：2.00）A.队列B.多维数组C.栈D.线性表12.允许对队列进行的操作有( )。【华中科技大学 2004 一、2(1 分)】（分数：2.00）A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素13.若用
6、单链表来表示队列，下面几种数据结构中，最合适的是( )。【四川大学 2004】（分数：2.00）A.带尾指针的非循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表14.对于循环队列( )。【北京理工大学 2005 十一、7(1 分)】（分数：2.00）A.无法判断队列是否为空B.无法判断队列是否为满C.队列不可能满D.以上说法都不是15.循环队列 A0,m 一 1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是( )。【南京理工大学 2001 一、5(15 分)】（分数：2.00）A.(rearfront+m)mB.rear-fr
7、ont+1C.rear-front-1D.rear-front二、填空题(总题数：12，分数：24.00)16.表达式 23+(12*32)4+34*57)+1089 的后缀表达式是_。【中山大学 1998 一、4(1分)】【北京邮电大学 2006 一、4(2 分)】（分数：2.00）_17.设 a=6，b=4，c=2，d=3，e=2，则后缀表达式 abc 一de*+的值为_。【南京邮电学院 2004二、1(5 分)】（分数：2.00）_18.在按算符优先法求解表达式 31+5*2 时，最先执行的运算是_，最后执行的运算是_ 。【北京理工大学 2005 二、3(2 分)】（分数：2.00）_1
8、9.用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1，2，3，4，为了得到 1，3，4，2 的出栈顺序，相应的 S 和 X 操作串为_。【同济大学 2005】（分数：2.00）_20._又称作先进先出表。【重庆大学 2000 一、7】（分数：2.00）_21.队列的特点是_。【北京理工大学 2000 二、2(2 分)】【中南大学 2005 二、6(2 分)】（分数：2.00）_22.在具有 n 个元素的非空队列中插入一个元素或者删除一个元素的操作时间复杂度采用大 O 形式表示为_。【北京航空航天大学 2006 一、4(1 分)】（分数：2.00）_23.循环队列是队列的一种_存储结
9、构。【南京理工大学 2005 二、10(1 分)】（分数：2.00）_24.循环队列的引入，目的是为了克服_。【厦门大学 2001 一、1(148 分)】（分数：2.00）_25.在循环队列中，队列长度为 n，存储位置从 0 到 n 一 1 编号，以 rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_。【南京邮电学院 2003 一、1(4 分)】（分数：2.00）_26.已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是_。【合肥工业大学 2000三、3(2 分)】（分数：2.00）_27.区分循环队列的满与空，只有两种方法，它们是_和_。【北京邮电
10、大学 200l 二、2(4 分)】（分数：2.00）_三、判断题(总题数：3，分数：6.00)28.队列逻辑上是一个下端和上端既能增加又能减少的线性表。( )【上海交通大学 1998 一、2(1 分)】（分数：2.00）A.正确B.错误29.设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为 O(1)。( )【中南大学 2003 一、5(1 分)】（分数：2.00）A.正确B.错误30.栈和队列都是线性表，只是在插入和删除时受到了一些限制。( )【北京邮电大学 2002 一、3(1 分)】【烟台大学 2007 二、3(1 分)】（分数：2.00）A.正确B.错误计算机专业基础综合数据
11、结构（栈和队列）历年真题试卷汇编 4 答案解析(总分：60.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.当字符序列工作为下图输入时，输出长度为 3 的，且可用作 C 语言标识符的序列的有( )。【浙江大学2004 二(5 分)】 （分数：2.00）A.4 个B.5 个C.3 个 D.6 个解析：2.和顺序栈相比，链栈有一个比较明显的优势是( )。【北京理工大学 2006 五、6(1 分)（分数：2.00）A.通常不会出现栈满的情况 B.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现解析：3.若一个栈以向量 V1,n存储，初始栈顶指针 to
12、p 为 n+1，则下面 x 进栈的正确操作是( )【南京理工大学 1998 一、13(2 分)】（分数：2.00）A.top=top+1； Vtop=xB.Vtop=x；top=top+1C.top=top1； Vtop=x D.Vtop=x；top=top 一 1解析：4.若栈采用顺序存储方式存储，现两栈共享空间 V1，m，topi代表第 i 个栈(i=1，2)栈顶栈 1 的底在V1，栈 2 的底在 Vm，则栈满的条件是( )。【南京理工大学 1999 一、14(1 分)】【江苏大学 2005 一、2(2 分)】（分数：2.00）A.1top2一 top11=0B.top1+1=top2 C
13、.top1+top2=mD.top1=top2解析：5.栈在( )中应用。【中山大学 1998 二、3(2 分)】（分数：2.00）A.递归调用B.子程序调用C.表达式求值D.A，B，C 解析：6.向一个栈顶指针为 h 的带头结点的链栈中插入指针 S 所指的结点时，应执行( )。【北京理工大学 2005十一、6(1 分)】（分数：2.00）A.h-next=s；B.s 一next=h；C.s 一next=h；h 一next=s；D.s 一next=-h 一next；h 一next=s； 解析：7.一个递归算法必须包括( )。【武汉大学 2000 二、21（分数：2.00）A.递归部分B.终止条
14、件和递归部分 C.迭代部分D.终止条件和迭代部分解析：8.function calc(x，y：integer)：integer； begin if y=1 then calc：=x else calc：=calc(x，y一 1)+x end；a、b 均为正整数，则 cale(a，b)=( )。【中国科学技术大学 1995 十四、14(6 分)】（分数：2.00）A.a*(b 一 1)B.a*b C.a+bD.a+a解析：9.执行完下列语句段后，i 值为( )。【浙江大学 2000 一、6(3 分)】 i1It f(int x1 (return(x0)?x*f(x-1)：2)；) int i；
15、i =f(f(1);（分数：2.00）A.2B.4 C.8D.无限递归解析：10.设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。【西安电子科技大学1996 一、6(2 分)】（分数：2.00）A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈 解析：11.递归过程或函数调用时，处理参数及返回地址，要用一种称为( )的数据结构。【福州大学。1998 一、1(2 分)】（分数：2.00）A.队列B.多维数组C.栈 D.线性表解析：12.允许对队列进行的操作有( )。【华中科技大学 2004 一、2(1 分)】（分数：2.00）A.对队列中的元素排序B.取出最
16、近进队的元素C.在队头元素之前插入元素D.删除队头元素 解析：13.若用单链表来表示队列，下面几种数据结构中，最合适的是( )。【四川大学 2004】（分数：2.00）A.带尾指针的非循环链表B.带尾指针的循环链表 C.带头指针的非循环链表D.带头指针的循环链表解析：14.对于循环队列( )。【北京理工大学 2005 十一、7(1 分)】（分数：2.00）A.无法判断队列是否为空B.无法判断队列是否为满C.队列不可能满D.以上说法都不是 解析：15.循环队列 A0,m 一 1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是( )。【南京理工大学 2001
17、一、5(15 分)】（分数：2.00）A.(rearfront+m)m B.rear-front+1C.rear-front-1D.rear-front解析：解析：循环队列入队、出队、求元素个数的运算都要用取模运算。本题是求元素个数。若入队，则新元素位置 rear=(rear+1)m，出队则 front=(front+1)m，队空 front=rear，队满是 (rear+1)m=front，m 是队列长度，4752 题都是循环队列问题。关于队头和队尾指针的指向，多数教材约定，队头指针指向队头元素的前一位置，队尾指针指向队尾元素，也有教材规定队头指针指向队头元素，队尾指针指向队尾元素的后一位置
18、。二、填空题(总题数：12，分数：24.00)16.表达式 23+(12*32)4+34*57)+1089 的后缀表达式是_。【中山大学 1998 一、4(1分)】【北京邮电大学 2006 一、4(2 分)】（分数：2.00）_正确答案：(正确答案：23123*24345*7+1089+表达式中的点(.)是数分隔符，如23123 是三个数)解析：17.设 a=6，b=4，c=2，d=3，e=2，则后缀表达式 abc 一de*+的值为_。【南京邮电学院 2004二、1(5 分)】（分数：2.00）_正确答案：(正确答案：9)解析：18.在按算符优先法求解表达式 31+5*2 时，最先执行的运算是
19、_，最后执行的运算是_ 。【北京理工大学 2005 二、3(2 分)】（分数：2.00）_正确答案：(正确答案：减法运算(31)、加法运算(2+10)解析：19.用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1，2，3，4，为了得到 1，3，4，2 的出栈顺序，相应的 S 和 X 操作串为_。【同济大学 2005】（分数：2.00）_正确答案：(正确答案：SXSSXSXX)解析：20._又称作先进先出表。【重庆大学 2000 一、7】（分数：2.00）_正确答案：(正确答案：队列)解析：21.队列的特点是_。【北京理工大学 2000 二、2(2 分)】【中南大学 2005 二、6(
20、2 分)】（分数：2.00）_正确答案：(正确答案：先进先出)解析：22.在具有 n 个元素的非空队列中插入一个元素或者删除一个元素的操作时间复杂度采用大 O 形式表示为_。【北京航空航天大学 2006 一、4(1 分)】（分数：2.00）_正确答案：(正确答案：O(1)解析：23.循环队列是队列的一种_存储结构。【南京理工大学 2005 二、10(1 分)】（分数：2.00）_正确答案：(正确答案：顺序(物理)解析：24.循环队列的引入，目的是为了克服_。【厦门大学 2001 一、1(148 分)】（分数：2.00）_正确答案：(正确答案：假溢出时大量移动数据元素)解析：25.在循环队列中，
21、队列长度为 n，存储位置从 0 到 n 一 1 编号，以 rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_。【南京邮电学院 2003 一、1(4 分)】（分数：2.00）_正确答案：(正确答案：rear=(rear+1)n)解析：26.已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是_。【合肥工业大学 2000三、3(2 分)】（分数：2.00）_正确答案：(正确答案：new(s)；s 一data=x；s 一next=r 一next；rnext=s；r=s；)解析：27.区分循环队列的满与空，只有两种方法，它们是_和_。【北京邮电大学 200l
22、二、2(4 分)】（分数：2.00）_正确答案：(正确答案：牺牲一个存储单元、设标记。(编者顺便指出，还有设立计数器等方法。)解析：三、判断题(总题数：3，分数：6.00)28.队列逻辑上是一个下端和上端既能增加又能减少的线性表。( )【上海交通大学 1998 一、2(1 分)】（分数：2.00）A.正确B.错误 解析：解析：队列只在下端(队尾)增加，在上端(队头)减少。29.设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为 O(1)。( )【中南大学 2003 一、5(1 分)】（分数：2.00）A.正确 B.错误解析：30.栈和队列都是线性表，只是在插入和删除时受到了一些限制。( )【北京邮电大学 2002 一、3(1 分)】【烟台大学 2007 二、3(1 分)】（分数：2.00）A.正确 B.错误解析：
