1、计算机专业基础综合（数据结构）模拟试卷 2 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 栈和队列的主要区别在于( )。（A）它们的逻辑结构不一样（B）它们的存储结构不一样（C）所包含的运算不一样（D）插入和删除运算的限定不一样2 若循环队列以数组 Q0m-1作为其存储结构，变量 rear。表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。（A）rear-length（B） (r
2、earlength+m)MOD m（C） (rearlength+1+m)MOD m（D）m-length3 一个以向量 Vn存储的栈，其初始栈顶指针 top 为 n+1，则对于 x，其正确的进栈操作是( )。（A）top=top+1；Vtop=x（B） Vtop=x；top=top+1（C） top=top-1；Vtop=x（D）Vtop=x ；top=top-14 为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在( )。（A）内存空间的首地址（B）内存空间的尾地址（C）内存空间的两端（D）内存空间的中间5 已知输入序列为 abcd，经
3、过输出受限的双端队列后，能得到的输出序列是( )。（A）dacb（B） cadb（C） dbca（D）以上答案都不对6 假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第i(1in)个出栈的元素是( )。（A）不确定（B） n-i+1（C） i（D）n-i7 假设一个序列 1，2，3，n 依次进栈，如果第一个出栈的元素是 i，那么第 i个出栈的元素是( ) 。（A）i-j1（B） i-j（C） ji+1（D）不确定的8 已知当前栈中有 n 个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为( )。（A）n-1（B） n（C） n+1
4、（D）n29 设有 5 个元素 a，b，c ， d，e 顺序进栈，下列几个选项中，不可能的出栈序列是( )。（A）a，b， c，d，e（B） d，e，c ，b，a（C） a，c ，e ，b，d（D）c，b， a，d，e10 有 6 个元素按 6，5，4，3，2，1 的顺序依次进栈，不合法的出栈序列是( )。（A）543612（B） 453126（C） 346521（D）23415611 有 5 个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C；D 最先出栈的次序不包括( )。（A）CDEBA（B） CDBEA（C） CDBAE（D）CDAEB12 对于 4 个元素依
5、次进栈，可以得到( )种出栈序列。（A）10（B） 12（C） 14（D）1613 现有两栈，其共享空间为 V1m，topi 代表第 i 个栈(i=1 ，2) 栈项，栈 1 的底在 V1，栈 2 的底在 Vm，若两栈均采用顺序存储方式存储，则栈满的条件是( )。（A）|top2-top1|=0（B） top1+1=top2（C） top1+top2=m（D）top1=top214 一个递归算法必须包括( )。（A）递归部分（B）终止条件和递归部分（C）迭代部分（D）终止条件和迭代部分15 执行完下列语句段后，i 值为( )。int f(int x)return(x0)?x*f(x1)：2)：i
6、=f(f(1)；（A）2（B） 4（C） 8（D）无限递归16 表达式 a*(b+c)一 d 的后缀表达式是( )。（A）abcd*+一（B） abc+*d（C） abc*+d（D）一+*abcd17 为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( )的数据结构。（A）队列（B）多维数组（C）栈（D）线性表18 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为( )。（A）1 和 5（B） 2 和 4（C） 4 和 2（D）5 和 119 队尾已到达一
7、维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。（A）上溢（B）下溢（C）假溢出（D）队列满20 已知有一维数组 A0,.mn 一 1，若要对应为 m 行、n 列的矩阵，将元素 Ak(0kmn)表示成矩阵的第 i 行、第 j 列的元素(0i1)printf(”栈号输入不对 ”)；exit(0)； if(s top1一 stop0=1)printf(“栈已满n“)：return(0); switch(i)case 0：sstack+stop0=X；return 1；break；case 1：sstack一一 stop1=X；return 1；退栈操作：ele
8、mtp pop(int i)if(i1)printf(”栈号输入错误n”)；exit(0) ； switch(i)case 0：if(stop0=一 1)printf(”栈空n”)；return 一 1；else return sstacks top0-；case 1：if(stop1=maxsize)printf(”栈空n”)；return 一 1；else return sstacks top1+；【知识模块】 数据结构25 【正确答案】 n(n+1) 2(压缩存储)或 n2(不采用压缩存储)。 提示：此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为1，2，3
9、，n 之和。【知识模块】 数据结构26 【正确答案】 上三角矩阵第 1 行有 n 个元素，第 i 一 1 行有 n 一(i 一 1)+1 个元素，第 1 行到第 i1 行是等腰梯形，而第 i 行上第 j 个元素( 即 aij)是第 i 行上第 j一 i+1 个元素，故元素 aij 在一维数组中的存储位置(下标 k)为： k=(n+(n 一(i1)+1)(i 一 1)2+(ji+1)=(2ni+2)(i 1)2+j-i+1 进一步整理为：【知识模块】 数据结构27 【正确答案】 #define maxsize 栈空间容量void InOutS(int Smaxsize)int top=0： top 为栈项指针，定义 top=0 时为栈空for(i=1；i=0(3)int queue_empty() 本算法判用栈 s1 和 s2 模拟的队列是否为空if(sempty(s1)&sempty(s2)return(1)； 队列空else return(0)； 队列不空【知识模块】 数据结构
