算法与程序设计笔试题

【简介】感谢网友“炸酱面”参与投稿，下面是小编为大家整理的算法与程序设计笔试题（共10篇），欢迎阅读与收藏。

篇1：算法与程序设计笔试题

简答(30分)

1、extern “C”{}是什么含义?用来解决什么问题，(10分)

2、至少说出两种经典设计模式，并举例说明使用场景，有伪代码更加.(10分)

3、TCP连接的.time_wait是什么状态，描述其发生的场景，说明它存在的好处坏处。(10分)

篇2：算法与程序设计笔试题

1.有一个任务执行器，每天需要定时执行很多任务(任务数N<1000),任务执行器每次只能执行一个任务而任务之间存在依赖关系，如A任务需要依赖于B任务完成后才能进行，虽然各个任务之间依赖关系复杂但是各个任务之间却没有循环依赖的问题，

给出一个合适的任务执行顺序。请详细描述你的算法思路(如需要，可给出伪代码来辅助描述)，并分析其时间和空间复杂度。(20分)

2.编写函数：

统计在某段英文文本完整句子的数目，文本只包括大小写英文字母、空格、点(.)、逗号(,)。

完整句子必须包含至少一个字母并以点结束。要求：请给出完整代码，在达到目标的情况下尽量高效，简介。(20分)

篇3：C笔试题算法

冒泡法：

这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： #include

void BubbleSort(int* pData,int Count)

{

int iTemp;

for(int i=1;i

{

for(int j=Count-1;j>=i;j--)

{

if(pData[j]

{

iTemp = pData[j-1];

pData[j-1] = pData[j];

pData[j] = iTemp;

}

}

}

}

void main

{

int data = {10,9,8,7,6,5,4};

BubbleSort(data,7);

for (int i=0;i<7;i++)

cout<

}

倒序

第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)

第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)

第一轮：7,8,10,9->7,8,9,10(交换1次)

循环次数：6次

交换次数：6次

其他：

第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)

第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)

第一轮：7,8,10,9->7,8,9,10(交换1次)

循环次数：6次

交换次数：3次

上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。

现在注意，我们给出O方法的定义：

若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵，不要说没学好数学呀，对于编程数学是非常重要的!!!)

现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。

再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样(每次循环判断都会交换)，复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。

篇4：C笔试题算法

选择法：

现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能(某些情况下)

这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。

#include

void SelectSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=0;i

{

iTemp = pData[i];

iPos = i;

for(int j=i+1;j

{

if(pData[j]

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData[i];

pData[i] = iTemp;

}

}

void main

{

int data = {10,9,8,7,6,5,4};

SelectSort(data,7);

for (int i=0;i<7;i++)

cout<

}

倒序(最糟情况)

第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)

第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)

循环次数：6次

交换次数：2次

其他：

第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)

第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)

循环次数：6次

交换次数：3次

遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。

我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。

所以，在数据较乱的时候，可以减少一定的交换次数。

篇5：C笔试题算法

交换法：

交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。

#include

void ExchangeSort(int* pData,int Count)

{

int iTemp;

for(int i=0;i

{

for(int j=i+1;j

{

if(pData[j]

{

iTemp = pData[i];

pData[i] = pData[j];

pData[j] = iTemp;

}

}

}

}

void main

{

int data = {10,9,8,7,6,5,4};

ExchangeSort(data,7);

for (int i=0;i<7;i++)

cout<

}

倒序

第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)

第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次)

第一轮：7,8,10,9->7,8,9,10(交换1次)

循环次数：6次

交换次数：6次

其他：

第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)

第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次)

第一轮：7,8,10,9->7,8,9,10(交换1次)

循环次数：6次

交换次数：3次

从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好，在某些情况下稍差)。

篇6：笔试题算法类

笔试题（算法类）

算法

1，鸟与火车问题，鸟和a火车从A地出发开往B，b火车从B地同时开往A，鸟在碰到b后往回飞，碰到a再往回飞，直到两车相碰，问鸟飞了多远，知道a，b，鸟的速度，和AB距离，

2，3顶黑色和2顶白色帽子，3个outlaw，每人一顶，自己不知道自己什么颜色，第一个猜错入狱，第二个也猜错入狱，第3个猜对了出狱，问如何猜对的'。

3，Give 2 Node , 问如何找得 Common root.(大概意思）。

C/C++

1，判断表达式正确与否(比较简单，会C就会)

2，x86,32位系统，sizeof的大小，

char str[]=”Hello”;char *p=str; int n=10;

问sizeof(str);sizeof(p);sizeof(n)的大小；

void *p=malloc(100)

问sizeof(p)大小；

3，问include和include “filesname.h”区别

4，写一String类，实现atoi(const char *s)功能（大概意思）；

其他

explain how ping works.

篇7：算法与程序设计的教案

算法与程序设计的教案

一、学情分析

通过上学期《算法与编程》部分的学习，学生初步了解算法及其表示、比较熟悉流程图设计；

本学期课程为《算法与程序设计》，对算法的理解更加深入，要求能通过visual basic实现简单算法；

在本课之前，学生应了解了流程图的应用，熟悉在一组数中求极值算法，对于排序及冒泡排序，学生比较熟练。

对于本部分，学生可能会对选择排序算法的原理理解较为困难，需要教师的引导学习。学生应当在学习过程中认真听取教师对于算法的分析，在教师指导下能解释该算法的流程图，进而实现程序。

二、教学目标

知识性目标：

了解排序的概念、能在现实生活中列举出关于排序的实例

能对照冒泡排序，解释选择排序的优势，指出选择排序的策略，找出数字之间的逻辑联系

有迁移应用能力，能由此及彼，归纳排序中的数字规律，探索更有效率的排序算法

技能性目标：

具有模仿水平，在教师指导下可以表达出选择排序的思想，能对流程图作出解释

能独立完成流程图的绘制，对选择排序的各个环节比较熟练，并能在visual basic环境中规范地编写程序

情感、态度、价值观目标：

学生在学习过程中，通过亲身经历体验选择排序的实现过程，获得对此算法的感性认识

利用信息技术手段，开展交流合作，把自己对此算法的心得与他人交流，培养良好的信息素养，提升热爱科学的理念

三、重点难点

重点：对选择排序原理的理解，绘制流程图，数据交换，调试程序

难点：分析流程图

四、教学策略与手段

把握重点，先导入问题，复习排序定义，分析冒泡中数据交换次数多的问题，指出冒泡排序法效率不高，从而引出数据交换次数较少的选择排序算法

在教学过程中，可通过flash演示材料，比较直观地把抽象的问题简单化，由“流程图雏形绘制”-“逐步完善流程图”-“程序实现”-“调试”的过程，让学生熟练此算法与程序实现。

在教学中可灵活运用小组合作、分组讨论、小组间竞赛等手段进行教学，通过发散性思维的培养，增强学生对知识的探索能力。

五、课前准备

1．学生的学习准备：对流程图的绘制方法、vb语法作巩固，对选择排序算法作预习；学生分组：4人一组

2．教师的.教学准备：准备充分的演示材料、相关数据、相关软件安装。

3．教学环境的设计与布置：计算机教室

六、教学过程

简要点拨排序的概念。

演示已经学习过的冒泡排序flash动画。

[小组讨论]在冒泡排序算法中，我们知道冒泡排序是依次把数组中相邻两个数据进行比较，通过交换数据，把较小的数据逐次向上移动的算法。由于数据的移动是逐次进行的，数据交换的次数相当多。大家想想它的实质既然是将一堆数据中的最小数据移动到某个位置，有没有必要让这个数字逐个移动？比如，对于数组：4、8、3、9、6、5、11、10、2、9，如果要用冒泡法实现排序，第一遍冒泡其实是把这组数据中最小数“2”移动到最前边，第二遍冒泡把“3”逐次移到第二个位置，其它类推。它们的过程是逐次向前的，这样做很多无谓的交换。为了达到移动2到最前边的目的我们可以怎么简化这个过程？

[学生]直接把2最前面的数4交换，再把3与第二个位置的数8交换，其它类推

[教师]这个思想就是今天我们要学习的选择排序算法

篇8：笔试题算法设计和编程

1. 请简介各种排序算法(以箱排序，冒泡，快速排序和堆排序为例)的排序过程，及其空间复杂度，平均时间复杂度和最坏时间复杂度．

2. 请检测一个未知长度的单向链表(NULL结束)是否存在环路.

3. 输入一正整数N，去掉其中任意S个数字后，剩下的数字按原左右次序组成一新正整数．寻找一方案，使剩下的.数字组成的新数最小，输出结果．

4. 有一个整数数列, 每个数可以是正, 负或零. 请找出其最佳连续子列使其子列内各数之和为最大.

篇9：知名公司经典算法笔试题

知名公司经典算法笔试题

微软

有一个整数数组，请求出两两之差绝对值最小的值，记住，只要得出最小值即可，不需要求出是哪两个数，

写一个函数，检查字符是否是整数，如果是，返回其整数值。(或者：怎样只用4行代码编写出一个从字符串到长整形的函数?)

给出一个函数来输出一个字符串的所有排列。

请编写实现malloc内存分配函数功能一样的代码。给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。

怎样编写一个程序，把一个有序整数数组放到二叉树中?

怎样从顶部开始逐层打印二叉树结点数据?请编程。

怎样把一个链表掉个顺序(也就是反序，注意链表的边界条件并考虑空链表)?

请编写能直接实现int atoi(const char * pstr)函数功能的代码。

编程实现两个正整数的除法，编程实现两个正整数的除法，当然不能用除法操作符。1// return x/y.2int div(const int x, const int y)3{4 ....5}

在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次，

平面上N个点，每两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。时间效率越高越好。

一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。注意：

5个数值允许是乱序的。比如： 8 7 5 0 6

0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4

0可以多次出现。

复杂度如果是O(n2)则不得分。

设计一个算法，找出二叉树上任意两个结点的最近共同父结点。复杂度如果是O(n2)则不得分。

一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。

一个整数数列，元素取值可能是1~N(N是一个较大的正整数)中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。复杂度最好是O(n)，如果是O(n2)则不得分。

Google

正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除，现给定a和b，需要计算出Q中的前几项，例如，当a=3，b=5，N=6时，序列为3，5，6，9，10，12 (1)、设计一个函数void generate(int a,int b,int N ,int * Q)计算Q的前几项(2)、设计测试数据来验证函数程序在各种输入下的正确性。

有一个由大小写组成的字符串，现在需要对他进行修改，将其中的.所有小写字母排在答谢字母的前面(大写或小写字母之间不要求保持原来次序)，如有可能尽量选择时间和空间效率高的算法 c语言函数原型void proc(char *str) 也可以采用你自己熟悉的语言。

如何随机选取1000个关键字，给定一个数据流，其中包含无穷尽的搜索关键字(比如，人们在谷歌搜索时不断输入的关键字)。如何才能从这个无穷尽的流中随机的选取1000个关键字?

判断一个自然数是否是某个数的平方。说明：当然不能使用开方运算。

给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

1024! 末尾有多少个0?

有5个海盗，按照等级从5到1排列，最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死?(提示：有一个海盗能拿到98%的金币)

23、Google华南地区笔试题。给定一个集合A=[0,1,3,8](该集合中的元素都是在0，9之间的数字，但未必全部包含)，指定任意一个正整数K，请用A中的元素组成一个大于K的最小正整数。比如，A=[1,0] K=21 那么输出结构应该为100。

百度

用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。

用C语言实现函数void * memmove(void *dest, const void *src, size_t n)。memmove 函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。分析：由于可以把任何类型的指针赋给void类型的指针，这个函数主要是实现各种数据类型的拷贝。

有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

腾讯

请定义一个宏，比较两个数a、b的大小，不能使用大于、小于、if语句

两个数相乘，小数点后位数没有限制，请写一个高精度算法

有A、B、C、D四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在17分钟内这四个人都过桥?

有12个小球,外形相同,其中一个小球的质量与其他11个不同，给一个天平,问如何用3次把这个小球找出来，并且求出这个小球是比其他的轻还是重

在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数。

腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。

雅虎

编程实现：把十进制数(long型)分别以二进制和十六进制形式输出，不能使用printf系列

编程实现：找出两个字符串中最大公共子字符串,如“abccade”,“dgcadde”的最大子串为“cad”

有双向循环链表结点定义为：1struct node2{3  int data;4  struct node *front,*next;5};有两个双向循环链表A，B，知道其头指针为：pHeadA,pHeadB，请写一函数将两链表中data值相同的结点删除。

网易

两个圆相交，交点是A1，A2。现在过A1点做一直线与两个圆分别相交另外一点B1，B2。B1B2可以绕着A1点旋转。问在什么情况下，B1B2最长

Smith夫妇召开宴会，并邀请其他4对夫妇参加宴会。在宴会上，他们彼此握手，并且满足没有一个人同自己握手，没有两个人握手一次以上，并且夫妻之间不握手。然后Mr. Smith问其它客人握手的次数，每个人的答案是不一样的。求Mrs Smith握手的次数

篇10：层次遍历算法笔试题

// 二叉树的数据结构

structBinaryTree

{

int value;    // 不写模板了，暂时用整形代替节点的数据类型

BinaryTree *left;

BinaryTree *right;

};

BinaryTree*root;    // 已知二叉树的`根节点

//层次遍历

voidLevel( const BinaryTree *root )

{

Queue *buf = new Queue();    // 定义一个空队列，假设此队列的节点数据类型也是整形的

BinaryTree t;                // 一个临时变量

buf.push_back(root);         //令根节点入队

while( buf.empty == false )    // 当队列不为空

{

p = buf.front();          // 取出队列的第一个元素

cout<

value<<' ';

if( p->left != NULL )     // 若左子树不空，则令其入队

{

q.push( p->left );

}

if( p->right != NULL )    // 若右子树不空，则令其入队

{

q.push( p->right );

}

buf.pop();              // 遍历过的节点出队

}

cout<

}