第1页 / 共73页
第2页 / 共73页
第3页 / 共73页
第4页 / 共73页
第5页 / 共73页
第6页 / 共73页
第7页 / 共73页
第8页 / 共73页
中科大考研复试面试题.pdf
好多人会问到时间复杂度
各种排序的时间复杂度和性能比较
什么叫堆排序？与快速排序有神马不同？
循环队列的顺序表示中，为什么要空一个位置。。。
什么是二叉查找树，原理
排序算法最优的时间复杂度
哈夫曼树
什么是哈希冲突，及如何解决
深度、广度搜索的过程
迪杰斯克拉算法的过程
链表查询某个元素，平均时间复杂度是多少？
图的存储方式
图的深度遍历是否唯一
图相关概念
连通图的概念
解释下最小生成树
n个节点的图的最小生成树有几个节点，几条边
平衡二叉树
二叉树怎么存储
单链表就地逆置
各种查找总结
m阶的B-树和m阶的B+树主要区别
折半查找，适用范围和时间复杂度
计算机和计算器的区别
线程/进程空间是什么
硬实时和软实时
进程和程序的区别
进程和线程的区别
什么是微内核
call和return 具体做了哪些工作
什么是DMA，什么是中断。DMA和中断有什么区别？
硬中断和软中断是什么，区别是什么？
页面置换算法有哪些？什么是LRU
操作系统中磁盘调度算法
操作系统中的信号量
什么是Pv操作
什么是操作系统
简述操作系统中系统调用过程
虚拟存储器，虚存，问有啥相关算法
存储器管理应具有的功能？（+）
什么是TLB
程序连接方式有哪些？（+）
程序的装入方式有哪些？（+）
什么是交换技术？什么是覆盖技术？及其区别（+）
内存连续分配管理方式有哪几种？（+）
动态分区分配算法有哪些？（+）
什么是拼接技术？（+）
什么是原子操作
什么内部碎片？什么是外部碎片？（+）
常用存储保护方法有哪些？（+）
连续分区分配vs非连续分区分配（+）
什么是页面？什么是块或物理块？（+）
什么是页表？及页表的作用？
段寄存器
进程线程树图
作业与进程的区别
进程的三种状态，以及之间转换的过程
进程调度算法
死锁
分页和分段的区别
死锁及死锁原因
介绍下银行家算法
RAID
数据库里面的：什么分级？什么是ER图？
视图在数据库的第几层
数据库的两级映像是什么，作用
数据库，ER模型转换成关系模型是数据库设计的第几个阶段。
数据库，数据模型有哪几种，说出至少两种的特征
数据库中什么叫主码
数据库的表怎样分级
事务
数据库操纵语言，定义语言，定义、操作、查询、控制
数据库中怎样预防死锁
并发控制是为了保证事务的？
在数据库中什么是关系，它和普通二维表啥区别
视图、索引
还有个根本没见过的说是什么标准。。。在数据库中的那一层？
数据库里的读锁、写锁
数据库里，如何解决数据冗余问题？
关系范式
断点之类的问题
关于显卡的，显卡作用，原理。
VGA
FPGA
算数移位、逻辑移位、循环移位
386的保护模式是什么？
什么是实模式？（+）
芯片组是什么
介绍下南桥和北桥芯片（+）
cache和虚拟存储的功能不同
接口芯片使用8259A8251
组成总线里的异步通信
两个时钟不同步的设备怎么通信?
编译:如何把一个机器的语言拿到另一台机器语言机器上执行
编译原理语法分析句法分析
编译的过程
路由协议有哪些？
通信的同步异步
比特率波特率
网络服务质量包括哪些方面？
什么是信道
信道分类？
什么是模拟信号？什么是数字信号？
什么是基带信号？什么是宽带信号？
java与C++区别他说他想问的是地址方面的.
传送介质和无线网络协议
什么是SHELL
网络里的时延、带宽
网络拥塞
CSMA/CD的原理
数据缓存cache的基本概念
应用层有什么协议，作用
网络各层的设备是什么和工作原理
传统的搜索引擎基本原理？基于内容的搜索？原理及实现？
客机被迫降到水面上，什么姿势才能保证平稳不栽倒水里面？
数据传输方式
数据链路层有哪些协议，举1~2例
电路交换和分组交换的区别及联系
电路交换、报文交换、分组交换主要的区别
什么是PN结？（模电数电）
CDMA全称及原理
ICMP
问我什么是非对称加密？什么是数据安全的特征？
保护频带
问到PPP协议
流量控制在哪些层实现
二层交换机是哪一层的设备，与三层交换机之间的区别？
三网，指哪三网
分组交换的优点及缺点
组成网络协议的三个要素
DNSandDHCP
网络安全有哪些方面
P2P协议
停止等待协议
ipv4地址匮乏解决办法
单工、半双工、全双工
TCP/IP模型分层
IPv4和IPv6怎么相互通信?
IPv4的替代方案
从网络的作用范围进行分类
从网络的使用范围分类
从网络的拓扑结构分类
信道划分，及其典型应用
复用的相关概念（频分、时分、码分等）
计算机网络中使用的信道共享技术有哪些？
中国科大软件学院（2012-2013学年）部分开课老师
中国科大软件学院（苏州）美景
School of Software Engineering
University of Science and Technology of China
2012 年参加中国科大软件学院复试前，收集了一些前几届的面试题目。
和大家分享一下，希望对大家有所帮助。
独上高楼，望尽天涯路。
衣带渐宽终不悔，为伊消的人憔悴。
众里寻她千百度，蓦然回首，伊人却在灯火阑珊处。
turinglife
2013-03-09
1. 好多人会问到时间复杂度.......................................................................................................... 5
2. 各种排序的时间复杂度和性能比较.......................................................................................... 5
3. 什么叫堆排序？与快速排序有神马不同？.............................................................................. 9
4. 循环队列的顺序表示中，为什么要空一个位置。。。.............................................................. 9
5. 什么是二叉查找树，原理........................................................................................................ 10
6. 排序算法最优的时间复杂度.................................................................................................... 10
7. 哈夫曼树....................................................................................................................................10
8. 什么是哈希冲突，及如何解决................................................................................................ 10
9. 深度、广度搜索的过程............................................................................................................ 11
10. 迪杰斯克拉算法的过程.......................................................................................................... 12
11. 链表查询某个元素，平均时间复杂度是多少？.................................................................. 12
12. 图的存储方式..........................................................................................................................12
13. 图的深度遍历是否唯一.......................................................................................................... 12
14. 图相关概念..............................................................................................................................13
15. 连通图的概念..........................................................................................................................13
16. 解释下最小生成树.................................................................................................................. 13
17. n 个节点的图的最小生成树有几个节点，几条边................................................................ 14
18. 平衡二叉树..............................................................................................................................14
19. 二叉树怎么存储...................................................................................................................... 14
20. 单链表就地逆置...................................................................................................................... 14
21. 各种查找总结..........................................................................................................................15
22. m 阶的 B-树和 m 阶的 B+树主要区别................................................................................... 18
23. 折半查找，适用范围和时间复杂度...................................................................................... 18
24. 计算机和计算器的区别.......................................................................................................... 18
25. 线程/进程空间是什么.............................................................................................................19
26. 硬实时和软实时...................................................................................................................... 19
27. 进程和程序的区别.................................................................................................................. 19
28. 进程和线程的区别.................................................................................................................. 19
29. 什么是微内核..........................................................................................................................20
30. call 和 return 具体做了哪些工作.............................................................................................20
31. 什么是 DMA，什么是中断。DMA 和中断有什么区别？..................................................20
32. 硬中断和软中断是什么，区别是什么？.............................................................................. 20
33. 页面置换算法有哪些？什么是 LRU..................................................................................... 21
34. 操作系统中磁盘调度算法...................................................................................................... 22
35. 操作系统中的信号量.............................................................................................................. 23
36. 什么是 Pv 操作........................................................................................................................23
37. 什么是操作系统...................................................................................................................... 24
38. 简述操作系统中系统调用过程.............................................................................................. 24
39. 虚拟存储器，虚存，问有啥相关算法.................................................................................. 24
40. 存储器管理应具有的功能？（+）........................................................................................25
41. 什么是 TLB............................................................................................................................. 26
42. 程序连接方式有哪些？（+）................................................................................................26
43. 程序的装入方式有哪些？（+）............................................................................................26
44. 什么是交换技术？什么是覆盖技术？及其区别（+）........................................................ 26
45. 内存连续分配管理方式有哪几种？（+）............................................................................27
46. 动态分区分配算法有哪些？（+）........................................................................................27
47. 什么是拼接技术？（+）........................................................................................................28
48. 什么是原子操作...................................................................................................................... 28
49. 什么内部碎片？什么是外部碎片？（+）............................................................................28
50. 常用存储保护方法有哪些？（+）........................................................................................28
51. 连续分区分配 vs 非连续分区分配（+）.............................................................................. 28
52. 什么是页面？什么是块或物理块？（+）............................................................................29
53. 什么是页表？及页表的作用？.............................................................................................. 29
54. 段寄存器..................................................................................................................................29
55. 进程线程树图..........................................................................................................................30
56. 作业与进程的区别.................................................................................................................. 30
57. 进程的三种状态，以及之间转换的过程.............................................................................. 30
58. 进程调度算法..........................................................................................................................31
59. 死锁..........................................................................................................................................31
60. 分页和分段的区别.................................................................................................................. 32
61. 死锁及死锁原因...................................................................................................................... 32
62. 介绍下银行家算法.................................................................................................................. 32
63. RAID......................................................................................................................................... 32
64. 数据库里面的： 什么分级？什么是 ER 图？..................................................................... 33
65. 数据库的三级模式结构.......................................................................................................... 34
66. 视图在数据库的第几层.......................................................................................................... 36
67. 数据库的两级映像是什么，作用.......................................................................................... 36
68. 数据库，ER 模型转换成关系模型是数据库设计的第几个阶段。.................................... 36
69. 数据库，数据模型有哪几种，说出至少两种的特征.......................................................... 37
70. 数据库中什么叫主码.............................................................................................................. 37
71. 数据库的表怎样分级.............................................................................................................. 37
72. 事务..........................................................................................................................................37
73. 数据库操纵语言，定义语言，定义、操作、查询、控制.................................................. 38
74. 数据库中怎样预防死锁.......................................................................................................... 38
75. 并发控制是为了保证事务的？.............................................................................................. 38
76. 在数据库中什么是关系，它和普通二维表啥区别.............................................................. 38
77. 视图、索引..............................................................................................................................39
78. 还有个根本没见过的说是什么标准。。。在数据库中的那一层？...................................... 39
79. 数据库里的读锁、写锁.......................................................................................................... 39
80. 数据库里，如何解决数据冗余问题？.................................................................................. 39
81. 关系范式..................................................................................................................................40
82. 断点之类的问题...................................................................................................................... 40
83. 关于显卡的，显卡作用，原理。.......................................................................................... 41
84. VGA.......................................................................................................................................... 41
85. FPGA.........................................................................................................................................41
86. 算数移位、逻辑移位、循环移位.......................................................................................... 41
87. 386 的保护模式是什么？........................................................................................................ 42
88. 什么是实模式？（+）............................................................................................................43
89. 芯片组是什么..........................................................................................................................43
90. 介绍下南桥和北桥芯片（+）................................................................................................44
91. cache 和虚拟存储的功能不同................................................................................................. 44
92. 接口芯片使用 8259A 8251.................................................................................................... 44
93. 组成总线里的异步通信.......................................................................................................... 45
94. 两个时钟不同步的设备怎么通信?........................................................................................ 45
95. 编译:如何把一个机器的语言拿到另一台机器语言机器上执行......................................... 45
96. 编译原理语法分析句法分析.................................................................................................. 45
97. 编译的过程..............................................................................................................................46
98. 路由协议有哪些？.................................................................................................................. 46
99. 通信的同步异步...................................................................................................................... 47
100. 比特率波特率........................................................................................................................47
101. 网络服务质量包括哪些方面？............................................................................................ 48
102. 什么是信道............................................................................................................................48
103. 信道分类？............................................................................................................................48
104. 什么是模拟信号？什么是数字信号？................................................................................ 49
105. 什么是基带信号？什么是宽带信号？................................................................................ 49
106. java 与 C++区别他说他想问的是地址方面的..................................................................... 49
107. 传送介质和无线网络协议.................................................................................................... 51
108. 什么是 SHELL.......................................................................................................................52
109. 网络里的时延、带宽............................................................................................................ 52
110. 网络拥塞................................................................................................................................53
111. CSMA/CD 的原理.................................................................................................................. 53
112. 数据缓存 cache 的基本概念................................................................................................. 54
113. 应用层有什么协议，作用 ................................................................................................. 54
114. 网络各层的设备是什么和工作原理.................................................................................... 54
115. 传统的搜索引擎基本原理？基于内容的搜索？原理及实现？........................................ 54
116. 客机被迫降到水面上，什么姿势才能保证平稳不栽倒水里面？.....................................55
117. 数据传输方式........................................................................................................................55
118. 数据链路层有哪些协议，举 1~2 例.................................................................................... 55
119. 电路交换和分组交换的区别及联系.................................................................................... 55
120. 电路交换、报文交换、分组交换主要的区别.................................................................... 56
121. 什么是 PN 结？（模电数电）............................................................................................. 56
122. CDMA 全称及原理................................................................................................................ 56
123. ICMP....................................................................................................................................... 57
124. 问我什么是非对称加密？什么是数据安全的特征？........................................................ 57
125. 保护频带................................................................................................................................58
126. 问到 PPP 协议....................................................................................................................... 58
127. 流量控制在哪些层实现........................................................................................................ 58
128. 二层交换机是哪一层的设备，与三层交换机之间的区别？............................................ 58
129. 三网，指哪三网.................................................................................................................... 59
130. 分组交换的优点及缺点........................................................................................................ 59
131. 组成网络协议的三个要素.................................................................................................... 59
132. DNS and DHCP.......................................................................................................................60
133. 网络安全有哪些方面............................................................................................................ 61
134. P2P 协议..................................................................................................................................61
135. 停止等待协议........................................................................................................................61
136. ipv4 地址匮乏解决办法.........................................................................................................61
137. 单工、半双工、全双工........................................................................................................ 63
138. TCP/IP 模型分层.................................................................................................................... 63
139. IPv4 和 IPv6 怎么相互通信?................................................................................................. 64
140. IPv4 的替代方案.................................................................................................................... 64
141. 从网络的作用范围进行分类................................................................................................ 64
142. 从网络的使用范围分类........................................................................................................ 65
143. 从网络的拓扑结构分类........................................................................................................ 65
144. 信道划分，及其典型应用.................................................................................................... 65
145. 复用的相关概念（频分、时分、码分等）........................................................................ 65
146. 计算机网络中使用的信道共享技术有哪些？.................................................................... 66
147. 中国科大软件学院（2012-2013 学年）部分开课老师...................................................... 67
148. 中国科大软件学院（苏州）美景........................................................................................ 71
1.1.1.1. 好多人会问到时间复杂度
按数量级递增排列，常见的时间复杂度有：
常数阶 O(1)，对数阶 O(log2n)，线性阶 O(n)，
线性对数阶 O(nlog2n)，平方阶 O(n^2)，立方阶 O(n^3)，
k 次方阶 O(n^k),，指数阶 O(2^n) 。
随着问题规模 nnnn 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
2.2.2.2. 各种排序的时间复杂度和性能比较
排序类别
基本思路 详细
时 间 复 杂 空 间 复 杂 特点 注意
分类
度
度
O(1)，需要
一 个 监 视
哨。
稳 定
排序
最 好 ( 正
序)：O(n)
最 坏 ( 逆
序）：O(n^2)
平 均 ：
O(n^2)
平 均 ：
O(n^2)
O(1)
平 均 ：
O(n^1.3)
O(1)
最坏：O(n2)
平均：O(n2)
O(1)
不 稳
定 排
序
稳 定
排序
不 稳
定 排
序
直接插入排序所产生的有序区
不一定是全局有序的，有序区
中的关键字并不一定大于或小
于 无 序 区 中 所 有 元 素 的 关 键
字，这样每一趟排序并不一定
将一个元素放置在最终的位置
上。插入排序与待排序数据的
顺序有关，当正序时效率最高，
当反序时效率最低。
折半插入排序仅减少了关键字
间的比较次数，而元素的移动
次数不变。
希尔排序每一趟并不产生有序
区，也不一定将一个元素放置
在最终的位置上，希尔排序和
待排序数据的顺序有关，正序
时最高，逆序时效率最低。
起泡排序中所产生的有序区一
定是全局有序的，有序区中的
所有元素的关键字一定大于或
小于无序区中所有元素的关键
字，每一趟排序都将一个元素
放置到最终位置上，起泡排序
与待排序数据的顺序有关，正
序效率最高，逆序效率最低。
在快速排序算法中，并不产生
有序区，但每一趟归位一个元
素，快速排序与待排序数据的
顺序有关，当正序和逆序时效
率都低，只有当数据随机分布，
每次划分的子区间长度大致相
等时效率最高。
插入排序
交换排序
每 一 趟 将
一 个 待 排
序的元素，
按 其 关 键
字 值 的 大
小 插 入 到
已 经 排 序
的 有 序 区
中 的 适 当
位置上，直
到 全 部 插
入完成。
基本思想：
两 两 比 较
待 排 序 元
素 的 关 键
字，发现两
个 元 素 的
次 序 相 反
时 即 进 行
交换，直到
没 有 反 序
的 元 素 为
止。
直接插入排序
折半插入
希尔排序
起泡排序
快速排序：在待排序的 n
个 元 素 中 任 取 一 个 元 素
（通常取第一个元素）作
为基准，把该元素放入最
终的位置上（归为一个元
素），数据序列被此元素划
分成两部分：所有关键字
比该元素关键字小的元素
放置在前一部分，所有比
他大的元素放置在后一部
分，这个过程称为一趟快
速排序，以后对所有的两
部分分别重复上述过程，
直至每部分内只有一个元
素或空为止。
选择排序
基本思想：
每 一 趟 从
简单选择排序：在无序区
中选择关键字最小的元素
O(1)
O(n2 )
不 稳
定 排
有序区全局有序，有序区中的
所有元素关键字要么全部大于
放在有序区的最后，形成
新 的 有 序 区 和 新 的 无 序
区。
堆排序： 一种树形选择排
序 。 在 排 序 过 程 中 ， 将
R[1…n]看成是完全二叉树
的顺序存储结构，利用完
全二叉树中的双亲和孩子
结点之间的关系来找到当
前序列中关键最大/小的元
素。
待 排 序 的
元 素 序 列
中 选 出 关
键 字 最 大
（或最小）
的元素，按
顺 序 放 在
已 排 序 的
元 素 序 列
的 最 后 面
（ 或 最 前
面），直到
全 部 拍 完
为止。
序
O(1)
n
O(nlog2
)
不 稳
定 排
序
无序区，要么全部小于无序区，
每趟排序归为一个元素，时间
复杂度与待排序数据序列的顺
序无关。
建初始堆所需要的比较次数较
多，所以堆排序不适宜于元素
较少的表。
所 产 生 的 有 序 区 一 定 全 局 有
序，有序区要么全部大于或小
于无序区中的关键字，每趟排
序归为一个元素，时间复杂度
与待排序数据顺序无关。
归并排序
基数排序
各种排序方法的综合比较
一.时间性能
1.按平均的时间性能来分，有三类排序方法：
时间复杂度为 O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
直接插入算法
折半插入算法
