精选优质文档-倾情为你奉上计算复杂性老师：程伟（考试内容是我考试下来大概记下来的，选择题和填空题记不太清楚）一、 选择题（单选或多选 15分，每小题3分）1.以下哪些问题是P类问题：A、 PATH B、HAMPATH C、互质问题 D、合数问题2. 以下哪些问题是NP类问题：A、PATH B、HAMPATH C、互质问题 D、合数问题3. 以下哪些问题是NPC问题：A. 团问题 B.3SAT问题 C.独立集问题 D.HAMPATH4. 以下哪些是PSPACE问题：记不清了5.记不清了二、填空题 （15分 一空1分 ）1. 屠呦呦获得了（诺贝尔生理学或医学）奖。2. 计算机界的诺贝尔奖是（图灵奖）。3. 我国唯一获得图灵奖的是（姚期智？）院士。4. 然后下面是两个排序题，时间复杂性排序。P ,NP ,PSPACE NPSPACE EXP排序 P L NL coNL EXP PSPACE（这个排序具体记不清了）二、 简答题（20分，一题4分）
