it笔试题目.docx
it笔试题目辩论赛题目推举度：军训作文题目推举度：傅雷家书题目及答案推举度：建党百年题目作文推举度： it笔试题目 it行业是信息技术产业，也是现代热门求职行业。it的笔试题目有哪些呢? it笔试题目(1) 1、有一个名人和许多平民在一块，平民都熟悉这个名人，但是这个名人不熟悉任何一个平民，任意两个平民之间是否熟悉是未知的，请设计一个算法，快速找个这个人中的那个名人。 已知已经实现了一个函数 bool know(int a,int b) 这个函数返回true的时候，说明a熟悉b，返回false的时候说明a不熟悉b。 思路：首先将n个人分为n/2组，每一组有2个人，然后每个组的两个人调用这个know函数，假设为know(a，b)，返回true的时候说明a熟悉b，则a确定不是名人，a可以排解掉了，依次类推，每个组都调用这个函数依次，那么n个人中就有n/2个人被排解掉了，数据规模将为n/2。同理在剩下的n/2个人中在使用这个方法，那么规模就会将为n/4，这样全部的遍历次数为n/2+n/4+n/8+. 这个一个等比数列，时间简单度为o(n)。 2、进程切换需要留意哪些问题? 保存处理器PC存放器的值到被中止进程的私有堆栈; 保存处理器PSW存放器的值到被中止进程的私有堆栈; 保存处理器SP存放器的值到被中止进程的进程掌握块; 保存处理器其他存放器的值到被中止进程的私有堆栈; 自待运行进程的进程掌握块取SP值并存入处理器的存放器SP; 自待运行进程的私有堆栈恢复处理器各存放器的值; 自待运行进程的私有堆栈中弹出PSW值并送入处理器的PSW; 自待运行进程的私有堆栈中弹出PC值并送入处理器的PC。 3、输入一个升序数组，然后在数组中快速查找两个数字，其和等于一个给定的值。 这个编程之美上面有这个题目的，很简洁的，用两个指针一个指向数组前面，一个指向数组的后面，遍历一遍就可以了。 4、推断一个自然数是否是某个数的平方。固然不能使用开方运算。 方法1： 遍历从1到N的数字，求取平方并和N进展比拟。 假如平方小于N，则连续遍历;假如等于N，则胜利退出;假如大于N，则失败退出。 简单度为O(n0.5)。 方法2： 使用二分查找法，对1到N之间的数字进展推断。 简单度为O(log n)。 方法3： 由于 (n+1)2 =n2 + 2n + 1， = . = 1 + (2*1 + 1) + (2*2 + 1) + . + (2*n + 1) 留意到这些项构成了等差数列(每项之间相差2)。 所以我们可以比拟 N-1， N - 1 - 3， N - 1 - 3 - 5 . 和0的关系。 假如大于0，则连续减;假如等于0，则胜利退出;假如小于 0，则失败退出。 简单度为O(n0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。 例如：32 = 9 = 1 + 2*1+1 + 2*2+1 = 1 + 3 + 5 42 = 16 = 1 + 2*1 + 1 + 2*2+1 + 2*3+1 int square(int n) int i = 1; n = n - i; while( n 0 ) i += 2; n -= i; if( n = 0 ) /是某个数的平方 return 1; else /不是某个数的平方 return 0; it笔试题目(2) 一、算法设计 1、设rand(s，t)返回s,t之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间简单度分析。 思路：这个使用数学中的极坐标来解决，先调用s1，t1随机产生一个数r，归一化后乘以半径，得到R*(r-s1)/(t1-s1)，然后在调用s2，t2随机产生一个数a，归一化后得到角度：360*(a-s2)/(t2-s2) 2、为分析用户行为，系统常需存储用户的一些query，但因query特别多，故系统不能全存，设系统每天只存m个query，现设计一个算法，对用户恳求的query进展随机选择m个，请给一个方案，使得每个query被抽中的概率相等，并分析之，留意：不到最终一刻，并不知用户的总恳求量。 思路：假如用户查询的数量小于m，那么直接就存起来。假如用户查询的数量大于m，假设为m+i，那么在1-m+i之间随机产生一个数，假如选择的是前面m条查询进展存取，那么概率为m/(m+i)，假如选择的是后面i条记录中的查询，那么用这个记录来替换前面m条查询记录的概率为m/(m+i)*(1-1/m)=(m-1)/(m+i)，当查询记录量很大的时候，m/(m+i)= (m-1)/(m+i)，所以每个query被抽中的概率是相等的。 3、C+ STL中vector的相关问题： (1)、调用push_back时，其内部的内存安排是如何进展的? (2)、调用clear时，内部是如何详细实现的?若想将其内存释放，该如何操作? vector的工作原理是系统预先安排一块CAPACITY大小的空间，当插入的数据超过这个空间的时候，这块空间会让某种方式扩展，但是你删除数据的时候，它却不会缩小。 vector为了防止大量安排连续内存的开销，保持一块默认的尺寸的内存，clear只是清数据了，未清内存，由于vector的capacity容量未变化，系统维护一个的默认值。 有什么方法可以释放掉vector中占用的全部内存呢? 标准的解决方法如下 template class T void ClearVector( vector T vt ) vector T vtTemp; veTemp.swap( vt ); 事实上，vector根本就不管内存，它只是负责向内存治理框架acquire/release内存，内存治理框架假如发觉内存不够了，就malloc，但是当vector释放资源的时候(比方destruct), stl根本就不调用free以削减内存，由于内存安排在stl的底层：stl假定假如你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存)，所以就没必要不停地malloc/free。假如是这个规律的话这可能是个trade-off 一般的STL内存治理器allocator都是用内存池来治理内存的，所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量，而不是真的把内存归还给系统。这样做一是为了避开内存碎片，二是提高了内存申请和释放的效率不用每次都在系统内存里查找一番。 二、系统设计 正常用户端每分钟最多发一个恳求至效劳端，效劳端需做一个特别客户端行为的过滤系统，设效劳器在某一刻收到客户端A的一个恳求，则1分钟内的客户端任何其它恳求都需要被过滤，现知每一客户端都有一个IPv6地址可作为其ID，客户端个数太多，以至于无法全部放到单台效劳器的”内存hash表中，现需简洁设计一个系统，使用支持高效的过滤，可使用多台机器，但要求使用的机器越少越好，请将关键的设计和思想用图表和代码表现出来。 三、求一个全排列函数： 如p(1,2,3)输出： 123、132、213、231、321、323 求一个组合函数 如p(1,2,3)输出： 1、2、3、1,2、2,3、1,3、1,2,3 这两问可以用伪代码。 it笔试题目(3) 1、对于一个内存地址是32位、内存页是8KB的系统。0X0005F123这个地址的页号与页内偏移分别是多少。 2、假如X大于0并小于65536，用移位法计算X乘以255的值为： (X8)-X X8-X是不对的，由于移位运算符的优先级没有减号的优先级高，首先计算8-X为0，X左移0位还是8。 3、一个包含n个节点的四叉树，每个节点都有四个指向孩子节点的指针，这4n个指针中有 3n+1 个空指针。 4、以下两个语句的区分是：第一个动态申请的空间里面的值是随机值，其次个进展了初始化，里面的值为0 int *p1 = new int10; int *p2 = new int10(); 5、计算机在内存中存储数据时使用了大、小端模式，请分别写出A=0X123456在不怜悯况下的首字节是，大端模式：0X12 小端模式：0X56 X86构造的计算机使用 小端 模式。 一般来说，大局部用户的操作系统(如windows, FreeBsd,Linux)是小端模式的。少局部，如MAC OS，是大端模式 的。 6、在嬉戏设计中，常常会依据不同的嬉戏状态调用不同的函数，我们可以通过函数指针来实现这一功能，请声明一个参数为int *，返回值为int的函数指针： int (*fun)(int *) 7、下面程序运行后的结果为：to test something char str = glad to test something; char *p = str; p+; int *p1 = static_cast(p); p1+; p = static_cast(p1); printf(result is %sn,p); 8、在一冒险嬉戏里，你见到一个宝箱，身上有N把钥匙，其中一把可以翻开宝箱，假设没有任何提示，随机尝试，问： (1)恰好第K次(1= (2)平均需要尝试多少次。 这个就是求期望值 由于每次翻开宝箱的概率都是1/n，则期望值为： 1*(1/n)+2*(1/n)+3*(1/n)+.+n*(1/n) = (n+1)/2 it笔试题目(4) 1、对于如下程序： #include using namespace std; class A public: A() coutA ; int main(void) A a4, b,*p; 会输出多少个A?( C ) A、2 B、3 C、5 D、6 p只是一个对象指针，并没有指向一个对象的内存空间，所以没有调用构造函数。 2、头文件中的 ifndef/define/endif 有什么作用? 答：防止该头文件被重复引用，避开变量、类型等被重新定义。 3、const 有什么用途?(请至少说明两种) 答：(1)可以定义 const 常量。 (2)const可以修饰函数的参数、返回值，甚至函数的定义体。被const修饰的东西都受到强制爱护，可以预防意外的变动，能提高程序的强健性。 4、如下的字符串函数,用于生存一个字符串 ”连接号码特别” ,并返回它的指针 char* strfun() char str20; strcpy(str, “连接号码特别”); printf(“%s n”, str); /printf语句1 return str; void main() char *pstr = strfun(); printf(%s n, pstr); /printf语句2 问题1 : printf语句1和printf语句2哪个能在屏幕上正在打印出来? 问题2 : 假如不能正常在屏幕上打印出字符串，请说明缘由。 问题3 : 假如不修改strfun的声明，请问该如何修改上述程序的错误。 答： 问题1：语句1可以正常打印，语句2不能正常打印; 问题2：语句2使用的指针所指向的内存空间str20，在函数strfun返回时已经被释放了; 问题3：可以将函数strfun中的语句char str20;改为char *str = new char20; 5、下面是交换两个double型数据的函数， void swap( double* p1, double* p2 ) double *p; *p = *p1; *p1 = *p2; *p2 = *p; void main() double a = 0.1; double b = 0.2; swap( a, b ); 请找出上述代码的错误，指出错误的缘由，并改正。 答：函数swap中混淆了double型指针与double型变量的差异，对于一个未初始化的指针访问其内存空间是特别危急的。对swap函数修改如下： void swap( double* p1, double* p2 ) double p; p = *p1; *p1 = *p2; *p2 =p; 6、在电信业务的后台处理程序中，常常会涉及处处理字符串，除了用char *处理字符串之外，C+还为我们供应了封装了的字符串类string，其本质也是用一个动态数组来保存字符串，类String的原型为： class String public: String(const char *str = NULL); / 一般构造函数 String(const String other); / 拷贝构造函数 String(void); / 析构函数 String operate =(const String other); / 赋值函数 private: char *m_data; / 用于保存字符串 ; 请编写String的上述4个函数一般构造函数、拷贝构造函数、析构函数和赋值函数。 代码如下： class String private: char *m_data; public: String(); String(const char *str = NULL); String(const String other); String(void); String operator =(const String other); ; String:String() m_data = NULL; String:String(const char *str = NULL) /带一个指针的一般构造函数 if(str = NULL) m_data = new char1; assert(m_data != NULL); *m_data = 0; else int length=strlen(str); m_data = new charlength+1; assert(m_data != NULL); strcpy(m_data,str); String:String(const String other) /拷贝构造函数 m_data = new charother.length+1; assert(m_data != NULL); strcpy(*this).m_data,other.m_data); String:String(void) /析构函数 if(m_data != NULL) delete m_data; m_data = NULL; String String:operator=(const String other) /赋值函数 if(other != this) delete (*this).m_data; (*this).m_data = new charother.length+1; assert(*this).m_data != NULL); strcpy(*this).m_data,other.m_data);
