JAVA数据库结构考题，适用于大连东软信息学院

3.7 习题

3.7.1知识点：栈的基本概念

一、选择题

1① 下列哪种数据结构常用于函数调用（ A ）。

Ａ．栈 Ｂ．队列 Ｃ．链表 Ｄ．数组 2① 编译器中通常以哪种数据结构处理递归程序调用（ C ） Ａ．队列

Ｂ．数组

C．栈 D．记录

3① 下列哪些数据结构可用来实现栈（ D ）。 （1）链表

（2）数组

（3）树 （4）图

D．（1），（2）

Ａ．（2），（3） Ｂ．（2），（4） C．（1），（4）

4② 元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是（ C ）。 A．dcba B．abcd C．dcab D．cbad

5② 已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A．5，4，3，2，1，6 B．2，3，5，6，1，4 C．3，2，5，4，1，6 D．1，4，6，5，2，3

6② 若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）。

A．SXSSXXXX B．SXXSXSSX C．SXSXXSSX D．SSSXXSXX 7① 对于栈操作数据的原则是（ B ）。【青岛大学 2001】

A． 先进先出 B．后进先出 C．后进后出 D．不分顺序 8① 栈在（ D ）中应用。【中山大学 1998】

A．递归调用 B．子程序调用 C．表达式求值 D．A，Ｂ，Ｃ 9② 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ）。【中山大学 1999】

A．不确定 B．n-i+1 C．i D．n-i

10② 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（D ）。【武汉大学 2000】

A．i-j-1 B．i-j C．j-i+1 D．不确定的 11② 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）【北方交通大学 2001】

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

12② 输入序列为ABC，可以变为CBA 时，经过的栈操作为（B ）【中山大学 1999】 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop

C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop

13② 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。【西安电子科技大学 1996】

A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈 二、填空题 1① 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 ，不允许插入和删除运算的一端称为 栈底 。 2① 对于顺序存储的栈，因为栈的空间是有限的，在进行 入栈 运算时，可能发生栈的上溢，在进行 出栈 运算时，可能发生栈的下溢。

3① 表达式求值是 栈 应用的一个典型例子。

4① 栈是__一种特殊_____的线性表，其运算遵循____先进后出_____________的原则。【北京科技大学 1997】

5② 设有一个空栈， 栈顶指针为1000H（ 十六进制） ， 现有输入序列为1 ， 2 ， 3 ， 4 ， 5 ， 经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是 2,3，_______，而栈顶指针值是_1000C_____H。设栈为顺序栈，每个元素占4 个字节。【西安电子科技大学 1998】

6② 用S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为1234，为了得到1342 出栈顺序，相应的S和X 的操作串为_________sxssxsxx__________。【西南交通大学 2000】 三、判断题

（ F ）1① 栈具有先进先出的特性。 （ T ）2① 栈用于实现子程序调用。 （ F ）3① 栈和链表是两种不同的数据结构。 （ T ）4① 栈顶的位置是随着操作而变化的。 （ T ）5① 栈和队列逻辑上都是线性表。

（ T ）6① 栈是实现过程和函数等子程序所必需的结构。【合肥工业大学 2000】 （ F ）7② 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。【北京邮电大学 1999】

（ T ）8② 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。【上海海运学院1995】

（ F ）9② 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。【上海海运学院 1999】 四、简答题

1① 什么是栈？试举两个应用实例。 2① 简述栈和线性表的差别。

3③ 计算表达式 6*3/2-5*1，要求绘出堆栈的处理过程。

答:

操作数栈 第一次 6 第二次 6 第三次 3 6 18 第五次 18 第六次 2 18 第七次 9 第八次 9 第九次 5 9 第十次 5 9 第十一次 1 5 9 第十二次 5 9 第十三次 4

运算符栈 空 * 空 * 空 / 空 / 空 - 空 - * - 空 * - 空 - 空 5② 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即C 第一个且D 第二个出栈）的次序有哪几个？【西南交通大学 2000】

3.7.2知识点：栈的存储

一、选择题

1① 如果以链表作为栈的存储结构，则入栈操作时（ B ）。

A．必须判别栈是否满 B．对栈不作任何判别 C．必须判别栈是否空 D．判别栈元素的类型

2① 上溢现象通常出现在（ A ）。

A．顺序栈的入栈操作过程中 B．顺序栈的出栈操作过程中 C．链栈的入栈操作过程中 D．链栈的出栈操作过程中 3① 判定一个栈ST（最多元素为m0）为空的条件是（ B ）

Ａ．ST->top！=0 Ｂ．ST->top= =0 Ｃ．ST->top！=m0 Ｄ．ST->top= =m0 4① 链表仿真堆栈时，栈空的条件是（B ）。

A．top

A．top

Ａ．new->next=stack->next； stack=new； Ｂ．new->next=stack； stack=new； Ｃ．new->next=stack；stack=new->next； Ｄ．stack=new；stack->next=new->next； 7② 若一个栈以向量V[1．．n]存储，初始栈顶指针top 为n+1，则下面x 进栈的正确操作是（ B ）。【南京理工大学 1998】

A．top=top+1; V [top]=x B．V [top] =x; top=top+1 C．top=top-1; V [top]=x D．V [top]=x; top=top-1 8② 执行完下列语句段后，i 值为：（ B）。【浙江大学 2000】 int f（int x）

{ return （（x>0） ? x* f（x-1）:2）;} int i ; i =f（f（1））;

A． 2 B． 4 C． 8 D． 无限递归 二、填空题

1② 以下语句是堆栈的入栈操作，用全局数组stack仿真堆栈，数组类型是int，大小是MaxSize，栈顶指针是top，初始化等于－1。

01 void push（int value） 02 {

03 if（top>MaxSize-1） 04 return –1; 05 else 06 { 07 top++;

08 stack[top]=value; 09 } 10 }

指出有错误的语句：___3_____________

写出改正后的语句：_____ top==MaxSize-1___________

2② 以下语句是数据从堆栈中取出操作,top为栈顶指针,stack为堆栈数组。

01 int pop（） 02 {

03 int temp; 04 if（top＝＝0） 05

return –1;

06 else 07 { 08 09 10 } 11 return temp; 12 }

temp = stack[top]; top ――;

指出有错误的语句：_______________________ 写出改正后的语句：_______8,9互换________________ 三、编程题

1④ 假设一个算术表达式中可以包含圆括号“（”和“）”，编写判别给定表达式中所含括号是否正确配对出现的算法。

2④ 编写斐波那契（Fibonacci） 数列的递归算法和迭代算法。

F0?0,F1?1,Fn?Fn?1?Fn?2(n??2)

3.7.3知识点：队列的基本概念及其应用

一、选择题

1① 下列哪种数据结构常用于系统程序的作业调度（ B ） A．栈

B．队列 C．链表 D．数组

2① 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印．该缓冲区应该是一个（ B ）结构．

A．堆栈 B．队列 C．数组 D．线性表

3② 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ C ）

A．6 B．4 C．3 D．2

4① 栈和队列的共同点是（ C ）。【燕山大学 2001 一、1（2 分）】 A． 都是先进先出 B．都是先进后出 C． 只允许在端点处插入和删除元素 D． 没有共同点 二、填空题

1① 栈和队列都是线性结构，对于栈只能在____栈顶______ 位置插入和删除元素，对于队列只能在______队尾________位置插入元素和_____队头_________位置删除元素。

2② 队列的队尾位置通常是随着_____入队_________操作而变化的。

3① 队列的特点是_______先进先出_________________。【北京理工大学 2000】 4② 循环队列的引入，目的是为了克服________假溢出________________。【厦门大学 2001】 三、判断题

（ T ）1① 队列中所有的插入操作都发生在表的一端，删除则发生在表的另一端。 （ F ）2① 队列为先进后出的结构。 （ F ）3① 队列必须用数组来表示。

（ T ）4① 队列用于操作系统中的作业调度。 （ T ）5① 栈和队列逻辑上都是线性表。

（ T ）6① 栈和队列是在程序中常用的两种数据结构。

（ T ）7① 栈与队列是一种特殊操作的线性表。【青岛大学 2001】 （ T ）8① 栈和队列都是限制存取点的线性结构。【中科院软件所 1999】

（ F）9① 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。【上海海运学院 1998】

（ F ）10① 通常使用队列来处理函数或过程的调用。【南京航空航天大学 1997】 （ F ）11① 队列逻辑上是一个下端和上端既能增加又能减少的线性表。【上海交通大学 1998】

（ T ）12① 栈和队列都是线性表，只是在插入和删除时受到了一些限制。【北京邮电大学2002】 四、简答题

1① 什么是队列？试举两个应用实例。 2① 说明线性表、栈和队列的异同点。

3① 顺序队的“假溢出”是怎样产生的？什么是循环队列？如何知道循环队列是空还是满？ 五、编程题

1④ 假设称正读和反读都相同的字符序列为“回文”，例如‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

3.7.4知识点：队列的存储

一、选择题

1① 循环队列用数组A[maxsize] 表示，下面哪个选项表示该循环队列队满

（ B ）

Ａ．rear= =maxsize-1 B． front= =（rear+1）%maxsize C． rear-front= =maxsize D． rear-front= =maxsize-1

2① 在用数组queue[maxsize]仿真队列时（temp为int型变量），假设队列中至少有一个元素，出队列操作应执行以下（ D ）

A．temp=queue[rear]; rear--; B． rear++; temp=queue[rear]; C．temp=queue[front]; front--; D． front++; temp=queue[front];

3① 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（ D ）

Ａ．r－f; Ｂ．（n＋f－r）% n; Ｃ．n＋r－f Ｄ．（n＋r－f）% n 4② 判断一个队列QU（最多元素为m0）为空的条件是（ C ）。 A．rear- front= =m0 C．front= = rear

B．rear- front-1= =m0 D．front= = rear+1

5② 一个队列（数组仿真，最多元素为MaxSize）下列哪个选项表示了队列空间全部被利用？（ A ）

A．rear – front = = MaxSize B．rear – front = = MaxSize –1 C．rear = = front D．rear + 1 = = front

6② 判定一个循环队列（数组仿真，最多元素为MaxSize）为空的条件是？（ A ） A．front = = rear B．front != rear

C．front = = （rear + 1）%MaxSize D．front != （rear + 1）%MaxSize 7① 用单链表表示的链式队列的队头在链表的（ A ）位置。【清华大学 1998】 A．链头 B．链尾 C．链中 D．任何

8② 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（ D ）。【北京理工大学 2001】

A．仅修改队头指针 B．仅修改队尾指针

C． 队头、队尾指针都要修改 D．队头,队尾指针都可能要修改

9② 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear，则当前队列中的元素个数为（ A ）。【北京工商大学 2001】

A．（rear-front+m）%m B．rear-front+1 C．（front-rear+m）%m D．（rear-front）%m 10② 循环队列存储在数组A[0．．m]中，则入队时的操作为（ D ）。【中山大学 1999】 A． rear=rear+1 B．rear=（rear+1） mod （m-1） C． rear=（rear+1） mod m D．rear=（rear+1）mod（m+1）

11② 若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为多少？（ B ）【浙江大学1999】

A． 1 和 5 B． 2 和4 C． 4 和2 D． 5 和1

12② 用链接方式存储的队列，在进行插入运算时（ B ）。【北方交通大学 2001】 A．仅修改头指针 B．仅修改尾指针 C．头、尾指针都要修改 D．头、尾指针可能都要修改 二、填空题

1① 栈、队列的建立可使用两种结构：______顺序________结构和____链式______结构。 2② 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为__10____________。

3③ 以下语句是环状队列的出队操作，用数组queue仿真环状队列，数组类型是int，大小是MaxSize，队尾指针是rear，队头指针是front。

01 int delqueue（） 02 {

03 int temp; 04 if（front==rear） 05 return –1; 06 else 07 { 08 front++;

09 temp=queue[front]; 10 queue[front]=0; 11 return temp; 12 } 13 }

指出有错误的语句：__________8_______________

写出改正后的语句：________front=(front+1)%MaxSize_______________

4② 区分循环队列的满与空，只有两种方法，它们是____设标志____和______少用一片空间_______。【北京邮电大学2001】

5② 设循环队列存放在向量sq．data[0..M]中，则队头指针sq.front 在循环意义下的出队操作可表示为__sq.front=(sq.front+1)%(M+1)_____，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear），则队满的条件为_sq.front==(sq.rear+1)%(M+1)___。【长沙铁道学院 1997】 三、判断题

（ T ）1① 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ T ）2① 单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

（ F ）3① 循环队列通常用指针来实现队列的头尾相接。【南京航空航天大学 1996】 （ T ）4① 循环队列也存在空间溢出问题。【青岛大学 2002】 四、简答题

1② 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 （1） front=11，rear=19; （2） front=19，rear=11； 问在这两种情况下，循环队列中各有元素多少个？8,32

2② 假设CQ[0,…,10]是一个环状队列，初始状态front=rear=1, 画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。

（1）d, e, b, g, h入队； （2）d, e 出队； （3）I, j, k, l, m入队； （4）b出队； （5）n, o, p, q, r入队。

3③ 阅读下列算法，并回答问题（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）。

void f31 （Queue*Q, Queue*Q1, Queue*Q2） {

int e;

lnitQueue （Q1）; lnitQueue （Q2）;

while （!QueueEmpty （Q）） {

e=DeQueue （Q）;

if （e>=0） EnQueue （Q1,e）; else EnQueue （Q2,e） } }

（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 （&Q,&Q1,&Q2）之后队列Q、Q1和Q2的状态；

Q为空

Q1=(1,0,2,9)Q2=(-5,-4,-6) （2）简述算法f31的功能。

4③ 阅读如下程序，并回答下列问题（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）。

void f 31（Queue *Q）{ DataType e;

if （!QueueEmpty（Q））{ e=DeQueue（Q）; f 31（Q）;

EnQueue（Q,e）; } }

（1） 设队列Q=（1，3，5，2，4，6）。写出执行算法f 31后的队列Q;

Q=(6,4,3,5,3,1)

（2）简述算法f 31的功能。将队列反转

5③ 阅读如下程序，它的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使其成为一个完整的算法。 typedef struct node{ DataType data； struct node *next； }QueueNode； typedef struct {

QueueNode *front；／／队头指针 QueueNode *rear；／／队尾指针 }LinkQueue；

void f 31（LinkQueue *Q） { QueueNode *p，*s； p= （1） ； while（p！=NULL） { s=p； p=p->next; free （s）;

（2） =NULL; Q->rear= （3） ； }

（1）______p=Q->front->next____________________

（2）______Q->front->next=NULL____________________________________ （3）______Q->rear=Q->front________________________________ 五、编程题

1④ 假设将循环队列定义为：以变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。 2④ 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

本文来源：https://www.bwwdw.com/article/8id2.html