2017年南开大学计算机技术、软件工程专业综合基础微机测试之数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：
源操作数目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：
注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：
（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？
（2）转移指令的目标地址范围是多少？
（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句
改变后的内容是什么？
【答案】（1）指令操作码占4位，则指令系统最多可有
量为128KB ，计算机字长为16位，故主存有
需16位。
（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。
（3）汇编语句
寄存器
R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为
：
第 2 页，共 37 页 （逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变? 条不同的指令；指令操作上占6个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有+对应的机器码为该指令执行后，
2． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式
给出它的next 函数值及next 函数的修正值nextval 之值。
【答案】KMP 算法的时间复杂性是p 的next 和nextval 值分别为01112212321和01102201320。
3． 为什么文件的倒排表比多重表组织方式节省空间？
【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。
4． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。
【答案】循环单链表若只设头指针，则出队操作时间复杂度是
是若只设尾指针，则出队和入队操作时间复杂度都是而如对操作时间复杂度
因此，用循环单链表来实现队请 列，设置一个尾指针更合适。
5． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。
（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？
（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？
【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问
块存储块
F 的文件区的文件长度加1，起始块号减1
（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29
块的链接地址存回磁盘又一次访存。一共就是
次。
4个字节的指针的地址范围为
所以此系统支撑文件的最大长度为
第 3 页，共 37 页
6． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？
（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？
（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？
1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（
（2）G2最多n （n-l ）条边，最少n 条边。
（3）G3最多n （n-l ）条边，最少n-1条边。
7． 主机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 图所示：
第 4 页，共 37 页