2017年云南财经大学算法与数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
2． 画出对算术表达式求值时操作数栈和运算符栈的变化过程。
【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式
表所示。
表 操作数栈和运算符找的变化过程
求值，过程如
3． 假定在一个8位字长的计算机中运行下列C 程序段：
若编译器编译时将8个8位寄存器R1〜R8分别分配给变量
回答下列问题。（提示：带符号整数用补码表示）
（1）执行上述程序段后，寄存器Rl 、R5和R6的内容分别是什么？（用十六进制表示） （2）执行上述程序段后，变量m 和kl 的值分别是多少？（用十进制表示）
（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现? 简述理由。
（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出? 上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？
【答案】（1）无符号整数运算，（Rl ） =x=134=10000110B=86H、（R5）=x-y=246=10010000B=90H、（R6）=x+y=01111100B=7CH。
（2） m 的机器数与x 的机器数相同为86H=1000 0110B，解释为带符号整数（用补码表示）时，其值为-111 1010B= -112; 同理kl=（m-n ）=（x-y ）=90H=1001 0000B，解释为带符号整数（用补码表示）时，其值为-111 1010B=-112；
（3）四种运算可以利用同一个加法器及辅助电路实现，n 位加法器实现的是模2n 无符号整数加法运算。对于无符号整数a 和b , a+b可以直接用加法器实现，而实现；对于带符号整数用补码表示，补码加减运算公式为
：
，所以四种运算都可在n 位加法器
中实现。
（4）判断溢出的方法有3种：一位符号位、进位位和双符号位。上述程序段中只有
语句会发 生溢出，因为2个带符号整数均为负数，它们相加之后，结果小于8位二进制所能表示的最小负数。
4． 证明：具有n 个顶点和多于n-1条边的无向连通图G —定不是树。
【答案】具有n 个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形 成回路的连通图不再是树。
5． 某主机的MAC 地址为00-15-C5-C1-5E-28, IP 地址为10.2.128.100 （私有地址）。题a 图是网络拓扑，题b 图是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASCII 码内容。
题a 图网络拓扑
请
题b 图以太网数据帧（前80字节）
请参考图中的数据回答以下问题。
（1）Web 服务器的IP 地址是什么? 该主机的默认网关的MAC 地址是什么？
（2）该主机在构造题47-b 图的数据帧时，使用什么协议确定目的MAC ±也址? 封装该协议请求报文的以太网帧的目的MAC 地址是什么？
（3）假设HTTP/1.1协议以持续的非流水线方式工作，以此请求一响应时间为RTT ，rfc.html 页面引用了5个JPEG 小图像，则从发出题b 图中的Web 请求开始到浏览器收到全部内容为止，需要多少个RTT?
（4）该帧所封装的IP 分组经过路由器R 转发时，需修改IP 分组头中的哪些字段? 注：以太网数据帧结构和IP 分组头结构分别如题c 图、题d 图所示。
题c 图以太网帧结构
题d 图IP 分组头结构
【答案】（1）以太网的数据部分是IP 数据报，只要找出相应字段所在的字节即可。根据图47-c 可知以太网头部 有6+6+2=14字节，根据图47-d 可知IP 地址有16字节，从图47-b 第一个字节开始数14+16 = 30字节，得目的IP 地址为40.aa.62.20即64.170.98.32。而以太网帧的前6字节00-21-27-21-51-ee 是目的MAC 地址，即为主机的 默认网关10.2.128.1端口的MAC 地址。
（2）该主机在构造题47-b 图的数据帧时，使用ARP 协议确定目的MAC 地址。封装该协议请求报文的以太网帧的目的MAC 地址是广播地址即FF-FF-FF-FF-FF-FF 。
（3）假设HTTP/1.1协议以持续的非流水线方式工作，客户机在收到前一个请求的响应后才能发出下一个请求。第一个RTT 用于请求Web 页面，客户机收到第一个请求的响应后，每访问一次对象就需一个RTT 。rfc.html 页面引用了5个JPEG 小图像，则从发出题47-b 图中的Web 请求开始到浏览开始到浏览器受到全部内容为止，故共需1+5 = 6个RTT 后浏览器收到全部内容。
（4）私有地址要和Internet 上的主机通信时，须由NAT 路由器进行网络地址转换，转换为一
相关内容
相关标签