(2)队列中能容纳元素的最多个数是多少?(1分)【东北大学2002一、1】 36.给出循环队列中元素个数的计算式(设队最大长度为N,队首指针 FRONT,队尾指针REAR) 【西北大学2000二、7(5分)】 37.顺序队列一般应该组织成为环状队列的形式,而且一般队列头或尾其中之一应该特殊处 理。例如,队列为 disarray[0..n-1],队列头指针为 front,队列尾指针为rear,则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。【北京大学1999一、3 (20/3分)】 38.设一个双端队列,元素进入该队列的次序为a,b,c,d。求既不能由输入受限的双端 队列得到,又不能由输出受限的双端队列得到的输出序列。【中山大学1999一、4(3分)】 39.若以1、2、3、4作为双端队列的输入序列,试分别求出以下条件的输出序列: (1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列 (2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列 (3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列 【山东科技大学2001一、3(6分)】 40.假设以数组sq[0..7]存放循环队列元素,变量f指向队头元素的前一位置,变量r指向 队尾元素,如用A和D分别表示入队和出队操作,请给出 (1)队空的初始条件 (2)执行操作序列ADAD2AD2A时的状态,并作必要的说明。【北方交通大学1993四(12 分)】 41、设输入元素为1、2、3、P和A,输入次序为123PA,如图(编者略)。元素经过栈后达 输出序列,当所有元素均到达输出序列后,有哪些序列可以作为高级语言的变量名。【中山 大学1997】 五算法设计题 1.设有两个栈S1,S2都采用顺序栈方式,并且共享一个存储区[0. mansize-1],为了尽量利 用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈 和出栈的操作算法。 【哈尔滨工业大学2001七(12分)】 2.设从键盘输入一整数的序列:a,a,a,…,a,试编写算法实现:用栈结构存储输入的 整数,当a;≠-1时,将a;进栈:当a1=-1时,输出栈顶整数并出栈。算法应对异常情况(入 栈满等)给出相应的信息 【南京航空航天大学1998六(10分)】 3.设表达式以字符形式已存入数组E[n]中,“#为表达式的结束符,试写出判断表达式中 括号(‘(’和‘)’)是否配对的C语言描述算法:EXYX(E);(注:算法中可调用栈操作的基 本算法。) 【北京科技大学2001九、1(10分)】 4.从键盘上输入一个逆波兰表达式,用伪码写出其求值程序。规定:逆波兰表达式的长度 不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种 运算。例如:23434+2*$ 【山东师范大学1999七(10分)】 5.假设以I和0分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序 列可表示为仅由I和0组成的序列,称可以操作的序列为合法序列,否则称为非法序列 (1)下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D.III00100（2）队列中能容纳元素的最多个数是多少？（1 分）【东北大学 2002 一、1】 36. 给出循环队列中元素个数的计算式(设队最大长度为 N,队首指针 FRONT，队尾指针 REAR) 【西北大学 2000 二、7 (5 分)】 37. 顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处 理。例如，队列为 listarray[0..n-1]，队列头指针为 front，队列尾指针为 rear， 则 listarray [rear]表示下一个可以插入队列的位置。请解释其原因。【北京大学 1999 一、3 （20/3 分）】 38. 设一个双端队列，元素进入该队列的次序为 a，b，c，d。求既不能由输入受限的双端 队列得到,又不能由输出受限的双端队列得到的输出序列。【中山大学 1999 一、4 （3 分）】 39. 若以 1、2、3、4 作为双端队列的输入序列，试分别求出以下条件的输出序列： （1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列； （2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列； （3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。 【山东科技大学 2001 一、3 （6 分）】 40. 假设以数组 sq[0..7]存放循环队列元素,变量 f 指向队头元素的前一位置,变量 r 指向 队尾元素，如用 A 和 D 分别表示入队和出队操作，请给出： （1） 队空的初始条件; （2）执行操作序列 A 3 D 1 A 5 D 2 A 1 D 2 A 4 时的状态,并作必要的说明。【北方交通大学 1993 四（12 分）】 41、设输入元素为 1、2、3、P 和 A，输入次序为 123PA，如图（编者略）。元素经过栈后达 输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名。【中山 大学 1997】 五 算法设计题 1. 设有两个栈 S1,S2 都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利 用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1,S2 有关入栈 和出栈的操作算法。 【哈尔滨工业大学 2001 七 （12 分）】 2. 设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的 整数，当 ai≠-1 时，将 ai 进栈；当 ai=-1 时，输出栈顶整数并出栈。算法应对异常情况（入 栈满等）给出相应的信息。 【南京航空航天大学 1998 六 （10 分）】 3. 设表达式以字符形式已存入数组 E[n]中，‘#’为表达式的结束符，试写出判断表达式中 括号（‘（’和‘）’）是否配对的 C 语言描述算法：EXYX(E); (注：算法中可调用栈操作的基 本算法。) 【北京科技大学 2001 九、1 （10 分）】 4. 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度 不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种 运算。例如：234 34+2*$ 【山东师范大学 1999 七 （10 分）】 5. 假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序 列可表示为仅由 I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO