选择题1.在Linux系统终端中,用于列出当前目录下所含的文件和子目录的命令为()。A.lsB.cdC.cpD.all
【解析】Linux系统中:ls命令用于显示指定工作目录下之内容(列出目前工作目录所含之文件及子目录);cd命令用于切换当前工作目录;cp命令主要用于复制文件或目录;all只是用来凑数的,没什么实际意义
故选A。2.二进制数001010102和000101102的和为()。001111002D.010000102010000002A.001111002B.010000002C.【解析】这是一个最基本的二进制加法,出现了连续的进位算出来是故选B。3.在程序运行过程中,如果递归调用的层数过多,可能会由于()引发错误。A.系统分配的栈空间溢出B.系统分配的队列空间溢出C.系统分配的链表空间溢出D.系统分配的堆空间溢出【解析】递归需要使用到系统堆栈空间,如果递归层数过多,导致系统堆栈空间不足。故选A。4.以下排序方法中,()是不稳定的。A.插入排序B.冒泡排序C.堆排序D.归并排序【解析】待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj(即i 【解析】当树为完全二叉树时的高度为最小,所以故选B。9.210≤2021<211 前序遍历和中序遍历相同的二叉树为且仅为()。A.只有1个点的二叉树B.根结点没有左子树的二叉树C.非叶子结点只有左子树的二叉树D.非叶子结点只有右子树的二叉树【解析】前序遍历:先根再左子树后右子树,中序遍历:先左子树再根后右子树。所以去掉左子树时两个相同,选择D。10.定义一种字符串操作为交换相邻两个字符。将DACFEB变为次上述操作。A.7B.8C.9D.6【解析】ADCFEB->ACDFEB->ACDEFB->ACDEBF->ACDBEF-> ABCDEF最少需要()ACBDEF->ABCDEF,共7次,故选A。11.有如下递归代码solve(t,n):ift=1return1 elsereturn5*solve(t-1,n)modn 则solve(23,23)的结果为()。A.1B.7C.12D.22【解析】程序的运行结果为522mod23,根据用费马小定理,在p为素数的情况下,ap-1≡1(modp),所以522≡1(mod23),故选A。12.斐波那契数列的定义为:F1=1,F2=1,Fn=Fn−1+Fn−2(n≥3)。现在用如下程序来计算斐波那契数列的第n项,其时间复杂度为()。F(n): ifn<=2return1 elsereturnF(n-1)+F(n-2) A.O(n)B.O(n2)C.O(2n)D.O(nlogn) 【解析】时间复杂度 f(n)=f(n-1)+f(n-2)每一层都包含一个加法操作 例如n=8时,T(n)=2^0+2^1+2^2+2^3+2^4+2^5+2^6=2^7-1O(n)=2^7-1=2^n 故选C。13.有8个苹果从左到右排成一排,你要从中挑选至少一个苹果,并且不能同时挑选相邻的两个苹果,一共有()种方案。A.36B.48C.D.【解析】选1个苹果,有8种结果。6+5+4+3+2+1=21种。种。选2个苹果,可以固定第一个往后,有选3个苹果,有4+3+2+1+3+2+1+2+1+1=20选4个苹果,有5种。所以总数故选C。14.设一个三位数8+21+20+5=8+21+20+5=。n=a,b,c,其中a,b,c均为1到9之间的整数,若以a,b,c作为三角形的三条边可以构成等腰三角形(包括等边),则这样的n有()个。A.81B.120C.165D.216【解析】考虑a=b≠c有几种。1,1无解。2,2有2+2−1−1=22种。同理,3,3有4种,4,4有6种,后面5到9都是所以8种。8×5+6+4+2=52。而a=b=c有9种。所以52×3+9=165。故选C。15.有如下的有向图,节点为A,B,…,J,其中每条边的长度都标在图中。则节点A到节点J的最短路径长度为()A.16B.19C.20D.22【解析】单源最短路径问题,没有负边权,可以用dijkstra算法模拟一下。故选B。首先先看一下程序,通过求t可以猜出这是三维坐标系。还有因为r可以大致猜测是球。cos60∘=0.5,而60∘在弧度制下就是π/3。π/3,所以本题和球关系很大,而d是半径。可以猜测一下,因为V=4/3πr3,r是16.将第21行中t的类型声明从int改为double,不会影响程序运行的结果。()没有任何下取整的操作,并且结果也是double不影响,故判对。17.将第26、27行中的/sqrt(t)/2替换为/2/sqrt(t),不会影响程序运行的结果。()这里sqrt是小数,若先除以2会默认下取整。故判错。18.将第28行中的x*x改成sq(x)、y*y改成sq(y),不会影响程序运行的结果。()sq()函数内是算int类型的平方,这里的x和y都是double类型。故判错。19.(2分)当输入为00011001时,输出为1.3090。()手动模拟,这个不会难算。结果为5π/12估算一下,差不多,故判对。20.当输入为11111112时,输出为()。A.3.1416B.6.2832走特判,所以C.4.7124 D.4.1888 4/3πr3直接带进去,其中r取1,故选D。21.(2.5分)这段代码的含义为()。A.求圆的面积并B.求球的体积并C.求球的体积交D.求椭球的体积并根据上面的分析和特判的min,所以判断是交,故选C。阅读程序后,发现这是在求最大子段和。先看solve2再看solve1会更轻松,不过其实把判断题带进去也很好22.程序总是会正常执行并输出两行两个相等的数。()确实。判对。23.第28行与第38行分别有可能执行两次及以上。()考虑二分到最边界,此时(n,n+1)会分成(n,n)和(n+1,n+1),相等情况被特判走了,所以不会走那两行特判。若开头输入的故判错。24.当输入为5-1011-95-7时,输出的第二行为“7”。()n=5,所以这一段的最大字段和为n<0n<0,也只会分别执行一次。11,故判错。25.solve1(1,n)的时间复杂度为()。A.O(logn) B.O(n) C.O(nlogn)D.O(n!) T(n)=2T(n/2)+1T(n)=2n−1故选B。26.solve2(1,n)的时间复杂度为()。A.O(logn)B.O(n)C.O(nlogn)D.O(n!) T(n)=2T(n/2)+nO(nlogn)故选C。27.当输入为10-32100--4-594时,输出的第一行为()。A.13B.17C.24D.12 n=10,所以最大字段和为2100--4-594,为17。(3)粗略扫过去可以发现是加密和解密过程。28.程序总是先输出一行一个整数,再输出一行一个字符串。()根据同学的说法,可能因为空串没东西,空串凭什么不是字符串(恼)。29.对于任意不含空白字符的字符串str1,先执行程序输入0str1,得到输出的第二行记为str2;再执行程序输入1str2,输出的第二行必为str1。()既然是加密和解密,这两个必然相同。故判对。30.当输入为1SGVsbG93b3JsZA==时,输出的第二行为HelloWorld。(手动模拟,判错。31.设输入字符串长度为n,encode函数的时间复杂度为()。A.Θ,O(n)B.O(n)C.O(nlogn) D.O(n!) 看程序,是O(n)的,故选B。32.输出的第一行为()。A.0xffB.255C.0xFFD.-1 怎么说,有的人电脑是-1有的人是255。等最后官方通知。答案是D。33.(4分)当输入为0CSP2021csp时,输出的第二行为()。A.Q1NQMjAyMWNzcAv=B.Q1NQMjAyMGNzcA==C.Q1NQMjAyMGNzcAv=D.Q1NQMjAyMWNzcA== 模拟,选D。)三、完善程序(单选题,每小题3分,共计30分)(1)(魔法数字)小H的魔法数字是法和整除运算得到4。给定n,他希望用若干个4进行若干次加法、减n。但由于小H计算能力有限,计算过程中只能出现不超过M=10000 的正整数。求至少可能用到多少个4。例如,当n=2时,有2=(4+4)/4,用到了3个4,是最优方案。试补全程序。本题类似dijkstra,每次选择已经确定最小操作的数字来转移到其他数字。而vis记录已经确定不会再更改操作数的数。34.①处应填()A.F[4]=0B.F[1]=4C.F[1]=2D.F[4]=1首先4需要的操作数是1,1需要的是2。对于程序来说,都是小操作数转移到大操作数。故选D,35.②处应填()A.!Vis[n]C.F[M]==INT_MAX B.r 结束掉件首先肯定是n已经算出来了。但r似乎对本题没有任何影响……当Fn有值时也不一定是最优的,只有当Fn作为可以去转移别人的时候才是最优的。故选A。36.③处应填()A.F[i]==rC.F[i] B.p->son[1]=S[top--]D.S[top--]->son[1]=p 这部分是在建笛卡尔树,笛卡尔树就是对于序列区间然后再跑(l,r),选取最大值x做为这区间的根,(l,x−1)和(x+1,r),再和这两个区间的根连边。可以用单调栈来解决。对于栈顶小于当前元素的情况,显然可以不断弹出,使当前元素找到他最大的左二子。故38题选A。39.②处应填()A.p->son[0]=S[top]C.S[top]->son[0]=p B.p->son[1]=S[top]D.S[top]->son[1]=p 而上述操作结束后,栈顶的元素就比当前元素大,所以可以先把栈顶的右儿子设为当前元素。若后面出现更大的也会覆盖掉。故39题选D。40.③处应填()A.x->dep B.x 其实在建完笛卡尔树后,val就没有用处了。这部分的min是在处理st的时候用的,所以是考虑深度。另外都min了不可能去操作max的方法吧((故选A。41.④处应填()A.A[i*b+j-1]==A[i*b+j]->son[0]B.A[i*b+j]->valvalC.A[i*b+j]==A[i*b+j-1]->son[1]D.A[i*b+j]->depdep因为只有+1和−1两种情况,所以按照题目说法,这里的二进制也是表示这个,用来存储本块内的情况。故选D。42.⑤处应填()A.v+=(S>>i&1)?-1:1B.v+=(S>>i&1)?1:-1C.v+=(S>>(i-1)&1)?1:-1D.v+=(S>>(i-1)&1)?-1:1这里是预处理出块内所有的2b−1种情况,方便到时候O(1))算。+1。因为刚刚是后者小于前者时为1。所以为1的时候应该−1,反之另外注意一下i是从1开始的。故选D。43.⑥处应填()A.(Dif[p]>>(r-p*b))&((1<<(r-l))-1)B.Dif[p] C.(Dif[p]>>(l-p*b))&((1<<(r-l))-1) D.(Dif[p]>>((p+1)*b-r))&((1<<(r-l+1))-1) 对于一个块内的查询(l,r)。这里的S是要确认本区间的状态。而刚刚的Dif已经预处理好了,p是块的位置。所以选C。 因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- efsc.cn 版权所有 赣ICP备2024042792号-1
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务