國家開放大學年秋季學期電大考試數據結構題庫

1、國家開放大學年秋季學期電大考試數據結構題庫 數據結構課程平時作業(yè) 1 一單項選擇題 1數據結構是一門研究非數值計算的程序設計問題中計算機的以及它們之間的和運算等的學科。 a操作對象 b計算方法 c邏輯存儲 d數據映象 a結構 b關系 c運算 d算法 2數據結構被形式地定義為（k，r），其中 k 是的有限集合，r 是 k 上的的有限集合。 a算法 b數據元素 c數據操作 d邏輯結構 a操作 b映象 c存儲 d關系 3在數據結構中，從邏輯上可以把數據結構分成( )。 a動態(tài)結構和靜態(tài)結構 b緊湊結構和非緊湊結構 c線性結構和非線性結構 d內部結構和外部結構 4. 線性結構是數據元素之間存在一種：

2、a）一對多關系 b）多對多關系 c）多對一關系 d）一對一關系 5. 數據結構中，與所使用的計算機無關的是數據的 結構； a) 存儲 b) 物理 c) 邏輯 d) 物理和存儲 二. . 填空題（將正確的答案填在相應的空中） 1在線性結構中，第一個結點前驅結點，其余每個結點有且只有個前驅結點；最后一個結點后續(xù)結點，其余每個結點有且只有個后續(xù)結點。 2在樹形結構中，樹根結點沒有結點，其余每個結點有且只有個前驅結點；葉子結點沒有結點，其余每個結點的后續(xù)結點可以。 3在圖形結構中，每個結點的前驅結點數和后續(xù)結點數可以。 4線性結構中元素之間存在關系，樹形結構中元素之間存在關系，圖形結構中元素之間存在關

3、系。 5. 數據結構包括數據的 、數據的 和數據的 這三個方面的內容。 6下面程序段的時間復雜度是。 for（i=0；in；i+） for（j=0；jm；j+） aij=0； 7下面程序段的時間復雜度是。 s0； for（i=0；ilt;n；i+） for（j=0; jlt;n; j+） s+=bij； sum=s; 三、簡答題 1. 數據結構是一門研究什么內容的學科？ 2. 數據元素之間的關系在計算機中有幾種表示方法？各有什么特點？ 3.設有數據邏輯結構 s=（d,r），試按題所給條件畫出這些邏輯結構的圖示，并確定相對于關系 r，哪些結點是開始結點，哪些結點是終端結點？ d=d1,d2,d3

4、,d4 r=(d1,d2),(d2,d3),(d3,d4) 部分 參考答案 一、單選題 1a b 2. b d 3. c 4. d 5. c 二、填空題 1. 無，1，無，1 2. 前驅，1 個 ，后繼，多個 3. 多個 4. 一對一，一對多，多對多 5. 邏輯結構、物理結構、數據運算 6. o(n*m) 7. o(n*n) 三、簡答題 1. 略 見課件 2. 略 3d1à d2àd3àd4 線性結構 數據結構課程平時作業(yè) 2 一單項選擇題 1.線性表 l=（a 1 , a 2 ,a n ）,下列說法正確的是 （ ）。 a每個元素都有一個直接前驅和一個直接后繼。

5、b線性表中至少要有一個元素。 c表中諸元素的排列順序必須是由小到大或由大到小。 d除第一個和最后一個元素外,其余每個元素都有一個且僅有一個直接前驅和直接后繼。 2. 在線性表的下列運算中，不改變數據元素之間結構關系的運算是（ ）。 a插入 b刪除 c排序 d定位 3. 在一個長度為 n 的順序表中，在第 i 個元素（1 lt;= i lt;=n+1）之前插入一個新元素時需向后移動（ ）個元素 an-1 bn-i+1 cn-i-1 di 4.一個數組第一個元素的存儲地址是 100，每個元素的長度為 2，則第 5 個 元素的地址是（ ） a110 b108 c100 d120 5. 線性表若采用鏈

6、式存儲結構時，要求內存中可用存儲單元的地址（ ）。 a必須是連續(xù)的 b部分地址必須是連續(xù)的 c一定是不連續(xù)的 d連續(xù)或不連續(xù)都可以 6.在一個單鏈表中，已知 q 所指結點是 p 所指結點的前驅結點，若在 q 和 p之間插入 s 結點，則執(zhí)行語句（ ）。 as-gt;next=p-gt;next;p-gt;next=s; bp-gt;next=s-gt;next;s-gt;next=p; cq-gt;next=s;s-gt;next=p; dp-gt;next=s;s-gt;next=q; 7若已知一個棧的進棧序列是 1，2，3，n，其輸出序列為 p1，p2，p3，.，pn，若 p13，則 p2

7、 為( )。 a 可能是 2 b 一定是 2 c 可能是 1 d 一定是 1 8. 有六個元素 6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（ ） a. 5 4 3 6 1 2 b. 4 5 3 1 2 6 c. 3 4 6 5 2 1 d. 2 3 4 1 5 6 9.設有一順序棧 s，元素 s1,s2,s3,s4,s5,s6 依次進棧，如果 6 個元素出棧的順序是 s2,s3,s4, s6 , s5,s1,則棧的容量至少應該是( ) a.2 b. 3 c. 5 d.6 10. 若棧采用順序存儲方式存儲，現兩棧共享空間 v1.m，topi代表第i個棧( i =1,2)

8、棧頂，棧1的底在v1，棧2的底在vm，則棧滿的條件是（ ）。 a. |top2-top1|=0 b. top1+1=top2 c. top1+top2=m d. top1=top2 二. . 填空題（將正確的答案填在相應的空中） 1. 向一個長度為 n 的向量中刪除第 i 個元素（1in）時，需向前移動_ 個元素。 2. 帶頭結點的單鏈表 head 為空的判定條件是 。 3. 對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為 。 4. 線性表（a, a,a）以鏈接方式存儲時，訪問第 i 位置元素的時間復雜性為 。 5.棧是 的線性表，其運算遵循 的原則。 6.一個棧的輸入序列是：1

9、，2，3 則不可能的棧輸出序列是 。 7.用 s 表示入棧操作，x 表示出棧操作，若元素入棧的順序為 1234，為了得到1342 出棧順序，相應的 s 和 x 的操作串為 。 8.隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是 。 部分參考答案 三、單選題 1d 2. d 3. b 4. b 5. d 6. c 7.a 8.c 9.b 10.b 四、填空題 1. n-i 2.head-gt;next= =null 3. o(n) 4.o(1) 5. 訪問受限，后進先出 6. 3,1,2 7. s xssxsxx 8.先進先出 數據結構課程平時作業(yè) 3 一單項選擇題 1下

10、面關于串的的敘述中，哪一個是不正確的？（ ） a串是字符的有限序列 b空串是由空格構成的串 c模式匹配是串的一種重要運算 d串既可以采用順序存儲，也可以采用鏈式存儲 2串是一種特殊的線性表，其特殊性體現在（ ）。 a可以順序存儲 b數據元素是一個字符 c可以鏈接存儲 d數據元素可以是多個字符 3串的長度是指（ ） a串中所含不同字母的個數 b串中所含字符的個數 c串中所含不同字符的個數 d串中所含非空格字符的個數 4設有兩個串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出現的位置的算法稱為（ ） a求子串 b聯接 c匹配 d求串長 5若串 s="software&#

11、39;,其子串的個數是（ ）。 a8 b37 c36 d9 6. 廣義表（a,b,c,d）的表頭是（ ），表尾是（ ）。 a. a b.（） c.（a,b,c,d） d.（b,c,d） 7. 設廣義表 l=（a,b,c），則 l 的長度和深度分別為（ ）。 a. 1 和 1 b. 1 和 3 c. 1 和 2 d. 2 和 3 8.設有一個 10 階的對稱矩陣 a，采用壓縮存儲方式，以行序為主存儲，a11 為第一元素，其存儲地址為 1，每個元素占一個地址空間，則 a85 的地址為（ ）。 a. 13 b. 33 c. 18 d. 40 9. 設有數組 ai,j，數組的每個元素長度為 3 字節(jié)，

12、i 的值為 1 到 8 ，j 的值為 1 到 10，數組從內存首地址 ba 開始順序存放，當用以列為主存放時，元素a5，8的存儲首地址為( )。 a. ba+141 b. ba+180 c. ba+222 d. ba+225 10. 假設以行序為主序存儲二維數組 a=array1.100，1.100，設每個數據元素占 2 個存儲單元，基地址為 10，則 loc5，5=（ ）。 a. 808 b. 818 c. 1010 d. 1020 二. . 填空題（將正確的答案填在相應的空中） 1含零個字符的串稱為( )串。任何串中所含( )的個數稱為該串的長度。 2當且僅當兩個串的( )相等并且各個對應

13、位置上的字符都( )時，這兩個串相等。一個串中任意個連續(xù)字符組成的序列稱為該串的( )串。 3index（datastructure， str）=（ ）。 4. 數組的存儲結構采用（ ）存儲方式。 5. 設二維數組 a-20.30,-30.20, 每個元素占有 4 個存儲單元, 存儲起始地址為 200。如按行優(yōu)先順序存儲,則元素 a25,18的存儲地址為（ ）；如按列優(yōu)先順序存儲,則元素 a-18,-25的存儲地址為（ ）。 6. 將整型數組 a1.8，1.8按行優(yōu)先次序存儲在起始地址為 1000 的連續(xù)的內存單元中，則元素 a7，3的地址是（ ）。 7.設廣義表 l=(),(), 則 hea

14、d(l)是（ ）；tail(l)是（ ）；l 的長度是（ ）；深度是（ ）。 8. 廣義表(a,(a,b),d,e,(i,j),k)的長度是（ ），深度是（ ）。 部分參考答案 五、單選題 1b 2. b 3. b 4. c 5. b 6. c.b 7.c 8.b 9.b 10.b 六、填空題 2. 空，字符 2.長度，串值，子串 3. 5 4.順序存儲 5. 9392 ，1208 6. 1200 7. （），（），2,2 8. 5 , 3 數據結構課程平時作業(yè) 4 一單項選擇題 1. 按照二叉樹的定義，具有 3 個結點的二叉樹有（ ）種。 a3 b. 4 c. d. 6 2. 有關二叉樹下列

15、說法正確的是（ ） a二叉樹的度為 2 b一棵二叉樹的度可以小于 2 c二叉樹中至少有一個結點的度為 2 d二叉樹中任何一個結點的度都為 2 3若一棵二叉樹具有 10 個度為 2 的結點，5 個度為 1 的結點，則度為 0 的結點個數是（ ） a9 b11 c15 d不確定 4. 深度為的二叉樹至多有（ ）個結點。 a. 16 b. 32 c.31 d.10 5在一棵高度為 k 的滿二叉樹中，結點總數為（ ） a2k -1 b2k c2k-1 dlog2k+11.設有無向圖 6.g=（v，e）和 g=（v,e）,如 g為 g 的生成樹，則下面不正確的說法是（ ） ag為 g 的子圖 bg為 g

16、 的連通分量 cg為 g 的極小連通子圖且 v=v dg是 g 的無環(huán)子圖 7.任何一個帶權的無向連通圖的最小生成樹（ ） a只有一棵 b有一棵或多棵 c一定有多棵 d可能不存在 8以下說法正確的是（ ） a連通分量是無向圖中的極小連通子圖。 b強連通分量是有向圖中的極大強連通子圖。 c在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧lt;a,bgt;。 d對有向圖 g,如果從任意頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖。 9圖中有關路徑的定義是（ ）。 a由頂點和相鄰頂點序偶構成的邊所形成的序列 b由不同頂點所形成的序列 c由不同邊所形成的序

17、列 d上述定義都不是 10設無向圖的頂點個數為 n，則該圖最多有（ ）條邊。 an-1 bn(n-1)/2 c n(n+1)/2 d0 en2 二. . 填空題（將正確的答案填在相應的空中） 樹是 n 個結點的有限集合，當 n=0 時稱為（ ）。 2 具有 256 個結點的完全二叉樹的深度為（ ）。 3. 如果結點 a 有 3 個兄弟，而且 b 是 a 的雙親，則 b 的度是( )。 4. 設 f 是由 t1,t2,t3 三棵樹組成的森林,與 f 對應的二叉樹為 b,已知t1,t2,t3的結點數分別為n1,n2和n3則二叉樹b的左子樹中有( )個結點，右子樹中有( )個結點。 5. 具有 n

18、個結點的二叉樹，采用二叉鏈表存儲，共有（ ）個空鏈域。 6具有 10 個頂點的無向圖，邊的總數最多為( )。 7對于一個具有 n 個頂點 e 條邊的無向圖的鄰接表的表示，則表頭向量大小為（ ），鄰接表的邊結點個數為（ ）。 8. 在有 n 個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要（ ）條弧。 9下圖中的強連通分量的個數為（ ）個。 10n 個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有（ ）個非零元素。 三. . 簡答題 1.已知某二叉樹的前序遍歷序列為：a b c d e f g 和中序遍歷序列為：c b e d a f g，求后續(xù)遍歷。 2. 已知如圖所示的有向圖，請給出該

19、圖的： 部分參考答案 一、單選題 1c 2. b 3. b 4. c 5. a 6. b 7.b 8.b 9.a 10.b 二、填空題 3. 空樹 2. 9 3. 4 4. n1 , n2+n3 5. n+1 6. 45 7. n , 2e 8. n 9. 3 10. 2(n-1) 三、簡答題 1.cedbagf 2. （1）頂點 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3 （2） 鄰接矩陣 （3）鄰接表 （1）每個頂點的入度、出度； （2）鄰接矩陣； （3）鄰接表； （4）逆鄰接表； （5）強連通分量。 （4）逆鄰接表 （5）強連通分量 數據結構課程平

20、時作業(yè) 5 一單項選擇題 1.若在線性表中采用二分查找法查找元素，該線性表應該( )。 a元素按值有序 b采用順序存儲結構 c元素按值有序，且采用順序存儲結構 d元素按值有序，且采用鏈式存儲結構 2.利用逐點插入法建立序列(51，71，43，81，74，20，34，45，64，30)對應的二叉排序樹以后，查找元素 34 要進行( )元素間的比較。 a4 次 b5 次 c. 7 次 d10 3.散列函數有一個共同性質，即函數值應按( )取其值域的每一個值。 a.最大概率 b.最小概率 c.同等概率 d.平均概率 4.一個哈希函數被認為是"好的'，如果它滿足條件( )。 a哈希地

21、址分布均勻 b.保證不產生沖突 c. 所有哈希地址在表長范圍內 d.滿足 b 和 c 5.平均查找長度最短的查找方法是( )。 a.折半查找 b.順序查找 c.哈希查找 d.其他 6. 若對 n 個元素進行直接插入排序，在進行第 i 趟排序時，假定元素 ri+1的插入位置為 rj，則需要移動元素的次數為（ ）。 a. j-i b. i-j-1 c. i-j d. i-j+1 7. 若對 n 個元素進行直接插入排序，則進行任一趟排序的過程中，為尋找插入位置而需要的時間復雜度為（ ）。 a. o(1) b. o(n) c. o(n2 ) d. o(log2n) 8. 在對 n 個元素進行冒泡排序的

22、過程中，第一趟排序至多需要進行（ ）對相鄰元素之間的交換。 a. n b. n-1 c. n+1 d. n/2 9. 在對 n 個元素進行冒泡排序的過程中，最好情況下的時間復雜度為（ ）。 a. o(1) b. o(log2n) c. o(n2) d. o(n) 10. 在對 n 個元素進行快速排序的過程中，第一次劃分最多需要移動（ ）次元素，包括開始把支點元素移動到臨時變量的一次在內。 a. n/2 b. n-1 c. n d. n+1 二. . 填空題（將正確的答案填在相應的空中） 1.( )法構造的哈希函數肯定不會發(fā)生沖突。 2. 線性有序表（a1，a2，a3，a256)是從小到大排列的

23、，對一個給定的值 k，用二分法檢索表中與 k 相等的元素，在查找不成功的情況下，最多需要檢索( )次。設有 100 個結點，用二分法查找時，最大比較次數是( )。 3.對 n 個關鍵字進行冒泡排序，時間復雜度為（ ）。 4折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素 20，它將依次與表中元素( )比較大小。 5. 在各種查找方法中，平均查找長度與結點個數 n 無關的查找方法是( )。 6.若待排序的序列中存在多個記錄具有相同的鍵值，經過排序，這些記錄的相對次序仍然保持不變，則稱這種排序方法是（ ）的，否則稱為（ ）的。 7.按照排序過程涉及的存儲設

24、備的不同，排序可分為（ ）排序和（ ）排序。 8.直接插入排序用監(jiān)視哨的作用是（ ）。 9.對 n 個記錄的表 r1.n進行簡單選擇排序，所需進行的關鍵字間的比較次數為（ ）。 10.在插入排序和選擇排序中，若初始數據基本正序，則選用（ ）較好。 三. . 簡答題 1對于給定的一組鍵值：83，40，63，13，84，35，96，57，39，79，61，15，分別畫出應用直接插入排序、直接選擇排序、快速排序、歸并排序對上述序列進行排序中各趟的結果。 部分參考答案 一、單選題 2c 2. a 3. c 4. d 5. c 6. d 7.c 8.b 9.d 10.b 二、填空題 4. 直接定址法 2

25、. 9 ，7 3. o(n 2 ) 4. 28, 12 ,20 5. 哈希表 6. 穩(wěn)定的，非穩(wěn)定的 7. 內部排序，外部排序 8. 防止數組越界 9. n(n-1)/2 10. 插入排序 四、簡答題 直接插入排序 序號 1 2 3 4 5 6 7 8 9 10 11 12 關鍵字 83 40 63 13 84 35 96 57 39 79 61 15 i = 2 40 83 63 13 84 35 96 57 39 79 61 15 i = 3 40 63 83 13 84 35 96 57 39 79 61 15 i = 4 13 40 63 83 84 35 96 57 39 79 61

26、 15 i = 5 13 40 63 83 84 35 96 57 39 79 61 15 i = 6 13 35 40 63 83 84 96 57 39 79 61 15 i = 7 13 35 40 63 83 84 96 57 39 79 61 15 i = 8 13 35 40 57 63 83 84 96 39 79 61 15 i = 9 13 35 39 40 57 63 83 84 96 79 61 15 i = 10 13 35 39 40 57 63 79 83 84 96 61 15 i = 11 13 35 39 40 57 61 63 79 83 84 96 15

27、i = 12 13 15 35 39 40 57 61 63 79 83 84 96 直接選擇排序 序號 1 2 3 4 5 6 7 8 9 10 11 12 關鍵字 83 40 63 13 84 35 96 57 39 79 61 15 i = 1 13 40 63 83 84 35 96 57 39 79 61 15 i = 2 13 15 63 83 84 35 96 57 39 79 61 40 i = 3 13 15 35 83 84 63 96 57 39 79 61 40 i = 4 13 15 35 39 84 63 96 57 83 79 61 40 i = 5 13 15

28、35 39 40 63 96 57 83 79 61 84 i = 6 13 15 35 39 40 57 96 63 83 79 61 84 i = 7 13 15 35 39 40 57 61 63 83 79 96 84 i = 8 13 15 35 39 40 57 61 63 83 79 96 84 i = 9 13 15 35 39 40 57 61 63 79 83 96 84 i = 10 13 15 35 39 40 57 61 63 79 83 96 84 i = 11 13 15 35 39 40 57 61 63 79 83 84 96 快速排序 關鍵字 83 40 6

29、3 13 84 35 96 57 39 79 61 15 第一趟排序后 15 40 63 13 61 35 79 57 39 83 96 84 第二趟排序后 13 15 63 40 61 35 79 57 39 83 84 96 第三趟排序后 13 15 39 40 61 35 57 63 79 83 84 96 第四趟排序后 13 15 35 39 61 40 57 63 79 83 84 96 第五趟排序后 13 15 35 39 57 40 61 63 79 83 84 96 第六趟排序后 13 15 35 39 40 57 61 63 79 83 84 96 第七趟排序后 13 15

30、35 39 40 57 61 63 79 83 84 96 歸并排序 關鍵字 83 40 63 13 84 35 96 57 39 79 61 15 第一趟排序后 40 83 13 63 35 84 57 96 39 79 15 61 第二趟排序后 13 40 63 83 35 57 84 96 15 39 61 79 第三趟排序后 13 35 40 57 63 83 84 96 15 39 61 79 第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96 電大開放專科英語 i(1) 試點機考題庫 選詞填句子（choose the correct answers

31、） 1this is where you work ,xiaoyan ,that is your desk and this is _ 選（b）mine 2john: paul,this is mr smith ,my landlord. paul: im pleased to meet you mr smith:_ 選（b）very pleased to meet you .too 3a: what does your mother do? b:_ 選（c）she is a clerk in a bank 4a: could you ring them up please?imsometim

32、es quite nervous on the phone. b:_ 選（c）yes of course .i will phone them for you 5david is _only accountant in my sons company 選（a）the 6 i usually get up _7 oclock _the morning 選（b）at ,in 7she_the flat advertisement. 選（a）has a problem with 8_would you like,tea or coffice? 選（c）what 9why is she _lunch

33、so early?its only 10 now 選（a）having 10i am planning a new marketing compaign at the moment_? 選（c）what are you doing 11whats_job?are_british? 選（c）your, you 12a: hello,xiaoyan ,how are you?and how are things? b:_everybody is very nice and helpful. 選（c）great.l am fine 13a;_? b:she is talking to mary 選（

34、a）what is she doing right now 14 a: the shower isnt working. b:_ 選（b）ill call the plumber 15i am_engineer 選（b）an 16this is his book could you give it _him? 選（a）to 17does david_? 選（a）like flying 18a: what tv programmes do you like? b:i_london lives. 選（a）like watching 19there_three plants in the offic

35、e 選（a）are 20my uncle_in the it department.but now he_on a plan for the marketing department 選（a）works. is working 21a_? b: my father is a manager. my mother is a nurse. 選（b）what do your parents do 22mr manning_in paris today and tomorrow. 選（c）is working 23_name is jane _is from the usa. 選（a）her ,she

36、 24 a:_? b: yes,id like to .thanks 選 （b） would you like to come to the shop one 25my mother is a doctor .she is _medicine. 選（c）in 26polly enjoys_in a band in her frem time. 選（c）playing the guitar 27a: _you like a drink?wine?beer? 選（b）would 28a: _? b: yes,i do , my mother and father live in oxford. 選

37、（a）do you have any family 29i_ this e-mail to tell you about my new office. 選（a）am writing 30we often have_supper at home 選（c）our 31a; - b: hi my names rose.are you from london? 選（a）hello. im paul. whats your 32a; what does your father do? b: _ 選（a）he is responsible for the central computer system 3

38、3a: where is david? b: hi is having lunch in_ chinese restaurant on_seventh floor 選（c）the .the 34i sometimes go to the pub_ friday _ my colleagues. 選（a）on, with 35my aunt_ for her friends at home 選（c）enjoys cooking 36a:_ polly? b: id like a glass of wine ,thank you. 選（b）what would you like 37_a coff

39、ee machine in the room 選（b）is therlondon? 選（a）hello. im paul. whats your 38jane and paul like good coffee ,so go and get some good coffee for_ 選（b）them 39hello im david manning .nice to meet you b:_ 選（c）nice to meet you im 40a:_,daid? b: anorange juice. 選（b）what would you like 41ive got a lot of pho

40、tos of my traveling .would you_them? 42a: are there two men in the room? 43david_ on a new database at the moment 44 a: why dont you go to an estate agent,then,youre talking face to face? b:well,_ 45my husband doesnt_ ,but i like it very much. 46a; _ b: she works in the oxford university 選（a）like to see 選（b）no, theres only one 選（b）is currently working 選（c）i dont know 選（a）like shopping 選（a）what does your mother 47london is _capital of britain ,and it is_great city too 選（c）the .a 48id_a beer toothank you 選（b）like to have 49_people are my frien