专业课计算机科学模拟题2020年(32)
(总分100,考试时间60分钟)
应用题
1. 1.操作系统必须具备的功能有哪些?
2. 2.有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在A和B的原有结点空间上完成。要求： (1)给出算法的基本设计思想。
(2)根据设计思想，采用c或C++或Java语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。
3. 3.已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则打印出该路径上的顶点。
4. 4.如果要实现对8位数据进行汉明校验，需要设置的校验位数有几位?设计该汉明校验码的编码。
5. 5.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。
6. 6.键树(Trie)，又称数字查找树，它是一棵度大于等于2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。请用类C语言或类PAscAL语言编写一个在键树T上查找关键字等于给定值KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。
7. 7.已知二又树T的结点形式为(Uink，data，count，rlink)，在树中查找值为X的结点，若找到，则记数(count)加1：否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
8. 8.现有一个三段的指令流水线，各段经过时间依次为△t，2△t，△t。请画出该流水线连续处理三条不相关指令的时空图，并计算流水线的吞吐率、加速比和效率。
9. 9.下图为多重中断的示意图，请说明该中断系统中实现了几重中断，描述此多重中断的过程。
10. 10.假定系统有三个并发进程read、move和print共享缓冲器B1和B2。进程read负责从输入设备上读信息，每读出一条记录后把它存放到缓冲器B1中。进程move从缓冲器B1中取出一条记录，加工后存入缓冲器B2。进程print将B2中的记录取出打印输出。缓冲器B1和B2每次只能存放一条记录。要求三个进程协调完成任务，使打印出来的与读入的记录的条数，次序完全一样。请用wait和signal原语写出它们的并发程序。 11. 11.段页式存储管理方式中如何实现地址变换?
12. 12.如果一个索引节点为128 B，指针长4 B，状态信息占用68 B，而每块大小为8 KB。问在索引节点中有多大空间给指针?使用直接、一次间接、二次间接和三次间接指针分别可表示多大的文件?
13. 13.假设Internet的2个自治系统构成的网络如下图所示：自治系统ASl由路由器R1连接2个子网构成：自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口IP地址如图所示：
请回答下列问题：假设路由表结构如下表所示，请利用路由聚合技术，给出R2的路由表，要求包括到图中所有子网的路由，且路由表中的路由项尽可能少。
根据操作数所在位置，指出其寻址方式(填空)： 14. 14.操作数在寄存器中，为( )寻址方式。 15. 15.操作数地址在寄存器，为( )寻址方式。 16. 16.操作数在指令中，为( )寻址方式。
17. 17.操作数地址(主存)在指令中，为( )寻址方式。
18. 18.操作数的地址为某一寄存器内容与位移量之和，可以是( )寻址方式。
19. 19.一个UNIX／Linux文件，如果一个盘块的大小为1KB，每个盘块占4B，那么，若进程欲访问偏移为263168B处的数据，需经过几次间接寻址?
因篇幅问题不能全部显示，请点此查看更多更全内容