第一章單選題1、下列關於演算法的基本特徵,說法不正確的是()。 能行性是演算法中的每乙個步驟必須能夠實現且能達到預期的目的。 演算法的確定性是指演算法中的每乙個步驟必須是有明確的定義,不允許模稜兩可。
演算法的有窮性是指演算法必須能在有限的時間內做完。 演算法與提供情報無關。
[d] 教師批改:d
2、演算法的時間複雜度取決於()。 問題的規模待處理的資料的初態
問題的難度 a 和 b
[d] 教師批改:d
3、下列選項中,不是演算法基本特徵的是()。 可行性有窮性
確定性高效率
[d] 教師批改:d
4、通常乙個好的演算法應達到的目標中,不包括()。 正確性可讀性
技巧性健壯性
[c] 教師批改:c
5、在一般的計算機系統中,基本的運算和操作不包括()。 語法處理算術運算
關係運算資料傳輸
[a] 教師批改:a
6、工程上常用的分治法是()。 列舉法歸納法
減半遞推技術回溯法
[c] 教師批改:c
多選題 7、演算法設計的要求包括()。
正確性可讀性
健壯性唯一性
[abc] 教師批改:a,b,c
8、演算法的時間複雜度應該與()無關。
所使用的計算機程式語言
基本運算的執行次數程式編制者
[abd] 教師批改:a,b,d
9、下列關於演算法的描述中,不正確的有()。
演算法即是電腦程式演算法是解決問題的計算方法
演算法是排序方法演算法是解決問題的有限運算序列
[abc] 教師批改:a,b,c
填空題16、所謂演算法是指( )。
教師批改:解題方****而完整的描述
17、演算法的基本特徵有( )、()、()和()
教師批改:能行性、確定性、有窮性和擁有足夠的情報。
18、乙個演算法通常由兩種基本要素組成,它們是()和()。
教師批改:演算法中對資料的運算和操作。
演算法的控制結構。
19、工程上常用的幾種演算法設計方法有列舉法和回溯法。
教師批改:歸納法、遞推、遞迴、減半遞推技術。
20、演算法的複雜度主要包括()複雜度和()複雜度。
教師批改:時間、空間
綜合題21、設給定3個整數a,b,c,試寫出尋找這3個整數的中數的演算法;並分析在平均情況與最壞情況下,該演算法分別要做多少次比較?
尋找這3個整數的中數的演算法用c語言描述如下(中數m由函式值返回):
int mid ( int a, int b, int c)
}else }
return ( m ) ;
}假設a,b,c中的每乙個數為中數的概率相等(均為1/3)。由於當a為中數時需要比較2次,b或c為中數時均需要比較3次,因此,在平均情況下上述演算法所需要的比較次數為
2*(1/3)+3*(1/3)+3*(1/3)= 8/3
即在平均情況下,上述演算法需要比較8/3次。
在最壞情況下,上述演算法需要比較3次(當b或c為中數時)。
第二章選擇題
1、下列排序方法中,哪乙個是穩定的排序方法()。 歸併排序稀爾排序
堆排序快速排序
[a] 教師批改:a
2、設輸入序列為1,2,3,4,借助乙個棧得到的輸出序列可以是()。 3,4,1,2 4,2,1,3
4,1,2,3 1,3,4,2
[d] 教師批改:d
3、用陣列a[m]存放迴圈佇列的元素值,若其頭尾指標分別為front和rear,則迴圈佇列中當前元素的個數為()。 (rear+front)%m (rear-front+m)%m
(rear-front)%m (rear-front+1)%m
[d] 教師批改:b
4、對於下三角矩陣a,若採用乙個一維陣列b以行為主順序存放壓縮矩陣a,則a43存放在()中. b7 b8
b9 b10
[c] 教師批改:c
5、深度為5的二叉樹至多有()個結點。 16 32
31 10
[c] 教師批改:c
6、乙個有n個頂點的無向圖最多有()條邊。 n n(n-1)
n(n-1)/2 2n
[c] 教師批改:c
7、下列說法不正確的是()。 線性表可以順序儲存線性表可以鏈式儲存
線性表在順序儲存下可以對分查詢線性表在鏈式儲存下可以對分查詢
[d] 教師批改:d
8、棧和佇列的共同點是()。 都是先進後出都是先進先出
只允許在端點處插入和刪除元素沒有共同點
[c] 教師批改:c
9、若進棧序列為a、b、c、d(進棧過程可以出棧),不可能得到的出棧序列是()。 a、d、c、b b、c、d、a
c、a、d、b c、d、b、a
[c] 教師批改:c
10、在乙個單鏈表中,若p結點不是最後一結點。在p結點之後插入s結點的正確操作是()。 s->next=p; p->next=s; s->next=p->next ; p->next=s;
s->next=p; p=p; p->next=s; s->next=p;
[b] 教師批改:b
11、由3個結點可以構造出多少種不同的二叉樹()。 2 4
5 8
[c] 教師批改:c
填空題 27、若一棵完全二叉樹共有100個結點,則其葉子結點數為()。
教師批改:50
28、在單鏈表中設定(表)頭結點的作用是()。
教師批改:簡化插入,刪除演算法,方便運算的實現。
29、結點最少的樹為(),結點最少的二叉樹為()。
教師批改:只有乙個(根)結點的樹。
空的二叉樹。
34、 在一棵二叉樹中有30個葉子結點,僅有乙個孩子的結點有20個,則該二叉樹結點數為()。
教師批改:79
35、 **性表的雜湊儲存中,處理衝突有()和()兩種方法。
教師批改:拉鍊法、開位址法
36、 已知一棵二叉樹的中序遍歷序列和後序遍歷序列分別為bdceafhg和decbhgfa,試寫出其前序遍歷序列。
教師批改:前序遍歷:abcdefgh
30、 資料的()結構與資料元素本身的內容、形式、個數和相對位置無關。
教師批改:邏輯
31、 資料的儲存結構有四種基本的儲存對映方式:順序 、()、 索引和()儲存方式。
教師批改:鏈式、雜湊
32、 用順序方法將完全二叉樹的結點逐層存放在陣列a[1]~a[n]中,若結點a[i] 有右子女,則右子女是結點為()。
教師批改:a[2*i+1]
33、設有二維陣列a4×6,其中每個元素佔兩個位元組,陣列按列優先順序儲存,第乙個元素a11的儲存位址為100,那麼元素a43的儲存位址為()。
教師批改:122
綜合題37、什麼叫資料結構?資料結構對演算法有什麼影響?
資料結構是指相互有關聯的資料元素的集合。因此,乙個資料結構既要反映資料元素的資訊,又要反映資料元素之間的關係。資料元素之間的關係可以是邏輯關係(通常用前後件關係來表示),也可以是資料元素在計算機中的儲存位置。
反映資料元素之間邏輯關係的資料結構稱為資料的邏輯結構。資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構,又稱為資料的物理結構。
同一批資料元素的集合,採用不同的資料結構(特別是儲存結構),其資料處理的效率是不一樣的,主要體現在演算法的時間複雜度與空間複雜度方面。比如:若只是對2~3個數進行排序,則用幾個if語句即可完成;而若對一般情況下的n個數進行排序,則要使用陣列,通過(雙重等)迴圈來完成。
38、 試寫出在順序儲存結構下逆轉線性表的演算法,要求使用最少的附加空間
順序儲存結構下逆轉線性表的演算法用c語言描述如下(其中et為資料元素的型別):
void invsl ( int n , et a [ ] )
else
k = k+1 ;
}if ( i = = n)
for ( t = j ; t < m ; t + + )
return ;}
資料結構答案
1 有乙個帶頭指標的單鏈表,寫出在值為x的結點之後插入m個結點的演算法 int insertm linklist l,int x,int m p next q連線斷點 3 假設乙個長度大於1的單迴圈鍊錶既無頭結點也無頭指標,s為指向鍊錶中某個結點的指標,試設計刪除結點s的直接前驅結點的演算法 voi...
《資料結構》作業
本課程作業由兩部分組成。第一部分為 客觀題部分 由選擇題組成,每題1分,共15分。第二部分為 主觀題部分 由簡答題和應用題組成,共15分。作業總分30分,將作為平時成績記入課程總成績。客觀題部分 一 選擇題 每題1分,共10題 1 順序儲存結構中資料元素之間的邏輯關係是由 表示的。a.線性結構 b....
資料結構作業
資料結構 課程設計報告 2014 2015學年第一學期 課程設計題目 設計學生姓名 所在系部名稱 計算機工程系 所在班級名稱 電腦科學2013 參加設計時間 課程設計課時 30 指導教師姓名 年月日第一題目 假設有兩個集合 a 和 b 分別用兩個線性表 la 和 lb 表示,即線性表中的資料元素即為...