1.灰度等级为256级,分辨率为1024*1024的显示器,至少需要的帧缓存容量为(1MB

灰度 = 256 = 2^8 ,因此需要8比特表示
缓存 = 8bit * 1k * 1k = 8Mbit = 8MB

2.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66),则以第一个关键字65为基准而得到的一趟快速排序结果是(34,56,25,65,86,99,72,66

八大排序基本笔试面试必考

3.在下列几种排序方法中,空间复杂度最高的是(归并排序

  • 归并排序O(N)
  • 快速排序:

    • 就地快排O(1)
    • 使用递归:
      每一次都平分数组,即最优情况是O(logn)
      退化为冒泡排序,即最差情况是O(n)
  • 直接插入、希尔、简单选择、堆排、冒泡都是O(1)
  • 基数排序为O(N+R)

4.下面哪些可能是重载的基本条件(参数的类型不同、参数的顺序不同、参数的个数不同)(注意:是可能为重载的基本条件)

这题强调了可能,因为参数顺序可能是method(int a,int b),也可能是指method(double a,int b)

5.为了保证连接的可靠建立,TCP通常采用(三次握手

三次握手,四次挥手。

6.下列有关计算机网络叙述正确的是(ABC
A.建立计算机网络的最主要的目的是实现资源共享
B.计算机网络是在通信协议控制下实现的计算机互联
C.利用Internet网可以使用远程的超级计算机中心的计算机资源
D.TCP/IP的网络接口层对应的OSI的物理层

7.小明的游戏账号密码是一串8位数字,只记前面5个数字为38034.但他肯定,后面3个数字全是奇数,最后一个数字是5,且后3个数字中相邻数字不相同,小明至少要试多少次才能保证登入(16

3 8 0 3 4 _(奇-后=5) _(1.3.7.9) 5
4*4=16

8.五个球从盒子里拿出来,打乱顺序放回去,均不在原位的排列数是多少(44

4 * ( 2 + 3 * 3 ) = 44

错排公式:
D(n) = (n-1) * ( D(n-1) + D(n-2) ),n >= 3,D(1) = 0 , D(2) = 1+

  1. [xA][][][][]把A放到其它位置有4种情况,这里设A在B位。
  2. [B][A][xC][xD][xE]若把B放在A位,则变成D(n-2)种情况的错排
    [xB][A][xC][xD][xE]若不把B放在A位,因为有这个前提所以B相当于为A的错排,则变成D(n-1)种情况的错排

9.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储比顺序存储要(

链式存储快,查找慢;顺序查找快,存储慢。

10.入栈序列是:a1,a3,a5,a2,a4,a6,出栈序列是:a5,a4,a2,a6,a3,a1,则栈的容量最小是(4

画图即可

11.对某二叉树进行先序遍历的结果是ABDEFC,中序遍历的结果是DBFEAC,则后序遍历的结果是(DFEBCA

先序:根→左→右
中序:左→根→右
后序:左→右→根

思路:通过先序的根1确定中序对应的位置,就可以知道根1前面的所有左子树,再递归下去。

12.对于有n个结点的二叉树,其高度为(不确定)(第一层高度1)

题目说的是二叉树,若为完全二叉树为[log2N]+1;若每层一个节点则高度为N。

13.设输入序列为1,2,3,则经过栈的作用后可以得到(5)中不同的输出序列。

卡特兰数:
f(3) = C36 / 3+1 = ((654)/(321)) / 4 = 20 / 4 = 5

14.一棵完全二叉树第六层有9个叶结点(根为第一层),则结点个数最多有(109

1 + 2 + 4 + 8 + 16 + 32 + 2*(32-9) = 63 + 46 = 109

15.i为整型变量,则以下循环语句的循环次数是(0

for(i=2;i<2;) 
printf(“%d”,i--);

16.64位系统上,定义的变量int* a3占据(48)字节

3 2 8字节 = 48字节

17.当一进程运行时,系统可基于某种原则,强行将其擞下,把处理器分配给其他进程,这种调度方式是(剥夺方式

优先权原则、短进程优先原则、时间片原则,采用直接剥夺的调度方式。

18.i的初值为0,i++在两个进程里面分别执行100次,能得到可能的值包括(0-200

多线程下,i++不是原子性操作,所以可能脏读。

19.在操作系统中同时存在多个进程,它们(可以共享允许共享的系统资源 可以调用同一段程序代码

20.【4399论述题】大学期间除了课程作业外做了哪些开发?用的什么语言?目的是什么?

图书管理系统,java
web爬虫,java
车辆预约系统,java
易网,python
...
尽量写简历上的项目,最好是比赛的。

21.【4399论述题】周围朋友一般因为你的什么特质而佩服你?

变相展示自己的出众点:
每天保持学习,能持之以恒去图书馆学习。
有明确的目标,不断学习前沿技术。
经常做博客积累并分享。

22.【4399论述题】请描述一个例子,你曾经解决过一个别的同学解决不了的技术问题,你是如何做到的

又是变相秀加分项:
Sql优化、GC调优、高并发等等加分的。

23.【4399论述题】大学期间,你是如何学习提升技术能力的,目前积累程度如何,请举例说明

展现自己的自学能力和学习态度,尽量详细写自学过程和坚持不懈。

24.描述一个例子,你曾经给自己设定了一个很高的目标,并且很努力的去完成的一件事

拿具体实例证明,注意可靠性。也是讲自己的目标、时间规划和学习态度。

25.【4399论述题】在工作中,你是更注重团队协作还是个人想法?请举例说明。

在一个代表的领导下,进行团队协作。在需求分析阶段可以开展头脑风暴充分展示个人的想法,再统一决定。开发阶段则各自完成自己的任务。

26.小陆所在的公司实行周末单双休,即一周只休周日,下一周休周六日,如此轮换。已知2016年8月13-14日是双休,输入年月日,以yyyymmdd的格式,如20160814,输出当天是否休息,(不考虑法定节假日)。要求:不能使用时间、日期相关的库函数

参考

#include<iostream>
#include<string>
using namespace std;

int main(){
  string inputString;
  long date;
  cin>> inputString;
  int year,month,day;
  int pos = 0;
  //去除字符串中的逗号
  while((pos=inputString.find(","))!=-1){
      inputString.erase(pos,1);
  }
  //将字符串转换为10进制int型
  date = stoi(inputString,0,10);
  //从日期中提取年月日
  year=date/10000;
  month=date%10000/100;
  day=date%100;
  int weekAfter[7] = {0,1,2,3,4,5,6};
  int weekBefore[7] = {0,6,5,4,3,2,1};
  int mon[12]={31,28,31,30,31,30,31,31,30,31,30,31};
  //判断闰年
  if(year%100!=0&&year%4==0||year%400==0)
    mon[1]=29;
  else
    mon[1]=28;
  int dou=2;  //记录单休双休,0双休,1单休
  int zhou=7; //记录是周几,7周日
  int t=0; //记录week中的下标
  if(date>20160814) //双休周日
  {
      while(year!=2016||month!=8||day!=14){
        day--;
        t++;
        if(month > 8 && day<1){
            day=mon[month];
            month--;
        }else if(year > 2016 && month<1){
            year--;
            month=12;
            if(year%100!=0&&year%4==0||year%400==0)
                mon[1]=29;
            else
                mon[1]=28;
        }
      }
      printf("%d\n",t);
      if(t%7!=0){
        dou=t/7+1;
      }else{
        dou=t/7;
      }
      dou=dou%2; //0为双休1为单休
      zhou=weekAfter[t%7];  //周几,0为周日,6周六,5周五……
  }else if(date<20160814){  //20160814之前
      while(year!=2016||month!=8||day!=14){
          day++;
          t++;
          if(day > mon[month]){
              month++;
              day=1;
          }else if(month>12){
              year++;
              month=1;
              if(year%100!=0&&year%4==0||year%400==0)
                 mon[1]=29;
              else
                 mon[1]=28;
          }
      }
      if(t%7!=0){
        dou=t/7;
      }else{
        dou=t/7;
      }
      dou=dou%2; //0为双休1为单休
      zhou=weekBefore[t%7];  //周几,0为周日
  }else{
      dou = 0;
      zhou = 0;
  }

  if(dou==1){  //单休
    if(zhou!=0) //不是周日
        cout<<"工作"<<endl;
    else
        cout<<"休息"<<endl;
  }else if(dou==0){ //双休
    if(zhou==0||zhou==6){ //是周日或周六
        cout<<"休息"<<endl;
    }else
        cout<<"工作"<<endl;
    }
}

27.将20个球放进12个不同的袋子,每个袋子可以放0-20个球,有多少种放法?分析如何计算,然后编程解答。
进阶问题:每个袋子只能放0个、2个或3个球,该如何计算?

参考

public int ballBag(int bag, int ball) {
        int[][] dp = new int[bag + 1][ball + 1];
        int i, j, k, sum;

        for (i = 1; i <= bag; i++) {
            dp[i][0] = 1;
        }//无论几个包,放入0个球的方法只有一种
    
        for (j = 0; j <= ball; j++) {
            dp[1][j] = 1;
        }//无论几个球,放入1个包的方法也只有一种
    
        for (i = 2; i <= bag; i++) {
            for (j = 1; j <= ball; j++) {
                sum = 0;
                for (k = 0; k <= j; k++) {
                    sum += dp[i - 1][k];
                }
                dp[i][j] = sum;
            }
        }
        return dp[bag][ball];
    }

28.关键字过滤:输入字符串s1和s2,判断s1中是否顺序包含s2中所有字符(大小写敏感),如果否,输出s1,如果是,输出“不可描述”
例:输入ABCde,Ad,输出:不可描述
输入ABCde,AA输出:ABCde
要求:不能使用字符相关的库函数

import java.util.Scanner;
 
public class solution {
 
        public String findit(String str){
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.next();
        String str2 = scanner.next();
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        int p1 = 0;
        int p2 = 0;
        while(p1<str1.length() && p2<str2.length()){
            while(p1<str1.length() && p2<str2.length() && char1[p1]!=char2[p2]){
                p1++;
            }
            p1++;
            p2++;
        }
        if(p2 >= char2.length){
            return new String("不可描述");
        }else{
            return str1;
        }        
    }
}

29.【附加题】n男n女去相亲,活动结束时两两异性间产生匹配值,用1-100整数表示。为了使活动完美,主办方希望找到一种匹配方案,使得所有异性两两匹配,并且中匹配值最大。
1)编程实现匹配算法,并分析时间算法复杂度,估算在你的计算机上n能支持到多大
2)当n比较大时,可能接受次优解,请描述可以怎么优化你的算法或使用别的算法

二分图的最大权匹配,KM算法。

Last modification:September 23rd, 2020 at 04:20 pm
喵ฅฅ