数据结构算法题汇总
1. 在計算機中，算法是指什么？
答案：解題方案的準確而完整的描述。
2. ，算法的四個基本特征是？
說明：可行性、確定性、有窮性和輸入輸出。
3. 算法一般都可以用哪幾種控制結構組合而成？
答案：順序、選擇、循環(huán)。
4. 算法的時間復雜度是指？
答案：算法執(zhí)行過程中所需要的基本運算次數(shù)。
5. 算法的空間復雜度是指？
答案：執(zhí)行過程中所需要的存儲空間。
6. 算法分析的目的是？
答案：分析算法的效率以求改進。
7. 下列敘述正確的是（C）
A．算法的執(zhí)行效率與數(shù)據(jù)的存儲結構無關
B．算法的空間復雜度是指算法程序中指令（或語句）的條數(shù)
C．算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止
D．算法的時間復雜度是指執(zhí)行算法程序所需要的時間
8. 數(shù)據(jù)結構作為計算機的一門學科，主要研究什么？
答案：主要研究數(shù)據(jù)的邏輯結構、對各種數(shù)據(jù)結構進行的運算，以及數(shù)據(jù)的存儲結構。
9. 數(shù)據(jù)結構中與所使用的計算機無關的是數(shù)據(jù)的（C）
A．存儲結構 B．物理結構
C．邏輯結構 D．物理和存儲結構
10. 下列敘述中，錯誤的是（B）
A．數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率密切相關
B．數(shù)據(jù)的存儲結構與數(shù)據(jù)處理的效率無關
C．數(shù)據(jù)的存儲結構在計算機中所占的空間不一定是連續(xù)的
D．一種數(shù)據(jù)的邏輯結構可以有多種存儲結構
11. 數(shù)據(jù)的存儲結構是指什么？
答案：數(shù)據(jù)的邏輯結構在計算機中的表示。
12. 數(shù)據(jù)的邏輯結構是指？
答案：反映數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結構。
13. 根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結構分為？
答案：線性結構和非線性結構
14. 下列數(shù)據(jù)結構具有記憶功能的是（C）
A．隊列
B．循環(huán)隊列
C．棧
D．順序表
16. 遞歸算法一般需要利用什么實現(xiàn)？
答案：隊列
20. 下列敘述中，正確的是（D）
A．線性鏈表中的各元素在存儲空間中的位置必須是連續(xù)的
B．線性鏈表中的表頭元素一定存儲在其他元素的前面
C．線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素的前面
D．線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的
21. 下列敘述中正確的是（A）
A．線性表是線性結構
B．棧與隊列是非線性結構? ? 是線性結構）
C．線性鏈表是非線性結構? ?
D．二叉樹是線性結構? ? ? ? ? ?非線性結構，可能有多個后繼
22. 線性表L＝（a1,a2,a3,……ai,……an），下列說法正確的是（D）
A．每個元素都有一個直接前件和直接后件
B．線性表中至少要有一個元素
C．表中諸元素的排列順序必須是由小到大或由大到小
D．除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前驅和直接后繼
23. 線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址怎么樣？
答案：連續(xù)不連續(xù)都可以。
24. 鏈表不具有的特點是（B）
A．不必事先估計存儲空間
B．可隨機訪問任一元素
C．插入刪除不需要移動元素
D．所需空間與線性表長度成正比
25. 在（D）中，只要指出表中任何一個結點的位置，就可以從它出發(fā)依次訪問到表中其他所有結點。
A．線性單鏈表
B．雙向鏈表
C．線性鏈表
D．循環(huán)鏈表
26. 以下數(shù)據(jù)結構屬于非線性數(shù)據(jù)結構的是（C）? ?//數(shù)據(jù)結構只有倆種，非信息結構和線性結構
A．隊列
B．線性表
C．二叉樹
D．棧
27. 樹是結點的集合，它的根結點數(shù)目是多少？
答案：有且只有1
28. 在一棵二叉樹上第8層的結點數(shù)最多是？? ? ? ? ?2的（n-1）次方
答案：128
29. 在深度為5的滿二叉樹中，葉子結點的個數(shù)為？
答案：16
30. 在深度為5的滿二叉樹中，共有多少個結點？ 1+2+4+8+16=31
答案：31
31. 設一棵完全二叉樹共有699個結點，則在該二叉樹中的葉子結點數(shù)為？
答案：350
完全二叉樹總結點數(shù)為N，若N為奇數(shù)，則葉子結點數(shù)為（N+1）/2；若N為偶數(shù)，則葉子結點數(shù)為N/2。
33. 若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是？
答案：gdbehfca
?
34. 串的長度是？
答案：串中所含字符的個數(shù)。
35. 設有兩個串p和q，求q在p中首次出現(xiàn)位置的運算稱做？
答案：模式匹配。
36. N個頂點的連通圖中邊的條數(shù)至少為？
答案：N-1
37. N個頂點的強連通圖的邊數(shù)至少有？
答案：N
38. 對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為？
答案：N? ? ? ? ? ?? ? ? ? n/1=n
39. 最簡單的交換排序方法是？??
答案：冒泡排序? ? 兩個for? 第一個范圍為n-1? 第二個為n-1-i? 然后j和j+1比較? 交換
40. 假設線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為？
答案：n(n-1)/2
41. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是？
答案：冒泡排序
42. 在最壞情況下，下列順序方法中時間復雜度最小的是？
答案：堆排序
堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩(wěn)定排序。
堆是具有以下性質(zhì)的完全二叉樹：
- 每個結點的值都大于或等于其左右孩子結點的值，稱為大根堆；
- 或者每個結點的值都小于或等于其左右孩子結點的值，稱為小根堆。?
實現(xiàn)網(wǎng)址：https://blog.csdn.net/l577217/article/details/80516654?
?
43. 希爾排序法屬于？
答案：插入類排序
44. 堆排序法屬于？
答案：選擇類排序
45. 排序方法中，要求內(nèi)存量最大的是？
答案：歸并排序
46. 已知數(shù)據(jù)表A中每個元素距其最終位置不遠，為節(jié)省時間，應采用？
答案：直接插入排序
（1）交換類排序法：
交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進行排序的一種方法。冒泡排序法與快速排序法都屬于交換類排序方法。冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n–1)/2。但這個工作量不是必需的，一般情況下要小于這個工作量。快速排序法也是一種交換類的排序方法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法。其關鍵是對線性表進行分割，以及對各分割出的子表再進行分割。
（2）插入類排序法：
插入類排序法主要有簡單插入排序法和希爾排序法。簡單插入排序法，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。在這種排序方法中，每一次比較后最多移掉一個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n–1)/2次比較。希爾排序法對簡單插入排序做了較大的改進。它是將整個無序序列分割成若干小的子序列分別進行插入排序。希爾排序的效率與所選取的增量序列有關。在最壞情況下，希爾排序所需要的比較次數(shù)為O(n1.5)。
（3）選擇類排序：
選擇類排序主要有簡單選擇類排序法和堆排序法。簡單選擇排序法的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置）；然后對剩下的子表采用同樣的方法，直到子表空為止。對于長度為n的線性表，在最壞情況下需要比較n(n–1)/2次。堆排序法也屬于選擇類排序法。具有n個元素的序列（h1, h2, …, hn），當且僅當滿足條件：? 或? (i=1, 2, …, n/2）時稱之為堆。可見，堆頂元素（即第一個元素）必為最大項。堆排序的方法對于規(guī)模較小的線性表并不適合，但對于較大規(guī)模的線性表來說是很有效的。在最壞情況下，堆排序需要比較的次數(shù)為O(nlog2n)。
?
1.棧和隊列的共同特點是（只允許在端點處插入和刪除元素）
2.如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是（e2,e4,e3,e1）
13.樹是結點的集合，它的根結點數(shù)目是（有且只有1）
15.具有3個結點的二叉樹有（5種形態(tài)）
16.設一棵二叉樹中有3個葉子結點，有8個度為1的結點，則該二叉樹中總的結點數(shù)為（13
17.已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（cedba）
(湊合看吧，就這水平了)
?
18.已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA）
（這個就很完美）
20.數(shù)據(jù)庫保護分為：安全性控制、 完整性控制 、并發(fā)性控制、數(shù)據(jù)的恢復。
1. 在計算機中，算法是指（解題方案的準確而完整的描述）
2算法一般應該具有的基本特征
算法的四個基本特征是：可行性、確定性、有窮性和擁有足夠的情報。ps老師整理的是擁有足夠的情報，我查的是輸入和輸出
18.當循環(huán)隊列非空且隊尾指針等于對頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為 上溢
19.當循環(huán)隊列為空時，不能進行退隊運算，這種情況稱為 下溢?
20. 在一個容量為25的循環(huán)隊列中，若頭指針front=16，尾指針rear=9，則該循環(huán)隊列中共有 18 個元素。注：當rear<front時，元素個數(shù)＝總容量－（front－rear）；
當rear>front時，元素個數(shù)＝rear－front。
1.判斷鏈表是否存在環(huán)型鏈表問題：判斷一個鏈表是否存在環(huán)，例如下面這個鏈表就存在一個環(huán)：
例如N1->N2->N3->N4->N5->N2就是一個有環(huán)的鏈表，環(huán)的開始結點是N5這里有一個比較簡單的解法。設置兩個指針p1，p2。每次循環(huán)p1向前走一步，p2向前走兩步。直到p2碰到NULL指針或者兩個指針相等結束循環(huán)。如果兩個指針相等則說明存在環(huán)。
2,鏈表反轉 單向鏈表的反轉是一個經(jīng)常被問到的一個面試題，也是一個非常基礎的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉后成為5->4->3->2->1。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然后將當前節(jié)點元素的指針反轉后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。源代碼如下：
struct linka {int data;linka* next; };void reverse(linka*& head) {if(head ==NULL)return;linka*pre, *cur, *ne;pre=head;cur=head->next;while(cur){ne = cur->next;cur->next = pre;pre = cur;cur = ne;}head->next = NULL;head = pre; }還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節(jié)點之前先調(diào)用遞歸函數(shù)反轉后續(xù)節(jié)點。源代碼如下。不過這個方法有一個缺點，就是在反轉后的最后一個結點會形成一個環(huán)，所以必須將函數(shù)的返回的節(jié)點的next域置為NULL。因為要改變head指針，所以我用了引用。算法的源代碼如下：
linka* reverse(linka* p,linka*& head){if(p == NULL || p->next == NULL){head=p;return p;}else{linka* tmp = reverse(p->next,head);tmp->next = p;return p;} }4.
abstract class Something {private abstract String doSomething (); }
該段代碼有錯嗎？
答案: 錯。abstract的methods不能以private修飾。abstract的methods就是讓子類implement(實現(xiàn))具體細節(jié)的，怎么可以用private把abstract method封鎖起來呢? (同理，abstract method前不能加final)。
?
5.看看下面的代碼段錯在哪里？
?
答案: 錯。局部變量前不能放置任何訪問修飾符 (private，public，和protected)。final可以用來修飾局部變量
(final如同abstract和strictfp，都是非訪問修飾符，strictfp?https://baike.baidu.com/item/strictfp?只能修飾class和method而非variable)。
6. 下面該段代碼是否有錯，若是有錯錯在哪里？
abstract class Name {private String name;public abstract boolean isStupidName(String name) {} }
答案: 錯。abstract method必須以分號結尾，且不帶花括號。
?
?
-------------------------------單項選擇題------------------------------
1.算法分析的目的是(??? C? )
A.找出數(shù)據(jù)結構的合理性?? ??B.研究算法中的輸入/輸出關系
C.分析算法的效率以求改進???? D.分析算法的易讀性
?
2.在需要經(jīng)常查找結點的前驅與后繼的場合中，使用(? B?? )比較合適。
A.單鏈表?????????? B.雙鏈表
C.順序表?????????? D.循環(huán)鏈表
?
3.下面關于線性表的敘述中，錯誤的為(? D??? )
A.順序表使用一維數(shù)組實現(xiàn)的線性表
B.順序表必須占用一片連續(xù)的存儲單元
C.順序表的空間利用率高于鏈表
D.在鏈表中，每個結點只有一個鏈域? ? ? ? ? // 一個指針域，一個數(shù)據(jù)域（循環(huán)，雙向鏈表有倆個指針域）
?
4.帶頭結點的單鏈表head為空的判斷條件是(?? B?? )
A. head=NIL????????????????????? B. head->next=NIL
C. head->next=head??????????????? D. head<>NIL
?
5.隊列通常采用兩種存儲結構是(?? A?? )
A.順序存儲結構和鏈表存儲結構???????? B.散列方式和索引方式
C.鏈表存儲結構和數(shù)組???????????????? D.線性存儲結構和非線性存儲結構
?
6.按照二叉樹的定義，具有3個結點的二叉樹有(? C? )種。
? A.3????????? B.4????????? C.5????????? D.6
?
8.深度為5的二叉樹至多有(? C? )個結點。 (2^n-1)
A.16????????? B.32????????? C.31????????? D.10
?
9.對于一個具有n個頂點的無向圖，若采用鄰接表表示，則存放表頭結點的數(shù)組的大小為 (? A? )
A.n????????? B.n+1????????? C.n-1????????? D.n+邊數(shù)
?
10.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要(? C? )條邊。
A.n????????? B.n+1????????? C.n-1????????? D.n/2
?
11.靜態(tài)查找表與動態(tài)查找表二者的根本差別在于(? B? )
A.它們的邏輯結構不一樣
B.施加在其上的操作不同
C.所包含的數(shù)據(jù)元素的類型不一樣
D.存儲實現(xiàn)不一樣
?
12.散列文件使用散列函數(shù)將記錄的關鍵字值計算轉化為記錄的存放地址。因為散列函數(shù)不是一對一的關系，所以選擇好的( D? )方法是散列文件的關鍵。
A.散列函數(shù)????????????? B.除余法中的質(zhì)數(shù)
C.沖突處理????????????? D.散列函數(shù)和沖突處理
?
散列表：https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E8%A1%A8/5981869?fromtitle=%E6%95%A3%E5%88%97%E8%A1%A8&fromid=10027933? ? 網(wǎng)頁最后的Data_structures有數(shù)據(jù)結構的內(nèi)容鏈接
散列文件：https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E6%96%87%E4%BB%B6/8597321
?
13.對于大文件的排序要研究在外設上的排序技術，即(?? C? )
A.快速排序法????????????? B.內(nèi)排序法
C.外排序法????????????? D.交叉排序法
?
14.設有5000個無序的元素，希望用最快的速度挑選出其中前50個最大的元素，最好選用(? C? )法。
A.冒泡排序???????????????????? B.快速排序
C.堆排序??????? ???????????????D.基數(shù)排序
?
二、判斷題
?
1.所謂數(shù)據(jù)的邏輯結構指的是數(shù)據(jù)元素之間的邏輯關系。(????×? )? ?邏輯關系的整體
?
2.在線性結構中，每個結點都有一個直接前驅和一個直接后繼。(???×?? )? head? 和? end 沒有
?
3.插入和刪除是數(shù)組的兩種基本操作。(??×??? )? ? ?查找和修改
?
4.在鏈棧的頭部必須要設置頭結點。(???×?? )? ? ?棧都是在頭部進行操作的，加了頭結點等于對頭結點后的結點進行操作，使算法復雜，只需要頭指針就可以了
?
5.在二叉樹中插入結點則該二叉樹便不再是二叉樹。(????×? )? ?不改變性質(zhì)就可以??每個節(jié)點最多含有兩個子樹的樹稱為二叉樹
?
6.查找表的邏輯結構是集合。(?√?)
?
7.靜態(tài)查找表的檢索與修改被分成兩個不交叉的階段分別進行。(??√??? )
?
8.在索引順序文件中插入新的記錄時，必須復制整個文件。(?????× )
記錄存放是按照寫入順序的，排序后索引將順序記錄各記錄的位置，相對于索引來說，是記錄排序第1記錄在文件中實際位置(存放的第幾條記錄)，因此避免重新移動記錄的麻煩，同時還能對同一個文件建立多個索引。
因此在添加新的記錄時，僅需要添加到文件末尾，重新計算并寫入索引部分即可。
?
9.如果某種排序算法是不穩(wěn)定的，則該方法沒有實際的應用價值。(??×??? )? ?排序的時間復雜度是不同的，要選擇合適的
?
10.對于n個記錄的集合進行冒泡排序，在最壞情況下所需要的時間是0(n2)(???√?? )
https://blog.csdn.net/qq_41835813/article/details/88969912? ?最后有表格
?
45. 冒泡排序算法在最好的情況下的元素交換次數(shù)為 0 。
46. 在最壞情況下，冒泡排序的時間復雜度為 n(n-1) /2 。
47. 對于長度為n的線性表，在最壞情況下，快速排序所需要的比較次數(shù)為 n(n-1) /2 。
48.在最壞情況下，簡單插入排序需要比較的次數(shù)為 n(n-1) /2 。
49.在最壞情況下，希爾排序需要比較的次數(shù)為 O(n1.5) 。注：括號里是n的1.5次方。
50. 在最壞情況下，簡單選擇排序需要比較的次數(shù)為 n(n-1) /2 。
51. 在最壞情況下，堆排序需要比較的次數(shù)為 o(nlog2n) 。
52.對于輸入為N個數(shù)進行快速排序算法的平均時間復雜度是 O(Nlog2 N)。
三、填空題
1.程序設計的實質(zhì)是___數(shù)據(jù)表示_____和____數(shù)據(jù)處理____。
?
2.設由字符串a(chǎn)=′data′、b=′structure′、c=′-′,則a與c連接然后與b連接的結果為：____data-structure____。
?
3.通常單鏈表的頭結點指的是___在單鏈表第一個結點之前增設的一個類型相同的結點_____；單鏈表的首結點指的是____表結點中的第一個結點____。
?
4.一個隊列的入隊序列是a、b、c、d，則隊列的輸出序列為____ a、b、c、d____。
?
5.棧結構通常采用的兩種存儲結構是____線性存儲____和____鏈式存儲____。
?
6.具有N個結點的完全二叉樹的深度為____〔log2N〕+1____。
?
7.樹的三種主要的遍歷方法是：____先序____、____后續(xù)____和層次遍歷。? ? 還有中序
?
8.在無向圖的鄰接矩陣A中，若A〔i,j〕等于1，則A〔j,i〕等于____1___。
?
9.采用散列技術實現(xiàn)散列表時，需要考慮的兩個主要問題是：構造___散列函數(shù)_____和解決____沖突____。
?
10.索引順序表上的查找分兩個階段：(1)____確定待查元素所在塊____；(2)____在塊中查找待查元素____。
?
11.散列文件中的記錄通常是成組存放的。若干的記錄組成一個存儲單位，稱作____桶____。
?
12.就文件而言，按用戶的觀點所確定的基本存儲單元稱為____邏輯結構____。按外設的觀點所確定的基本存儲單元稱為____物理結構____。
?
13.文件的檢索有三種方式：____順序____存取、____直接____存取和按關鍵字存取。
?
14.最簡單的交換排序方法是____冒泡____排序。
?
15.外排序的基本方法是_____歸并___。
總結
- 上一篇： AM2302温湿度单总线测量的问题
- 下一篇： 【python @ 小甲鱼网课】 P6列