一、计算机专业综合知识

  1. 快速排序(quick sort)和合并排序(merge sort)两种方法都将输入的待排序序列划分为2个子序列,并且递归地对所得的两个子序列分别排序。请阐述快速排序及合并排序两种算法之间的主要区别

    归并排序:是将数组不断细分成最小的单位,然后每个单位分别排序,排序完毕后合并,重复以上过程最后就可以得到排序结果
    快速排序:是先选定一个基准元素,然后以基准元素划分数组,再在被划分的部分重复以上过程,最后得到排序结果。
    两者都是分治法的思想,不过最后归并排序的合并操作比快速排序的繁琐

    #include <stdio.h>//归并排序
    #include <stdlib.h>
    int *b;
    void print(int *a, int n) {
    for (int i = 0; i < n; ++i) {
    printf("%d",a[i]);
    if(i != n-1) printf(" ");
    }
    printf("\n");
    }
    void merge(int *a, int low, int mid, int high) {
    int i,j,k;
    for (i = low; i <= high; ++i) {
    b[i] = a[i];
    }
    for (i = low, j = mid+1, k = i;i <= mid && j <= high ; k++) {
    if(b[i] <= b[j]) {
    a[k] = b[i++];
    } else {
    a[k] = b[j++];
    }
    }
    while(i <= mid) a[k++] = b[i++];
    while(j <= high) a[k++] = b[j++];
    }
    void mersort(int *a, int low, int high) {
    if(low < high) {
    int mid = (low+high)/2;
    mersort(a,low,mid);
    mersort(a,mid+1,high);
    merge(a,low,mid,high);
    print(a,7);
    }
    }
    int main() {
    int a[7] = {49,38,65,97,76,13,27};
    b = (int *)malloc(7* sizeof(int));
    printf("排序过程如下:\n");
    print(a,7);
    mersort(a,0,6);
    print(a,7);
    return 0;
    }
    #include <stdio.h>//快速排序
    #include <stdlib.h>
    int *b;
    void print(int *a, int n) {
    for (int i = 0; i < n; ++i) {
    printf("%d",a[i]);
    if(i != n-1) printf(" ");
    }
    printf("\n");
    }
    int partiton(int *a, int low, int high){
    int pivot = a[low];
    while(low < high) {
    while(low < high && a[high] >= pivot) high--;
    a[low] = a[high];
    while(low < high && a[low] <= pivot) low++;
    a[high] = a[low];
    }
    a[low] = pivot;
    return low;
    }
    void quicksort(int *a, int low, int high){
    if(low < high){
    int pivotos = partiton(a,low,high);
    print(a,7);
    quicksort(a,low,pivotos-1);
    quicksort(a,pivotos+1,high);
    }
    }
    int main() {
    int a[7] = {49,38,65,97,76,13,27};
    b = (int *)malloc(7* sizeof(int));
    printf("排序过程如下:\n");
    print(a,7);
    quicksort(a,0,6);
    print(a,7);
    return 0;
    }
  2. 请你用任何语言(例如C,C++,Python等)写一个正确的程序完成如下的问题:实现10进制向2进制转换。输入为一个10进制数,输出为该数的2进制表示。例如输入为‘9’,输出为‘1001’

    #include <stdio.h>
    int num[31] = {0};
    int main() {
    int a;
    scanf("%d", &a);
    int i = 0;
    do {
    num[i++] = a % 2;
    a /= 2;
    } while(a);
    for(int j = i - 1; j >= 0; j--) {
    printf("%d", num[j]);
    }
    return 0;
    }
  3. 请你用任何语言(例如C,C++,Python等)写一个正确的程序完成如下的问题:必须用二分法查找(binary search)解决下面的问题。输入为一个从小到大排好序的整数阵列A[0,…,N-1],N代表A阵列的个数,M是要查找的整数。输出是k,这个k代表A[k]是A阵列中的最大数其值是<=M。例如A=[1,3,15,70,108],则N=5.若M=20,则输出k是2

    #include <stdio.h>
    int main() {
    int A[5] = {1,3,15,70,108};
    int M,k=0;
    scanf("%d",&M);
    int low = 0, high = 5,mid;
    while(low <= high) {
    mid = (low+high)/2;
    if(M == A[mid]) {
    k = mid;
    break;
    } else if(M < A[mid]) {
    high = mid-1;
    } else {
    low = mid+1;
    }
    }
    if(A[k] != M) {
    k = mid - 1;
    }
    printf("%d",k);
    return 0;
    }
  4. 请解释进程与线程的差别。可从调度,地址空间,系统开销等角度进行叙述

    根本区别:进程是操作系统资源分配的基本单位,线程是任务调度和执行的基本单位。
    地址空间:进程有自己独立的地址空间,每启动一个进程,系统都会为其分配地址空间;线程没有独立的地址空间,同一进程的线程共享本进程的地址空间。
    资源:进程之间的资源是独立的;同一进程内的线程共享本进程的资源

    开销:进程执行开销大,线程执行开销小;且线程上下文切换比进程上下文切换要快的多

  5. 请简述TCP/IP的IP的功能?TCP的作用又是什么?

    IP是TCP/IP体系中的网络层协议。设计IP的目的是提高网络的可扩展性:一是解决互联网问题,实现大规模、异构网络的互联互通;二是分割顶层网络应用和底层网络技术之间的耦合关系,以利于两者的独立发展。根据端到端的设计原则,IP为主机提供一种无连接、不可靠、尽力而为的数据报传输服务。
    TCP是为了在不可靠的互联网络上提供可靠的端到端字节流的有连接的一个传输协议。
    OSI七层模型:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层
    TCP/IP模型:网络接口层、网络层、传输层、应用层

  6. 阐述目前的计算机层次化存储体系结构,并说明cache存在的意义

    目前的计算机层次化存储结构为寄存器->Cache->主存->磁盘->外部存储器,存储系统层次结构主要体现在“Cache-主存”和“主存-辅存”之间,前者主要解决CPU和主存速度不匹配的问题,后者主要解决存储系统的容量问题。
    随着CPU技术的飞速发展,处理器的速度越来越快,但是与之相匹配的存储器的速度却没有获得相应的提升,这大大限制了CPU的处理性能。Cache就是用来解决这个问题的,Cache位于CPU和主存之间,可以节省CPU从主存读取指令和数据的时间。

  7. 介绍一下你对大数据及其应用的了解

    大数据是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能处理的具有更强的决策力、洞察发现力和流程优化能力的海量、高增长和多样化的信息资产。
    大数据的5V特点:Volume(大量)、Velocity(高速)、Variety(多样)、Value(低价值密度)、Veracity(真实性)
    应用:(1)医疗大数据,拥有大量的病例、病理报告和治愈方案,看病更高效
    (2)生物大数据,改良基因
    (3)金融大数据,理财利器
    (4)交通大数据,畅通出行

二、专业英语翻译

Computer technology has made incredible progress in the roughly 55 years since the first general-purpose electronic computer was created. Today, less than a thousand US dollars will purchase a personal computer that has more performance, more main memory, and more disk storage than a computer bought in 1980 for $1 million. This rapid rate of improvement has come both from advances in the technology used to build computers and from innovation in computer design.

自从第一台通用电子计算机诞生以来,计算机技术在大约55年中取得了令人难以置信的进步。如今,与1980年以100万美元的价格购买的计算机相比,购买一台性能更高,内存更大,磁盘存储量更大的个人计算机的价格还不到一千美元。这种快速的增长率既来自建造计算机的技术进步,也来自计算机设计的创新。

Although technological improvements have been fairly steady, progress arising from better computer architectures has been much less consistent. During the first 25 years of electronic computers, both forces made a major contribution; but beginning in about 1970, computer designers became largely dependent upon integrated circuit technology. During the 1970s, performance continued to improve at about 25% to 30% per year for the mainframes and minicomputers that dominated the industry.

尽管技术进步一直相当稳定,但是更好的计算机体系结构所带来的进步却不一致。在电子计算机的最初25年中,两个部队都做出了重大贡献。但是从1970年左右开始,计算机设计人员开始很大程度上依赖于集成电路技术。在1970年代,主导该行业的大型机和小型计算机的性能继续以每年约25%至30%的速度提高。

The late 1970s saw the emergence of the microprocessor. The ability of the microprocessor to ride the improvements in integrated circuit technology more closely than the less integrated mainframes and minicomputers led to a higher rate of improvement - roughly 35% growth per year in performance.

1970年代末期出现了微处理器。与不那么集成的大型机和微型计算机相比,微处理器能够更紧密地利用集成电路技术的改进的能力带来了更高的改进率-性能每年大约增长35%