计算机专业基础综合(数据结构)模拟试卷2

计算机专业基础综合（数据结构）模拟试卷2（总分：70.00，做题时间：90分钟）一、单项选择题（总题数：21，分数：42.00）单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）解析：栈和队列的主要区别在于（）。（分数：2.00）它们的逻辑结构不一样它们的存储结构不一样所包含的运算不一样插入和删除运算的限定不一样丿解析：解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是D。3•若循环队列以数组Q[0..m-1]作为其存储结构，变量rear。表示循环队列中的队尾元素的实际位置，其移动按rear=（rear+l）MODm进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是（）。（分数：2.00）rear-length（rear—length+m）MODm（rear—length+1+m）MODmVm-length解析：解析：按照循环队列的定义，因为元素移动按照rect=（rear+1）MODm进行，则当数组Q[m—1]存放了元素之后，下一个入队的元素将存放到Q[0]中，因此队列的首元素的实际位置是（rear—length+l+m）M0Dm。一个以向量V[n]存储的栈，其初始栈顶指针top为n+1,则对于x,其正确的进栈操作是（）。（分数：2.00）top=top+1；V[top]=xV[top]=x；top=top+1top=top-1；V[top]=xVV[top]=x；top=top-1解析：解析：此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈顶为n+1,应该用减法，所以选C。D是先存入，破坏原有数据，所以错。为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在（）。（分数：2.00）内存空间的首地址内存空间的尾地址内存空间的两端V内存空间的中间解析：解析：两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。6•已知输入序列为abed，经过输出受限的双端队列后，能得到的输出序列是（）。（分数：2.00）daebeadbVdbea以上答案都不对解析：解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。分析选项A，输入序列为abed,输出序列为dacb,由输出受限性质可知以da开头的结果只有dabc,选项A为错误答案。分析选项B,输入序列为abed，输出序列为cadb，其输入输出顺序为：先在输出端输入a,然后在非输出端输入b,这时队列中的序列为ba。再在输出端输入c,这时队列中的序列为bac；输出c,再输出a；再在输出端输入d,这时队列中的序列为bd；输出d,再输出b。最后得到输出序列为cadb。分析选项C,输入序列为abcd,输出序列为dbca,由输出受限性质可知以db开头的结果只有dbac,选项C为错误答案。7•假设一个序列1,2,3,…，n依次进栈，如果出栈的第一个元素是n,那么第i（lWiWn）个出栈的元素是（）。（分数：2.00）不确定n-i+l丿in-i解析：解析：进栈的顺序是：1,2,…，n,且出栈的第一个元素是n,那么根据栈后进先出的特点可知，出栈的顺序依次为：n,…，2,1,那么第n一i+1个出栈元素就是第i个进栈的元素。8•假设一个序列1,2,3,…，n依次进栈，如果第一个出栈的元素是i,那么第i个出栈的元素是（）。（分数：2.00）TOC\o"1-5"\h\zi-j—1i-jj—i+1不确定的V解析：解析：此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是i,只能说明前i一1个元素均入栈，而第j个元素何时入、出栈并不能确定，所以选D。9•已知当前栈中有n个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为（）。（分数：2.00）TOC\o"1-5"\h\zn-1nVn+1n／2解析：解析：由于栈中有n个元素是执行进栈操作，但是发生上溢，则说明此栈中最多可以包含n个数据元素,即栈的最大容量为n。设有5个元素a,b,c,d,e顺序进栈，下列几个选项中，不可能的出栈序列是（）。（分数：2.00）A.a,b,c,d,eB.d,e,c,b,aC.a,c,e,b,dVD.c,b,a,d,e解析：解析：由进栈出栈规则可知，对于a,b,c,d,e顺序进栈的五个元素，A、B、D均为可能的出栈序列，所以选Co有6个元素按6,5,4,3,2,1的顺序依次进栈,不合法的出栈序列是（）。（分数：2.00）543612453126346521V234156解析：解析：此题考查的知识点是栈的后进先出特点。考查出栈序列,要保证先入栈的一定不能在后入栈的前面出栈，C选项中的6在5前入栈，5没有出栈，6却出栈了，所以不合法。其他都符合规律。所以选C。

有5个元素，其入栈次序为A,B,C,D,E,在各种可能的出栈次序中，以元素C；D最先出栈的次序不包括()。(分数：2.00)CDEBACDBEACDBAECDAEB丿解析：解析：以元素C,D最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。对于4个元素依次进栈,可以得到()种出栈序列。(分数：2.00)101214 丿解析：解析：n个入栈元素可得到16出栈序列。本题4个元素,可有14解析：解析：n个入栈元素可得到现有两栈，其共享空间为V[l..m],top[i]代表第i个栈(i=l,2)栈项，栈1的底在V[l],栈2的底在V[m],若两栈均采用顺序存储方式存储，则栈满的条件是()。分数：2.00)|top[2]-top[1]|=0top[1]+1=top[2]丿top[1]+top[2]=mtop[1]=top[2]解析:解析:此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当top[1]+1=top[2]或top[2]-1=top[1]时都表示栈满，所以选B,而A,C没有任何意义。D表示已经出现覆盖了，也是错的。一个递归算法必须包括()。(分数：2.00)递归部分终止条件和递归部分丿迭代部分终止条件和迭代部分解析：解析：此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分,所以选B。A不全面,C、D不是递归算法。执行完下列语句段后,i值为()。intf(intx){return((x>0)?x*f(x—1)：2)：}i=f(f(1))；(分数：2.00)24丿8无限递归解析：解析：此题考查的知识点是递归算法的分析。根据题意可计算f(0)=2,f(1)=2,f(2)=4,所以选B。表达式a*(b+c)—d的后缀表达式是()。(分数：2.00)abcd*+一abc+*d—丿abc*+d—一+*abcd解析：解析：此题考查的知识点是利用栈完成表达式的中后缀转换。顺序扫描表达式,操作数顺序输出,而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低,若高则入栈,否则出栈输出。本题中输出顺序为a输出,*进栈,(进栈,b输出,+进栈,c输出,此时)低于+,所以“+”输出。“）"与"（”相等，出栈删除，一低于*，所以*出栈，此时输出序列为abe+*,—入栈，输出d,输出一，结束。所以选B。为了处理参数及返回地址,在递归过程或函数调用时,要用一种称为（）的数据结构。（分数：2.00）队列多维数组栈丿线性表解析：解析：此题考查的知识点是栈的应用。要处理参数及返回地址，需要后进先出规则，应选C。A是先进先出规则，B是普通的存储结构，D是普通的逻辑结构。若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。（分数：2.00）1和52和4丿4和25和1解析：解析：此题考查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除front+1，插入rear+1，计算后rear=2，front=4，应选Bo队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作（）。（分数：2.00）上溢下溢假溢出丿队列满解析：解析：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度（容量）。已知有一维数组A[0,.mXn—1]，若要对应为m行、n列的矩阵，将元素A[k]（0Wk<mXn）表示成矩阵的第i行、第j列的元素（OWi（分数：2.00）i=k／n，j=k％mi=k／m，j=k％mi=k/n，j=k%n丿i=k／m，j=k％n解析：解析：本题是求一维数组向二维数组转化的问题。最简单的方法是把数组A的第0—n—l共n个元素放到数组B的第一行，数组A的第n一2n—1共n个元素放到数组B的第二行中，依此类推，数组A的最后n个元素放到数组B的最后一行中。求A[k]在数组B中的位置，应先确定A[k]处在哪一行，显然应该是k/n行；然后再确定处在k/n行的哪一列，显然是k%n。二、综合应用题（总题数：14，分数：28.00）综合应用题41-47小题。（分数：2.00）解析：简述栈、队列、循环队列的定义（分数：2.00）正确答案：（正确答案：（1）栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的兀素最先删除，故栈也称后进先出（LIFO）表。（2）队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO）表。（3）循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。）解析：假设以I和O分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由I和O组成的序列表示。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列?如能得到，请举例说明。（分数：2.00）正确答案：（正确答案：（1）通常有两条规则。第一是给定序列中I的个数和O的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，I的个数要大于或等于O的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C,则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的IOIOIO操作序列；对于合法序列BAC，我们使用IIOOIO操作序列。）解析：25•有5个元素，其入栈次序为A，B，C，D，E,在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？（分数：2.00）正确答案：（正确答案：3个：C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。提示：此题考查的知识点是栈的后进先出特点。按题意，C先出，说明A，B已入栈，D出栈再出栈，E可以入栈就出栈，可以有序列C，D，E，B，A。也可以B先出E再入，再出，得序列C，D，B，E，A。还可以B，A都出栈后，E再入栈出栈，得序列C，D，B，A，E。只有这三种情况。）解析：为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈si、s2都采用顺序栈方式，并且共享一个存储区[0〜maxsize—1]。设计共享存储空间的两个栈si、s2的入栈和出栈算法。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释；（分数：2.00）正确答案：（正确答案：（1）栈sl、s2共享向量空间，将两栈栈底设在向量两端。初始时，si栈顶指针为一1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。（2）算法设计如下：#definemaxsize／／两栈共享顺序存储空间所能达到的最多元素数#defineelemtpint//假设元素类型为整型typedefstruct｛elemtpstack[maxsize]；//栈空间inttop[2]； //top为两个栈顶指针stk；stks： //s是如上定义的结构类型变量，为全局变量①入栈操作：intpush（inti，intX）｛//入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右//边的栈s2，X是入栈元素。入栈成功返回1，否则返回0if（i<0IIi〉l）｛printf（”栈号输入不对”）；exit（0）；｝if（s.top[1]一s.top[0]==1）｛printf（"栈已满\n"）:return（0）;｝switch（i）｛case0：s.stack[++s.top[0/]/]=X；return1；break；case1：s.stack[一一s.top[1/]/]=X；return1；｝｝②退栈操作：elemtppop（inti）｛if（i<0||i〉l）｛printf（”栈号输入错误\n”）；exit（0）；｝switch（i）｛case0：if（s.top[0]==一l）｛printf（”栈空\n”）；return一1；｝elsereturns.stack[s.top[0]一]；case1:if（s.top[l]==maxsize）｛printf（”栈空\n”）；return一1；｝elsereturns.stack[s.top[1]++]；｝｝）解析：—个nXn的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？（分数：2.00）正确答案：（正确答案：n（n+1）/2（压缩存储）或n2（不采用压缩存储）。提示：此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为1，2,3，…，n之和。）解析：设有一个nXn的上三角矩阵(a”)，将其上三角中的元素按先行后列的顺序存于数组B[m]中，使得B[k]=a且k=f(i)f(j)+c,请推导出函数f、f和常数c,要求f和f中不含常数项。TOC\o"1-5"\h\zij 1 2 1 2 1 2(分数：2.00)正确答案：(正确答案：上三角矩阵第1行有n个元素，第i一1行有n一(i一1)+1个元素，第1行到第i—1行是等腰梯形，而第i行上第j个元素(即a)是第i行上第j一i+1个元素，故元素a在一维ij ij29•已知有一整数序列{a，a，a，…，a}。栈A中只保存整数，即序列中元素为整数时允许其入1 2 3 n栈。设计一个算法实现如下功能：用栈结构存储入栈的整数，当a工一1时，将a进栈；当a=一1i i i时，输出栈顶整数并出栈。(分数：2.00)正确答案：(正确答案：#definemaxsize//栈空间容量voidInOutS(intS[maxsize]){inttop=0： //top为栈项指针，定义top=0时为栈空for(i=1；i<=n；i++){//n个整数序列作处理ScaRf("%d"，&x)；//从输入整数序列if(X!=—1)//读入的整数不等于一1时入栈if(top==maxsize一l){printf(”栈满\n")；exit(0)；}elses[++top]=x； //x入栈else{//读入的整数等于一1时退栈if(top==0){printf("栈空\n")；exit(O)；}elseprintf(”出栈元素是％d\n",S[top—一])；}}})解析：30.设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是0(1)(不计new和dispose时间)。(分数：2.00)正确答案：(正确答案：本题要求用链接结构实现一个队列，可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p"，且要求入队和出队操作的时间复杂性是O(1)，因此用只设尾指针的循环链表来实现队列。(1)procaddq(varp：l°inkedlist,x：elemtp)； //p是数据域为data、链域为link的用循环链表表示的队列的尾指针new(s)； //申请新结点。假设有内存空间，否则系统给出出错信息sf.data：=x；sf.1ink：=pf.link； //将s结点入队pf.1ink：=s；p：=s；//尾指针p移至新的队尾endp；(2)procdeleq(Varp：linkedlist，Varx：elemtp)； //p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实//现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息if(pf.link==p)then{writeln("空队列”)：return(0)；}//带头结点的循环队列、else{s：=pf.linkf.link； //找到队头元素pf.linkf.link：=sf.link；//删队头元素x：=sf.data；//返回出队元素if(p==s)thenp：=pf.link；//队列中只有一个结点，出队后成为空队列dispose(s)； //回收出队元素所占存储空间}endp；提示：上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量"。)解析：31•判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组E[n]中，'#'为字符表达式的结束符。给出一个算法，用于判断表达式中括号('('和')')是否配对。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(分数：2.00)正确答案：(正确答案：(1)算法的基本思想：判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。在读入表达式结束符'#'时，栈中若只剩'#'表示括号全部配对成功；否则表示括号不匹配。另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。因假设栈容量足够大，因此入栈时未判断溢出。(2)算法的设计如下：intexyx(charE[],intn){//判断表达式中圆括号是否匹配chars[30]； //s是一维数组，容量足够大，用作存放括号的栈inttop=0； //top用作栈顶指针s[top]='#'； //'#'先入栈，用于和表达式结束符号'#'匹配inti=0；//字符数组E的工作指针while(E[i]!='#')//逐字符处理字符表达式的数组switch(E[i]){case'('：s[++top]='('；i++；break；case')'：if(s[top]=='('){top—一；i++；break；}else{printf(”括号不配对”)；exit(0)；}case'#':if(s[top]=='#'){printf("括号配对\n”)；return(l)：}else{printf(”括号不配对\n”)；return(O)；}//括号不配对default：i++；//读入其他字符，不作处理}})解析：32.从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、/四种运算，例如：234—34+2*$。(分数：2.00)正确答案：(正确答案：逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND，对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。floatexpr(){//从键盘输入逆波兰表达式，以'$'表示输入结束，本算法求逆波兰表达式的值floatOPND[30]； //OPND是操作数栈init(OPND)； //两栈初始化floatnum=0.0； //数字初始化scanf(”％C”，&x)； //x是字符型变量while(X!='$'){switch(X){case'0'：case'1'.case'2'case'3'：case'4'：case'5'：case'6'：case'7'：case'8'：case'9'：while((x〉='O'&&x<='9')||x==.')//拼数if(x!='.'){num=num*10+(ord(x)一ord('O'))；scanf(”％C”，&x)；}//处理整数else{//处理小数部分scale=10.0；scanf(”％C”，&x)；while(x〉='O'&&x<='9'){num=num+(ord(x)-ord('O'))/scale；scale=scale*10；scanf(”％c”，&x):}}//elsepush(OPND，hum)；hum=0.0；//数压入栈，下个数初始化case”：break；//遇空格，继续读下一个字符case'+'：push(OPND,pop(OPND)+pop(OPND))；break；case'-'：x1=pop(OPND)；x2=pop(OPND)；push(OPND，x2-x1)；break；case'*'：push(OPND，pop(OPND)*pop(OPND))；break；case'/'：x1=pop(OPND)；x2=pop(OPND)；push(OPND，x2/x1)；break；default：//其他符号不作处理}//结束switchscanf(”％c”，&x): //读入表达式中下一个字符}//结束while(x!='$')printf(”后缀表达式的值为％f”)；pop(OPND)； })解析：33•假设以I和0分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。(1)下面所示的序列中哪些是合法的?A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false(假定被判定的操作序列已存入一维数组中)。(分数：2.00)正确答案：(正确答案：(1)A和D是合法序列，B和C是非法序列。(2)设被判定的操作序列已存入一维数组A中。intJudge(charA[]){//判断字符数组A中的输入/输出序列是否是合法序列。如是，返回true， //否则返回falseinti=0： //i为下标intj=k=0； //j和k分别为I和字母0的个数while(A[i]!='\0'){switch(A[i]){case'I'：j++；break；//入栈次数增1case'0'；k++；if(k〉j){printf("序列非法\n”)；exit(0)；}}i++； //不论A[i]是'I'或'0'，指针i均后移}if(j!=k){printf("序列非法\n”)；return(false)；}else{printf("序列合法\n”)；return(true)：}}})解析：34.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。(分数：2.00)]、'{'、'}'，使用栈，正确答案：(正确答案：表达式中的括号有以下三对：'('、')'、'['当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对：否则，结论表达式括号不配对。int]、'{'、'}'，使用栈，Match(LinkedListla){//算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对charS[]； //s为字符栈，容量足够大P=la一〉link； //p为工作指针，指向待处理结点StackInit(S)；//初始化栈Swhile(P!=la){//循环到头结点为止switch(p一〉ch){case'('：push(s,p一〉ch)；break；case')'：if(StackEmpty(s)IIStackGetTop(s)!='('){printf(”括号不配对\n")；retum(O)：}elsepop(S)；break；case'['：push(s,p->ch)；break；case'['：if(StackEmpty(s)||StackGetTop(s)!=l['){printf(”括号不配对\n")；return(O)；}elsepop(S)；breakicase'{'：push(s，p->ch)；break；case'}'：if(StackEmpty(s)||StackGetTop(s)!='{'){printf(”括号不配对\n")：return(0)；}elsepop(S)：break；}P=p->lin