本課程作業由兩部分組成。第一部分為「客觀題部分」,由選擇題組成,每題1分,共15分。第二部分為「主觀題部分」,由簡答題和應用題組成,共15分。
作業總分30分,將作為平時成績記入課程總成績。
客觀題部分:
一、選擇題(每題1分,共10題)
1、順序儲存結構中資料元素之間的邏輯關係是由( )表示的。
a.線性結構 b.非線性結構
c.儲存位置 d.指標
2、演算法指的是( )。
a.對特定問題求解步驟的一種描述,是指令的有限序列。
b.電腦程式
c.解決問題的計算方法
d.資料處理
3、演算法在發生非法操作時可以作出處理的特性稱為( )。
a.健壯性 b.確定性
c.可行性 d.正確性
4、若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨,則採用( )儲存方法最節省時間。
a.順序表 b.單鏈表
c.雙鏈表 d.單迴圈鍊錶
5、頭結點的單鏈表head為空的判定條件是( )。
a.head==null b.head->next==null
c.head->next==head d.head!=null
6、單迴圈鍊錶的主要優點是( )。
a.不再需要頭指標了
b.從表中任一結點出發都能掃瞄到整個鍊錶;
c.已知某個結點的位置後,能夠容易找到它的直接前趨;
d.在進行插入、刪除操作時,能更好地保證鍊錶不斷開。
7、使用雙向鍊錶儲存線性表,其優點是可以( )。
a.方便雙向查詢 b.更方便資料的插入和刪除
c.節約儲存空間 d.很快**儲存空間
8、設陣列s[n]作為兩個棧s1和s2的儲存空間,對任何乙個棧只有當s[n]全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是( )。
a.s1的棧底位置為0,s2的棧底位置為n-1
b.s1的棧底位置為0,s2的棧底位置為n/2
c.s1的棧底位置為0,s2的棧底位置為n
d.s1的棧底位置為0,s2的棧底位置為1
9、設棧s和佇列q的初始狀態為空,元素e1、e2、e3、e4、e5、e6依次通過棧s,乙個元素出棧後即進入佇列q,若6個元素出隊的順序是e2、e4、e3、e6、e5、e1,則棧s的容量至少應該是( )。
a.6 b.4
c.3 d.2
10、表示式a*(b+c)-d的字尾表示式是( )。
a.abcd*+- b.abc+*d-
c.abc*+d- d.-+*abcd
11、深度為k的完全二叉樹至少有()個結點。
a.2k-2+1 b.2k-1
c.2k-1 d.2k–1-1
12、乙個高度為h的滿二叉樹共有n個結點,其中有m個葉子結點,則有()成立。
a.n=h+m b.h+m=2n
c.m=h-1 d.n=2h-1
13、設森林中有4棵樹,樹中結點的個數依次為n1、n2、n3、n4,則把森林轉換成二叉樹後,根結點的左子樹上有()個結點。
a.n1-1 b.n1
c.n1+n2+n3 d.n2+n3+n4
14、有乙個按元素值排好序的順序表(長度大於2),分別用順序查詢和折半查詢與給定值相等的元素,比較次數分別是s和b,在查詢不成功的情況下,s和b的關係是( )。
a.s=b b.s>b
c.s d.不一定
15、雜湊技術中的衝突指的是( )。
a.兩個元素具有相同的序號
b.兩個元素的鍵值不同,而其他屬性相同
c.資料元素過多
d.不同鍵值的元素對應於相同的儲存位址
主觀題部分:
一、簡答題(每題2.5分,共2題)
1、已知如圖所示的有向圖,請給出該圖的
(1)每個頂點的入/出度;
(2)鄰接矩陣;
(3)鄰接表;
(4)逆鄰接表;
(5)強連通分量。
2、帶頭結點的鍊錶和不帶頭結點的鍊錶有什麼不同?
二、應用題(每題5分,共2題)
1、如果矩陣a中存在這樣的乙個元素a[i][j]滿足條件:a[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,則稱之為該矩陣的乙個馬鞍點。編寫乙個函式計算出m×n的矩陣a的所有馬鞍點。
2、有七個帶權結點,其權值分別為3,7,8,2,6,10,14,試以它們為葉結點構造一棵哈夫曼樹(請按照每個結點的左子樹根結點的權小於等於右子樹根結點的權的次序構造〉,並計算出帶權路徑長度wpl及該樹的結點總數。
資料結構作業
資料結構 課程設計報告 2014 2015學年第一學期 課程設計題目 設計學生姓名 所在系部名稱 計算機工程系 所在班級名稱 電腦科學2013 參加設計時間 課程設計課時 30 指導教師姓名 年月日第一題目 假設有兩個集合 a 和 b 分別用兩個線性表 la 和 lb 表示,即線性表中的資料元素即為...
資料結構作業
1 將順序表逆置,要求用最少的附加空間。2 從鍵盤讀入n個整數 公升序 請編寫演算法實現 1 createlist 建立帶表頭結點的單鏈表 include stdio.h typedef struct lnode定義結構體 int data struct lnode next lnode,linkl...
資料結構作業答案
第一章單選題1 下列關於演算法的基本特徵,說法不正確的是 能行性是演算法中的每乙個步驟必須能夠實現且能達到預期的目的。演算法的確定性是指演算法中的每乙個步驟必須是有明確的定義,不允許模稜兩可。演算法的有窮性是指演算法必須能在有限的時間內做完。演算法與提供情報無關。d 教師批改 d 2 演算法的時間複...