习题集

习题集1求整数的二分序列算法如下，该算法的渐近时间复杂度函数是（）。voidbinary(intn){while(n){printf(%d\n,n);n=n/2;}}A、O(log(n))B、O(n*log2(n))C、O(n^2)D、O(n)正确答案：A2算法分析是为了分析算法的效率以求改进，那么算法分析的两个主要方面是（）。A、正确性和简明性B、空间复杂度和时间复杂度C、可读性和文档性D、数据复杂性和程序复杂性正确答案：B3下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2*n)的算法（3）最坏时间复杂度是指在最坏情况下，估算出来的算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A、(1)B、(1),(2)C、(1),(4)D、(3)正确答案：C4在下面程序段中，x赋值语句的频度是（）for(i=1;i(j=1;jA、O(2*n)C、O(n^2)D、O(log2(n))正确答案：C5下面有若干算法（关于问题规模n）的执行时间频度函数和若干渐近时间复杂度函数，请问以下哪个对应关系是正确的。(1)100*n^3(2)6*n^2-12*n+1(3)1024(4)n+2*log2(n)(5)n*(n+1)*(n+2)/6(6)2^(n+1)+100*n(a)O(1)(b)O(2^n)(c)O(n)(d)O(n^2)(e)O(log2(n))(f)O(n^3)A、(1)--(a)(2)--(b)(3)--(c)(4)--(d)(5)--(e)(6)--(f)B、(1)--(f)(2)--(d)(3)--(a)(4)--(c)(5)--(f)(6)--(b)C、(1)--(f)(2)--(e)(3)--(d)(4)--(c)(5)--(b)(6)--(a)D、(1)--(f)(2)--(b)(3)--(c)(4)--(e)(5)--(f)(6)--(b)正确答案：B6在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法正确答案：C7数据结构在计算机内存中的表示是指（）A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系正确答案：A8算法的计算量的大小称为算法的（）。A、效率B、复杂度D、难度正确答案：B9在数据结构中，从逻辑关系上可以把数据结构分成（）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构正确答案：C10算法的时间复杂度取决于（）。A、问题的规模B、待处理数据的初态C、A和BD、执行算法的计算机速度正确答案：C11在数据结构中，与所使用的计算机无关的是数据的（）结构。A、逻辑B、存储C、逻缉和存储D、物理正确答案：A12计算机执行下面的语句时，语句s的执行次数为（）。for(i=1;ifor(j=n;j=i;j--)s;A、n*(n+1)/2B、n*(n-1)/2C、n^2D、(n-2)*(n+3)/2正确答案：D13下面算法的渐近时间复杂度函数分别是（）。voidcombi(intn){inti,j,k;for(i=1;ifor(j=i+1;jfor(k=j+1;kprintf(%d,%d,%d,i,j,k);}}A、O(n)B、O(n^2)C、O(n^3)D、O(n*log(n))正确答案：C14循环队列的引入，目的是为了克服_______。A、假溢出时大量移动数据元素B、空间不够C、队列为空D、队列未分配空间正确答案：A15用I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，能够完成操作的序列称为合法序列，否则称为非法序列。下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOOA、ABB、ADC、CDD、BC正确答案：B16有数组elema[m+1]作为循环队列的存储空间，front为队头指示器，rear为队尾指示器，则出队操作的语句是A、front=front+1B、front=（front+1）%mC、rear=(rear+1)%(m+1)D、front=(front+1)%(m+1)正确答案：D17栈是操作受限的线性表，其插入和删除操作遵循_______的原则。A、FIFOB、FILOC、LILOD、以上都对正确答案：B18元素6，5，4，3，2，1依序进栈，请问下列哪个出栈序列是不合法的A、543612B、453126C、346521D、234156正确答案：C19表达式求值是_______应用的一个典型例子。A、队列B、线性表C、栈D、顺序表正确答案：C20假设用S表示入栈操作、X表示出栈操作。若元素入栈的顺序为1、2、3、4，为了得到1、3、4、2的出栈顺序，相应的S和X操作串是（）。A、SXSXSXSXB、SXSSXSXXC、SSSSXXXXD、SXXSSSXX正确答案：B21用单链表存储的队列，进行删除操作时，应该A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要修改正确答案：D22栈是操作受限的线性表，其运算遵循()的原则。A、先进先出B、同进同出C、后进先出D、先进不出正确答案：C23已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是s=(LinkedList)malloc(sizeof(LNode))；s-data=x;____________；r-next=s；r=s；A、r-next=s-nextB、r-next==s;C、s-next=r-nextD、s-next=r正确答案：C24表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂A、3,2,4,1,1；(*^(+*-B、3,2,8；(*^-C、3,2,4,2,2；(*^(-D、3,2,8；(*^(-正确答案：D25函数调用时，为处理参数及返回地址，要用一种称为（）的数据结构A、队列B、多维数组C、栈D、线性表正确答案：C26设有顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，若这6个元素出栈顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是A、2B、3C、5D、6正确答案：B27一个栈的输入序列是1、2、3，则不可能的栈输出序列是()。A、312B、123C、321D、以上都可能正确答案：A28下面的程序段执行完后，变量i值应该是：intfunc(intx){if(x0)returnx*func(x-1);elsereturn2;}inti;i=func(func(1));A、2B、4C、8D、无限递归正确答案：B29队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。A、先进先出B、先进后出C、先进不出D、后进不出正确答案：A30已知循环队列用数组A[0..m-1]存放元素，其头尾指示器分别是front和rear，则队列的元素个数是（）。A、rear-front+1B、rear-front+mC、(rear-front+m)%mD、(rear-front+1)%m正确答案：C31已知一个栈的进栈序列是1，2，3，…，n，输出序列是p1，p2，p3，...，pn，若p1＝3，则p2应该A、可能是2B、一定是2C、可能是1D、一定是1正确答案：A32链栈定义如下：typedefstructNode{intdata;structNode*next;}StackNode,*LStack;以下函数实现了(带头结点的)链栈初始化，请问________________处用哪条语句予以填充。voidInitStack(LStack*S){________________;}A、S=NULLB、S-next=NULLC、S.next=NULLD、以上都不对正确答案：B33有链栈定义如下：typedefstructNode{intdata;structNode*next;}StackNode,*LStack;以下函数实现了(带头结点)链栈上的进栈，请问空白处应用哪些语句予以填充。voidPush（LStack*S,intx）{LStackp;p=(LStack)malloc(sizeof(StackNode));________________;p-next=S-next;________________;}A、p-data=xS-next=p-nextB、S-next=pp-data=xC、p-data=xS=pD、p-data=xS-next=p正确答案：D34若栈中已有n个元素，在作进栈操作时发生了溢出，则说明该栈的最大容量是A、n-1B、nC、n+1D、n/2正确答案：B35若栈采用数组方式存储，现将两个栈共享一个数组v[0..m-1]的空间，数组元素top[i]代表第i个栈(i=1,2)栈顶，栈1的栈底在v[0]，栈2的栈底在v[m-1]，则栈满的判定条件应该是A、top[2]-top[1]的绝对值=0B、top[1]+1=top[2]C、top[1]+top[2]=mD、top[1]=top[2]正确答案：B36以下运算实现在(元素为整数的)链队列上的入队操作，请问空白处应用哪些语句予以填充。voidEnQueue(LinkQueue*q,intx){LNode*p;p=(LNode*)malloc(sizeof(LNode));________________=x;p-next=NULL;(q-rear)-next=________________;________________;}A、p-datapq-rear=pB、p-datapq-rear=p-nextC、p-datapq=pD、pp-dataq-rear=p正确答案：A37一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。A、321B、123C、213D、312正确答案：D38循环队列的队满条件应该是（提示：队尾指示器始终指向末元素的下一个可用空位）A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.front+1)%maxsize==sq.rearC、(sq.rear+1)%maxsize==sq.frontD、sq.rear==sq.front正确答案：C39栈和队列的共同点是A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点正确答案：C40循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是()A、(rear-front)%mB、(rear-front+1)%mC、(front-rear+1)%mD、rear-front正确答案：B41队列是限制插入只能在表的一端、删除在表的另一端进行的线性表，其特点是()。A、LILOB、LIFOC、FILOD、以上都不对正确答案：A42顺序栈定义如下：typedefstruct{intdata;inttop;//等于实际栈顶元素的下标intstacksize;intincrementsize;}SqStack;以下函数实现了退栈操作，请问空白处应用哪些语句予以填充。intPop(SqStack*S,int*x){if(________________)return0;*x=________________;S-top=________________;return1;}A、S-top==0S-elem[S-top]S-top-1B、S-top==-1S-elem[S-top]S-top-1C、S-top==-1S-top-1S-elem[S-top]D、S-top==0S-to