2008年北航计算机专业基础真题
[color=#000000][b][size=14pt][font=Times New Roman]2008[/font][/size][/b][b][font=宋体][size=14pt]年北航计算机专业基础真题[/size][/font][/b][b][size=14pt][/size][/b][/color][color=#000000][font=宋体] [/font][font=Times New Roman]2008[/font][font=宋体]计算机专业基础[/font][/color]
[color=#000000][font=宋体] 一、简答题[/font][font=Times New Roman](4[/font][font=宋体]’×[/font][font=Times New Roman]5)[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]1[/font][font=宋体]、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]2[/font][font=宋体]、已知元素的入栈顺序为[/font][font=Times New Roman]A,B,C,D,E[/font][font=宋体]，在所有可能的出栈顺序中，写出第一个出栈的元素为[/font][font=Times New Roman]C[/font][font=宋体]且第二个出栈的元素为[/font][font=Times New Roman]D[/font][font=宋体]的所有组合。[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]3[/font][font=宋体]、根据单词[/font][font=Times New Roman](Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr)[/font][font=宋体]的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度[/font][font=Times New Roman]ASL[/font][font=宋体]。[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]4[/font][font=宋体]、证明：具有[/font][font=Times New Roman]n[/font][font=宋体]个顶点的无向图最多有[/font][font=Times New Roman] [/font][font=宋体]条边。[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]5[/font][font=宋体]、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法[/font][font=Times New Roman]?[/font][font=宋体]为什么[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] 二、算法设计题[/font][font=Times New Roman](10[/font][font=宋体]’[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] 已知一非空完全二叉树存放于数组[/font][font=Times New Roman] [/font][font=宋体]中，请写出中序遍历该二叉树的非递归算法。[/font][/color]
[color=#000000][font=宋体] 三、算法设计题[/font][font=Times New Roman](10[/font][font=宋体]’[/font][font=Times New Roman])[/font][/color]
[font=宋体][color=#000000] 写出不带头结点的双向链表的插入排序算法。[/color][/font]
[color=#000000][font=宋体] 四、简答题[/font][font=Times New Roman](4[/font][font=宋体]’×[/font][font=Times New Roman]5)[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]1[/font][font=宋体]、数据传输控制方式有哪些[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]2[/font][font=宋体]、引入线程的目的是什么[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]3[/font][font=宋体]、[/font][font=Times New Roman]P, V[/font][font=宋体]操作是如何实现互斥的的[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]4[/font][font=宋体]、什么是死锁[/font][font=Times New Roman]?[/font][font=宋体]产生死锁的原因是什么[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]5[/font][font=宋体]、什么是文件系统[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] 五、判断题[/font][font=Times New Roman](1[/font][font=宋体]’×[/font][font=Times New Roman]10)[/font][/color]
[color=#000000][font=宋体] 略。[/font][font=Times New Roman]([/font][font=宋体]基本上来自于历年真题[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] 六、解答题[/font][font=Times New Roman](10[/font][font=宋体]’[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] 某机器字长为[/font][font=Times New Roman]16[/font][font=宋体]位，采用段页式存储管理算法，页内偏移为[/font][font=Times New Roman]12[/font][font=宋体]位，段表和页表内容如下，给出[/font][font=Times New Roman]4[/font][font=宋体]个虚拟地址[/font][font=Times New Roman]([/font][font=宋体]二进制形式[/font][font=Times New Roman])[/font][font=宋体]，问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。[/font][font=Times New Roman]([/font][font=宋体]地址格式中段号占[/font][font=Times New Roman]1[/font][font=宋体]位，段内页号占[/font][font=Times New Roman]3[/font][font=宋体]位，页内偏移为[/font][font=Times New Roman]12[/font][font=宋体]位，另外，在给出的页表中，物理块号占[/font][font=Times New Roman]6[/font][font=宋体]位，最后又问该机器的最大物理内存是多少[/font][font=Times New Roman]([/font][font=宋体]答案：[/font][font=Times New Roman]256 KB)[/font][font=宋体]。[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] 七、简答题[/font][font=Times New Roman](4[/font][font=宋体]’×[/font][font=Times New Roman]4)[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]1[/font][font=宋体]、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]2[/font][font=宋体]、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]3[/font][font=宋体]、[/font][font=Times New Roman] [/font][font=宋体]之间的真值关系是什么[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]4[/font][font=宋体]、如何判断公式中某个变元是约束变元还是自由变元[/font][font=Times New Roman]?[/font][font=宋体]举例说明一个变元可以既是约束的又是自由的。[/font][/color]
[color=#000000][font=宋体] 八、判断下列结论是否成立，并至少用两种方法证明你的判断[/font][font=Times New Roman](6[/font][font=宋体]’[/font][font=Times New Roman] + 8[/font][font=宋体]’[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]1[/font][font=宋体]、[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]2[/font][font=宋体]、[/font][/color]
[color=#000000][font=宋体] 九、填空题[/font][font=Times New Roman](1[/font][font=宋体]’×[/font][font=Times New Roman]8)[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]1[/font][font=宋体]、冯•诺依曼计算机体系包括存储器、运算器、控制器和输入输出设备。[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]2[/font][font=宋体]、在总线同步控制方式种，哪一种速度最快，哪一种对电路故障最敏感[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]3[/font][font=宋体]、在程序查询方式、程序中断方式和[/font][font=Times New Roman]DMA[/font][font=宋体]方式中，哪一种方式主存与设备间有数据通路，哪一种方式使[/font][font=Times New Roman]CPU[/font][font=宋体]与外设串行化[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]4[/font][font=宋体]、指令中的操作数分别为立即寻址和寄存器直接寻址时[/font][font=Times New Roman]CPU[/font][font=宋体]访问主存的次数分别为多少次[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman]5[/font][font=宋体]、存储器分层体系是根据程序访问的局部性原理提出的。[/font][/color]
[color=#000000][font=宋体] 十、存储器扩展的题[/font][font=Times New Roman](6[/font][font=宋体]’[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] 某机器字长为[/font][font=Times New Roman]16[/font][font=宋体]位，最大物理内存为[/font][font=Times New Roman]64 KB[/font][font=宋体]，最低地址的[/font][font=Times New Roman]8 KB[/font][font=宋体]存放[/font][font=Times New Roman]BIOS[/font][font=宋体]程序，其他空间存放用户程序，现有[/font][font=Times New Roman]4K[/font][font=宋体]×[/font][font=Times New Roman]4[/font][font=宋体]的[/font][font=Times New Roman]ROM[/font][font=宋体]和[/font][font=Times New Roman]4K[/font][font=宋体]×[/font][font=Times New Roman]4[/font][font=宋体]的[/font][font=Times New Roman]SRAM[/font][font=宋体]，问各需要多少片[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] 十一、[/font][font=Times New Roman]Cache[/font][font=宋体]题[/font][font=Times New Roman](8[/font][font=宋体]’[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] 主存大小为[/font][font=Times New Roman]2 MB[/font][font=宋体]，[/font][font=Times New Roman]Cache[/font][font=宋体]大小为[/font][font=Times New Roman]8 KB[/font][font=宋体]，采用[/font][font=Times New Roman]2[/font][font=宋体]路组相联方式，每个[/font][font=Times New Roman]Cache[/font][font=宋体]块大小为[/font][font=Times New Roman]128[/font][font=宋体]字节。[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman](1)[/font][font=宋体]求主存地址格式及各字段的位数和含义[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman](2)Cache[/font][font=宋体]的格式[/font][/color]
[color=#000000][font=宋体] [/font][font=Times New Roman](3)Cache[/font][font=宋体]的[/font][font=Times New Roman]Tag[/font][font=宋体]需多少位[/font][font=Times New Roman]?[/font][/color]
[color=#000000][font=宋体] 十二、指令系统的设计[/font][font=Times New Roman](8[/font][font=宋体]’[/font][font=Times New Roman])[/font][/color]
[color=#000000][font=宋体] [/font][/color]
页:
[1]