数据结构算法设计笔试面试题1

导读:要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码,请给出解决问题的算法,并证明该算法,里面数据无任何限制,请写一个高精度算法,要求:空间复杂度O(1),时间复杂度为O(n)。9、输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如:输入的数组为1,-2,3,10,-4,

数据结构算法设计笔试面试题1

要求:空间复杂度O(1),时间复杂度为O(n)。 9、输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如:输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。

10、输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。

要求:时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。 例如:输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

11、有两个序列a,b,大小都为n,序列元素的值任意整数,无序;

要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。 例如:

var a=[100,99,98,1,2, 3]; var b=[1, 2, 3, 4,5,40];

12、求一个矩阵中最大的二维矩阵(元素和最大)。如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3

要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码。

13、一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值。 比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1; {3,6}{2,4,3} m=2

{3,3}{2,4}{6} m=3 所以m的最大值为3

14、求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}

15、如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)。

16、输入一个正数n,输出所有和为n连续正数序列。

例如:输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。

17、给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。 要求:空间复杂度O(1),时间复杂度为O(n)。

18、一个整型数组里除了两个数字之外,其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

19、输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。 例如输入数组{32, 321},则输出这两个能排成的最小数字32132。 请给出解决问题的算法,并证明该算法。

20、把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。

例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

21、数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。

22、一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。

能否只用一个额外数组和少量其它空间实现。

23、在一个int数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。

24、求随机数构成的数组中找到长度大于=3的最长的等差数列,输出等差数列由小到大。 格式:

输入[1,3,0,5,-1,6] 输出[-1,1,3,5]

要求时间复杂度,空间复杂度尽量小。

25、递归法求数组中的最大值。[参考]

26、用递归的方法判断整数组a[N]是不是升序排列。

27、计算数组中连续元素和的最大值。[参考]

【其它】

1、1024!末尾有多少个0?[参考]

2、编程实现两个正整数的除法(不能用除法操作符)。

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

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

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

6、输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 例如:如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

则依次打印出数字1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10。

7、用1、2、2、3、4、5这六个数字,写一个main函数,打印出所有不同的排列。

如:512234、412345等,要求:\不能在第三位,\与\不能相连。

8、求两个或N个数的最大公约数和最小公倍数。

9、如果一个整数能够表示成两个或多个素数之和,则得到一个素数和分解式。

对于一个给定的整数,输出所有这种素数和分解式。 注意,对于同构的分解只输出一次(比如5只有一个分解2 + 3,而3 + 2是2 + 3的同构分解式)。

例如,对于整数8,可以作为如下三种分解: (1) 8 = 2 + 2 + 2 + 2 (2) 8 = 2 + 3 + 3 (3) 8 = 3 + 5

10、输入n个整数,输出其中最小的k个。

例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。

11、求1+2+…+n

要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A ? B : C)。

12、定义Fibonacci数列如下: 0 if n = 0

f(n)= 1 if n = 1

f(n-1)+f(n-2) if n >= 2

输入n,用最快的方法求该数列的第n项。[参考]

13、输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,使其和等于m。 要求将其中所有的可能组合列出来。

14、输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。

15、对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)某一个元素也加一。

现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。

16、四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())

17、我们把只包含因子2、3和5的数称作丑数(Ugly Number)。

例如:6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。 求按从小到大的顺序的第1500个丑数。

18、输入数字n,按顺序输出从1最大的n位10进制数。比如输入3,则输出1、2、3一直到最大的3位数即999。

19、大整数数相乘的问题。

五星文库wxphp.com包含总结汇报、资格考试、专业文献、办公文档、word文档、人文社科、考试资料、教学教材、教程攻略、旅游景点、出国留学以及数据结构算法设计笔试面试题1等内容。

本文共3页123