1.以下不属于面向对象程序设计语言的是(D)。
A.C++
B.Python
C.Java
D.C
题目解析
正确答案: D,C语言是面向过程的编译性语言
---------------------------------------------------------------------------------------------------------------------------------
2.以下奖项与计算机领域最相关的是(B)。
A.奥斯卡奖
B.图灵奖
C.诺贝尔奖
D.普利策奖
题目解析
正确答案: B,图灵奖是计算机领域的国际最高奖项
---------------------------------------------------------------------------------------------------------------------------------
3.目前主流的计算机储存数据最终都是转换成(A)数据进行存储。
A.二进制
B.十进制
C.八进制
D.十六进制
题目解析
正确答案: A,计算机中以二进制方式存储数据
---------------------------------------------------------------------------------------------------------------------------------
4.以比较作为基本运算,在N个数中找出最大数,最坏情况下所需要的最少的比较次数为(C)。
A.N2
B.N
C.N-1
D.N+1
题目解析
正确答案: C, 最值问题,以第一个数作为初始值,从第二个数开始比较,最坏情况下要比较到序列末尾才能得到最大值,即比较 N−1 次
---------------------------------------------------------------------------------------------------------------------------------
5.对于入栈顺序为a,b,c,d,e的序列,下列(D)不是合法的出栈序列。
A.a,b,c,d,e
B.e,d,c,b,a
C.b,a,c,d,e
D.c,d,a,e,b
题目解析
正确答案: D, acb进栈,c出栈,d进栈出栈,之后从栈顶到栈底还有b,a没有出栈,a无法在b之前先出栈
---------------------------------------------------------------------------------------------------------------------------------
6.对于有n个顶点,m条边的无向连通图(m>n),需要删掉(D)条边才能使其称为一棵树。
A.n-1
B.m-n
C.m-n-1
D.m-n+1
题目解析
正确答案: D, n个顶点的树有n−1条边,需删除 m-(n-1)= m-n+1 条边
---------------------------------------------------------------------------------------------------------------------------------
7.二进制数101.11对应的十进制数是(C)。
A.6.5
B.5.5
C.5.75
D.5.25
8.如果一棵二叉树只有根结点,那么这棵二叉树高度为1。请问高度为5的完全二叉树有(A)种不同的形态?
A.16B.15C.17D.32
题目解析
正确答案: A, h=5的完全二叉树共有 24 个节点,第五层最少1个节点,最多16个节点,因此一共有16种情况
---------------------------------------------------------------------------------------------------------------------------------
9.表达式a*(b+c)*d的后缀表达式为(B),其中“*”和“+”是运算符。
A.**a+bcd
B.abc+*d*
C.abc+d**
D.*a*+bcd
题目解析
正确答案: B, 考察前后缀表达式。表示为( a [ bc +] * ) d *,后缀表达式为 abc+*d*
---------------------------------------------------------------------------------------------------------------------------------
10.6个人,两个人组一队,总共组成三队,不区分队伍的编号,不同的组队情况有(B)。
A.10B.15C.30D.20
---------------------------------------------------------------------------------------------------------------------------------
11.在数据压缩编码种的哈夫曼编码方法,在本质是一种(B)的策略。
A.枚举
B.贪心
C.递归
D.动态规划
题目解析
正确答案: B, 哈夫曼编码每次把频率最低的两个节点合并,产生新的节点并放在集合中,删除用来合并的两个节点,重复这个过程直到剩下一个节点为止。每次选择频率最小的两个节点就是贪心的思想。
---------------------------------------------------------------------------------------------------------------------------------
12.由1,1,2,2,3这五个数字组成不同的三位数有(A)种。
A.18
B.15
C.12
D.24
题目解析
正确答案: A, 枚举法,不同的三位数有:321,322,311,312,211,212,213, 221, 223,231, 232, 112,113,121,122,123,131,132共十八种
---------------------------------------------------------------------------------------------------------------------------------
13.考虑如下递归算法
solve(n) if n=5 return n*solve(n-2) else return n*solve(n-1)则调用solve(7)得到的返回结果为(C)。
A.105B.840C.210D.420
---------------------------------------------------------------------------------------------------------------------------------
14.以a为起点,对右边的无向图进行深度优先遍历,则b,c,d,e四个点中有可能作为最后一个遍历到的点的个数为(B)。
A.1
B.2
C.3
D.4
题目解析
正确答案: B,从a→b方向的遍历:a−b−d−c−e; 从a→c方向的遍历:a-c-e-d-b和a−c−d−b−e. 则最多有两个终点:e和b
---------------------------------------------------------------------------------------------------------------------------------
15.有四个人要从A点坐一条船过河到B点,船一开始在A点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1,2,4,8,且两个人坐船的过河时间为两人独自过河时间的较大者。则最短(B)时间可以让四个人过河到B点(包括从B点把船开回A点的时间)。
A.14
B.15
C.16
D.17
题目解析
正确答案: B, 1和2从 A→B,1从B→A,此时A点有1,4,8 ;
B点有2,所用时间:2+1=3; 4和8从A→B,2从B→A。此时A点有1,2; B点有4,8,所用时间:8+2=10;
最后1和2从A→B,所用时间为2;总时间为3+10+2=15
---------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------
二、阅读程序(程序输入不超过数组或字符串定义的范围,共计40分)01 #include 02 03 int n;04 int a[1000];05 06 int f(int x)07 {08 int ret = 0;09 for(; x; x &= x - 1) ret ++;10 return ret;11 }12 13 int g(int x)14 {15 return x & - x;16 }17 18 int main()19 {20 scanf("%d", &n);21 for (int i = 0; i