搜索
选择题第一题，两台电脑在局域网中，机器为千兆网卡，一台作服务器里面有一张网页为1K字节，问另一台下载这个网页的速度。我答：我不知道1K是指1024还是1000…不过按我的算法没区别，1000000000/8/1k我选了10000张/秒第二题，单链表插入一个节点的问题。在p指向的节点后插入一个q指向的节点。我答：q-next=p-next;p-next=q;之后乱序，我记不清楚题号了。有一题，地图染色问题，每个国家用矩形表示，让相邻国家颜色不同。离散里面有有一题，问快速排序达到最坏情况时间复杂度n2的原数数组的具体情形。见数据结构有一题，很扯的…指针取址符号混乱，选项却很白痴。有一题，入栈序列1,2,3,4,5,..,n，第一个出栈的是n，问第i个出栈的是多少。我答：n-i+1最后一题，给中缀和后缀表达式，求前缀表达式。填空题第一题：数组(a1,a2,a3,a4..,an)，删除任意一个的概率相同，问平均删除一个要移动多少个。我答：(n-1)/2第二题：一个程序填空，程序大意是在数组里面找第二大的数。注：不难第三题：大致如下一个程序片段：voidxxx(x){intcountx=0;while(x){countx++;x=x&(x-1);}coutcountxendl;}问xxx(9999)输出什么。我答：8，记得做ACM的时候碰到过那个式子，貌似关于排列的，具体意思忘记了，搞一下可以明白是x变成二进制，里面有多少个1就是答案。第四题：大致如下一个代码inta[3][2]={1,2,3,4,5,6};int*p[3];p[0]=a[1];问*(p[0]+1)是个什么东西我答：4，蛮基础嗯。简答题第一题：7公斤米，50克砝码，200克砝码各一个，称1350克米问最少要多少次，并编程回答。我答，6次，可能一开始会想到1350/250+2=7次，说明贪心无效。我不知道我的方法是不是很笨，用了递推，或者你可以看成是动态规划。转化一下题目的意思就是1克和4克砝码，问多少次称出27克大米，F[N]代表N克大米最少需要多少次。则有：F[N]=min{F[N-1],F[N-4],F[N-5]}+1代码如下：intfindmin(intweight){intv=weight/50;intf[150];f[0]=0;f[1]=1;f[2]=2;f[3]=3;f[4]=1;if(v5)returnf[v];inti;for(i=5;i=v;i++)f[i]=min(f[i-1]+1,f[i-4]+1,f[i-5]+1);returnf[v];}注：我一开始愣了很久，我在想，称好的大米可以作为砝码来用吗？？这样就是另一种问题了吧。第二题，n个鸡蛋放到m个篮子，每个篮子不能为空，问所有可能的摆放方法，使得满足对于任意一个不大于n的数可以又若干个篮子里面的鸡蛋数加起来。我答：不能想出算出所有摆放方法的方法，期待ACM大牛路过。第三题，大意淘宝网的评论系统，原先只有一个评论表，对于现在大用户，大数据量，大访问量，请设计一个合理可行的架构来优化关于评论的数据库。我答：哥蒙了，哥胡言乱语的。附加题：前端设计师必答第一题：图片默认为半透明，鼠标移上去变成不透明。我注：img标签onfocus和onblur的应用，注意这个透明的属性在IE和FireFox下是不同的。而且用js控制的时候，属性名也要注意…第二题：一个输入框，和一个列表框，列表框里面有很多字符串，在输入框里面输入字符串时，列表框中字符串前缀是该字符串的做高亮或者其他显著表示。最后回车选择或者鼠标双击列表框选择。1.把二元查找树转变成排序的双向链表（树）题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/\614/\/\481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};2.设计包含min函数的栈（栈）定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。3.求子数组的最大和（数组）题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。4.在二元树中找出和为某一值的所有路径（树）题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10/\512/\47则打印出两条路径：10,12和10,5,7。二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};5.查找最小的k个元素（数组）题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。第6题（数组）腾讯面试题：给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下：【0，1，2，3，4，5，6，7，8，9】举一个例子，数值:0,1,2,3,4,5,6,7,8,9分配:6,2,1,0,0,0,1,0,0,00在下排出现了6次，1在下排出现了2次，2在下排出现了1次，3在下排出现了0次....以此类推..第7题（链表）微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?第8题（算法）此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?3.★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。★用一种算法整理一个数组。你为什么选择这种方法?★用一种算法使通用字符串相匹配。★颠倒一个字符串。优化速度。优化空间。★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，实现速度最快，移动最少。★找到一个子字符串。优化速度。优化空间。★比较两个字符串，用O(n)时间和恒量空间。★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?★不用乘法或加法增加8倍。现在用同样的方法增加7倍。第9题（树）判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/\610/\/\57911因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。第10题（字符串）翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“Iamastudent.”，则输出“student.aamI”。第11题（树）求二叉树中节点的最大距离...如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义距离为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。第12题（语法）题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。第13题（链表）：题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};第14题（数组）：题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。第15题（树）：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。例如输入：8/\610/\/\57911输出：8/\106/\/\11975定义二元查找树的结点为：structBSTreeNode//anodeinthebinarysearchtree(BST){intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};第16题（树）：题目（微软）：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入8/\610/\/\57911输出861057911。第17题（字符串）：题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。分析：这道题是2006年google的一道笔试题。第18题（数组）：题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。July：我想，这个题目，不少人已经见识过了。第19题（数组、递归）：题目：定义Fibonacci数列如下：/0n=0f(n)=1n=1\f(n-1)+f(n-2)n=2输入n，用最快的方法求该数列的第n项。分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。第20题（字符串）：题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串345，则输出整数345。第21题（数组）2010年中兴面试题编程求解：输入两个整数n和m，从数列1，2，3.......n中随意取几个数,使其和等于m,要求将其中所有的可能组合列出来.第22题（推理）：有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，再分别在A、B、C三人额头上贴任意两张牌，A、B、C三人都可以看