笔试题目2007-9-5

出自求职百科

1 选错的

A.在共有继承下，基类的public在子类中仍然是public

B.在共有继承下，基类的private在子类中是private

C.在共有继承下，基类的protected在子类中是protected

D.在私有继承下，基类的public在子类中是private

2边长为n的正方形可以分成多个边长为1的正方形，如边长为2的正方形有2×2个边长为1的正方形和1个边长为2的正方形；问边长为5的正方形有几个正方形；

3 public class Person {

　　public void printValue(int i,int j){

　　　　　　　　　　System.out.println("1111111111111"); 　　　} 　　　public void printValue(int i){

　　　　　　　　System.out.println("22222222222");

　　　　}

}

public class Teacher extends Person {

　　public void printValue(){

　　　　System.out.println("333333333");

　　　　}

　　　　　public void printValue(int i){

　　　　System.out.println("4444444444");

　　　}

　　　　　public static void main(String[] args) {

　　　　　　　　Person t=new Teacher();

　　　　　　　　　t.printValue(10);

　　}

}

输出结果是：4444444444

44.找错误

int tolower(const char *str)

{

　　　　　if(NULL==str) return 0;

　　　　　int i=0,iCount=0;

　　　　　for(;i <strlen(str);i++)

　　　　　{

　　　　　if(str[i] <= "Z " ¦ &brvbarstr[i] >= "A ")

　　　　　{

　　　　　　　　str[i]+= "z "- "Z ";

　　　　　　　　iCount++;

　　　　　　}

　　　　　}

       return   iCount; 

}

5有个长度为12的无重复有序表，按折半查找法进行查找，在表内各元素等概率情况下，查找成功所需的平均比较（三元比较）的次数为（）

　　A 35/12 B37/12 C 39/12 D 43/12

6从n个数里面找最大的两个数理论最少需要比较

A 2logn B 2 logn -1 C n+ logn -2 D2n-3

7 386781634*234659874=6（30秒）

8Linux的非root用户，在自己的目录中，不可以删除非空目录dirs的方法是：

A rm dir dirs B rm-rdirs C mv dirs /dev/null D destroy dirs

9 Shell运算结果是3的是

A echo(9/3)

B echo$[16/5]

C echo$((10-7))

D echo’21/6’ &brvbarbc

大题：

1每个整数0-9这10个数组成，如223有2个2 ，和1个3，输入m和n（0 <m <n <10^20）

求出m到n之间所有整数共包含了多少个0，1。。。。9

实现函数void foo(const char*m, const char * n, char * result, size_t len ) result为输出缓冲，len为result的长度。

要求写出思路、程序程序效率，计算时间复杂度和空间复杂度

2linux32位系统下有10个无序文件，各文件大小不一（均小于1G）现在需要将此10个文件归并为一组，不超过10个有序文件（第一个文件最大数小于或等于第二个文件最小数，依次类推）请选择你擅长的语言实现

说明 文件的每一行最大不超过128位的阿拉伯数字组合，每一行只有一个数字，头一位不是零

要求写出思路和程序，计算时间复杂度和空间复杂度

3网页3种操作，查询，删除，最加到末尾

例如：每页显示20个，现在要查第50页。假如用有序数组，则从下标20×49开始，直接返回后面20个即可，但是当删除时会有大量数据移动，所以数组对删除效率低，另外一种方法是，不删除只作标记，但是查询时必须又从头开始计数，数一下应该从哪个位开始返回

设计一种数据结构高效率的完成3种功能

限制：1操作在硬盘上发生

　　　2网页大小不相同

　　　3总数小于10M

　　　4单个小于100K

完成函数

size_t foo(unsigned int *a1, size_t al1, unsigned int* a2, size_t al2)

其中a1和a2都为无符号数组，al1和al2为数组的长度，数组的长度为偶数。

无符号数组由一对数字区间组成。如下例：

a1 为 0,1,3,6,10,20

a2 为 0,1,20,50,4,5

则 a1表示以下区间[0,1] [3,6] [10,20]

     a2表示以下区间[0,1]   [20,50]   [4,5] 

则a1,a2的重叠部分为[0,1] [4,5]，其长度为2

函数foo要求返回重叠区间的长度。上例中为2.

要求：

     详细说明自己的解题思路，说明自己实现的一些关键点。 

写出函数foo原代码，另外效率尽量高，并给出代码的复杂性分析。

限制：

al1和al2的长度不超过100万。而且同一个数组的区间可能出现重重叠。

     如a1可能为   0,5,     4,8,     9,100,     70,80 

     使用的存储空间尽量小。 

2 多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:

176, 178, 180, 170, 171

这些捣乱分子对为 <176, 170 >, <176, 171 >, <178, 170 >, <178, 171 >, <180, 170 >, <180, 171 >, 那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)

要求：

输入:

为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。

输出：

为一个文件(out)，每行为一个数字，表示捣乱分子的对数。

详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码，并分析时间复杂度。

限制：

输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。

二、下面是两道选做题，请根据自己的情况选择其中的一道作答(WEB方向请答第4道，其他职位方向答第3道）。

3考虑一个在线好友系统。系统为每个用户维护一个好友列表，列表限制最多可以有500个好友，好友必须是这个系统中的其它用户。好友关系是单向的，用户B是用户A的好友，但A不一定是B的好友。

用户以ID形式表示，现给出好友列表数据的文本形式如下：

1 3,5,7,67,78,3332

2 567,890

31 1,66

14 567

78 10000

…

每行数据有两列，第一列为用户ID，第二列为其好友ID，不同ID间用”,”分隔，ID升序排列。列之间用”t”分隔。

要求：

请设计合适的索引数据结构，来完成以下查询：

给定用户A和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。

如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。

详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的伪代码实现建立索引过程和查询过程，并说明空间和时间复杂度。

限制：

用户数量不超过1000万，平均50个好友。

4有关系模式：User（userId, userName）， Article（articleId, userId, title, content），Vote（articleId, score），User为用户关系，Article为用户发表的文章关系，Vote为文章得票关系，title为文章标题、score为得票数。

（1）用SQL语言查询所有没发表过文章的用户名；

（2）用SQL语言查询得票数大于100的所有文章标题，按得票数倒序排列；

（3）用SQL语言查询出发表文章数大于5，文章平均得票数大于100的用户名，按平均得票数倒序排列；

（4）设计这些表的主键、外键和索引，并指出上面三个查询所使用的索引。

（5）当用户数超过1000万，文章数超过1亿时，如何考虑存储及性能的改进和优化？

1）15分如下数据结构：

typedef struct TreeNode {

char c;

TreeNode *leftchild;

TreeNode *rightchild;

}

请实现两棵树是否相等的比较,相等返回0否则返回其它值.并说明你的算法复杂度

int CompTree(TreeNode* tree1, TreeNode* tree2);

注:A,B两棵树相等当且仅当RootA- >c==RootB- >c，而且A和B的左右子树对应相等或者左右互换后相等．

2）15分已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写C语言函数实现从中去掉所有ansi编码的的数字和字母（包括大小写).要求在原字串上返回结果。

int filter_ansi(char* gbk_string);

　　注：汉字的GBK编码范围是0x8140 - 0xFEFE

3）30分

芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片好芯片，说明你所用的比较次数上限．其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．坏芯片和其它芯片比较时，会随机的给出好或是坏。

4）40分

请设计一个网页存储系统，能存储千万量级的网页。

要求： 1.支持按照URL为键值的随机添加，删除和修改网页

2.支持多个线程同时添加，修改和删除

3.支持多线程按照入库时间批量的获取网页，并尽可能的快

提示:设计应包括如下几方面:

1.网页的存储方式设计,即硬盘数据的组织形式

2.如何支持随机查找

3.如何优化批量检索

4.增删改查之间的同步和互斥,如何达到最大的并发.

           系统限制和一些参考参数:

硬盘400G, 内存4G

硬盘的I/O比内存的I/O速度慢1000倍

硬盘的连续I/O比随机I/O快10倍

网页的平均长度为25K

附加：

请说明你的系统在亿到十亿规模的扩展方法

写出输出结果：

1. include <iostream >

using namespace std;

 class   A 

　　{

　　protected:

　　int m_data;

　　public:

　　A(int data = 0){m_data = data; }

　　int GetData(){return doGetData();}

　　virtual int doGetData(){ return m_data;/*m_data ＝ 0 */}//接口，如不直接调用，则调用派生类中实现他的函数

　　};

　　class B:public A

　　{

   protected:

   int   m_data;

   public:

　　B(int data = 1){m_data = data; }//这里 A 中的m_data = 0 ,B中的m_data = 1

　　int doGetData(){ return m_data  ;/*m_data ＝ 1 */} //实现接口 };

class C:public B //C继承了A＆B类的方法＆属性，且未从新定义接口，故接口还是B类中定义的 { 　　protected: 　　int m_data; 　　public: 　　C(int data = 2){m_data = data; } 　　//这里 A 中的m_data = 0 ,B中的m_data = 1,C 类中的m_data = 2 };

int main() { C c(10);

cout < <c.GetData() < <endl;

//本来是要调用C类的GetData(),C中未定义，故调用B中的，但是B中未定义，故调用A中的GetData()，因为A中的doGetData()是虚函数，所以调用

//B类中的doGetData(),而B类的doGetData()返回B::m_data,故输出 1cout < <c.A::GetData() < <endl;

//因为A中的doGetData()是虚函数，又因为C类中未重定义该接口，所以调用B类中的doGetData(),而B类的doGetData()返回B::m_data,故输出 1cout < <c.B::GetData() < <endl;

//肯定返回 1 了cout < <c.C::GetData() < <endl;

//因为C类中未重定义GetData()，故调用从B继承来的GetData()，但是B类也未定义，所以调用A中的GetData(),因为A中的 doGetData()是虚函数，所以调用B类中的doGetData(),而B类的doGetData()返回B::m_data,故输出 1 cout < <c.doGetData() < <endl;

//肯定是B类的返回值 1 了cout < <c.A::doGetData() < <endl;

//因为直接调用了A的doGetData(),所以输出 0 了cout < <c.B::doGetData() < <endl;

//因为直接调用了B的doGetData(),所以输出 1 了cout < <c.C::doGetData() < <endl;

//因为C类中未重定义该接口，所以调用B类中的doGetData(),而B类的doGetData()返回B::m_data,故输出 1 system("PAUSE");

return 0; }

1. Write a function that prints the binary representation of an unsigned integer using only putchar() for output

2. Memory Management/Pointer manipulation Write a function that allows you to remove a substring from a string and returns a new string that uses only the amount of storage needed Assume: All arguments are always valid

         The   original   string   should   remain   untouched 

Use the following function prototype char * remove_substr(char *str, int pos, int length);

3.Data structures Implement a circular queue of size n using an array. Use the given fragments for your implementation 　　typedef stuct QUEUE{ 　　　　　　　　　　int head, tail; 　　　　　　　　　　void * data[N]; 　　}queue; 　　[52RD.com] 　　void init-queue() 　　{ 　　}

　　int queue(void *data) 　　{ 　　} 　　void * dequeue() 　　{ 　　}

4.　Problem solving/operating systems A multitasking OS has a producer program that writes data to a buffer and consumer one that reads that data and prints it. Show the work that needs to be done to make sure this works smoothly.

5. C syntax Identify all the errors in the following piece of C code. Assuming you fix it so it compiles correctly. What would it print? (be sure to specify any assumptions) 　　void init_array(unsigned int array[]) 　　{[52RD.com] 　　　　　　　　　　int size = sizeof(array); 　　　　　　　　　　int i;

 　　　　　　　　　for(i=0;   i 

　　　　　　　　　　array[i]=-1; 　　} 　　void main() 　　{ 　　char * string=”Here is rather long constant to fit my needs”; 　　char * another_string; 　　　　　　　 unsigned int array[11]; 　　　　　　　　init_array(&array[0]); 　　　　　　　　another_string=(char*)malloc(strlen(string)); 　　　　　　　　strcpy(another_string,string); 　　　　　　　　for(i=0; i <=40; i+=4){ 　　　　　　　　array[i/4]=int(*)string[i]; 　　　　　　　　printf(“%s”, (char *) array); 　　}

• 参考：http://lihaochn.spaces.live.com/blog/cns!79ce398f9d65f44!258.entry