《2022年C语言面试题 .pdf》由会员分享，可在线阅读，更多相关《2022年C语言面试题 .pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10 / 6 14 / / 4 8 12 16 转换成双向链表4=6=8=10=12=14=16 。首先我们定义的二元查找树节点的数据结构如下：struct BSTreeNode int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node ; 2.设计包含min 函数的栈。定义栈的
2、数据结构，要求添加一个min 函数，能够得到栈的最小元素。要求函数min、push 以及 pop 的时间复杂度都是O(1)。3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5 ，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与
3、输入整数相等的所有路径。例如输入整数22 和如下二元树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 10 / 5 12 / 4 7 则打印出两条路径：10, 12 和 10, 5, 7。二元树节点的数据结构定义为：struct BinaryTreeNode / a node in the binary tree int m_nValue; / value of node BinaryTreeNode *m_pLeft; /
4、left child of node BinaryTreeNode *m_pRight; / right child of node ; 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】初看此题，貌似很难，10 分钟过去了，可能有的人，题目都还没看懂。举一个例子，数值
5、: 0,1,2,3,4,5,6,7,8,9 分配 : 6,2,1,0,0,0,1,0,0,0 0 在下排出现了6 次， 1 在下排出现了2 次，2 在下排出现了1 次， 3 在下排出现了0 次 . 以此类推 . 昨天，用c+实现了此题。 (*_*) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 第 7 题- 微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们
6、假设俩个链表均不带环。问题扩展：1.如果链表可能有环列? 2.如果需要求出俩个链表相交的第一个节点列? 选一些比较怪的题， ，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间， 一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人? 3用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。用
7、一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。用一种算法整理一个数组。你为什么选择这种方法? 用一种算法使通用字符串相匹配。颠倒一个字符串。优化速度。优化空间。颠倒一个句子中的词的顺序，比如将“ 我叫克丽丝 ” 转换为 “ 克丽丝叫我 ” ，实现速度最快，移动最少。找到一个子字符串。优化速度。优化空间。比较两个字符串，用O(n)时间和恒量空间。假设你有一个用1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1 到 1000(包括 1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字
8、。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗? 不用乘法或加法增加8 倍。现在用同样的方法增加7 倍。第 9 题- 判断整数序列是不是二元查找树的后序遍历结果名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、 8，由于这一整数序列是如下树的后序遍历结果：8 /
9、 6 10 / / 5 7 9 11 因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。第 10 题- 翻转句子中单词的顺序。题目： 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入 “I am a student.”，则输出 “student. a am I”。第 11 题- 求二叉树中节点的最大距离. 如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义 距离 为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距
10、离。第 12 题题目：求1+2+n ，要求不能使用乘除法、for 、 while、 if、 else、 switch 、 case 等关键字以及条件判断语句（A?B:C） 。第 13 题：题目： 输入一个单向链表，输出该链表中倒数第k 个结点。 链表的倒数第0 个结点为链表的尾指针。链表结点定义如下：struct ListNode 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - int m_nKey; ListNode* m_
11、pNext; ; 第 14 题：题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n) 。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、 15 和数字 15。由于 4+11=15，因此输出4 和 11。第 15 题：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。例如输入：8 / 6 10 / / 5 7 9 11 输出：8 / 10 6 / / 11 9 7 5 定义二元查找树的结点为：
12、struct BSTreeNode / a node in the binary search tree (BST) int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node ; 第 16 题：题目（微软） ：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
13、 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - / 6 10 / / 5 7 9 11 输出 8 6 10 5 7 9 11。第 17 题：题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出 b。分析：这道题是2006 年 google 的一道笔试题。第 18 题：题目： n 个数字（ 0,1, ,n -1）形成一个圆圈，从数字0 开始，每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数字） 。当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。求出在这个圆圈中剩下的最后一个数字。
14、July：我想，这个题目，不少人已经见识过了。第 19 题：题目：定义Fibonacci 数列如下：/ 0 n=0 f(n)= 1 n=1 f(n-1)+f(n-2) n=2 输入 n，用最快的方法求该数列的第n 项。分析：在很多C 语言教科书中讲到递归函数的时候，都会用Fibonacci 作为例子。因此很多程序员对这道题的递归解法非常熟悉，但.呵呵，你知道的。 。第 20 题：题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串345 ，则输出整数345。第 21 题2010 年中兴面试题编程求解：输入两个整数n 和 m，从数列 1，2，3.n 中 随意取几个数 , 使
15、其和等于m ,要求将其中所有的可能组合列出来. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 第 22 题：有 4 张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在A、B、C 三人额头上贴任意两张牌，A、 B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A 说不知道， B 说不知道， C 说不知道，然后A 说知道了。请教如何推理，A 是怎么知道的。如果用程序，又怎么实现呢？第 23
16、题：用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。 3D 坐标系原点(0.0,0.0,0.0) 圆形 : 半径 r = 3.0 圆心 o = (*.*, 0.0, *.*) 正方形 : 4 个角坐标 ; 1:(*.*, 0.0, *.*) 2:(*.*, 0.0, *.*) 3:(*.*, 0.0, *.*) 4:(*.*, 0.0, *.*) 第 24 题：链表操作，（1）.单链表就地逆置，（2）合并链表第 25 题：写一个函数 ,它的原形是int continumax(char *outputstr,char *intputstr) 功能：在字符串中找出连续最长的数字串，并把这
17、个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr 所指内存。例如： abcd12345ed125ss123456789的首地址传给intputstr 后，函数将返回9，outputstr 所指的值为123456789 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 26.左旋转字符串题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef 左旋转 2 位得到字符串
18、cdefab。请实现字符串左旋转的函数。要求时间对长度为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。27.跳台阶问题题目：一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。求总共有多少总跳法，并分析算法的时间复杂度。这道题最近经常出现，包括MicroStrategy 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。28.整数的二进制表示中1 的个数题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制表示为1010，有两个 1，因此输出2。分析：这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。29.栈的
19、 push、pop 序列题目：输入两个整数序列。其中一个序列表示栈的push 顺序，判断另一个序列有没有可能是对应的pop 顺序。为了简单起见，我们假设push 序列的任意两个整数都是不相等的。比如输入的push 序列是 1、2、3、4、5，那么 4、5、3、2、1 就有可能是一个pop 系列。因为可以有如下的push 和 pop 序列：push 1， push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop 序列就是4、5、3、 2、1。但序列 4、3、5、1、2 就不可能是push 序列 1、 2、3、4、5 的 pop 序列。30.
20、在从 1 到 n 的正数中 1 出现的次数题目：输入一个整数n，求从 1 到 n 这 n 个整数的十进制表示中1 出现的次数。例如输入12，从 1 到 12 这些整数中包含1 的数字有1，10，11和 12，1 一共出现了5 次。分析：这是一道广为流传的google 面试题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 31.华为面试题：一类似于蜂窝的结构的图，进行搜索最短路径（要求5 分钟）32. 有两个序列a,b，大小都
21、为n,序列元素的值任意整数，无序；要求：通过交换a,b 中的元素，使 序列 a 元素的和 与序列 b 元素的和 之间的差最小。例如 : var a=100,99,98,1,2, 3; var b=1, 2, 3, 4,5,40; 33. 实现一个挺高级的字符匹配算法：给一串很长字符串，要求找到符合要求的字符串，例如目的串：123 1*3*2 ,12*3这些都要找出来其实就是类似一些和谐系统。 。 。 。34. 实现一个队列。队列的应用场景为：一个生产者线程将int 类型的数入列，一个消费者线程将int 类型的数出列35. 求一个矩阵中最大的二维矩阵(元素和最大 ).如: 1 2 0 3 4 2
22、 3 4 5 1 1 1 5 3 0 中最大的是 : 4 5 5 3 要求 :(1)写出算法 ;(2)分析时间复杂度;(3)用 C 写出关键代码第 36 题-40 题（有些题目搜集于CSDN 上的网友，已标明） ：36.引用自网友： longzuo 谷歌笔试：n 支队伍比赛，分别编号为0，1，2。 。 。 。n-1，已知它们之间的实力对比关系，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 存储在一个二维数组wnn 中，wij
23、 的值代表编号为i，j 的队伍中更强的一支。所以 wij=i 或者 j，现在给出它们的出场顺序，并存储在数组ordern 中，比如 ordern = 4,3,5,8,1.，那么第一轮比赛就是4 对 3， 5 对 8。. 胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4 对 5,直至出现第一名编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组resultn ，求出result。37. 有 n 个长为 m+1 的字符串，如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配， 则两个字符串可以联
24、接，问这 n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。38. 百度面试：1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x 次天平，最多可以从y 个小球中找出较轻的那个，求y 与 x 的关系式2.有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中随机取得m 个记录3.大量的 URL 字符串，如何从中去除重复的，优化时间空间复杂度39. 网易有道笔试：(1). 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，
25、优化时间空间复杂度。(2). 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。40.百度研发笔试题引用自： zp155334877 1)设计一个栈结构，满足一下条件：min，push，pop 操作的时间复杂度为O(1)。2)一串首尾相连的珠子(m 个)，有 N 种颜色 (N=10) ，设计一个算法，取出其中一段，要求包含所有N 中颜色，并使长度最短。并分析时间复杂度与空间复杂度。3)设计一个系统处理词语搭配问题，比如说中国 和人民可以搭配，则中国人民人民中国都有效。要求：* 系统每秒的查询数量可能上千次；* 词语的数量级为10W；* 每个词至多可以与1W 个词搭配当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -