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

本文由简悦 SimpRead 转码，原文地址 blog.csdn.net

温馨提示

必须熟悉输入输出，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 = τ / T0 ，其中 τ 是单程端到端时延，T0 是帧的发送时间，等于帧长与发送速率之比。
极限信道利用率为 Smax = 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. 重复上述过程。

AOV 网：一种以顶点表示活动，以边表示活动的先后次序且没有回路的有向图（有向无环图）。
？？？处填写入度，即入度为 0 的结点入栈。
入度为 0 表示没有前驱结点。

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

希尔排序是一种分组插入排序。
增量初始值一般取为数组长度的一半（向上取整），当增量为 1 时排序结束。

操作系统¶

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

D. strtime

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

4KB = 212 bit
32 - 12 = 20，因此共有 220 个页。
页表项是不可分割的，20 ÷ 12 = 1 余 8，采用两级页表合适。

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

SIGFPE：floating-point exception，浮点异常，包括浮点运算出错、溢出和除数为 0 等。
Linux 中的其它 SIGNAL 信号
SIGILL：illegal instruction 非法指令
SIGHUP：hang up 挂断
SIGBUS：非法地址，包括内存地址对齐出错。
SIGTRAP：由断点指令或其他 trap 指令产生。
SIGPIPE：管道破裂。
SIGSEGV：试图访问未分配给自己的内存, 或试图往没有写权限的内存地址写数据.。

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

计算机组成原理¶

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

我觉得要分情况，是几级流水线结构。

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

卡内余额是一个 int 型整数，4 字节，32 比特，即 232 = 4294967296。
若以无符号数考虑，其值为 0 ~ 4294967296，余额范围 0 ~ 42949672.96。
若以有符号数考虑，其值为 - 2147483648 ~ 2147483648。
最小单位考虑到分，则有符号数表示余额范围：-21474836.48 ~ 21474836.48。
4294967276 = 0xFFFF FFEC，因为负数在存储时采用补码形式，恢复其原码：
0xEC = 0b1110 1100，首先减 1 = 0b1110 1011，然后取反 = 0b1001 0100 = -20（十进制），最高位符号位还是 1，表示负数。
所以应是 - 20，然后还要考虑元角分，因此是 - 0.2 元。

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

C，快表命中，页肯定命中，不可能发生缺页。

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);
    }
}

参考¶

2021 年南京大学计算机院夏令营随笔
 2019 年南京大学计算机本科生开放日机试
 Linux 中的 SIGNAL 信号

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