[数据结构与算法] 南京大学计院夏令营历年机试笔试题汇总（刷题版）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 南京大学计院夏令营历年机试笔试题汇总（刷题版） -> 正文阅读

[数据结构与算法]南京大学计院夏令营历年机试笔试题汇总（刷题版）

温馨提示

必须熟悉输入输出，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 - 12 = 20，因此共有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);
    }
}