(完整版)复试题

1、数据结构 1. 链表可以用什么实现 2. 折半查找的时间复杂度，前提条件 3. 二叉树排序算法 4. 单链表的空间复杂度和时间复杂度 5. 完全二叉树 6. 什么是堆，有什么作用 7. 排序的最优复杂度 8. 如何实现循环队列，有什么好处 9. 队列的线性表示法中，为什么要留空一个位置？ 10. 单链表中查找某一元素的时间复杂度？ 11. 深度优先搜索形成的是什么？（森林，不能说树）森林唯一么？（不唯一，因为邻接表可 能不唯一） 12. 满二叉树的结点个数（n层） 13. 二叉查找树查找的时间复杂度以及中序遍历后得到什么样的序列 14. 快速排序算法 15. 什么图可以进行拓扑排序 16. 折

2、半排序和快速排序的时间复杂度和空间复杂度 17. 什么是连通图 18. 描述一下哈夫曼树，就是讲一下它的作用啦 19. 散列表中什么是冲突，冲突的解决办法 20. 图的两种存储方式（顺序表矩阵和链表） 21. 平衡2叉树 22. 折半查找问折半查找复杂度，过程 23. 什么是哈希冲突，及如何解决 24. 简述排序树查找过程 25. 怎样将单链表就地逆置 26. 顺序队列的特征 27. DFS过程，时间/空间复杂度，访问节点的顺序是否唯一 28. 强连通图和连通图的定义；非连通图如何遍历访问每一个节点 29. 堆排序 计算机组成原理or微机原理 1. RAM和ROM的原理和区别 2. 一位全加器

3、的真值表以及逻辑表达式 3. 什么是芯片组 4. 触发器相关的问题 5. 中断的软件实行过程 6. 查询和中断，解释比较 7. 过程调用具体执行了哪些操作 8. PC机的端口是同步的还是异步的？什么是异步？ 9. 控制单元设计分为组合逻辑和微程序两者区别优缺点 10. 关于10接口的，微机原理中的内容，要仔细看下。 11. 中断（概念，补充：中断可不可以被打断，有哪些情况） 12. 简述 RAM、ROM、PROM、EPROM、EEPPROM 的区别 13. 什么是指令，时钟，总线周期，有什么关系 14. 80 x86 的硬件组成 15. 80 x86 的寻址方式 16. 条件查询的工作方式 1

4、7. call 和 return 具体做了哪些工作 dma 和中断有什么区别 18. 选择回答了 cache 的相关知识 操作系统 1. 进程和线程区别 2. 控制管理模块是写在哪个文件里，那个文件是什么文件 3. 磁盘阵列 4. 操作系统的组成 5. 死锁的概念以及解决办法 6. 进程有哪些状态，相互之间怎样转换 7. 虚拟存储器相关的 8. 解释LRU 9. 什么是微内核 10. 操作系统中用到了哪些数据结构中的数据结构？请举例说明 11. 说出常见的进程调度算法，并详细介绍下一中2-3 个的原理 12. 什么是饥饿？（即操作系统中的进程饿死相关问题） 13. 常用的页面置换算法有哪些？（

5、最优，clock, FIFO, LRU等）LRU是如何实现的？（在每 个页面设置一个时间项，及时更新） 14. 进程和程序的区别 15. 什么是软实时和硬实时！ 16. 关于内存 CPU 管理，自己设计，怎么管，怎么写，怎么硬件沟通。 17. 什么是 PV 操作 18. DMA 19. 段表 20. 口头叙述 clock 算法的实现过程 计算机网络 1. 连接 2个局域网需要用什么 在那一层 2. TCP 与 UDP 的连接区别及适用情况 3. 路由和交换的区别 4. 七层网络结构 5. 时分复用的时隙 6. IPV4和IPV6的位数 7. 单工、半双工、全双工 8. 集线器 交换机 路由器分

6、别是网络哪一层的 9. 网络通信过程 10. 简述一下停等协议 11. 应用层有什么协议，举出两个协议的作用 12. 数据链路层的作用 13. 路由协议有哪些 14. 频分复用如何避免各路信号间的干扰 15. 简述计算机网络中各层作用 这问题回答之后 老师一直追着网络层问了好多 问得我发懵 了。 16. 列举数据链路层的协议。 。 2个即可 17. 网络各层的设备分别是什么 18. 什么是滑动窗口协议 19. PPP 协议 20. 网络按地理范围分 21. 保护频带 就是插入一些 空白的频段 22. 一个网络安全有哪些方面，还有个 p2p 协议 23. DNS DHCP DNS 倒是记得是让网

7、址转换 IP 地址的 映射 IP 地址 动态主机。 。协 议 DHCP 是动态分配 ip 吗 24. 流量控制在哪些层实现 25. 频分复用 时分复用 波分复用 码分复用 26. 拥塞控制发生在哪一层 27. CSMA/CD 协议 如果两端同时发送信息会出现什么情况，为什么？ 28. 线路交换，分组交换 29. 简述下 CSMA/CD 协议的实现原理 30. 描述网络某一层的原理 31. 说一下路由器的原理 数据库 1. 什么是视图 2. 数据库分几层，并简述 3. 什么是关系 4. 三层模式映射 5. 什么事数据库的两级映像，有什么作用 6. 描述一下关系模式的定义和一个关于范式的小问题 7

8、. DDL ， DML 8. 什么是数据库的两级映像 9. 什么分级 什么 er 图 10. 操纵语言 定义语言 11. 定义、操作、查询、控制 12. 关系和二维表什么区别 13. 并发控制是为了保证事务的？ 14. 模式的两种映射 15. E-R 图形成于什么阶段，还有 E-R 图相关概念，作用 16. 说出至少三种数据库类型（关系，层次，网状什么的）并简要解释了一下，然后数据库那 个关系型数据库说了半天的定义， 最后才知道老师想听到的是关系型数据库就是一个二维表。 只 问了问题就没了 语言 1. C语言里面指针问题 2. C中结构体和共同体区别 3. 面向对象的定义和特征 4. C+和C

9、有什么区别，什么是面向对象面向过程，从抽象的角度说说什么是类的继承和泛 化 5. 面像对象有什么特征 6. 指针的指针 7. 测试和调试有啥区别 8. C语言中怎样定义字符串 编译原理 1. 编译过程有哪些步骤，编译过程生成什么文件。 2. 自己设计个编译系统。觉得怎么设计个编译系统能让一台机子跑另一个机子的指令。说系 统的设计，想法。 3. 具体讲讲语法分析的所有过程以及联系。对于上一个编译系统如何理解，如何运用。 4. 简述编译的基本过程（编译程序把高级语言程序转换到机器语言的过程），如第一步是词 法分析，回答后面的几步，语法分析的结果是什么？（是哪种数据结构？好像是这么问的，记 不清了，面试时想了好久说了个语法分析树。） 5. 如何用编译原理解决体系结构中的相关问题 电子、自动化、通信方面 1. 电子线路，集成电路设计流程 2. 单片机和PC机的cpu区别 3. PN节原理 4. 传递函数里并联环节的等效 5. 能控性、能观性概念 6. AD转换后的精度由什么决