1、給出下列二叉樹的順序儲存結構;並寫出其先序、中序、後序遍歷序列。
2、設字元集合s=,權值集合為,對字元集合根據對應權值集合進行哈夫曼編碼。
(1)畫出構造的哈夫曼樹
(2)計算帶權路徑長度
(3)求各字元的哈夫曼編碼
3、已知一組元素為(12,8,10,20,6,2,16,15),試畫出按元素排列順序輸入而生成的一棵排序二叉樹,並且給出它的中序遍歷的輸出結果。
4、使用prim或kruscal演算法構造最小生成樹,給出中間步驟。
5、給出從頂點1出發到其餘各點的最短路徑及長度。
6、對於a[0…10]有序表,採用二分查詢法時,求查詢成功的平均查詢長度。並對於有序表,當用二分查詢法查詢100時,需進行多少次查詢才能確定成功;查詢57時需進行多少次查詢可確定成功;查詢110時,需進行多少次查詢才能確定不成功。
7、試從現實生活中遇到的例項中尋找下列資料結構的原型:佇列、棧、樹、圖,並描述其特點。
8、有一組待排序的記錄,其關鍵字為10 , 2 , 16, 13 , 4 , 25 , 3 , 10 , 20 , 6 , 18 。寫出選擇排序每一趟結束時的狀態。(從小到大排序)
1、**性結構中,開始結點沒有前驅結點,其餘每個結點有且只有_【1】_個前驅結點;終端結點沒有後續結點,其餘每個結點有且只有_【2】__個後續結點。
2、下面程式段的時間複雜度是_【3】_
for ( i=1 ;i<=n ;i++)
for ( j=1; j<=m ; j++)
a [i][j] = i –j ;
3、從乙個長度為n的向量中刪除第i個元素(1<=i<=n)時,需向前移動__【4】個元素。
4、一棵二叉樹的第i(i>=1)層最多有_【5】 個結點
5、結點最少的二叉樹是__【6】__
6、資料結構是研究資料的邏輯結構和儲存結構的,資料的邏輯結構包括線性結構,__【7】__和__【8】__三種型別,資料的儲存結構即物理結構包括_【9】__和鏈式儲存結構兩種基本型別。
7、若圖中每條邊都是有方向的,則其頂點之間的關係用_【10】__表示,這種圖叫_【11】__。若圖中的每條邊都沒有方向,則其頂點之間的關係用無向邊表示,這種圖叫無向圖。
8、陣列的儲存結構採用_【12】__儲存方式
9、二叉樹由【13】__,_【14】___,右子樹三個基本單元組成。
10、對矩陣壓縮是為了__【15】____
1、資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的_______和運算的學科。
a 結構 b 關係 c 運算d 演算法
2、在資料結構中,從邏輯上可以把資料結構分為________
a. 動態結構和靜態結構b 緊湊結構和非緊湊結構
c 線性結構和非線性結構 d 內部結構和外部結構
3、演算法分析的兩個主要方面是______
a 空間複雜性和時間複雜性 b 正確性和簡明性
c 可讀性和文件性d 資料複雜性和程式複雜性
4、線性表若採用鍊錶儲存結構時,要求記憶體中可用儲存單元的位址_______
a 必須是連續的 b 部分位址必須是連續的
c 一定是不連續的 d 連續不連續都可以
5、在以下的敘述中,正確的是_____
a 線性表的線性儲存結構優於鍊錶儲存結構
b 二維陣列是它的每個資料元素為乙個線性表的線性表
c 棧的操作方式是先進先出
d 佇列的操作方式是先進後出
6、乙個向量第乙個元素的儲存位址是100,每個元素的長度為2,則第5個元素得位址是____
a 110 b 108 c 100 d 120
7、乙個棧的入棧序列是a, b , c , d , e ,則棧的不可能輸出序列是_____
a e d c b a b d e c b a c d c e a b d a b c d e
8、棧結構通常採用的兩種儲存結構是_________
a 順序儲存結構和鍊錶儲存結構b 雜湊方式和索引方式
c 鍊錶儲存結構和陣列d 線性儲存結構和非線性儲存結構
9、乙個佇列的入隊序列是1,2,3,4,則佇列的輸出序列是_________
a 4,3,2,1 b 1,2,3,4 c 1,4,3,2 d 3,2,4,1
10、判定乙個迴圈佇列q(最多元素為m0)為滿的條件是_______
a q.front = =q. rear b q.front != q.rear
c q.front= =( q.rear + 1 ) % m0 d q.front != ( q . rear +1 ) % m0
11、表示式 a * ( b + c ) – d 的字尾表示式是_______
a abcdb abc+*d – c abc*+d – d – + * abcd
12、帶頭結點的單鏈表head為空的判定條件是_______
a . head = = null b head -> next = = null
c head->next = = head d head != null
13、在乙個單鏈表中,已知q結點是p結點的前驅結點,若在q 和p之間插入s結點,則執行
a s->next = p ->next ; p->next = s ;
b p->next = s -> next; s - >next = p ;
c q ->next = s ; s ->next = p ;
d p->next = s ; s ->next = q ;
14、在乙個單鏈表中,若要刪除p結點的後續結點,則執行
a p->next = p ->next ->next ;
b p = p ->next ; p ->next = p ->next ->next ;
c p ->next = p ->next ;
d p = p ->next ->next ;
15、空串與空格串是相同的,這種說法______
a 正確 b 不正確
16、設有兩個串p和q,求q在p中首次出現的位置的運算稱作_______
a 連線 b 求子串 c 模式匹配 d 求串長
17、18、設高度為h的二叉樹上只有度為0和度為2的結點,則此類二叉樹中所包含的結點數至少為_______
a 2h b h + 1 c 2h+1 d 2h – 1
19、深度為5的二叉樹至多有_____個結點
a 16 b 32 c 31 d 10
20、樹最適合用來表示______
a 有序資料元素b 無序資料元素
c 元素之間具有分支層次關係的資料
d 元素之間無聯絡的資料
21、在乙個圖中,所有頂點的度數之和等於所有邊數的____倍
a 1/2 b 1 c 2 d 4
22、乙個具有n個頂點的無向圖最多有____條邊。
a n (n – 1)/2 b n (n –1 ) c n d 2
23、具有6個頂點的無向圖至少應有____條邊才能確保是乙個連通圖.
a 5 b 6 c 7 d 8
24、對於乙個具有n個頂點的無向圖,若採用鄰接矩陣表示,則該矩陣的大小是____
a n b (n-1 )2c n-1 d n2
25、對於乙個具有n個頂點和e條邊的無向圖,若採用鄰接鍊錶表示,則表頭向量的大小為______
a . n b. n+1 c n-1 d n+e
26、對線性表進行二分查詢時,要求線性表必須_____
a 以順序方式儲存 b 以鏈結方式儲存
c 以順序方式儲存,且結點按關鍵字有序排序
d 以鏈結方式儲存,且結點按關鍵字有序排序
27、在所有排序演算法中,關鍵字比較的次數與記錄的初始排列次序無關的是______
a 希爾排序 b 起泡排序(改進後) c 插入排序 d 選擇排序
28、在待排序的元素序列基本有序的前提下,效率最高的排序方法是_______
a.插入排序 b 選擇排序 c 快速排序 d 歸併排序
29、下述幾種排序方法中,要求記憶體量最大的是是_____
a 插入排序 b 選擇排序 c 快速排序 d 歸併排序
30、快速排序方法在___情況下最不利於發揮其長處
a 要排序的資料量太大
b 要排序的資料中含有多個相同值
c 要排序的資料已經基本有序
d 要排序的資料個數為奇數
java資料結構面試題
1.棧和佇列的共同特點是 只允許在端點處插入和刪除元素 4.棧通常採用的兩種儲存結構是 線性儲存結構和鍊錶儲存結構 5.下列關於棧的敘述正確的是 d a.棧是非線性結構b.棧是一種樹狀結構c.棧具有先進先出的特徵d.棧有後進先出的特徵 6.鍊錶不具有的特點是 b a.不必事先估計儲存空間 b.可隨機...
2023年 資料結構 複習題
第一部分 資料結構 線性結構 順序表 鍊錶 棧 佇列 陣列 串 考點 1 時間複雜度 2 資料的邏輯結構與儲存結構相關知識 分類 與儲存結構之間的關係 3 順序表的知識 特點 4 鍊錶的知識 程式設計求單鏈表中結點的個數 插入 刪除。5 棧與佇列知識 特點 迴圈佇列 基本術語 鏈佇列 6 陣列與矩陣...
資料結構複習
0.緒論 一 填空題 1 資料的邏輯結構是資料元素之間的邏輯關係,通常有下列4類 2 資料的儲存結構是資料在計算機儲存器裡的表示,主要有4種基本儲存方法 二 選擇題 1 乙個演算法必須在執行有窮步之後結束,這是演算法的 a 正確性 b 有窮性 c 確定性 d 可行性 2 演算法的每一步必須有確切的定...