第一部分 单项选择题
1、给定二叉树如图,设 N代表二叉树的根,L代表节点的左子树,R代表节点的
右子树。若遍历后的节点序列为 2、6、4、7、1、3、5,则其遍历方式是______。
LRN
NRL
RLN
LNR
2、下列关于无向连通图特性的叙述中,正确的是______。
Ⅰ.所有顶点的度之和为偶数
Ⅱ.边数大于顶点个数
Ⅲ.至少有一个顶点的度为 1
只有Ⅰ
只有Ⅱ
Ⅰ和Ⅱ
Ⅰ和Ⅲ
3、10个相同的糖果,分给三个人,每个人至少要得一个。有 种不同分
法。
33
34
35
36
4、2个人,一人只说真话,一人只说假话,如何只问其中某个人一句话,就分
辨出谁是说真话的,谁是说假话的?______。
问任何一人:你是说真话的,对吗
指着其中一人,问另一人:他是说真话的,对吗
指着其中一人,问另一人:他是说假话的,对吗
做不到
5、频繁的插入删除操作使用____结构比较合适。
数组
队列
链表
栈
6、以下访问速度最快的设备是 。
寄存器
内存
磁盘
L1 Cache
7、一个容器类数据结构,读写平均,使用锁机制保证线程安全。如果要综合提
高该数据结构的访问性能,最好的办法是______。
只对写操作加锁,不对读操作加锁
读操作不加锁,采用 copyOnWrite 的方式实现写操作
分区段加锁
无法做到
8、考虑如下程序存在的问题是__________。
class A {
public:
A(B* b) : _b(b) {}
~A() {delete b;}
private:
B* _b;
};
int main()
{
B b;
A(&b);
return 0;
}
double free
stack free
memory leak
无以上问题
9、对于二分查找算法下面描述正确的是 。
只能用于数组
只能用于链表
只能在已经排序的数据上进行查找
最坏情况下时间复杂度是 O(N*logN)
10、在
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个离线的大数据处理系统,下面哪个性能指标不是系统追求的?
健壮性
高吞吐
低延迟
处理的数据规模
11、下列叙述中正确的是 。
循环队列有队头和队尾两个指针,因此,循环队列是非线性结构
在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况
在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况
循环队列中元素的个数是由队头指针和队尾指针共同决定
12、下面序列中,哪一种序列 不可能是一个二叉搜索树的后序遍历结
果?
1,2,3,4,5
1,2,5,4,3
5,4,3,2,1
3,5,1,4,2
13、在 linux中,列举当前目录下文件的是哪个命令______。
ps
cd
mv
ls
14、已知一棵有 2014 个结点的树,其叶结点个数为 116,该树对应的二叉树
中无左孩子结点或右孩子结点的结点个数是______。
118
119
1898
1899
15、已知一个递归算法的算法复杂度计算公式为 T(n)=T(n/2)+n,则 T(n)的算法
复杂度为____。
O(n)
O(logn)
O(n2)
O(nlogn)
16、在长度为 n的有序线性表中进行二分查找,需要的比较次数为______。
log n
n log n
n/2
(n+1)/2
17、甲乙两人玩掷骰子,比谁掷出的点数大,点数大的获胜。如果一样大,那么
就是平局。请问甲赢的概率是______。
1/4
1/3
5/12
1/2
18、假设某虚拟存储系统的物理内存只有 3个页(page),当进程 A访问虚拟页
的序列依次是 1, 2, 3, 4, 2, 7, 5, 3, 5, 7, 4, 3, 当页面淘汰算法为先进
先出(FIFO)且内存在刚开始为空,那进程 A遭遇的页面失效次数为_____。
7 次
8 次
9 次
10 次
19、下列代码的输出结果是
int i=-1;
unsigned j=1;
if (i
i)
printf("(j>i)成立\n");
else
printf("(j>i)不成立\n");
(ii)成立
(ii)不成立
(ii)成立
(ii)不成立
20、在 N个乱序数字中查找第 k大的数字,时间复杂度可以减小至 。
O(N*logN)
O(N)
O(1)
O(N^2)
第二部分 不定项选择题
21、一个二进制网络通信
协议
离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载
的报文,包头定长,除了包头以外,可以携带长度
和内容都不定的负载,设计报文
格式
pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载
时,可以用____方式,确保协议处理程序能
够正确识别每一个报文。
在包头中第一个定长字段中写明报文全长
在包头中某个定长字段中写明负载负载长度
在报文头尾加固定长度的边界符
使用定长报文,如负载超长,则分片
22、下面属性中,是事物(Transaction)属性的有____。
原子性(Atomic)
并发性(Concurrency)
一致性(Consistent)
隔离性(Isolated)
持久性(Durable)
23、 程序
struct T {
char a;
int *d;
int b;
int c:16;
double e;
};
T *p;
在 64位系统上以下描述正确的是 。
sizeof(p) == 8
sizeof(*p) == 32
sizeof(p->a) == 1
sizeof(p->e) == 4
24、一个二进制网络通信协议的报文,包头定长,除了包头以外,可以携带长度
和内容都不定的负载,设计报文格式时,可以用______,确保协议处理程序能够
正确识别每一个报文。
在包头中第一个定长字段中写明报文全长
在包头中某个定长字段中写明负载长度
在报文头尾加固定长度的边界符
使用定长报文,如负载超长,则分片
第三部分 主观题
25、
以下是一段基于链表的栈的实现代码,请补充空白处的代码。
class Stack {
Node top;
Object pop() {
if (top != null) {
Object item = top.data;
(1)
return item;
}
return null;
}
void push(Object item) {
Node t = new Node(item);
(2)
top = t;
}
}
class Node{
Node next;
Object data;
public Node(Object item){
data = item;
}
}
26、
2 个有序数组,长度为 n,查找两个数组整体中值(中值:一组数据中居中的数),复杂度是 ?用 方
法?
27、
长度为 100 的环形双向链表,A 指针顺时针方向每次走 3 步,B 指针逆时针方向每次走 5 步,每次走
完判断是否相遇,初始状态 B 在 A 逆时针方向相距 20,走 100 次,AB 指针能相遇几次?
28、
我们需要在淘宝的商品中提取一批优质商品(有特色、质量好、服务好等),比如需要提取 100 万件,
准确率要求是 95%。我们有 n 个不同的方法可以提取这些商品,但每个方法在保持准确率满足要求
的情况下都不能做到提取完整的 100 万件商品。因此可以把这 n 个方法得到的满足要求的商品集按
如下方法合并起来:如果一个商品被 k 个方法选为优质商品,则将它的分数设为 k;按照 k 从大到小
排序选取前 100 万件。但实际中发现这样选出的 100 万件商品不符合精度要求,请解释可能的原因。
还可以向哪个方向努力?
29、
有一种玻璃球,需要测试它的强度,方法是通过高空坠落的方式进行(大于承载高度玻璃球会摔碎)。
假设玻璃球的强度在[1, 100]的楼层之间,请问至少 次才能测量准确,这种情况下优先尝试的楼层
是第 层?原理是什么?
30.java选做题 wait和 sleep的区别