1. 大工13秋數據結構在線作業答案
大工13秋《數據結構》在線作業2
一、單選題
1. 二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是（ ）。
A. E
B. F
C. G
D. H
正確答案：C
2. 對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大於其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小於其右孩子的編號，可採用（ ）次序的遍歷實現編號。
A. 先序
B. 中序
C. 後序
D. 從根開始按層次遍歷
正確答案：C
3. 一棵非空的二叉樹的先序遍歷序列與後序遍歷序列正好相反，則該二叉樹一定滿足（ ）。
A. 所有的結點均無左孩子
B. 所有的結點均無右孩子
C. 只有一個葉子結點
D. 是任意一棵二叉樹
正確答案：C
4. 樹中的結點數等於所有結點的度數加（ ）。
A. 0
B. 1
C. 2
D. 3
正確答案：B
5. 已知某二叉樹的後序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。
A. acbed
B. decab
C. deabc
D. cedba
正確答案：D
6. union(A,B,C)表示求集合A和B的並集C。若A={a,b,c},B={c,d},則union(A,B,C)運算後C=（ ）。
A. {a,b,c,d}
B. {a,b,c}
C. {a,b}
D. {c,d}
正確答案：A
7. concat(s,t)表示連接運算。將串t連接在串s之後，形成新的串s。若s="he",t="llo",則concat(s,t)之後，s="（ ）"。
A. hello
B. helo
C. hllo
D. hell
正確答案：A
8. 若串S="software",其子串的數目是（ ）。
A. 8
B. 37
C. 36
D. 9
正確答案：B
9. 在完全二叉樹中，若一個結點是葉結點，則它沒（ ）。
A. 左子結點
B. 右子結點
C. 左子結點和右子結點
D. 左子結點，右子結點和兄弟結點
正確答案：C
10. 非空二叉樹上葉子結點數等於雙分支結點數加（ ）。
A. 0
B. 1
C. 2
D. 3
正確答案：B
二、判斷題
1. index(s,t)表示子串定位運算。若串t是串s的子串，則函數返回值是串t在串s中第一次出現的開始位置，否則返回值是0。（ ）
A. 錯誤
B. 正確
正確答案：B
2. 深度優先遍歷類似於二叉樹的後序遍歷。（ ）
A. 錯誤
B. 正確
正確答案：A
3. difference(A,B,C)表示求集合A和B的差集C。（ ）
A. 錯誤
B. 正確
正確答案：B
4. 遍歷一棵具有n個結點的二叉樹，在先序序列、中序序列和後序序列中所有葉子結點的相對次序都不相同。（ ）
A. 錯誤
B. 正確
正確答案：A
5. 設樹根為第1層，在一棵二叉樹上第5層的結點數最多為16。（ ）
A. 錯誤
B. 正確
正確答案：B
6. 在一個具有n個頂點和e條邊的無向圖的鄰接表中，邊結點的個數為2e。（ ）
A. 錯誤
B. 正確
正確答案：B
7. 具有5個頂點的無向圖至少應有4條邊才能確保是一個連通圖。（ ）
A. 錯誤
B. 正確
正確答案：B
8. 廣度優先遍歷類似於二叉樹的前序遍歷。（ ）
A. 錯誤
B. 正確
正確答案：A
9. concat(s,t)表示連接運算。將串t連接在串s之後，形成新的串s。（ ）
A. 錯誤
B. 正確
正確答案：B
10. union(A,B,C)表示求集合A和B的並集C。（ ）
A. 錯誤
B. 正確
正確答案：B
大工13秋《數據結構》在線作業3
一、單選題
1. 運用直接插入排序方法對下面四個序列進行從小到大排序，元素比較次數最少的是（ ）。
A. 90,69,80,46,21,40
B. 40,21,46,69,90,80
C. 90,80,69,46,40,21
D. 21,40,46,69,80,90
正確答案：D
2. 一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（ ）。
A. (38,40,46,56,79,84)
B. (40,38,46,79,56,84)
C. (40,38,46,56,79,84)
D. (40,38,46,84,56,79)
正確答案：C
3. 快速排序方法在（ ）情況下最不利於發揮其長處。
A. 要排序的數據量太大
B. 要排序的數據中含有多個相同值
C. 要排序的數據個數為奇數
D. 要排序的數據已基本有序
正確答案：D
4. 二分法查找，要求線性表一定是（ ）。
A. 順序存儲的無序表
B. 鏈式存儲的無序表
C. 順序存儲的有序表
D. 鏈式存儲的有序表
正確答案：C
5. 散列表的地址區間為0-17,散列函數為H(K)=K mod 17。採用線性探測法處理沖突，並將關鍵字序列26，25，72，38，8，18，59依次存儲到散列表中。存放元素59需要搜索的次數是（ ）。
A. 2
B. 3
C. 4
D. 5
正確答案：C
6. 若查找每個記錄的概率均等，則在具有n個記錄的連續順序文件中採用順序查找法查找一個記錄，對成功的查找，其平均查找長度為（ ）。
A. (n-1)/2
B. n/2
C. (n+1)/2
D. n
正確答案：C
7. 若要求排序是穩定的，且關鍵字為實數，則在下列排序方法中應選（ ）排序為宜。
A. 直接插入
B. 直接選擇
C. 堆
D. 快速
正確答案：A
8. 將10個元素散列到100000個單元的哈希表中，則（ ）產生沖突。
A. 一定會
B. 一定不會
C. 仍可能會
D. 以上都不對
正確答案：C
9. 下列排序演算法中（ ）不能保證每趟排序至少能將一個元素放到其最終的位置上。
A. 快速排序
B. shell排序
C. 堆排序
D. 冒泡排序
正確答案：B
10. 採用簡單選擇排序，比較次數與移動次數分別為（ ）。
A. O（n）,O(logn)
B. O(logn),0(n*n)
C. 0(n*n),0(n)
D. 0(nlogn),0(n)
正確答案：C
二、判斷題
1. 快速排序是穩定的排序方法。（ ）
A. 錯誤
B. 正確
正確答案：A
2. 直接插入排序是不穩定性排序法。（ ）
A. 錯誤
B. 正確
正確答案：A
3. 從未排序序列中挑選元素，並將其依次放入已排序序列（初始時為空）一端的方法，稱為希爾排序。（ ）
A. 錯誤
B. 正確
正確答案：A
4. 散列文件的基本存儲單位是頁塊。（ ）
A. 錯誤
B. 正確
正確答案：A
5. 合並排序是利用「合並」方法來進行排序。合並是將兩個或多個有序表進行合並，得到一個有序表。（ ）
A. 錯誤
B. 正確
正確答案：B
6. 堆是完全二叉樹。（ ）
A. 錯誤
B. 正確
正確答案：B
7. 用冒泡排序的方法對n個數據進行排序，第一趟共比較n-1對元素。（ ）
A. 錯誤
B. 正確
正確答案：B
8. 交換排序的基本思想是兩兩比較待排序記錄的排序碼，並交換不滿足順序要求的那些偶對，直到全部滿足順序要求為止。（ ）
A. 錯誤
B. 正確
正確答案：B
9. 通常，磁帶只適合於存儲散列文件。（ ）
A. 錯誤
B. 正確
正確答案：A
10. 存儲在磁帶上的順序文件的查找只能用順序查找。（ ）
A. 錯誤
B. 正確
正確答案：B
2. 《數據結構》在線作業
大工11秋《數據結構》在線作業1
一,單選題
1. B
2. B
3. B
4. A
5. A
6. C
7. B
8. B
9. C
10.B
二,判斷題
1.B
2.A
3.B
4.B
5.B
6.A
7.B
8.B
9.B
10.A
大工11秋《數據結構》在線作業2
一,單選題
1. difference(A,B,C)表示求集合A和B的差集C.若A={b,c,d},B={c,e},則difference(A,B,C)運算後C=( ).
A. {b,c,d,e}
B. {c}
C. {b,d}
D. {b,c,c,d,e}
正確答案：C
2. 具有6個頂點的無向圖至少應有（）條邊才能確保是一個連通圖.
A. 5
B. 6
C. 7
D. 8
正確答案：A
3. min(A),函數的返回值是集合A的所有元素中按線性序最小的那個元素.則min({2,3,4})=( )
A. 2
B. 3
C. 4
D. 0
正確答案：A
4. index(s,t)表示子串定位運算.若串t是串s的子串,則函數返回值是串t在串s中第一次出現的開始位置,否則返回值是0.若s="ababa",t="ba",則index(s,t)=( ).
A. 0
B. 1
C. 2
D. 3
正確答案：C
5. 在一棵二叉樹上第5層的結點數最多為（）,設樹根為第1層.
A. 16
B. 15
C. 8
D. 32
正確答案：A
6. intersection(A,B,C)表示求集合A和B的交集C.若A={b,c,d},B={c,e},則intersection(A,B,C)運算後C=( ).
A. {b,c,d,e}
B. {c}
C. {b,d}
D. {b,c,c,d,e}
正確答案：B
7. 在一個具有n個頂點和e條邊的無向圖的鄰接表中,邊結點的個數為（）.
A. n
B. ne
C. e
D. 2e
正確答案：D
8. union(A,B,C)表示求集合A和B的並集C.若A={b,c,d},B={c,e},則union(A,B,C)運算後C=( ).
A. {b,c,d,e}
B. {c}
C. {b,d}
D. {b,c,c,d,e}
正確答案：A
9. 在一個具有n個頂點和e條邊的有向圖的鄰接表中,保存頂點單鏈表的表頭指針向量的大小至少為（）.
A. n
B. 2n
C. e
D. 2e
正確答案：A
10. concat(s,t)表示連接運算.將串t連接在串s之後,形成新的串s.若s="beg",t="in",則concat(s,t)之後,s="( )".
A. begin
B. bein
C. begn
D. beggin
正確答案：A
二,判斷題
1. 樹中的結點數等於所有結點的度數加1.
A. 錯誤
B. 正確
正確答案：B
2. 有向圖用鄰接表表示,頂點i的度是對應頂點i鏈表中結點個數.
A. 錯誤
B. 正確
正確答案：A
3. 字典是一種特殊的集合,其中每個元素由關鍵碼和屬性組成.
A. 錯誤
B. 正確
正確答案：B
4. 有向圖用鄰接表表示,頂點i的出度是對應頂點i鏈表中結點個數.
A. 錯誤
B. 正確
正確答案：B
5. 一個圖的鄰接矩陣表示是惟一的.
A. 錯誤
B. 正確
正確答案：B
6. 有向圖的鄰接矩陣一定是對稱矩陣.
A. 錯誤
B. 正確
正確答案：A
7. 無向圖的鄰接矩陣一定是對稱矩陣.
A. 錯誤
B. 正確
正確答案：B
8. 一個圖的鄰接表表示是惟一的.
A. 錯誤
B. 正確
正確答案：A
9. 非空二叉樹上葉子結點數等於雙分支結點數加1.
A. 錯誤
B. 正確
正確答案：B
10. 連通圖的生成樹不一定是惟一的.
A. 錯誤
B. 正確
正確答案：B
大工11秋《數據結構》在線作業3
一,單選題
1. 下述幾種排序方法中,要求內存量最大的是（）.
A. 插入排序
B. 選擇排序
C. 堆排序
D. 歸並排序
正確答案：D
2. 堆排序是一種（）排序.
A. 插入
B. 選擇
C. 交換
D. 歸並
正確答案：B
3. 在長度為n的順序表中進行順序查找,查找失敗時需與關鍵字比較次數是( ).
A. n
B. 1
C. n-1
D. n+1
正確答案：D
4. 用起泡排序方法對n個記錄按排序碼從小到大排序時,當初始序列是按排序碼從大到小排列時,與排序碼總比較次數是（）.
A. n-1
B. n
C. n+1
D. n(n-1)/2
正確答案：D
5. 對線性表進行順序查找時,要求線性表的存儲結構是（）.
A. 倒排表
B. 索引表
C. 順序表或鏈表
D. 散列表
正確答案：C
6. 對於順序存儲的有序表(5,12,20,26,37,42,46,50,64),若採用折半查找,則查找元素26的查找長度為( ).
A. 2
B. 3
C. 4
D. 5
正確答案：C
7. 哈希表的平均查找長度和（）無直接關系.
A. 哈希函數
B. 裝填因子
C. 哈希表記錄類型
D. 處理沖突的方法
正確答案：C
8. 排序方法中,從未排序序列中挑選元素,並將其依次放入已排序序列（初始時為空）的一端的方法,稱為（）.
A. 希爾排序
B. 歸並排序
C. 插入排序
D. 選擇排序
正確答案：D
9. 磁帶適合存儲的文件類型是（）.
A. 索引文件
B. 順序文件
C. 散列文件
D. 倒排文件
正確答案：B
10. 排序方法中,從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較,將其放入已排序序列的正確位置上的方法,稱為（）.
A. 插入排序
B. 冒泡排序
C. 希爾排序
D. 選擇排序
正確答案：A
二,判斷題
1. 散列表既是一種查找方法,又是一種存儲方法.
A. 錯誤
B. 正確
正確答案：B
2. 在散列文件中刪除記錄時,只要對被刪記錄作一標記即可.
A. 錯誤
B. 正確
正確答案：B
3. 散列文件中存放一組記錄的存儲單位稱為桶.
A. 錯誤
B. 正確
正確答案：B
4. 二分查找對線性表的存儲結構無任何要求.
A. 錯誤
B. 正確
正確答案：A
5. 直接選擇排序屬於選擇類排序,是一種穩定的排序方法.
A. 錯誤
B. 正確
正確答案：A
6. 哈希表查找無須進行關鍵字的比較.
A. 錯誤
B. 正確
正確答案：A
7. 對快速排序來說,初始序列為正序和反序都是最壞情況.
A. 錯誤
B. 正確
正確答案：B
8. 在執行某個排序過程中,出現排序碼朝著最終位置相反方向移動,則該演算法是不穩定的.
A. 錯誤
B. 正確
正確答案：A
9. 堆排序是一種不穩定的排序方法.
A. 錯誤
B. 正確
正確答案：B
10. 若待排序記錄已按排序碼基本有序,則應採用直接插入排序或起泡排序.
A. 錯誤
B. 正確
正確答案：B