数据库单元练习3

单元练习3一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）栈是运算受限制的线性表。（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。（ㄨ）（3）栈一定是顺序存储的线性结构。（√）（4）栈的特点是“后进先出”。（ㄨ）（5）空栈就是所有元素都为0的栈。（ㄨ）（6）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。（√）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（ㄨ）（8）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（ㄨ）（9）递归定义就是循环定义。（√）（10）将十进制数转换为二进制数是栈的典型应用之一。二．填空题（1）在栈结构中，允许插入、删除的一端称为栈顶(表尾)。（2）在顺序栈中，当栈顶指针top=-1时，表示栈空。（3）在有n个元素的栈中，进栈操作的时间复杂度为O（1）。（4）在栈中，出栈操作的时间复杂度为：O(1)。（5）已知表达式，求它的后缀表达式是栈的典型应用。（6）在一个链栈中，若栈顶指针等于NULL，则表示栈空。（7）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p-next=top；和top=p；操作。（8）顺序栈S存储在数组S-data[0..MAXLEN-1]中，进栈操作时要执行的语句有：S-top++。（或=S-top+1）（9）链栈LS，指向栈顶元素的指针是LS-next。（10）从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。（11）由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。（12）已知顺序栈S，在对S进行进栈操作之前首先要判断栈是否满。（13）已知顺序栈S，在对S进行出栈操作之前首先要判断栈是否空。（14）若内存空间充足，链栈可以不定义栈满运算。（15）链栈LS是空的条件是LS-next=NULL。（16）链栈LS的栈顶元素是链表的首元素。（17）同一栈的各元素的类型相同。（18）若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为B。（19）A+B/C-D*E的后缀表达式是：ABC/+DE*-。（20）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，x的值是C。三．选择题（1）插入和删除只能在一端进行的线性表，称为(C)。A．队列B．循环队列C．栈D．循环栈（2）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为(D)A．1234B．1243C．1324D．1423（3）如果以链表作为栈的存储结构，则出栈操作时（B）A．必须判别栈是否满B．必须判别栈是否空C．必须判别栈元素类型D．队栈可不做任何判别（4）元素A,B,C,D依次进栈以后，栈顶元素是（D）A．AB．BC．CD．D（5）顺序栈存储空间的实现使用（B）存储栈元素。A．链表B．数组C．循环链表D．变量（6）在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（A）。A．已固定B．不固定C．可以改变D．动态变化（7）带头结点的链栈LS的示意图如下，栈顶元素是（A）LSHABCDΛA．AB．BC．CD．D（8）链栈与顺序栈相比，有一个比较明显的优点是（B）。A．插入操作更加方便B．通常不会出现栈满的情况。C．不会出现栈空的情况D．删除操作根加方便（9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列(D)命令。A．x=top;top=top-next;B．top=top-next;x=top-data;C．x=top-data;D．x=top-data;top=top-next;（10）在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列(B)命令。A．HS-next=S;B．S-next=HS-next;HS-next=S;C．S-next=HS-next;HS=S;D．S-next=HS;HS=HS-next;（11）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（B）。A．AB．BC．CD．D（12）元素A,B,C,D依次进栈以后，栈底元素是（A）。A．AB．BC．CD．D（13）经过下列栈的运算后，再执行ReadTop(s)的值是（A）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);Pop(s)A．aB．bC．1D．0（14）经过下列栈的运算后，x的值是（B）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);ReadTop(s);Pop(s,x);A．aB．bC．1D．0（15）经过下列栈的运算后，x的值是（B）。InitStack(s)（初始化栈）;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);A．aB．bC．1D．0（16）经过下列栈的运算后，SEmpty(s)的值是（C）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);Pop(s,x);Pop(s,x);A．aB．bC．1D．0（17）向顺序栈中压入元素时，（B）。A．先存入元素，后移动栈顶指针B．先移动栈顶指针，后存入元素C．谁先谁后无关紧要D．同时进行（18）初始化一个空间大小为5的顺序栈S后，S-top的值是（B）。A．0B．-1C．不再改变D．动态变化（19）一个栈的入栈次序ABCDE，则栈的不可能的输出序列是(C)。A．EDCBAB．DECBAC．DCEABD．ABCDE（20）设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少应是(A)。A．3B．4C．5D．6四．设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出下列出栈的操作序列。（1）C，B，A，D，E（2）A，C，B，E，D解：（1）IIIOOOIOIO（2）IOIIOOIIOO五．求后缀表达式（1）A^B^C/D（2）-A+B*C+D/E（3）A*(B+C)*D-E（4）(A+B)*C-E/(F+G/H)-D（5）8/(5+2)-6解:（1）AB^C^D/（2）0A–BC*+DE/+（3）ABC+*D*E-（4）AB+C*EFGH/+/-D-（5）852+/6-六．算法设计题1．设用一维数组stack[n]表示一个堆栈，若堆栈中每个元素需占用M个数组单元（M1），（1）试写出其入栈操作的算法。（2）试写出其出栈操作的算法。2．设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。1．解：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S[1]开始存放元素。（1）入栈算法：voidpush(charx){if((top+M)MAXLEN-1)printf(“堆栈溢出！”);else{if(top==0){top++;S[top]=x;}else{top=top+M;S[top]=x;}}}（2）出栈算法：voidpop(charx){if(top==0)printf(“堆栈为空栈！”);else{if(top==1){x=S[top];top––;}else{x=S[top];top=top–M;}}}2．解：设表达式在字符数组a[]中，使用一堆栈S来帮助判断。intcorrect(chara[]){stacks;InitStack(s);//调用初始化栈函数for(i=0;istrlen(a);i++)if(a[i]==’(’)Push(s,’(’);elseif(a[i]==’)’){ifStackEmpty(s)//调用判栈空函数return0;//若栈为空返回0；否则出栈elsePop(s);}if(StackEmpty(s))//调用判栈空函数printf(“配对正确！”);//若栈空，说明配对正确，并返回1elseprintf(“配对错误！”);//配对错误返回0}模拟考题求后缀表达式1．求下列表达式：A/B∧C+D*E-A*C的后缀表达式。解：ABC∧/DE*+AC*-2．求下列表达式：A/B-C+D*E-F的后缀表达式。解：AB/C-DE*+F-写出运行下列程序段的输出结果voidmain(){StackS;charx,y;InitStack(S);//初始化栈x=c;y=k;Push(S,x);Push(S,a);Push(S,y);Pop(S,x);Push(S,t);Push(S,x);Pop(S,x);Push(S,s);While(!SEmpty(S)){Pop(S,y);couty;};coutx;}答：stack程序填空1.下列程序是判别一个算术表达式（存在字符数组a[]中）的圆括号配对是否正确？试填空完成下列程序。intcorrect(chara[]){stacks;InitStack(s);//初始化栈for(i=0;istrlen(a);i++)if(a[i]==’(’)Push(s,’(’);elseif(a[i]==’)’){ifSEmpty(s)return0;//若栈为空返回0；否则出栈elsePop(s);}if(SEmpty(s))cout配对正确！;//printf(配对正确！);elsecout配对错误！;//printf(配对错误！);}2．链栈的存储结构和栈顶指针定义如下，试写出把十进数转换为二进制数的程序。#defineMAXLEN100typedefstructstacknode//定义栈的存储结构{intdata;structstacknode*next;}stacknode;typedefstruct{stacknode*top;//定义栈顶的指针}linkstack;解：voidConversion(intn)//栈的应用：二—十进制转换{linkstacks;intx;s.top=NULL;//置栈空do{x=n%2;//取余数n=n/2;//取新的商stacknode*p=newstacknode;//申请新结点p-next=s.top;//修改栈顶指针s.top=p;s.top-data=x;//余数入栈}while(n);cout转换后的二进制数值为：;//printf(转换后的二进制数值为：);while(s.top)//出栈处理{couts.top-data;stacknode*p=s.top;s.top=s.top-next;deletep;//出栈一个余数，收回一个结}}