GOOGLE：
1、80x86中，十进制数-3用16位二进制数表示为？

2、假定符号-、*、$分别代表减法、乘法和指数运算，且

1)三个运算符优先级顺序是：-最高，*其次，$最低；

2)运算符运算时为左结合。请计算3-2*4$1*2$3的值：

(A)4096，(B)-61，(C)64，(D)-80，(E)512

3、下列伪代码中，参数是引用传递，结果是？

calc(double p, double q, double r){q=q-1.0;r=r+p}
main(){
  double a = 2.5, b = 9.0;
  calc(b-a, a, a);
  print(a);
}
(A)1.5 (B)2.5 (C)10.5 (D)8 (E)6.5

4、求输出结果：

int foo(int x, int y){
  if(x <=0 || y <= 0) return 1;
  return 3 * foo(x - 1, y / 2);
}
printf("%d\n", foo(3, 5));
(A)81 (B)27 (C)9 (D)3 (E)1

5、下列哪个数据结构在优先队列中被最广泛使用？

(A)堆 (B)数组 (C)双向链表 (D)图 (E)向量

6、以下算法描述了一个在n国元素的双向链表中到第k个元素的方法（k >= 1且k <= n）：

如果k <= n - k，从链表开始往前进k-1个元素。

否则，从终点出发，往回走n - k个元素。

这个算法的时间代价是？

(A)θ(nlogn) (B)θ(max{k, n - k}) (C)θ(k + (n - k))

(D)θ(max{k, k - n}) (E)θ(min{k, n - k})


7、有一个由10个顶点组成的图，每个顶点有6个度，那么这个图有几条边？

(A)60 (B)30 (C)20 (D)80 (E)90

8、正则表达式L = x*(x|yx+)。下列哪个字符串不符合L

(A)x (B)xyxyx (C)xyx (D)yxx (E)yx

9、为读取一块数据而准备磁盘驱动器的总时间包括

(A)等待时间 (B)寻道时间 (C)传输时间 (D)等待时间加寻道时间

(E)等待时间加寻道时间加传输时间

二、算法

1、打印出一个二叉树的内容。

2、在一个字符串中到第一个只出现一次的字符。如abaccdeff，输出b。

3、给定一个长度为N的整数数组（元素有正有负），求所有元素之和，最大的一个子数组。分析算法时空复杂度。不必写代码。
假设有这样一种字符串，它们的长度不大于   26   ，而且若一个这样的字符串其长度为   m   ，则这个字符 串必定由   a,   b,   c   ...   z   中的前   m   个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字 符串长度为   5   ，那么它一定是由   a,   b,   c,   d,   e   这   5   个字母构成，不会多一个也不会少一 个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。     
   
  现在我们用一个由大写字母   A   和   B   构成的序列来描述这类字符串里各个字母的前后顺
序：     
   
  如果字母   b   在字母   a   的后面，那么序列的第一个字母就是   A   （After），否则序列的第一个字母就是   B   字符串长度1是什么意思（Before）；     
  如果字母   c   在字母   b   的后面，那么序列的第二个字母就是   A   ，否则就是   B；     
  如果字母   d   在字母   c   的后面，那么   ……   不用多说了吧？直到这个字符串的结束。     
   
  这规则甚是简单，不过有个问题就是同一个   AB   序列，可能有多个字符串都与之相符，比方说序列“ABA”，就有“acdb”、“cadb”等等 好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的   AB   序列，问你究竟有多少个不同的字 符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。     
   
   
  嘿嘿，这就是你要解决的问题了。如果不嫌慢的话大可以穷举，不过这种解法拿出来那是显然不好意思和人打招呼的。事实上，如果设   AB   序列的长度为   n   ，那么这个问题是可以做到   O(n^3)   的。 
1.  下面一段代码的输出是[  ]
void fn( int* b){
    (*b)++;
}
int main(){
    int a=7;
    fn(&a);
cout<<a;
return 0;
}
A.0     B.7    C.8    D.undefined

2.  定义int i,j,*p=&i; 那么下面哪条语句可以完成i=j的赋值[  ]
A.i=*p;     B. *p=*&j;    C.i=&j;    D.I=**p;

3.  用二叉搜索树和哈希表存储相同的数据集,对于以下何种操作,二叉搜索树比哈希表


速度更快?[  ]
A.检索    B. 插入    C.删除    D.更新    E.排序

4.  包含N个几点和M条边的有向带权图G, 边的权为正, 以下操作中不可以在O(N+M)
的时间复杂度内完成的操作是:[  ]
A.  求结点s到结点t之间的最短距离
B.  求距离结点s最近的结点
C.  已知起始结点, 对图G中的结点进行拓扑排序
D.  求图G的最大强连通子图


5.  有如下递归函数f(n),其时间复杂度为[  ]
int f(int n){
    if(n==0)
     return 0;
    if(n==1)
     return 1;
    return ( 5*f(n-1) - 6*f(n-2));
}
A.O(n)     B. O(n^2)    C. O(n^3)    D. O(2^n)

6.  下面所述步骤中,哪一个不是创建经常所必需有的[  ]
A.由调度程序为进程分配CPU       B.建立一个进程控制块
C.为进程分配内存                    D.将进程控制块链入就绪队列

7.  在多进程的系统中,为了保证公区变量的完整性,各进程应互斥进入临界区。所谓临


界区是[  ]
A.一个缓冲区        B.一个数据区        C.一个同步机构      D.一段程序

8.  能产生满足如下条件语言的正则表达式是：1.每一个a后至少紧跟两个c; 2.每一个b


后至少紧跟一个c [  ]
A.(acc|bc|c)*   B.(acc|bc)* C.(ac|bc)*  D.不是正则语言

9.  以下哪项不是RPC（远程过程调用）的特点[  ]
A.速度快        B.降低系统耦合度        C.可以实现异构系统间的协作

10. 有三个桶，容量分别是3升，5升，7升，你只能进行下面的操作：
把一个桶中所有的水倒掉；
把一个桶A中的水倒入桶B，直到桶A空了或者桶B满了；
假设一开始容量为3升和5升的桶是满的，7升的桶是空的，希望通过一系列操作使3个桶


中任意一个中正好有4升水，那么至少需要[  ]次操作。
A.3     B.5     C.7     D.不可能

2.  程序设计与算法
2.1 实现如下编码算法，对于重复2-9次数的字符，用两个数字表示，即NX（其中N为重


复的次数，X为重复的字符，下同），超过九个则先输出9X，然后处理剩下的字符。对于



连续的不重复的字符，则两边加1来封字符串。如果被封的字符串其中有数字为1，则用1


来转义。    示例： AAAAAABCCCC -> 6A1B14C,  12344 -> 11123124。。。（下面的框


架是用C++语言写的。你可以用你熟悉的语言。）
void encode (const char* text, char* dest)
text 为需要编码的字符串，dest表示编码输出的目标空间，而空间足够大

2.2给定一颗有n个结点的二叉树。求它的所有结点数为m的连通子图数目。m<=n分析你的


算法的时间复杂度，解释算法即可，不必写代码。
1，写两个N*N的矩阵的乘法，给出了C的格式，你可以选择你喜欢的语言去写。。
int* multi(int* a1, int* a2, int N){
}

2，寻一个单向链表的中项，如果存在两个则返回前一个。给出了C的格式，同样你可
以选择。。。。
struct {
    Node* next;
    int value;
} Node;
Node* someFunc(Node* head){
}

3，给一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的组合
乘积中最大的一组。。。写出算法的时空复杂度。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。