經典數據結構面試題含答案(已修改)

　

【正文】 棧和隊列的共同特點是__________________________.棧通常采用的兩種存儲結構是______________________.用鏈表表示線性表的優點是_______________________，增加頭結點的目的是___________________，它的根結點數目是_____________________，葉子結點的個數為_______________（_____________________，有8個度為1的結點，則該二叉樹中總的結點數為____________________，中序遍歷序列是debac，它的前序遍歷序列是____________________________，則該二叉樹的后序遍歷為______________________，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是_______________________：安全性控制、 完整性控制 、并發性控制和數據的恢復。 在計算機中，算法是指_______________________算法一般都可以用哪幾種控制結構組合而成_____________________.算法的時間復雜度是指______________________5. 算法的空間復雜度是指__________________________ 6. 算法分析的目的是__________________________11. 數據的存儲結構是指_________________________12. 數據的邏輯結構是指（_______________________________13. 根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為__________________________________16. 遞歸算法一般需要利用_______________________實現。28. 非空的循環單鏈表head的尾結點（由p所指向），滿足（_____________________，雙向鏈表的優點之一是____________________________34. 在一棵二叉樹上第8層的結點數最多是____________35. 在深度為5的滿二叉樹中，葉子結點的個數為____________\36. 在深度為5的滿二叉樹中，共有________________個結點，則在該二叉樹中的葉子結點數為_________________說明：完全二叉樹總結點數為N，若N為奇數，則葉子結點數為（N+1）/2；若N為偶數，則葉子結點數為N/2。，中序遍歷序列debac，它的前序遍歷序列是（cedba） 40. 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA），中序遍歷訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是（gdbehfca）42. 串的長度是（串中所含字符的個數） ，求q在p中首次出現位置的運算稱做（模式匹配）44. N個頂點的連通圖中邊的條數至少為（N1）（N），在最壞情況下所需要的比較次數為（N）47. 最簡單的交換排序方法是（冒泡排序） ，則在最壞情況下，冒泡排序需要的比較次數為（n(n1)/2） 49. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）50. 在最壞情況下，下列順序方法中時間復雜度最小的是（堆排序） 51. 希爾排序法屬于（插入類排序）52. 堆排序法屬于（選擇類排序）53. 在下列幾種排序方法中，要求內存量最大的是（歸并排序） 54. 已知數據表A中每個元素距其最終位置不遠，為節省時間，應采用（直接插入排序）55. 算法的基本特征是可行性、確定性、 有窮性 和擁有足夠的情報。一個算法通常由兩種基本要素組成：一是對數據對象的運算和操作，二是算法的控制結構。1. 算法的復雜度主要包括時間復雜度和 空間 復雜度。2. 實現算法所需的存儲單元多少和算法的工作量大小分別稱為算法的空間復雜度和時間復雜度 。，包括插入、刪除、查找、更改等運算，也包括對數據元素進行分析。 數據元素 的集合。，線性鏈表屬于 存儲結構 。 邏輯 結構和數據的存儲結構。7. 數據結構包括數據的邏輯結構、數據的 存儲結構 以及對數據的操作運算。 前趨和后繼 關系來描述。、鏈接、 索引 等存儲結構。11. 順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 相鄰 的存儲單元中。12. 棧的基本運算有三種：入棧、退棧與讀棧頂元素 。13. 隊列主要有兩種基本運算：入隊運算與 退隊運算 。14. 在實際應用中，帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為 可利用棧 。 鏈式存儲和順序存儲 。，其主要特點是 邏輯結構中相鄰的結點在存儲結構中仍相鄰 。17. 循環隊列主要有兩種基本運算：入隊運算與退隊運算。每進行一次入隊運算，隊尾指針就 進1 。，說明循環隊列已滿，不能進行入隊運算。這種情況稱為 上溢 。，不能進行退隊運算，這種情況稱為 下溢 。20. 在一個容量為25的循環隊列中，若頭指針front=16，尾指針rear=9，則該循環隊列中共有 18 個元素。注：當rearfront時，元素個數＝總容量－（front－rear）；當rearfront時，元素個數＝rear－front。（D） （B） ＝（a1,a2,a3,……ai,……an），下列說法正確的是（D） ，其余每個元素都有一個且只有一個直接前件和直接后件，要求內存中可用存儲單元的地址（D） 7. 下列敘述正確的是（C）A．算法的執行效率與數據的存儲結構無關B．算法的空間復雜度是指算法程序中指令（或語句）的條數C．算法的有窮性是指算法必須能在執行有限個步驟之后終止D．算法的時間復雜度是指執行算法程序所需要的時間，主要研究數據的邏輯結構、對各種數據結構進行的運算，以及（數據的存儲結構）9. 數據結構中，與所使用的計算機無關的是數據的（C）A．存儲結構 B．物理結構 C．邏輯結構 D．物理和存儲結構10. 下列敘述中，錯誤的是（B）A．數據的存儲結構與數據處理的效率密切相關B．數據的存儲結構與數據處理的效率無關C．數據的存儲結構在計算機中所占的空間不一定是連續的D．一種數據的邏輯結構可以有多種存儲結構14. 下列數據結構具有記憶功能的是（C）A．隊列B．循環隊列C．棧D．順序表15. 下列數據結構中，按先進后出原則組織數據的是（B）A．線性鏈表 B．棧 C．循環鏈表 D．順序表17. 下列關于棧的敘述中正確的是（D）A．在棧中只能插入數據B．在棧中只能刪除數據C．棧是先進先出的線性表 D．棧是先進后出的線性表20. 由兩個棧共享一個存儲空間的好處是（節省存儲空間，降低上溢發生的機率） 21. 應用程序在執行過程中，需要通過打印機輸出數據時，一般先形成一個打印作業，將其存放在硬盤中的一個指定（隊列）中，當打印機空閑時，就會按先來先服務的方式從中取出待打印的作業進行打印。（C）A．在隊列中只能插入數據 B．在隊列中只能刪除數據 C．隊列是先進先出的線性表 D．隊列是先進后出的線性表，正確的是（D）A．線性鏈表中的各元素在存儲空間中的位置必須是連續的B．線性鏈表中的表頭元素一定存儲在其他元素的前面 C．線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但表頭元素一定存儲在其他元素的前面 D．線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且各元素的存儲順序也是任意的（A）A．線性表是線性結構 B．棧與隊列是非線性結構C．線性鏈表是非線性結構160