CSP第一轮测试模拟题四

83、分辨率为1920*1080的真彩色位图图像所占用的存储空间为（）

A、6075KB

B、4050KB

C、2025KB

D、8100KB

84、已知rand()可以生成一个0到32767的随机整数，如果希望得到一个范围在[a,b)的随机整数，a和b均为不超过100的正整数且a<b,那么可形的表达式是（）

A、(rand()%(b-a))+a

B、(rand()%(b-a+1))+a

C、(rand()%(b-a))+a+1

D、(rand()%(b-a+1))+a+1

85、AI是（）的英文缩写

A 、Automatic Intelligence

B 、Artificial Intelligence

C、Automatic Information

D、Artificial Information

86、下列四个不同进制的数中，与其它三项数值上不相等的是（）

A、(269)16

B、(617)10

C、(1151)8

D、(1001101011)2

87、在一条长度为1的线段上随机取两个点，则以这两个点位为端点的线段的期望长度是（）

A、1/2

B、1/3

C、2/3

D、3/5

88、二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是（）

A、01 0010 1000 1011

B、01 0010 1000 0011

C、01 0010 1001 0011

D、01 0010 1000 0001

89、据说古希腊拜拉图学院门口立了一块牌子，“不懂几何者禁止入内”。有一天来了一群人，他们都是懂几何的人，那么他们（）

A、可能会被允许进入

B、一定会被允许进入

C、一定不会被允许进入

D、不可能不被允许进入

90、高度为n的均衡的二叉树是指，如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根节点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）

A、10

B、11

C、12

D、13

91、关键字序列(8、9、10、4、5、6、20、1、2)只能是系列排序算法中（）两趟排序后的结果

A、选择排序

B、冒泡排序

C、插入排序

D、快速排序

92、一颗二叉树具有10个度为2的结点，5个度1的结点，则度为0的结点的个数是（）

A、9

B、11

C、15

D、不能确定

93、前序遍历序列与中序遍历序列相同的二叉树为（）

A、根结点无左子树的二叉树

B、根结点无右子树的二叉树

C、只有根结点的二叉树或非叶子结点只有左子树的二叉树

D、只有根结点的二叉树或非叶子结点只有右子树的二叉树

94、关于拓扑排序，下面说法正确的是（）

A、所有连通的有向图都可以实现拓扑排序

B、对一个图而言，拓扑排序的结果是唯一的

C、拓扑排序中入度为0的结点总会排在入度大于0的结点的前面

D、拓扑排序结果序列中的第一个结点一定是入度为0的点。

95、将2个红球，1个蓝球，1个白球放到10个编号不同的盒子中去，每个盒子最多放一个球。有（）种放法。

A、5040

B、2520

C、420

D、1260

96、已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为节点的编号，以下同)，中根遍历是4 2 6 5 1 7 3，则二叉树的后根遍历是（）

A、4 6 5 2 7 3 1

B、4 6 5 2 1 3 7

C、4 2 3 1 5 4 7

D、4 6 5 3 1 7 2

97、全完二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第K号节点的父节点如果存在的话，应当存放在数组的（）号位置

A、2K

B、2K+1

C、k/2下取整

D、(k+1)/2下取整

98、广度优先搜索时，需要用到的数据结构是（）

A、链表

B、队列

C、栈

D、散列表

99、在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）

A、程序运行时理论上所占的内存空间

B、程序运行时理论上所占的数组空间

C、程序运行时理论上所占的硬盘空间

D、程序源文件理论上所占的硬盘空间

100、（）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题.....直到最后的子问题可以简单的直接求解。而原问题的解就是子问题的解的并。

A、动态规划

B、贪心

C、分治

D、搜索

101、地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（）

A、128KB

B、1MB

C、1GB

D、4GB

102、如果对于所有规模为n的输入，一个算法均恰好进行（）次运算，我们可以说该算法的时间复杂度为O(2n).

A、2(n+1)

B 、3n

C、n*2n

D、2(2n)

103、（）的平均时间复杂度为O(nlogn)，其中n是待排序的元素个数。

A、快速排序

B、插入排序

C、冒泡排序

D、基数排序

104、T(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式T(n)=2*T(n/2)+2n,那么T(n)=（）.

A、O(n)

B、O(nlogn)

C、O(n2)

D、O(n2logn)

105、链表不具有的特点是（）

A、不必事先估计存储空间

B、可随机访问任一元素

C、插入删除不需要移动元素

D、所需空间与线性表长度成正比

106、在无向图中，所有顶点的度数之和是边数的（）倍。

A、0.5

B、1

C、2

D、4

107、同时查找2n个数中的最大值和最小值，最少比较次数为（）

A、3(n-2)/2

B 、4n-2

C 、3n-2

D 、2n-2

109、某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n为正整数)及T(0)=1，则该算法的时间复杂度为（）

A、O(logn)

B、O(nlogn)

C、O(n)

D、O(n2)

109、线性表若采用链表存储结构，要求内存中可用存储单元地址（）

A、必须连续

B、部分地址必须连续

C、一定不连续

D、连续不连续均可

110、双向链表中有两个指针域，llink和rlink,分别指向前驱和后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q,则正确的插入为（）

A、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p>llink;

B、q->llink=p->llink; p->llink->rlink=q;q->rlink=p;p->llink=q->rlink;

C、q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;

D、p->llink->rlink=q;q->rlink=p;q->llink=p-llink;p->llink=q;

111、有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种方法。

A、7

B、8

C、21

D、37

112、假设某算法的计算时间表示为递推关系式T(n)=2T(n/4)+sqrt(n),T(1)=1，则算法的时间复杂度为（）

A、O(n)

B 、O(sqtr(n))

C、O(sqrt(n)logn)

D、O(n^2)

113、给定含有n个不同的数的数组L=<x1,x2,.....xn>.如果L中存在xi(1<i<n)使得x1<x2<......<xi-1<xi>xi+1>.....xn,则称L是单峰的，并称xi是L的“峰顶”。现在已知L是单峰的，请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。
a.search(k+1,n)
b.search(1,k-1)
c.return L[k]
Search(1,n)
1.k←Ln/2」
2.If L[k]>L[k-1] and L[k]>L[k+1]
3.then______
4.else if L[k]>L[k-1] and L[k]<L[k+1]
5.then _______
6.else _______
正确的填空顺序是()

A.c,a,b

B.c,b,a

C.a,b,c

D.b,a,c

114、向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行（）

A.hs->next = s;

B.s->next = hs;hs=s;

C.s->next=hs->next;hs->next=s;

D.s->next=hs;hs=hs->next;

115、若某算法的计算时间表示为递推关系是T(N)=2T(N/2)+N log N,T(1)=1则该算法的时间复杂度为（）

A、O(N)

B、O(NlogN)

C、O(N(logN)^2)

D、O(N^2)

116、由四个不同的点构成的简单无向连通图的个数是（）

A、32

B、35

C、38

D、41

117、根节点深度为0，一棵深度为h的满k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有（）个结点。

A、(k^(h+1)-1)/(k-1)

B、k^(h-1)

C、k^h

D、(k^(h-1))/(k-1)

118、由四个没有区别的点构成的简单无向连通图的个数是（）

A、6

B、7

C、8

D、9

119、一些数字可以颠倒过来看，例如0,1,8颠倒过来还是本身，6颠倒过来是9,9颠倒过来看还是6，其他数字颠倒过来都不构成数字，类似的一些多位数也是可以颠倒过来看，比如106颠倒过来是901.假设某个城市的车牌只有5位数字组成，每一位都可以取0到9.请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌（）

A、75

B、100

C、125

D、60

120、假设一颗二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则前序遍历序列为（）

A、ABCDEFGHIJ

B、ABDEGHJFIC

C、ABDEGHJCFI

D、ABDEGJHCFI