注意,向地址的高端生长,称为向上生成堆栈:向地址低端生长叫向下生成堆栈,本题中底部为n,向地址的低端递减生成, 称为向下生成堆栈 8.【9Ⅰ初程P77】从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写 在答卷的对应栏内 在做进栈运算时,应先判别栈是否A:在做退栈运算时,应先判别栈是否B。当栈中元素为 n个,做进栈运算时发生上溢,则说明该栈的最大容量为C 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的D 分别设在这片内存空间的两端,这样,只有当E时,才产生上溢 供选择的答案: A,B:①空 ③上溢④下溢 C:①n-1 n+1 ④n/2 D:①长度②深度 ③栈顶④栈底 E:①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点 ③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空,且一个栈的栈顶到达另一个栈的栈底 答案: ABCDE=212 四、简答题(每小题4分,共20分) 【严题集3.2①和3.11①】说明线性表、栈与队的异同点。 答:相同点:都是线性结构,都是逻辑结构的概念。都可以用顺序存储或链表存储:栈和队列是两种特殊的线性表,即受 限的线性表,只是对插入、删除运算加以限制 不同点:①运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入、删除运算,因而是后进先出表LIFO:队列 是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。 ②用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理、指令寄存及其他运算等等。 2.【统考书P604-11,难于严题集3.1①】设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的 车站,具体写出这四辆列车开出车站的所有可能的顺序。 刘答:至少有14种。 ①全进之后再出情况,只有1种:4,3,2,1 ②进3个之后再出的情况,有3种,3,4,2,132,4,13,2,1,4 ③进2个之后再出的情况,有5种,2,43,12,34,12,1,3,42,1,4,32,1,3,4 ④进1个之后再出的情况,有5种,1,43,21,3,2,41,3,4,21,2,3,41,2,4,3 3.【刘自编】假设正读和反读都相同的字符序列为“回文”,例如,abba’和‘ abeba’是回文,‘ abcde 和‘ ababab’则不是回文。假设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出 其回文的可能性? 答:线性表是随机存储,可以实现,靠循环变量(j-)从表尾开始打印输出 堆栈是后进先出,也可以实现,靠正序入栈、逆序出栈即可 队列是先进先出,不易实现。 哪种方式最好,要具体情况具体分析。若正文在机内已是顺序存储,则直接用线性表从后往前读取即 或将堆栈栈顶开到数组末尾,然后直接用POP动作实现。(但堆栈是先减后压还是……) 若正文是单链表形式存储,则等同于队列,需开辅助空间,可以从链首开始入栈,全部压入后再依次 输出。3 注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为 n，向地址的低端递减生成， 称为向下生成堆栈。 8. 【91 初程 P77】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写 在答卷的对应栏内。 在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为 n 个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。 供选择的答案： A，B：①空 ② 满 ③ 上溢 ④ 下溢 C： ①n-1 ② n ③ n+1 ④ n/2 D： ① 长度 ②深度 ③ 栈顶 ④ 栈底 E：①两个栈的栈顶同时到达栈空间的中心点 ②其中一个栈的栈顶到达栈空间的中心点 ③两个栈的栈顶在达栈空间的某一位置相遇 ④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底 答案：ABCDE＝2, 1, 2, 4, 3 四、简答题（每小题 4 分，共 20 分） 1. 【严题集 3.2①和 3.11①】说明线性表、栈与队的异同点。 刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受 限的线性表，只是对插入、删除运算加以限制。 不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表 LIFO；队列 是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表 FIFO。 ② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。 2. 【统考书 P60 4-11，难于严题集 3.1①】设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的 车站，具体写出这四辆列车开出车站的所有可能的顺序。 刘答：至少有 14 种。 ① 全进之后再出情况，只有 1 种：4，3，2，1 ② 进 3 个之后再出的情况，有 3 种，3,4,2,1 3,2,4,1 3,2,1,4 ③ 进 2 个之后再出的情况，有 5 种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④ 进 1 个之后再出的情况，有 5 种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3 3. 【刘自编】假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出 其回文的可能性？ 答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出； 堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。 哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即 可，或将堆栈栈顶开到数组末尾，然后直接用 POP 动作实现。（但堆栈是先减后压还是……） 若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次 输出