1、3417(34的17次方)对6取余, 结果是多少()
A、2 B、3 C、4 D、5
2、有如下算式成立,13*7=88,是采用()进制计算的
A、14 B、13 C、12 D、11
3、有字符序列(Q,H,C,Y,P,A,M,N,R,D,F,X),新序列(M,H,C,D,F,A,Q,N,R,Y,P,X)是下列()排序算法一趟扫描结果
A、希尔排序 B、快速排序 C、堆排序 D、冒泡排序
4、二叉排序树中的最小值在二叉排序树的何处()
A、只能在根节点 B、只能在叶子节点
C、可能在叶子节点, 也可能在根节点,也可能在只有右孩子的父节点 D、可以在任何节点
5、一棵树用左儿子右兄弟表示法呈如下结构,请问这棵树原先结构前序遍历是()
A、ABFEDC B、ABCEFD C、ABDCEF D、ADCEFB
6、一个含有n个顶点和e条边的简单无向图, 在其邻接矩阵存储结构中共有()个零元素
A、e B、2e C、n的2次方-e D、n的2次方-2e
7、下面程序中, 输出是什么()
int fun(int x){ int count = 0; while(x){ count++; x = x &(x-1) } return count; } int main(){ cout << "fun(2015)=" << fun(2015)<<endl; }
A、fun(2015)=11 B、fun(2015)=10 C、fun(2015)=9 D、fun(2015)=8
8、若系统中有五台绘图仪,有多个进程均需要使用两台,规定每个进程一次仅允许申请一台,则至多允许()个进程参于竞争,而不会发生死锁
A、2 B、3 C、4 D、5
9、通过文件名存取文件时,文件系统内部的操作过程是通过()
A、文件在目录中查找文件数据存取位置
B、文件名直接找到文件的数据,进行存取操作
C、文件名在目录中查找对应的i节点,通过i节点存取文件数据
D、文件名在目录中查找对应的超级块,在超级块查找对应i节点,通过i节点存取文件数据
10、以下哪个协议不是无状态协议()
A、TCP协议 B、HTTP协议 C、UDP协议 D、IP协议
11、12个元素的排序数组进行二分查找,每个元素被查找的概率是相等的,平均比较次数为 。
12、(a1+a2+a3+…+an)/b与a1/b+a2/b+…an/b(除法为整除)最大差值为 。
13、有如下图所示(左)的一棵二叉树, 请设计一种遍历方式,使得按照如下方式(右)输出各个元素:(从下到上, 从右到左输出, 要求每层之间换行, 同行元素之间用tab分割,写出完整代码)。
14、某星球上出现了一种怪物, 这种怪物是单亲繁殖,从出生起第3个月起每个月就能繁衍一批后代共m个,但是这种怪物很短命,生存第5个月后就会毙命。目前该星球有一个这样的怪物,请编写程序计算n个月后怪物的总数。(这里我们假定第5个月怪物繁衍后再毙命)
15、有一个二叉树, 节点全部为整数,如何找到一个子树,它所有节点的和最大?要求编程序实现。
16、一般在大型系统中,都会为每个资源分配一个唯一的ID,在大型系统中这个并非易事,目前人人网一天产生新鲜事在千万量级,现在由你来设计一个产生新鲜事ID的模块。要求写出解题思路和伪代码。
1、C 2、B 3、A 4、C 5、B 6、D 7、B 8、C 9、C 10、A
11、37/12
12、n-1
13、参考代码:
// 逆序 BFS 搜索 void reverseBFS(Tree *t) { if(NULL == t) { return; } vector<vector<char>> vv; queue<Tree*> que; que.push(t); int length = 1; while(!que.empty()) { vector<char> v; while(length != 0) { Tree *t = que.front(); //cout<<t->data<<endl; que.pop(); if(t->left) { que.push(t->left); } if(t->right) { que.push(t->right); } v.push_back(t->data); v.push_back(' '); length--; } v.push_back('\n'); vv.push_back(v); length = que.size(); } //cout<<vv.size()<<endl; for (int i = vv.size() - 1; i >= 0; i--) { vector<char> v = vv[i]; for(int j = 0; j < v.size(); j++) { cout<<v[j]; } } }
14、参考代码:
#include <iostream> using namespace std; int sum(int n,int m) { int res=1; int A[100]; A[0]=1; A[1]=0; A[2]=0; if(n<3) return res; for(int i=3;i<=n;i++) { A[i]=(res-A[i-1]-A[i-2])*m; res+=A[i]; if(i>=5) res-=A[i-5]; } return res; } int main() { int n,m; cin>>n>>m; cout<<sum(n,m)<<endl; return 0; }
15、
思路:使用递归方法,可以使用前序遍历,首先分别计算左右子树各自的子树和,然后记录目前最大的;再加入当前的父节点,再计算父节点开头的子树是否最大;该层递归上去即可。
参考代码:
public class MaxSumSubTree { class TreeNode{ TreeNode left,right; int tag; TreeNode(int tag){ this.tag = tag; } } private TreeNode maxRoot = new TreeNode(0); public int find(TreeNode root){ if(root==null){ return 0; } else{ int lSum = find(root.left); int rSum = find(root.right); if(maxRoot.tag<lSum) maxRoot = root.left; if(maxRoot.tag<rSum) maxRoot = root.right; return root.tag+lSum+rSum; } } }
16、
思路:
1)使用单例模式。定义一个sequenceGenerator单例类, 声明一个getSequence方法,将sequence序号依次相加 。
2)产生 ID 的规则是:将 ID设置为字符串。ID = 当前日期+整型sequence。
伪代码:
public class SequenceGenerator { private SequenceGenerator generatorInstance = null; private long sequence = 0; private SequenceGenerator (){} public static SequenceGenerator getInstance(){ if(generatorInstance == null){ synchoronized(this){ generatorInstance = new SequenceGenerator (); } return generatorInstance ; } } public synchronized int getSequence(){ if(++sequence没有超过long型的最大值)return sequence; } }