二、不定项选择题
1. 如果对于所有规模为n的输入,一个算法均恰好进行(A)次运算,我们可以说该算法的时间复杂度为O(2^n)。
A.2^(n+1) B.3^n C.n2^n D.2^2n
Wrong answer:AC
解析:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。在考虑时间复杂度时,忽略这个函数的低阶项和首项系数,主要看最高阶项,2^(n+1)=22^n。
-
一棵二叉树一共有19个结点,其叶子结点可能有(ABC)个。
A.1 B.9 C.10 D.11
Wrong answer:/
解析:一棵任意形态的n个节点的数的二叉树的叶子数范围是1~floor((n+1)/2)。 -
十进制下的无限循环小数(不包括循环节内的数字均为0或均为1的平凡情况),在二进制下有可能是(A)。
A.无限循环小数(不包括循环节内的数字均为0或均为1的平凡情况) B.无限不循环小数 C.有限小数 D.整数
Wrong answer:AB
解析:小数转化为二进制用乘法,先排除整数和有限小数,因为是十进制循环小数,每次乘2取整后的数都一样,一直循环再下去就成了无限循环小数。 -
以下关于计算复杂度的说法中,正确的有(BD)。
A.如果一个问题不存在多项式时间的算法,那它一定是NP类问题
B.如果一个问题不存在多项式时间的算法,那它一定不是P类问题
C.如果一个问题不存在多项式空间的算法,那它一定是NP类问题
D.如果一个问题不存在多项式空间的算法,那它一定不是P类问题
Wrong answer:/
解析:NP问题是指存在多项式算法能够验证的非决定性问题,而其中NP完全问题又是最有可能不是P问题的问题类型。所有的NP问题都可以用多项式时间归约到他们中的一个。所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解,当且仅当所有的其他的NP-完全问题也可以在多项式时间内求解。
P问题是具有多项式算法的判定问题。这里的P代表Polynomial。P问题就是可以有一个确定型图灵机在多项式时间内解决的问题。即那些存在O(n),O(n^k),O(nlogn)等多项式时间复杂度解法的问题。比如排序问题、最小生成树、单源最短路径。直观的讲,我们将P问题视为可以较快解决的问题。
三、问题求解
1.256
Wrong answer:/
解析:对于p,q,r三个变量,每个变量可取0和1两种值,可以得到有8种组合。对于每种组合,带入表达式只有0和1两种答案。因此两两不等价的表达式只有2^8=256种。
2.5536
Wrong answer:/
解析:这道题考察DP,可以发现题目给出的是一棵二叉树,那么可以做一遍树形DP:
设g[i]表示以i为根的子树的独立集数;f[i][0]表示不选i号节点,以i为根的子树的独立集数;f[i][1]表示选i号节点,以i为根的子树的独立集数;
显然有g[i]=f[i][0]+f[i][1],lc为左儿子,rc为右儿子,那么有f[i][0]=g[rc],f[i][1]=f[lc][0]*f[rc][0]。最后答案为g[root]。
四、阅读程序写结果
3.(1)7
Wrong answer:/
(2)2004
Wrong answer:/
解析:本题由代码可知是统计合并的次数,合并的过程执行一次便统计一次。合并的条件是data[h]=data[h-1],自己写几个数据后归纳出最后data[]数组中的数据为:1024,512,256,128,64,16,8,4。即:2012=1024+512+256+128+64+16+8+4,即最终的结果是将输入的一个数通过归并的方式拆分成若干个2的整数次方的和,而2^m需要2^{m-1}次合并,所以最终结果为1023+511+255+127+63+15+7+3=2004,故答案为2004。另一个输入8自然也就输出7了。
五、完善程序
2.(1)return (k%c)+1
wrong answer:/
(2)s[n]=q[tail]
Wrong answer:/
(3)q[head]
Wrong answer:/
(4)q[head]
Wrong answer:/
(5)q[tail]
Wrong answer:/
(6)next(head)
Wrong answer:/
解析:题目说的很清楚,思考一下,本题的思路是前c个数用循环队列来维护,用direction来记录这个队列的方向,如果需要翻转,就在这个队列里翻转即可。push就是看队列里有没有满,满了就先让一个数到s这个栈里,再加入队列,否则直接加入。而pop则只需要看队列里还有没有数,有就直接输出,否则ERROR。那弹出之后如果队列不满且s中还有数,就可以将s中的数弹出放入队列中。
大部分解析都是看了别人的文章的。
版权声明:本文为CSDN博主「Da_un」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/Da_un/article/details/120171639