(完整版)復試題

1、數(shù)據(jù)結(jié)構(gòu) 1. 鏈表可以用什么實現(xiàn) 2. 折半查找的時間復雜度，前提條件 3. 二叉樹排序算法 4. 單鏈表的空間復雜度和時間復雜度 5. 完全二叉樹 6. 什么是堆，有什么作用 7. 排序的最優(yōu)復雜度 8. 如何實現(xiàn)循環(huán)隊列，有什么好處 9. 隊列的線性表示法中，為什么要留空一個位置？ 10. 單鏈表中查找某一元素的時間復雜度？ 11. 深度優(yōu)先搜索形成的是什么？（森林，不能說樹）森林唯一么？（不唯一，因為鄰接表可 能不唯一） 12. 滿二叉樹的結(jié)點個數(shù)（n層） 13. 二叉查找樹查找的時間復雜度以及中序遍歷后得到什么樣的序列 14. 快速排序算法 15. 什么圖可以進行拓撲排序 16. 折

2、半排序和快速排序的時間復雜度和空間復雜度 17. 什么是連通圖 18. 描述一下哈夫曼樹，就是講一下它的作用啦 19. 散列表中什么是沖突，沖突的解決辦法 20. 圖的兩種存儲方式（順序表矩陣和鏈表） 21. 平衡2叉樹 22. 折半查找問折半查找復雜度，過程 23. 什么是哈希沖突，及如何解決 24. 簡述排序樹查找過程 25. 怎樣將單鏈表就地逆置 26. 順序隊列的特征 27. DFS過程，時間/空間復雜度，訪問節(jié)點的順序是否唯一 28. 強連通圖和連通圖的定義；非連通圖如何遍歷訪問每一個節(jié)點 29. 堆排序 計算機組成原理or微機原理 1. RAM和ROM的原理和區(qū)別 2. 一位全加器

3、的真值表以及邏輯表達式 3. 什么是芯片組 4. 觸發(fā)器相關(guān)的問題 5. 中斷的軟件實行過程 6. 查詢和中斷，解釋比較 7. 過程調(diào)用具體執(zhí)行了哪些操作 8. PC機的端口是同步的還是異步的？什么是異步？ 9. 控制單元設(shè)計分為組合邏輯和微程序兩者區(qū)別優(yōu)缺點 10. 關(guān)于10接口的，微機原理中的內(nèi)容，要仔細看下。 11. 中斷（概念，補充：中斷可不可以被打斷，有哪些情況） 12. 簡述 RAM、ROM、PROM、EPROM、EEPPROM 的區(qū)別 13. 什么是指令，時鐘，總線周期，有什么關(guān)系 14. 80 x86 的硬件組成 15. 80 x86 的尋址方式 16. 條件查詢的工作方式 1

4、7. call 和 return 具體做了哪些工作 dma 和中斷有什么區(qū)別 18. 選擇回答了 cache 的相關(guān)知識 操作系統(tǒng) 1. 進程和線程區(qū)別 2. 控制管理模塊是寫在哪個文件里，那個文件是什么文件 3. 磁盤陣列 4. 操作系統(tǒng)的組成 5. 死鎖的概念以及解決辦法 6. 進程有哪些狀態(tài)，相互之間怎樣轉(zhuǎn)換 7. 虛擬存儲器相關(guān)的 8. 解釋LRU 9. 什么是微內(nèi)核 10. 操作系統(tǒng)中用到了哪些數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)結(jié)構(gòu)？請舉例說明 11. 說出常見的進程調(diào)度算法，并詳細介紹下一中2-3 個的原理 12. 什么是饑餓？（即操作系統(tǒng)中的進程餓死相關(guān)問題） 13. 常用的頁面置換算法有哪些？（

5、最優(yōu)，clock, FIFO, LRU等）LRU是如何實現(xiàn)的？（在每 個頁面設(shè)置一個時間項，及時更新） 14. 進程和程序的區(qū)別 15. 什么是軟實時和硬實時！ 16. 關(guān)于內(nèi)存 CPU 管理，自己設(shè)計，怎么管，怎么寫，怎么硬件溝通。 17. 什么是 PV 操作 18. DMA 19. 段表 20. 口頭敘述 clock 算法的實現(xiàn)過程 計算機網(wǎng)絡 1. 連接 2個局域網(wǎng)需要用什么 在那一層 2. TCP 與 UDP 的連接區(qū)別及適用情況 3. 路由和交換的區(qū)別 4. 七層網(wǎng)絡結(jié)構(gòu) 5. 時分復用的時隙 6. IPV4和IPV6的位數(shù) 7. 單工、半雙工、全雙工 8. 集線器 交換機 路由器分

6、別是網(wǎng)絡哪一層的 9. 網(wǎng)絡通信過程 10. 簡述一下停等協(xié)議 11. 應用層有什么協(xié)議，舉出兩個協(xié)議的作用 12. 數(shù)據(jù)鏈路層的作用 13. 路由協(xié)議有哪些 14. 頻分復用如何避免各路信號間的干擾 15. 簡述計算機網(wǎng)絡中各層作用 這問題回答之后 老師一直追著網(wǎng)絡層問了好多 問得我發(fā)懵 了。 16. 列舉數(shù)據(jù)鏈路層的協(xié)議。 。 2個即可 17. 網(wǎng)絡各層的設(shè)備分別是什么 18. 什么是滑動窗口協(xié)議 19. PPP 協(xié)議 20. 網(wǎng)絡按地理范圍分 21. 保護頻帶 就是插入一些 空白的頻段 22. 一個網(wǎng)絡安全有哪些方面，還有個 p2p 協(xié)議 23. DNS DHCP DNS 倒是記得是讓網(wǎng)

7、址轉(zhuǎn)換 IP 地址的 映射 IP 地址 動態(tài)主機。 。協(xié) 議 DHCP 是動態(tài)分配 ip 嗎 24. 流量控制在哪些層實現(xiàn) 25. 頻分復用 時分復用 波分復用 碼分復用 26. 擁塞控制發(fā)生在哪一層 27. CSMA/CD 協(xié)議 如果兩端同時發(fā)送信息會出現(xiàn)什么情況，為什么？ 28. 線路交換，分組交換 29. 簡述下 CSMA/CD 協(xié)議的實現(xiàn)原理 30. 描述網(wǎng)絡某一層的原理 31. 說一下路由器的原理 數(shù)據(jù)庫 1. 什么是視圖 2. 數(shù)據(jù)庫分幾層，并簡述 3. 什么是關(guān)系 4. 三層模式映射 5. 什么事數(shù)據(jù)庫的兩級映像，有什么作用 6. 描述一下關(guān)系模式的定義和一個關(guān)于范式的小問題 7

8、. DDL ， DML 8. 什么是數(shù)據(jù)庫的兩級映像 9. 什么分級 什么 er 圖 10. 操縱語言 定義語言 11. 定義、操作、查詢、控制 12. 關(guān)系和二維表什么區(qū)別 13. 并發(fā)控制是為了保證事務的？ 14. 模式的兩種映射 15. E-R 圖形成于什么階段，還有 E-R 圖相關(guān)概念，作用 16. 說出至少三種數(shù)據(jù)庫類型（關(guān)系，層次，網(wǎng)狀什么的）并簡要解釋了一下，然后數(shù)據(jù)庫那 個關(guān)系型數(shù)據(jù)庫說了半天的定義， 最后才知道老師想聽到的是關(guān)系型數(shù)據(jù)庫就是一個二維表。 只 問了問題就沒了 語言 1. C語言里面指針問題 2. C中結(jié)構(gòu)體和共同體區(qū)別 3. 面向?qū)ο蟮亩x和特征 4. C+和C

9、有什么區(qū)別，什么是面向?qū)ο竺嫦蜻^程，從抽象的角度說說什么是類的繼承和泛 化 5. 面像對象有什么特征 6. 指針的指針 7. 測試和調(diào)試有啥區(qū)別 8. C語言中怎樣定義字符串 編譯原理 1. 編譯過程有哪些步驟，編譯過程生成什么文件。 2. 自己設(shè)計個編譯系統(tǒng)。覺得怎么設(shè)計個編譯系統(tǒng)能讓一臺機子跑另一個機子的指令。說系 統(tǒng)的設(shè)計，想法。 3. 具體講講語法分析的所有過程以及聯(lián)系。對于上一個編譯系統(tǒng)如何理解，如何運用。 4. 簡述編譯的基本過程（編譯程序把高級語言程序轉(zhuǎn)換到機器語言的過程），如第一步是詞 法分析，回答后面的幾步，語法分析的結(jié)果是什么？（是哪種數(shù)據(jù)結(jié)構(gòu)？好像是這么問的，記 不清了，面試時想了好久說了個語法分析樹。） 5. 如何用編譯原理解決體系結(jié)構(gòu)中的相關(guān)問題 電子、自動化、通信方面 1. 電子線路，集成電路設(shè)計流程 2. 單片機和PC機的cpu區(qū)別 3. PN節(jié)原理 4. 傳遞函數(shù)里并聯(lián)環(huán)節(jié)的等效 5. 能控性、能觀性概念 6. AD轉(zhuǎn)換后的精度由什么決