程序员考试下午题知识点总结

程序员考试下午题知识点总结

第一大题：程序框图

程序流程图又称程序框图，是用统一规定的标准符号描述程序运行具体步骤的图形表示。程序框图的设计是在处理流程图的基础上，通过对输入输出数据和处理过程的详细分析，将计算机的主要运行步骤和内容标识出来。程序框图是进行程序设计的最基本依据，因此它的质量直接关系到程序设计的质量。
程序流程图由处理框、判断框、起止框、连接点、流程线、注释框等构成，并结合相应的算法，构成整个程序流程图。
任何复杂的算法，都可以由顺序结构、选择（分支）结构和循环结构这三种基本结构组成，因此，构造一个算法的时候，也仅以这三种基本结构作为“建筑单元”，遵守三种基本结构的规范，基本结构之间可以并列、可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。正因为整个算法都是由三种基本结构组成的，就像用模块构建的一样，所以结构清晰，易于正确性验证，易于纠错，这种方法，就是结构化方法。遵循这种方法的程序设计，就是结构化程序设计。相应地，只要规定好三种基本结构的流程图的画法，就可以画出任何算法的流程图。
参考博客

2至4题 C语言程序设计

1.循环语句

参考博客

2.查找和排序算法（选择、插入、冒泡、快速排序，顺序查找和二分查找）

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：
(1)冒泡排序; (2)选择排序； (3)插入排序； (4)希尔排序； (5)归并排序； (6)快速排序； (7)基数排序； (8)堆排序； (9)计数排序；
(10)桶排序。

常见排序方法与评价标准

稳定性是一个特别重要的评估标准。稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序，这是我们不愿意看到的。我们在使用排序算法或者选择排序算法时，更希望这个次序不会改变，更加稳定，所以排序算法的稳定性，是一个特别重要的参数衡量指标依据。就如同空间复杂度和时间复杂度一样，有时候甚至比时间复杂度、空间复杂度更重要一些。所以往往评价一个排序算法的好坏往往可以从下边几个方面入手：
（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。
（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。
（3）使用场景：排序算法有很多，不同种类的排序算法适合不同种类的情景，可能有时候需要节省空间对时间要求没那么多，反之，有时候则是希望多考虑一些时间，对空间要求没那么高，总之一般都会必须从某一方面做出抉择。
（4）稳定性：稳定性是不管考虑时间和空间必须要考虑的问题，往往也是非常重要的影响选择的因素。

插入排序
插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。插入排序分直接插入排序、折半插入排序和希尔排序3类。

#include 
#include 
int main() {
    int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//随机数组
    int n = sizeof(a)/sizeof(a[0]);//获取数组大小
    int i,j,k;
 //在要排序的一组数中，假定前n-1个数已经排好序，现将第n个数插到前面的有序数列中，
 //使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
    for(i = 0; i < n-1; i ++) {
        for(j = i+1; j > 0; j --)
            if(a[j] < a[j-1]) {
                k = a[j-1];
                a[j-1] = a[j];
                a[j] = k;
            } else
                break;
    }
    for(i = 0; i < n; i ++)//输出排序后的结果
        printf("%d ",a[i]);
    return 0;
}
//运行结果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

冒泡排序
冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第(n一1)个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。

#include 
#include 
int main() {
    int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//随机数组
    int n = sizeof(a)/sizeof(a[0]);//获取数组大小
    int i,j,k;
//比较相邻的两个数据，如果第二个数小，就交换位置。从后向前两两比较，一直到比较最前两个数据。
        for(i = 1; i < n; i ++) {
            for(j = 0; j < n-1; j ++) {
                if(a[j] > a[j+1]) {//从小到大排序
                    k = a[j];
                    a[j] = a[j+1];
                    a[j+1] = k;
                }
            }
        }  
    for(i = 0; i < n; i ++)//输出排序后的结果
        printf("%d ",a[i]);
    return 0;
}
//运行结果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

选择排序
选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法。首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置，再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。使用这种排序时，要注意其中一个不同于冒泡法的细节。举例说明：序列58539．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。

#include 
#include 
int main() {
    int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//随机数组
    int n = sizeof(a)/sizeof(a[0]);//获取数组大小
    int i,j,k;
        //第一次遍历n-1个数，找到最小的数值与第一个元素交换
        //第二次遍历n-2个数，找到最小的数值与第二个元素交换
        // 以此类推
        //第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
    for(i = 0; i < n-1; i ++) {
        for(j = i+1; j < n; j ++) {
             if(a[i] > a[j]) {//从小到大排序
                    k = a[i];
                    a[i] = a[j];
                    a[j] = k;
             }
         }
    }
    for(i = 0; i < n; i ++)//输出排序后的结果
        printf("%d ",a[i]);
    return 0;
}
//运行结果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

快速排序
快速排序的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，最终能够实现将所需排序的无序序列元素变为一个有序的序列。 [3]
归并排序
归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。

#include 
#include 
//先从数列中取出一个数作为key值
//将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边
//对左右两个小数列重复第二步，直至各区间只有1个数。
void quickSort(int a[],int l,int r) {
    if(l>=r)
        return;
    int i = l;
    int j = r;
    int key = a[l];//选择第一个数为key
    while(i<j) {
        while(i<j && a[j]>=key)//从右向左找第一个小于key的值
            j--;
        if(i<j) {
            a[i] = a[j];
            i++;
        }
        while(i<j && a[i]<key)//从左向右找第一个大于key的值
            i++;
        if(i<j) {
            a[j] = a[i];
            j--;
        }
    }
    a[i] = key;
    quickSort(a, l, i-1);//继续排左部分，递归调用
    quickSort(a, i+1, r);//继续排右部分，递归调用
}
int main() {
    int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//随机数组
    int i,n = sizeof(a)/sizeof(a[0]);//获取数组大小
    quickSort(a,0,n-1);//快速排序函数入口
    for(i = 0; i < n; i ++)//输出排序后的结果
        printf("%d ",a[i]);
    return 0;
}
//运行结果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

常见的查找算法

查找算法分类
1）静态查找和动态查找；
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找。
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）
需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。

查找性能
从快到慢：
顺序查找，时间复杂度O(N),
分块查找，时间复杂度O(logN+N/m);
二分查找，时间复杂度O(logN)
Fibonacci查找，时间复杂度O(logN)
差值查找，时间复杂度O(log(logN))
哈希查找，时间复杂度O(1)

顺序查找
说明：属于有序查找，顺序查找适合于存储结构为顺序存储或链接存储的线性表。
复杂度分析：
查找成功时的平均查找长度为：
（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n);
所以，顺序查找的时间复杂度为O(n)。

public static int SequenceSearch(int a[], int value, int n) {
		for(int i=1;i<n;i++) {
			if(a[i]==value) {
				return i;
			}
		}
		return -1;
	}
1
2
3
4
5
6
7
8

二分查找
基本思想：
也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
复杂度分析：
最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；对于一个有1024个元素的数组，在最坏的情况下，二分查找法只需要比较log2n + 1= 11次，而在最坏的情况下线性查找要比较1023次。
注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

// 迭代版
public static int BinarySearch(int a[], int value, int n) {
		int low = 0;
		int high = n-1;
		int mid = 0;
		while (low <= high) {
			mid = low + (high - low) * 1/2;
			if(a[mid] == value) {
				return mid;
			}
			if(a[mid] > value) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		return -1; //return low 应该插入的位置
	}
// 递归版
public int binarySearchRecur(int[] nums, int target, int low, int high) {
	if (low > high) { return low; } //base case
	int mid = low + (high - low) / 2;
	if (nums[mid] > target) {
		return binarySearchRecur(nums,target,low,mid-1);
	} else if (nums[mid] < target) {
		return binarySearchRecur(nums,target,mid+1,high);
	} else {
		return mid;
	}
}
//含有重复数字的情况
//主要区别：等于mid也要将high-1；直到low>high结束，返回low（其实是高位，重复数字的第一位）
public static int BinarySearchDuplicate(int a[], int value, int n) {
	int low = 0;
	int high = n-1;
	int mid = 0;
	while (low <= high) {
		mid = low + (high - low) * 1/2;
		if(a[mid] >= value) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return low;
}
//含有重复数字：递归版
public int firstOccurrenceRecur(int[] nums, int target, int low, int high) {
	if (low > high) { return low; }
		int mid = low + (high - low) / 2;
	if (nums[mid] < target) {
		return firstOccurrenceRecur(nums,target,mid + 1,high);
	} else {
		return firstOccurrenceRecur(nums,target,low,mid-1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

3.字符串相关计算（匹配和对比、复制、取数字、计算单词个数、指针）

参考博文

4.链表（链表的重构：逆转、合并、排序；二叉查找树、树的构造、元素处理）

链表
二叉查找树
树的构造
元素处理

5.函数（函数调用、递归）

参考博文

6.其他数值运算（时间日期）

C语言常用时间函数

5、6选做题（Java、C++ ）

面向对象