南京大学计院夏令营历年机试笔试题汇总（刷题版）

温馨提示

• 必须熟悉输入输出，Java中是Scanner scan = new Scanner(System.in);（在Java.util包下）
• 必须熟悉各类集合框架，如HashMap、ArrayList等。（在Java.util包下）
• 字符串转数字：Integer.valueOf(字符串);
• 必须熟悉动态规划和DFS+回溯。
• 线上可能通过选择题考察计网、数据结构、计组、操作系统等。
• 本人自做答案，有误请指正！

2021年本科生开放日

计算机网络

1、传统IP地址有ABC三类，下面属于B类的形式的是?

• A类地址：网络号占一个字节，且第一位确定为0，可指派的网络号为1.0.0.0~126.0.0.0，因为网络号全0表示本网络，网络号127保留用作环回测试，如127.0.0.1。
• B类地址：网络号占两个字节，前两位确定为10，尽管这样网络号不会存在全0和全1问题，但128.0.0.0是不指派（谢希仁 教材第7版），因此可指派的网络号为128.1.0.0~191.255.0.0。
• C类地址：网络号占三个字节，前三位确定为110，同样192.0.0.0网络号也是不指派的，因此可指派的网络号为192.0.1.0~223.255.255.0。
  注意：主机号也不能全0或全1！

2、TCP连接中，A发送给B大小分别为300、500字节的数据包，已知A的发送序号为200，问：B接受两个数据包后，要通知A已经收到，该信息的序号?

这个300和500字节视为有效载荷，B正确接收到数据包后应回复 ack = 200+300+500 = 1000。
B的确认包：B收到packetA，向A发送确认包packetB（seq=packetA.ack，ack=packetA.seq+packetA.有效载荷）

3、以太网，传输速率100Mbps，信号传播速度200000km/s，如果最小数据帧的长度增大90bits，则
（1）电缆的最大长度能够增加多少？（2）信道利用率是上升还是下降？

数据链路层是学习时容易遗漏的部分，需要以下知识：
以太网MAC帧的最小帧长度为 64 bit；100M以太网的最大电缆长度为100米。
a = τ / T₀ ，其中 τ 是单程端到端时延，T₀是帧的发送时间，等于帧长与发送速率之比。
极限信道利用率为S_max = 1 / (1 + a)，a需要远小于1才能达到较高的极限信道利用率。
（1）a = (τ × 发送速率) / 帧长 = (电缆长度 × 发送速率) / (传播速度 × 帧长)，为保持a不变，帧长由64bit变为154bit，电缆长度由100米变为240.625米。
（2）帧长变大，a变小，信道利用率上升。

数据结构

1、归并排序

2、给定一张图，通过某种遍历方法，得到一个生成树，问采用了哪种遍历方法？

3、m叉树，度为Ni的结点有i个(i=1,2,…m)，问度为0的结点有多少个？

4、n个元素的散列表查找的复杂度是多少？（理想情况）

4、入栈顺序为：1 2 3 4 … n；出栈顺序为：p1 p2 p3 p4 … pn，如果p1=n，则pi=？

5、二叉树有n个结点，查找一个元素最坏的复杂度？

6、AOV中求解拓扑排序，分为abc三个步骤。a. 把？？？为0结点都入栈 b. 如果栈非空， pop栈顶元素Vj，查看它的直接后继Vk，删除Vk的出边，然后重新统计？？？为0的结点，继续入栈 c. 如果栈为空…

7、希尔排序，增量一次为3，2，1，问前两次排完后的结果

操作系统

1、C标准库函数中，哪个函数不借助任何系统调用？ 选项是：A. malloc B. printf C. time D. strtime

D. strtime

2、x86-64架构中，32位虚拟地址空间，4kB页面大小，采用的页表级数是几？

4KB = 2¹⁵ bit
32 - 15 = 17，因此共有2¹⁷个页

3、整数除零后会发送什么信号？ 有选项是：SIGILL、SIGFPE

4、Linux…ELF在gdb执行start后，第一条指令位于？ 有选项是：ELF指向的入口地址

计算机组成原理

1、流水线结构中，branch指令发生跳转，需要插入多少个空操作（bubble）或者阻塞多少个周期？

2、交通卡上显示余额42949672.76元，显示错误，问实际最有可能是多少？

3、CPU访问内存，以下哪种不可能发生？其中CD选项为：C. TLP命中，但发生缺页。 D. cache没有命中，但没有发生缺页。

4、主存地址线32位，按字节编址。cache块大小64Byte，cache的数据容量是64Kbyte，cache采用写回，cache和主存采取直接映射，问cache容量多大？

5、指令取到指令寄存器开始后，POP X2; DIV X2,X1; AND X1,X2; MOV X1 0(X2)，这四种哪一个不会发生异常？

2019年本科生开放日

题1：

给定一个十进制正整数n(0 < n < 1000000000)，每个数位上数字均不为0。n的位数为m。
现在从m位中删除k位(0<k < m)，求生成的新整数最小为多少？
例如: n = 9128456, k = 2, 则生成的新整数最小为12456

思路：
我们选取的贪心策略为，每一步总是选择一个使剩下的数最小的数字删去。
即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。
然后回到串首，按上述规则再删除下一个数字。重复以上过程k次，剩下的数字串便是问题的解了。

package summerCamp.NJU;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 题目见 https://blog.csdn.net/Shaft_/article/details/96226294
 */
public class NJU_2019_01 {

    public static void main(String[] ags){
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入数据");
        Long n = scanner.nextLong(); // 输入的数据

        String data = n.toString(); // 转为字符串
        int len = data.length();
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            list.add(data.charAt(i));
        }

        System.out.println("要删除的位数为");
        int m = scanner.nextInt(); // 读入要删除的位数

        while(m > 0) {
            for (int i = 0 ; i < list.size() - 1; i++){
                if (list.get(i) > list.get(i + 1)) {
                    list.remove(i);
                    m--;
                    break;
                }
                if (list.get(i) < list.get(i + 1) && i == list.size() - 2) {
                    list.remove(i + 1);
                    m--;
                    break;
                }
            }
        }
        System.out.println(list);
    }
}
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

参考

2021年南京大学计算机院夏令营随笔
2019年南京大学计算机本科生开放日机试