1、School of Software EngineeringUniversity of Science and Technology of China2012 年参加中国科大软件学院复试前，收集了一些前几届的面试题目。和大家分享一下，希望对大家有所帮助。独上高楼，望尽天涯路。衣带渐宽终不悔，为伊消的人憔悴。众里寻她千百度，蓦然回首，伊人却在灯火阑珊处。turinglife2013-03-09关于版本号：主版本号+次版本号+修订号版本号修改内容修改时间修改人1.0.000第一版本发布2013-03-09turinglife1.0.001增加 2013 年第一批面试真题2013-03-24turi
2、nglife1.0.002追加 2013 年第一批面试真题2013-03-26turinglife1.0.003追加 2013 年第一批面试真题，添加部分题目答案。2013-03-29turinglife1.好多人会问到时间复杂度.62.各种排序的时间复杂度和性能比较.73.什么叫堆排序？与快速排序有神马不同？.104.循环队列的顺序表示中，为什么要空一个位置。.105.什么是二叉查找树，原理.116.排序算法最优的时间复杂度（11,13）.117.哈夫曼树（11,12,13）.118.什么是哈希冲突，及如何解决（13）.119.深度、广度搜索的过程.1210.图的深度优先遍历序列是否唯一？为
3、什么？（13）.1311.迪杰斯克拉算法的过程.1312.链表查询某个元素，平均时间复杂度是多少？.1313.图的存储方式(12,13).1314.图的深度遍历是否唯一.1415.图相关概念.1416.连通图的概念（12,13）.1417.解释下最小生成树.1518.n 个节点的图的最小生成树有几个节点，几条边.1519.平衡二叉树.1520.二叉树怎么存储.1521.单链表就地逆置.1522.各种查找总结.1623.m 阶的 B-树和 m 阶的 B+树主要区别.1924.折半查找，适用范围和时间复杂度.1925.计算机和计算器的区别.1926.线程/进程空间是什么.2027.硬实时和软实时（
4、11,12,13）.2028.进程和程序的区别.2029.进程和线程的区别（11,13）.2030.什么是微内核（11,12,13）.2131.call 和 return 具体做了哪些工作.2132.什么是 DMA，什么是中断。DMA 和中断有什么区别？（12,13）.2133.硬中断和软中断是什么，区别是什么？.2134.什么是内存？（13）.2235.页面置换算法有哪些？什么是 LRU.2236.操作系统中磁盘调度算法.2337.操作系统中的信号量.2438.什么是 Pv 操作.2439.什么是操作系统.2540.简述操作系统中系统调用过程.2541.虚拟存储器，虚存，问有啥相关算法（12
5、,13）.2642.存储器管理应具有的功能？（+）.2643.什么是 TLB.2744.程序连接方式有哪些？（+）.2745.程序的装入方式有哪些？（+）.2746.什么是交换技术？什么是覆盖技术？及其区别（+）.2847.内存连续分配管理方式有哪几种？（+）.2848.动态分区分配算法有哪些？（+）.2849.什么是拼接技术？（+）.2951.什么内部碎片？什么是外部碎片？（+）.2952.常用存储保护方法有哪些？（+）.2953.连续分区分配 vs 非连续分区分配（+）.2954.什么是页面？什么是块或物理块？（+）.3055.什么是页表？及页表的作用？（12,13）.3056.段寄存器.
6、3057.进程线程树图.3158.作业与进程的区别.3159.进程的三种状态，以及之间转换的过程（11,12,13）.3160.进程调度算法.3261.死锁.3262.分页和分段的区别（11,12,13）.3363.死锁及死锁原因.3364.介绍下银行家算法.3365.RAID.3466.数据库里面的：什么分级？什么是 ER 图？.3567.数据库的三级模式结构.3668.视图在数据库的第几层.3769.数据库的两级映像是什么，作用.3770.数据库，ER 模型转换成关系模型是数据库设计的第几个阶段。.3871.数据库，数据模型有哪几种，说出至少两种的特征.3872.数据库中什么叫主码.397
7、3.关系操作有哪些（13）.3974.数据库的表怎样分级.3975.事务是什么？及其四个特征（11,12,13）.3976.数据库操纵语言，定义语言，定义、操作、查询、控制.3977.数据库中怎样预防死锁.4078.并发控制是为了保证事务的什么性质？（11,13）.4079.在数据库中什么是关系，它和普通二维表啥区别.4080.视图、索引.4081.还有个根本没见过的说是什么标准。在数据库中的那一层？.4182.数据库里的读锁、写锁.4183.数据库里，如何解决数据冗余问题？.4184.关系范式.4185.断点之类的问题.4286.关于显卡的，显卡作用，原理。.4287.VGA.4388.FP
8、GA.4389.算数移位、逻辑移位、循环移位.4390.386 的保护模式是什么？.4491.什么是实模式？（+）.4492.芯片组是什么.4593.介绍下南桥和北桥芯片（+）.4594.cache 和虚拟存储的功能不同.4695.接口芯片使用 8259A8251.4696.组成总线里的异步通信.4797.PC 机的串口是同步的还是异步的？(13).4798.512*4 的芯片，要组成 4M 的存储空间要用几个芯片级联。具体用多少引脚。(13)4799.两个时钟不同步的设备怎么通信?.47100.X86 寻址方式有哪些?（2013 年第一批）.47101.编译:如何把一个机器的语言拿到另一台机
9、器语言机器上执行.48102.编译原理语法分析句法分析.48103.编译的过程.48104.路由协议有哪些？.49105.通信的同步异步定义及其相关(11,13).50106.比特率波特率.50107.网络服务质量包括哪些方面？.50108.什么是信道.51109.信道分类？.51110.什么是模拟信号？什么是数字信号？.51111.什么是基带信号？什么是宽带信号？.51112.局部变量和全局变量在内存中是如何存储的（13）.51113.java 与 C+区别他说他想问的是地址方面的.52114.传送介质和无线网络协议.54115.什么是 SHELL（11,13）.54116.网络里的时延、带
10、宽.55117.滑动窗口协议是什么（13）.55118.网络拥塞.55119.CSMA/CD 的原理（12,13）.56120.数据缓存 cache 的基本概念.56121.应用层有什么协议，作用.57122.网络各层的设备是什么和工作原理（12,13）.57123.传统的搜索引擎基本原理？基于内容的搜索？原理及实现？.57124.客机被迫降到水面上，什么姿势才能保证平稳不栽倒水里面？.57125.数据传输方式.57126.数据链路层有哪些协议，举 12 例.58127.电路交换和分组交换的区别及联系.58128.电路交换、报文交换、分组交换主要的区别.58129.什么是 PN 结？（模电数电
11、）.59130.CDMA 全称及原理.59131.ICMP.59132.问我什么是非对称加密？什么是数据安全的特征？.60133.保护频带.60134.问到 PPP 协议.60135.流量控制在哪些层实现.61136.二层交换机是哪一层的设备，与三层交换机之间的区别？.61137.三网，指哪三网.61138.分组交换的优点及缺点.61139.组成网络协议的三个要素.62140.DNS and DHCP.62141.网络安全有哪些方面.63142.P2P 协议.63143.停止等待协议.63144.ipv4 地址匮乏解决办法.64145.单工、半双工、全双工（12,13）.65146.TCP/I
12、P 模型分层（11,12,13）.66147.IPv4 和 IPv6 怎么相互通信?.66148.IPv4 的替代方案.66149.从网络的作用范围进行分类.67150.从网络的使用范围分类.67151.从网络的拓扑结构分类.67152.信道划分，及其典型应用.67153.复用的相关概念（频分、时分、码分等）.68154.计算机网络中使用的信道共享技术有哪些？（13）.68155.自控问的是时域和频域的稳定性判据分别是什么？(13).69156.反馈系统中偏差信号是指什么信号的偏差(13).69157.中国科大软件学院（2012-2013 学年）部分开课老师.70158.中国科大软件学院（苏州
13、）美景.74159.中国科大软件学院（合肥）美景.77160.Reference.781.1.1.1.好多人会问到时间复杂度好多人会问到时间复杂度按数量级递增排列，常见的时间复杂度有：常数阶 O(1)，对数阶 O(log2n)，线性阶 O(n)，线性对数阶 O(nlog2n)，平方阶 O(n2)，立方阶 O(n3)，k 次方阶 O(nk),，指数阶 O(2n)。随着问题规模问题规模 n n n n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。2.2.2.2.各种排序的时间复杂度和性能比较各种排序的时间复杂度和性能比较排序类别排序类别基本思路基本思路详细详细分类分类时 间 复 杂时
14、间 复 杂度度空 间 复 杂空 间 复 杂度度特点特点注意注意插入排序每 一 趟 将一 个 待 排序的元素，按 其 关 键字 值 的 大小 插 入 到已 经 排 序的 有 序 区中 的 适 当位置上，直到 全 部 插入完成。直接插入排序最 好(正序)：O(n)O(1)，需要一 个 监 视哨。稳 定稳 定排序直接插入排序所产生的有序区不一定是全局有序不一定是全局有序的，有序区中的关键字并不一定大于或小于无序区中所有元素的关键字，这样每一趟排序并不一定将一个元素放置在最终的位置上。插入排序与待排序数据的顺序有关，当正序正序时效率最高效率最高，当反序反序时效率最低效率最低。最 坏(逆序）：O(n2)
15、平均：O(n2)折半插入平均：O(n2)O(1)折半插入排序仅减少了关键字间的比较次数，而元素的移动次数不变。希尔排序平均：O(n1.3)O(1)不 稳不 稳定定 排序希尔排序每一趟并不产生有序区，也不一定将一个元素放置在最终的位置上，希尔排序和待排序数据的顺序有关，正序正序时最高最高，逆序逆序时效率最低最低。交换排序基本思想：两 两 比 较待 排 序 元素 的 关 键字，发现两个 元 素 的次 序 相 反时 即 进 行交换，直到没 有 反 序的 元 素 为止。起泡排序最坏：O(n2)平均：O(n2)O(1)稳 定稳 定排序起泡排序中所产生的有序区一定是全局有序的全局有序的，有序区中的所有元素
16、的关键字一定大于或小于无序区中所有元素的关键字，每一趟排序都将一个元素放置到最终位置上，起泡排序与待排序数据的顺序有关，正正序序效率最高最高，逆序逆序效率最低最低。快速排序：在待排序的 n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入最终的位置上（归为一个元素），数据序列被此元素划不 稳不 稳定定 排序在快速排序算法中，并不产生不产生有序区有序区，但每一趟归位一个元素，快速排序与待排序数据的顺序有关，当正序正序和逆序逆序时效效率都低率都低，只有当数据随机分布，每次划分的子区间长度大致相分成两部分：所有关键字比该元素关键字小的元素放置在前一部分，所有比他大的元素放置在后一部分，这个过程称为一趟快速排序，以后对所有的两部分分别重复上述过程，直至每部分内只有一个元素或空为止。等时效率最高。选择排序基本思想：每 一 趟 从待 排 序 的元 素 序 列中 选 出 关键 字 最 大（或最小）的元素，按顺 序 放 在已 排 序 的元 素 序 列的 最 后 面（或 最 前面），直到全 部 拍 完为止。简单选择排序：在无序区中选择关键字最小的元素放在有序区的最后，形成新的有序区和新的无序