《IT软件开发笔试面试题》由会员分享，可在线阅读，更多相关《IT软件开发笔试面试题（10页珍藏版）》请在金锄头文库上搜索。
1、计算机笔试/面试题【字符串】1、输入一个字符串，打印出该字符串中字符的所有排列。 例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。2、有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面 （大写或小写字母之间不要求保持原来次序），如有可能尽量选择时间和空间效率高的算法。 c语言函数原型void proc（char *str），也可以采用你自己熟悉的语言。3、编写反转字符串的程序，要求优化速度、优化空间。4、用C语言实现函数void * memmove(void *dest, const vo
2、id *src, size_t n)。 memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。 分析：由于可以把任何类型的指针赋给void类型的指针，这个函数主要是实现各种数据类型的拷贝。5、编程找出两个字符串中最大公共子字符串,如abccade, dgcadde的最大子串为cad。6、输入一个字符串，输出该字符串中对称的子字符串的最大长度。 比如输入字符串google，由于该字符串里最长的对称子字符串是goog，因此输出4。7、字符串原地压缩。题目描述：“eeeeeaaaff 压缩为 e5a3f2，请编程实现。8、请以回溯与不回溯算法实现字符串匹配。9、输入一个
3、英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。 为简单起见，标点符号和普通字母一样处理。 例如：输入I am a student.，则输出student. a am I。10、在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。11、写一个函数，它的原形是int continumax(char *outputstr,char *intputstr) 功能： 在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。 例如：abcd12345ed125ss的首地址传给intp
4、utstr后，函数将返回9，outputstr所指的值为。12、定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。 如：把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。 要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。13、有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接。 问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。14、如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。 注意，并不要求子串
5、（字符串一）的字符必须连续出现在字符串二中。 请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。 例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，则输出它们的长度4，并打印任意一个子串。 分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题。15、输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。 例如，输入They are students.和aeiou，则删除之后的第一个字符串变成Thy r stdnts.。16、一个文件，内含一千万行字符串，
6、每个字符串在1K以内，要求找出所有相反的串对，如abc和cba。17、给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。18、已知一个字符串，比如asderwsde,寻找其中的一个子字符串比如sde的个数，如果没有返回0，有的话返回子字符串的个数。19、求最大连续递增数字串（如ads3slDF3456ld345AA中的）。20、实现strstr功能，即在父串中寻找子串首次出现的位置。21、编码完成下面的处理函数。 函数将字符串中的字符*移到串的前部分，前面的非*字符后移，但不能改变非*字符的先后顺序，函数返回串中字符*的数量。 如原始串为：ab*cd*e*12
7、，处理后为*abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）22、删除字符串中的数字并压缩字符串。如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。23、求两个串中的第一个最长子串（神州数码以前试题）。如abractyeyt，dgdsaeactyey的最大子串为actyet。【栈、链表、树、图】1、编写一个程序，把一个有序整数数组放到二叉树中。2、编程实现从顶部开始逐层打印二叉树节点数据。参考3、编程实现单链表逆转。4、设计一个算法，找出二叉树上任意两个结点的最近共同父结点。复杂度不能为O(n2)。5、二叉排序树中，令f = (最大值+最小
8、值) / 2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度不能为O(n2)。6、有双向循环链表结点定义为： struct node int data; struct node *front,*next; ; 有两个双向循环链表A，B，知道其头指针为：pHeadA、pHeadB，请写一函数将两链表中data值相同的结点删除。7、输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下： struct ListNode int m_nKey; ListNode* m_pNext; ;8、输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，
9、只调整指针的指向。 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 ;参考9、设计包含min函数的栈。 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。
10、10、输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如 输入整数22和如下二元树 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; / left child of node BinaryTreeNode *m_pRight; / right
11、 child of node ;11、给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。 问题扩展： (1) 如果链表可能有环列? (2) 如果需要求出俩个链表相交的第一个节点列?12、输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回true，否则返回false。 例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / 6 10 / / 5 7 9 11 因此返回true。 如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。13、如果我们把二叉树
12、看成一个图，父子节点之间的连线看成是双向的，我们姑且定义距离为两节点之间边的个数。 写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。14、输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。 链表结点定义如下： struct ListNode int m_nKey; ListNode* m_pNext; ;15、输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。 用递归和循环两种方法完成树的镜像转换。 例如输入： 8 / 6 10 / / 5 7 9 11 输出： 8 / 10 6 / / 11 97 5
13、定义二元查找树的结点为： struct BSTreeNode int m_nValue; / value of node BSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node ; 参考16、求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是 这两个节点间边的个数。 比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。17、求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。18、设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。19、请修改append函数，利用这个函数实现： 两个非降序链表的并集，1-
