2017年西南民族大学计算机导论之数据结构(C语言版)复试仿真模拟

目录

2017年西南民族大学计算机导论之数据结构(C语言版)复试仿真模拟三套题（一） ................ 2 2017年西南民族大学计算机导论之数据结构(C语言版)复试仿真模拟三套题（二） ................ 8 2017年西南民族大学计算机导论之数据结构(C语言版)复试仿真模拟三套题（三） .............. 15

第 1 页，共 22 页

2017年西南民族大学计算机导论之数据结构(C语言版)复试仿真模拟三套题（一）

说明：本资料为2017复试学员内部使用，严格按照2017复试常考题型及难度全真模拟预测。 ————————————————————————————————————————

一、应用题

1． 主机H通过快速以太网连接Internet, IP地址为

题 a表

服务器S的IP地址为211.68.71.80。

H与S使用TCP通信时，在H上捕获的其中5个IP分组如题a表所示。

请回答下列问题。

（1）题a表中的IP分组中，哪几个是由H发送的?哪几个完成了TCP连接建立过程?哪几个在通过快速以太网传输时进行了填充？

（2）根据题a表中的IP分组，分析S已经收到的应用层数据字节数是多少？

（3）若题a表中的某个IP分组在S发出时的前40字节如题b表所列，则该IP分组到达H时经过了多少个路由器？

题 b表

注：IP分组头和TCP段头结构分别如题a图、题b图所示：

题a图IP分组头结构

第 2 页，共 22 页

题b图TCP段头结构

【答案】（1）由于题a表中1、3、4号分组的源IP地址（第13?16字节）均为192.168.0.8 ，所 以1、3、4号分组是由H发送的。 （coa80008H）

，seq=846b41c5H, 2题a表中1号分组封装的TCP段的FLAG为02H （即SYN=1，ACK=0）

，seq=e059 9feffl，ack=846b41c6H，号分组封装的TCP 段的 FLAG为12H （即 SY=1, ACK=1）

3号分组封装的TCP 段的FLAG为10H （即 ACK=1）seq=846b41c6H, ack=e059 9ff0H，，所以 1、2、3号分组完成了 TCP 连接建立过程。

5号分组的总长度为40由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、（28H）字节，小于46字节，其余分组总长度均大于46字节，所以3、5号分组在通过快速以太网传输时进行了填充。

（2）由3号分组封装的TCP段可知，发送应用层数据初始序号为846b 41c6H,由5号分组封装的TCP段可知，ack为846b 所以5号已经收到的应用层数据的字节数为

（3）由于S发出的IP分组的标识=6811H，所以该分组所对应的是题47-a表中的5号分组。S发出的IP 分组的TTL=40H=64,5号分组的TTL=31H=49, 64-49=15。所以，可以推断该IP分组到达H时经过了15个路由器。

2． 设目标为

模式为

（1）计算模式p的nextval函数值；

（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P的nextval函数值为0110132（P的next函数值为0111232）。 （2）利用KMP（改进的nextval）算法，每趟匹配过程如下： 第一趟匹配：abcab（i=5,j=5） 第二趟匹配：abc（i=7，j=3） 第三趟匹配：a（i=7，j=l） 第四趟匹配：

第 3 页，共 22 页

（成功）abcabaa（i=15，j=8）

3． 文件F由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F中，作为其第30条记录，请回答下列问题，并说明理由。

（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F的文件控制区内容会有哪些改变？

（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？

【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问

块存储块

F的文件区的文件长度加1，起始块号减1

（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29块的链接地址存回磁盘又一次访存。一共就是

次。

4个字节的指针的地址范围为

所以此系统支撑文件的最大长度为

4． 对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。

（1）试问这种二叉树的结点总数是多少？ （2）试证明

。其中：表示第i个叶结点所在的层号（设根结点所在层号为1）。

【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l。

（2）证明：当i=l时，成立。

设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1,对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中.因为

5． 某计算机的CPU主频为500MHz，CPI为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

（1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？

第 4 页，共 22 页

,公式成立。设当i=n-1时公式成立，证明当i=n时公式仍

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2017年西南民族大学计算机导论之数据结构(C语言版)复试仿真模拟在线全文阅读。