1、 科目代码： 875 科目名称： 计算机专业课程综合 第 1 页 共 4 页 南京师范大学南京师范大学 20212021 年硕士研究生入学考试初试试题（年硕士研究生入学考试初试试题（ B 卷）卷） 科目代码： 875 科目名称： 计算机专业课程综合 满分： 150 分 考生注意：认真阅读答题纸上的注意事项；所有答案必须写在考生注意：认真阅读答题纸上的注意事项；所有答案必须写在答题纸答题纸上，写在本试题纸或草稿纸上上，写在本试题纸或草稿纸上均无效；均无效；本试题纸须随答题纸一起装入试题袋中交回！本试题纸须随答题纸一起装入试题袋中交回！ 数据数据结构结构部分部分（共（共 90 分分） 一、填空题（
2、每空一、填空题（每空 1 分，共分，共 10 分）分） 1.算法的有穷性是指 （1） 。 2. p 指针指向非空单链表中的某个结点，判断该结点是表尾结点的条件是 （2） 。 3.设有 1、2、3、n 共 n 个元素按所列次序入栈，则有 （3） 种可能的出栈序列。 4.循环队列的元素存放在一维数组 datasize中，用变量 front 和 rear 分别表示队头元素和队尾元素在数组中的下标，则该队列中元素个数的计算式是 （4） 。 5.稀疏矩阵压缩存储的方式有十字链表和 （5） 。 6.一棵二叉树中叶子结点有 8 个，单分支结点有 10 个，则该二叉树总结点个数为 （6） 。 7.Dijkst
3、ra 算法的作用是 （7） 。 8.有 10 个结点的无向完全图共有 （8）条边。 9.在长度为 13 的有序表中进行折半查找时， 查找不成功的情况下， 最多需要比较 （9） 次。 10.在 5000 个数据中以最快速度找出前 5 个最大的数，采用 （10） 排序方法最好。 二、简答题（每二、简答题（每小小题题 5 分，共分，共 20 分）分） 1.已知模式串 t=“abcaacbabc” ，请计算出按照 KMP 算法进行串模式匹配时，next 数组的取值。 2.设有一个广义表 L = ( a , ( ) , (c,(e,(f) )，写出其长度值、深度值、表头及表尾。 3.已知二叉树的中序和后
4、序序列分别为 DBAEGFC 和 DBGFECA， 试画出该二叉树， 并给出它的先序遍历序列。 4.请简述 B 树和 B+树的主要区别。 三、求解题（每三、求解题（每小小题题 10 分，共分，共 30 分）分） 1. 已知在一份电文中只使用了 6 个字符 A、B、C、D、E、F，其统计频率分别为 8%、28%、16%、15%、14%、19%。 （1）画出建立的一棵 Huffman 树。 （2）给出每个字符所对应的 Huffman 编码。 2. 已知无向带权图 G=(V,E)，其中 V=A,B,C,D,E,F,G,H，E=(A,B,2),(A,C,3), 科目代码： 875 科目名称： 计算机专
5、业课程综合 第 2 页 共 4 页 (B,D,2),(C,D,1),(D,E,2),(D,F,4),(E,F,1),(E,G,5),(F,G,2),(F,H,1),(G,H,1)。 （1）画出图 G。 （2）分别用 prim 算法和 kruskal 算法构造该网的最小生成树，要求写出构造的过程。 3. 将关键字序列（21、8、11、18、9、14、26）散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为：H(key)=(key*3) mod 7，处理冲突采用线性探测法，要求装填（载）因子为 0.7。 （1）请画出所构造的散列表。 （2）计算等概率情况下查找成功的平
6、均查找长度。 四、算法题（每四、算法题（每小小题题 10 分，共分，共 30 分）分） 1.已知两个带头结点的整数单链表 A、B，其中数据元素均递增有序，试编写算法：求出 A、B 中数据元素的并集 C，同样以递增顺序存储在单链表 C 中，并将并集中元素的个数存入链表 C 头结点的数据域中。 2.设有整型数组x，试编写算法：将所有偶数集中在数组x的一端，奇数集中在数组x的另一端。要求算法时间复杂度为O(n)。 3. 请编写算法，判断有向图是否存在回路。 计算机网络部分计算机网络部分（共（共 60 分分） 一、名词解释（每一、名词解释（每小小题题 3 3 分，共分，共 1515 分）分） 1.流量
7、控制(Flow Control)和拥塞控制(Congestion Control) 2.IP 地址和 MAC 地址 3.多播(Multicast)和任播(Anycast) 4.无分类编址(CIDR) 5.电路交换和分组交换 二二、简答题（每、简答题（每小小题题 5 5 分，共分，共 2525 分）分） 1.请简要阐述 CSMA/CD 的工作流程以及指数退避算法的作用。 2.请简要阐述互联网采用的分层路由机制以及采用分层路由的原因。 3.一个数据报的总长度为 1972 字节，其中 IP 报文头部为 20 字节，TCP 头部为 20 字节。某个数据链路层除了数据链路层头部之外能够承载的最大数据量是
8、 644 字节。请问在上述链路上传输该数据报，数据报将被分成多少个 IP 分片？给出每一个 IP 分片的片偏移字段值。 4.简要阐述 ARP 协议的工作流程， 并给出 ARP 请求报文和响应报文的报文格式 （源 IP 地址、源 MAC 地址、目的 IP 地址、目的 MAC 地址） 。 科目代码： 875 科目名称： 计算机专业课程综合 第 3 页 共 4 页 5. 某路由器的路由表如下所示： 目的网络 下一跳 202.39.211.0/24 200.0.0.1 202.39.208.0/20 200.0.1.1 202.39.192.0/18 200.0.2.1 202.36.208.0/22
9、 200.0.3.1 0.0.0.0 200.0.4.1 现路由器接收到了如下目的地址的报文，请给出这些报文的下一跳地址： (1)202.36.209.5 (2)202.39.208.6 (3)202.36.212.7 (4)202.39.212.8 (5)202.39.192.8 三三、综合综合题（每题（每小小题题 1010 分，共分，共 2020 分）分） 图 1：拥塞控制窗口大小变化示意图 1.图 1 给出了某个终端使用 TCP 协议时其拥塞控制窗口随时间的大小变化情况。请分别指出图中 所标的位置发生了什么事件？TCP 对这些事件的应对方式是什么，并简要说明其理由。 （10 分） 2.
10、如图 2 所示，G 为网络地址转换(NAT)设备，R1、R2 为路由器，A、B、C 为主机。A 的 MAC地址为 11-11-11-11-11-11,G 左侧端口的 MAC 地址为 22-22-22-22-22-22， G右侧端口的 MAC地址为 33-33-33-33-33-33，R1 左侧端口的 MAC 地址为 44-44-44-44-44-44，R2 右侧端口的 MAC 地址为 55-55-55-55-55-55，C 的 MAC 地址为 66-66-66-66-66-66 （1）请为 A、G 的两个端口、R1 的左侧端口、R2 的右侧端口和 C 配置合适的 IP 地址。 （3 科目代码： 875 科目名称： 计算机专业课程综合 第 4 页 共 4 页 分） （2）假如 A 要给 C 传输一个报文，请给出所传输的报文在 A-G、G-R1 和 R2-C 这三段链路上的报文头部格式（包括源 IP 地址、目的 IP 地址、源 MAC 地址、目的 MAC 地址） 。 （7 分） 图 2：某网络示意图
