logo资料库

中科大软件学院历年面试真题.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：5.15M 资料格式：pdf 举报 版权申诉
第1页 / 共73页
第2页 / 共73页
第3页 / 共73页
第4页 / 共73页
第5页 / 共73页
第6页 / 共73页
第7页 / 共73页
第8页 / 共73页
资料共73页，剩余部分请下载后查看
    School of Software Engineering University of Scienceand Technology of China 2012 年参加中国科大软件学院复试前，收集了一些前几届的面试题目。 和大家分享一下，希望对大家有所帮助。 独上高楼，望尽天涯路。 衣带渐宽终不悔，为伊消的人憔悴。 众里寻她千百度，蓦然回首，伊人却在灯火阑珊处。 turinglife 2013-03-09
    1. 好多人会问到时间复杂度 .......................................................................................................... 5 2. 各种排序的时间复杂度和性能比较 .......................................................................................... 5 .............................................................................. 9 3. 什么叫堆排序？与快速排序有神马不同？ 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............................................................................................................................. 42. 程序连接方式有哪些？（ +） ................................................................................................26 43. 程序的装入方式有哪些？（ +） ............................................................................................26 26
    +）........................................................ 26 +） ............................................................................ 27 44. 什么是交换技术？什么是覆盖技术？及其区别（ 45. 内存连续分配管理方式有哪几种？（ 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 ........................................ 54 115. 传统的搜索引擎基本原理？基于内容的搜索？原理及实现？ 116. 客机被迫降到水面上，什么姿势才能保证平稳不栽倒水里面？ .....................................55 117. 数据传输方式 ........................................................................................................................ 55 118. 数据链路层有哪些协议，举 1~2 例 .................................................................................... 55 119. 电路交换和分组交换的区别及联系 .................................................................................... 55 120. 电路交换、报文交换、分组交换主要的区别 .................................................................... 56 121. 什么是 PN 结？（模电数电） ............................................................................................. 56 122. CDMA 全称及原理 ................................................................................................................ 56 123. ICMP....................................................................................................................................... 57 ........................................................ 57 124. 问我什么是非对称加密？什么是数据安全的特征？ 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 ........................................................................ 65 145. 复用的相关概念（频分、时分、码分等） 146. 计算机网络中使用的信道共享技术有哪些？ .................................................................... 66 147. 中国科大软件学院（ 2012-2013 学年）部分开课老师 ...................................................... 67 148. 中国科大软件学院（苏州）美景 ........................................................................................ 71 1. 好多人会问到时间复杂度 按数量级递增排列，常见的时间复杂度有： 常数阶 O(1) ，对数阶 O(log2n) ，线性阶 O(n) ， 线性对数阶 O(nlog2n) ，平方阶 O(n^2) ，立方阶 O(n^3) ， k 次方阶 O(n^k), ，指数阶 O(2^n) 。 随着 问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2. 各种排序的时间复杂度和性能比较 排序类别 基本思路 详细 时 间 复 杂 空 间 复 杂 特点 注意
    分类 度 度 插入排序 交换排序 每 一 趟 将 一 个 待 排 序的元素， 按 其 关 键 字 值 的 大 小 插 入 到 已 经 排 序 的 有 序 区 中 的 适 当 位置上， 直 到 全 部 插 入完成。 基本思想： 两 两 比 较 待 排 序 元 素 的 关 键 字，发现两 个 元 素 的 次 序 相 反 时 即 进 行 交换，直到 没 有 反 序 的 元 素 为 止。 选择排序 基本思想： 每 一 趟 从 直接插入排序 折半插入 希尔排序 起泡排序 n 快速排序：在待排序的 个 元 素 中 任 取 一 个 元 素 （通常取第一个元素）作 为基准，把该元素放入最 终的位置上（归为一个元 素），数据序列被此元素划 分成两部分：所有关键字 比该元素关键字小的元素 放置在前一部分，所有比 他大的元素放置在后一部 分，这个过程称为一趟快 速排序，以后对所有的两 部分分别重复上述过程， 直至每部分内只有一个元 素或空为止。 简单选择排序：在无序区 中选择关键字最小的元素 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) 不 稳 定 排 序 稳 定 排序 不 稳 定 排 序 直接插入排序所产生的有序区 不一定是全局有序 的，有序区 中的关键字并不一定大于或小 于无序区中所有元素的关键 字，这样每一趟排序并不一定 将一个元素放置在最终的位置 上。插入排序与待排序数据的 顺序有关， 当 正序 时 效率最高 ， 当 反序 时效率最低 。 折半插入排序仅减少了关键字 间的比较次数，而元素的移动 次数不变。 希尔排序每一趟并不产生有序 区，也不一定将一个元素放置 在最终的位置上，希尔排序和 待排序数据的顺序有关， 正序 时 最高 ，逆序 时效率 最低 。 起泡排序中所产生的有序区一 定是 全局有序的 ，有序区中的 所有元素的关键字一定大于或 小于无序区中所有元素的关键 字，每一趟排序都将一个元素 放置到最终位置上，起泡排序 与待排序数据的顺序有关， 正 序 效率 最高 ， 逆序 效率 最低 。 在快速排序算法中，并 不产生 有序区 ，但每一趟归位一个元 素，快速排序与待排序数据的 顺序有关，当 正序 和 逆序 时 效 率都低 ，只有当数据随机分布， 每次划分的子区间长度大致相 等时效率最高。 O(1) O( n2 ) 不 稳 定 排 有序区全局有序 ，有序区中的 所有元素关键字要么全部大于
    放在有序区的最后，形成 新 的 有 序 区 和 新 的 无 序 区。 堆排序： 一种树形选择排 序 。 在 排 序 过 程 中 ， 将 R[1… n] 看成是完全二叉树 的顺序存储结构，利用完 全二叉树中的双亲和孩子 结点之间的关系来找到当 前序列中关键最大 /小的元 素。 待 排 序 的 元 素 序 列 中 选 出 关 键 字 最 大 （或最小） 的元素， 按 顺 序 放 在 已 排 序 的 元 素 序 列 的 最 后 面 （ 或 最 前 面），直到 全 部 拍 完 为止。 序 O(1) n O(n log2 ) 不 稳 定 排 序 无序区， 要么全部小于无序区， 每趟排序归为一个元素，时间 复杂度与待排序数据序列的 顺 序无关 。 建初始堆所需要的比较次数较 多，所以堆排序不适宜于元素 较少的表。 所产生的 有序区一定全局有 序 ，有序区要么全部大于或小 于无序区中的关键字，每趟排 序归为一个元素，时间复杂度 与 待排序数据顺序无关 。 归并排序 基数排序 各种排序方法的综合比较 一.时间性能 1.按平均的时间性能来分，有三类排序方法： 时间复杂度为 O(nlogn) 的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好； 直接插入算法
    折半插入算法
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料