南京大学2007年博士生入学考试试题--计算机科学与技术基础

2023-04-10 06:22:18 文档大全网 [ 字体：小中大 ] [ 阅读： ]

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《南京大学2007年博士生入学考试试题--计算机科学与技术基础》，欢迎阅读！
南京大学,考试试题,博士生,入学,计算机
南京大学2007年博士生入学考试试题（三小时）

考试科目名称及代码273计算机科学与技术基础适用专业：计算机软件与理论计算机应用技术

注意：

1.所有答案必须写在博士生入学考试答题纸上，写在试卷和其他纸上无效； 2.本科目不允许使用计算器。一．（共25分）图中点独立集是指图中顶点集的一个子集，其中任意两点之间没有边。找出图中最大点独立集是一个优化问题。 1）定义相应的判定问题。

2）证明：该判定问题是NP-问题。

3）证明：如果判定问题能在多项式时间内解，则上述的优化问题也能在多项式时间内解。 4）证明：该判定问题是NP-完全问题。

5）证明：如果独立集判定问题中独立集大小是常数，则该问题为P问题。

二．（10分）程序中的断言是什么？为何要引入它？如何对程序中的断言施加归纳以证明相关程序正确性？这种方法的不足之处何在？三．（15分）以你参加过或了解的软件开发为例，简述一种软件方法或工具，并分析其优点。

四．解释题（共18分，每题3分）

1）解释作业和进程、进程和线程的关系。 2）解释中断（外中断）和异常的概念。 3）解释进程并发中的同步与互斥问题。 4）说明虚拟存储管理的原理。 5）说出3种文件共享方式。 6）给出3种安全机制。