資料結構與演算法離線作業2023年夏

2022-09-10 23:33:19 字數 3844 閱讀 6500

浙江大學遠端教育學院

《資料結構與演算法》課程離線作業

一、填空題:(【序號,章,節】)

【1,1,2】線性結構中元素之間存在一對一關係,樹形結構中元素之間存在

一對多關係,圖形結構中元素之間存在多對多關係。

【2,1,2】為了最快地訪問資料元素,物理結構宜採用順序儲存結構。

【3,1,2】儲存結構可根據資料元素在機器中的位置是否一定連續分為順序儲存結構__, 鏈式儲存結構___。

【4,1,3】度量演算法效率可通過時間複雜度__來進行。

【5,1,3】設n 為正整數,下面程式段中前置以記號@的語句的頻度是 n(n+1)/2 。

for (i=0; i for (j=0; jif (i+j==n-1)

@ a[i][j]=0;

}【6,1,3】設n 為正整數,試確定下列各程式段中前置以記號@的語句的頻度:

(1) i=1; k=0;

while (i<=n-1)

(2) k=0;

for (i=1; i<=n; i++)

【7,3,2】線性表(a1,a2,…,an)有兩種儲存結構: 順序儲存結構和鏈式儲存結構,請就這兩種儲存結構完成下列填充: _順序__ 儲存密度較大;_順序___儲存利用率較高;_順序___可以隨機訪問;__鏈式____不可以隨機訪問;__鏈式___插入和刪除操作比較方便。

【8,3,2】從乙個長度為n的順序表中刪除第i個元素(1≤i≤n)時,需向前移動n-i 個元素。

【9,3,2】帶頭結點的單鏈表head為空的條件是__ head->next=null

【10,3,2】在乙個單鏈表中p所指結點(p所指不是最後結點)之後插入乙個由指標s所指結點,應執行s->next=__ p->next ___;和p->next=___ s_____的操作。

【11,3,2】在乙個單鏈表中刪除p所指結點時,應執行以下操作:

q= p->next;

p->data= p->next->data;

p->next= p->next->next __ ;

free(q);

【12,3,2】帶頭結點的單迴圈鍊錶head的判空條件是_ head->next == head;___; 不帶頭結點的單迴圈鍊錶的判空條件是__ head == null; ___。

【13,3,2】已知l是帶表頭結點的非空單鏈表, 且p結點既然不首元結點,也不是尾元結點,試從下列提供的答案中選擇合適的語句序列。

a. 刪除p結點的直接前驅結點的語句序列是________10 12 8 11 4 14 ______。

b. 刪除結點p的語句序列是10 12 7 3 14

c. 刪除尾元結點的語句序列是9 11 3 14______。

(1) p = p->next;

(2) p->next = p;

(3) p->next = p->next ->next;

(4) p = p->next ->next;

(5) while (p != null) p = p->next;

(6) while (q->next != null);

(7) while (p->next != q) p = p->next;

(8) while (p->next->next != q) p = p->next;

(9) while (p->next->next != null) p = p->next;

(10) q = p;

(11) q = p->next;

(12) p = l;

(13) l = l->next;

(14) free (q);

【14,3,3】對乙個棧,給定輸入的順序是a、b、c,則全部不可能的輸出序列有不可能得到的輸出序列有cab

【15,3,3】.在棧頂指標為hs的鏈棧中,判定棧空的條件是  head->next==null      。

【16,3,3】下列程式把十進位制數轉換為十六進製制數,請填寫合適的語句成分。

void conversion10_16()

while(!stackempty(s))

} /* conversion */

【17,3,4】若用乙個大小為6個元素的陣列來實現迴圈佇列,且當前rear=0和front=3。當從佇列中刪除乙個元素,再加入兩個元素後,rear和front的值分別是 2 和 4 。

【18,3,4】堆疊和佇列都是線性表, 堆疊是_____後進先出_________的線性表, 而佇列是先進先出______的線性表。

【19,3,4】若用乙個大小為6個元素的陣列來實現迴圈佇列,且當前rear=0和front=3。當從佇列中刪除乙個元素,再加入兩個元素後,rear和front的值分別是2 和 4 。

【20,4,2】已知一棵樹邊的集合是。那麼根結點是 e ,結點b的雙親是 d ,結點a的子孫有 bcdj ,樹的深度是 4 ,樹的度是 3 ,結點g在樹的第 3 層。

【21,4,3】從概念上講,樹與二叉樹是二種不同的資料結構,將樹轉化為二叉樹的基本的目的是樹可採用二叉樹的儲存結構並利用二叉樹的已有演算法解決樹的有關問題

【22,4,3】滿三叉樹的第i層的結點個數為 3i-1 ,深度為h時該樹中共有 3h-1 結點。

【23,4,3】已知一棵完全二叉樹有56個葉子結點,從上到下、從左到右對它的結點進行編號,根結點為1號。則該完全二叉樹總共結點有_____111____個;有__7_______層;第91號結點的雙親結點是__45_____號;第63號結點的左孩子結點是_________號。

【24,4,3】下列表示的圖中,共有____5___個是樹;有____3___個是二叉樹;有__2_____個是完全二叉樹。

【25,4,4】n個結點的二叉排序樹的最大深度是 n ,最小深度為 [log2n]+1 。

【26,4,3】如果某二叉樹的後序遍歷序列是abcdefghi,中序遍歷序列是acbidfehg,則其先序遍歷序列的第乙個字母是 i ,最後乙個字母是 g 。

【27,4,3】下列二叉樹的中序遍歷序列是_______ dbngoaec _ __;後序遍歷序列是dnigbeca

【28,5,4】設hash表的大小為 n (n=10), hash函式為 h(x)=x % 7, 如果二次探測再雜湊方法hi=(h(key)+di) mod 10 (di = 12,22,32,…,)解決衝突,在hash表中依次插入關鍵字以後,關鍵字1、20和27所在位址的下標分別是 17_ 和 5 。插入上述6個元素的平均比較次數是 2 。

【29,6,3】設無權圖g的鄰接矩陣為a,若(vi,vj)屬於圖g的邊集合,則對應元素a[i][j]等於 1 ,22、設無向圖g的鄰接矩陣為a,若a[i][j]等於0,則a[j][i]等於 0 。

【30,6,3】若乙個圖用鄰接矩陣表示,則刪除從第i個頂點出發的所有邊的方法是矩陣第i行全部置為零 。

【31,6,2】設乙個圖

g=},v=,a=。那麼頂點e的入度是 2 ;出度是 1 ;通過頂點f的簡單迴路有 2 條;就連通性而言,該圖是強連通圖;它的強連通分量有 1 個;其生成樹可能的最大深度是  5 。

【32,7,1】排序過程一般需經過兩個基本操作,它們是比較和移動 。

【33,7,2】在對一組關鍵字是(54,38,96,45,15,72,60,23,83)的記錄進行直接插入排序時,當把第七個記錄(關鍵字是60)插入到有序表時,為尋找插入位置需比較 3 次。

【34,7,4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸併排序、和基數排序方法中,不穩定的排序方法有希爾排序、快速排序、堆排序 。

資料結構與演算法離線作業答案

浙江大學遠端教育學院 一 填空題 序號,章,節 1,1,2 線性結構中元素之間存在一對一關係,樹形結構中元素之間存在 一對多關係,圖形結構中元素之間存在多對多關係。2,1,2 為了最快地訪問資料元素,物理結構宜採用順序儲存結構。3,1,2 儲存結構可根據資料元素在機器中的位置是否一定連續分為順序儲存...

資料結構與演算法離線作業答案 2019版甲

浙江大學遠端教育學院 一 填空題 1,1,2 線性結構中元素之間存在一對一關係,樹形結構中元素之間存在 一對多關係,圖形結構中元素之間存在多對多關係。2,1,2 為了最快地訪問資料元素,物理結構宜採用順序儲存結構。3,1,2 儲存結構可根據資料元素在機器中的位置是否一定連續分為順序儲存結構 鏈式儲存...

資料結構與演算法作業

說明 1 題號形式 每題都以 sn,cha,sec 開頭,sn表明本題的題目序號,每道題都有唯一的序號 cha表示內容所在的章 sec表示內容所在的節。如 17,2,1 表示序號17的題來自第2章第1節。2 題型 1 填空題 1 80 2 分析計算作圖題 序號1 30題 選自 資料結構題集 嚴蔚敏等...