電大數(shù)據(jù)結(jié)構(gòu)課程平時作業(yè)

1、數(shù)據(jù)結(jié)構(gòu)課程平時作業(yè)1一單項選擇題 1數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的以及它們之間的和運算等的學科。 A操作對象 B計算方法 C邏輯存儲 D數(shù)據(jù)映象 A結(jié)構(gòu) B關(guān)系 C運算 D算法 2數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是的有限集合，R是K上的的有限集合。 A算法 B數(shù)據(jù)元素 C數(shù)據(jù)操作 D邏輯結(jié)構(gòu) A操作 B映象 C存儲 D關(guān)系 3 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( )。 A 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 4. 線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對

2、一關(guān)系5. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲 二.填空題（將正確的答案填在相應的空中）1在線性結(jié)構(gòu)中，第一個結(jié)點前驅(qū)結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；最后一個結(jié)點后續(xù)結(jié)點，其余每個結(jié)點有且只有個后續(xù)結(jié)點。2在樹形結(jié)構(gòu)中，樹根結(jié)點沒有結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；葉子結(jié)點沒有結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以。3在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以。4線性結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。5. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 、數(shù)據(jù)的 和數(shù)據(jù)的 這三個方面的內(nèi)容。6下面

3、程序段的時間復雜度是。 for（i=0；in；i+） for（j=0；jm；j+） Aij=0；7下面程序段的時間復雜度是。 S0； for（i=0；i<n；i+） for（j=0; j<n; j+） s+=bij； sum=s; 三、簡答題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學科？2. 數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法？各有什么特點？3.設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點？ D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 部分參考答案一、 單選題1

4、 A B 2. B D 3. C 4. D 5. C二、 填空題1. 無，1，無，12. 前驅(qū)，1個 ，后繼，多個3. 多個4. 一對一，一對多，多對多5. 邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、數(shù)據(jù)運算 6. O(n*m) 7. O(n*n)三、簡答題 1. 略 見課件 2. 略 3d1à d2àd3àd4 線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)課程平時作業(yè)2一單項選擇題 1.線性表L=（a, a,a）,下列說法正確的是 （ ）。A每個元素都有一個直接前驅(qū)和一個直接后繼。B線性表中至少要有一個元素。C表中諸元素的排列順序必須是由小到大或由大到小。D除第一個和最后一個元素外,其余每個元素都有一個且僅有

5、一個直接前驅(qū)和直接后繼。2. 在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（ ）。A插入 B刪除C排序 D定位3. 在一個長度為n的順序表中，在第i個元素（1 <= i <=n+1）之前插入一個新元素時需向后移動（ ）個元素An-1 Bn-i+1 Cn-i-1 DI4.一個數(shù)組第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）A110 B108 C100 D1205. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以6.在一個單鏈表中，已知q所指結(jié)點是p

6、所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行語句（ ）。As->next=p->next;p->next=s; Bp->next=s->next;s->next=p; Cq->next=s;s->next=p; Dp->next=s;s->next=q;7若已知一個棧的進棧序列是1，2，3，n，其輸出序列為p1，p2，p3，.，pn，若p13，則p2為( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 8. 有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（ ） A. 5 4 3 6

7、 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 9.設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4, s6 , s5,s1,則棧的容量至少應該是( ) A.2 B. 3 C. 5 D.6 10. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ ）。 A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top2 二.填空題（將正確的答案

8、填在相應的空中）1. 向一個長度為n的向量中刪除第i個元素（1in）時，需向前移動_個元素。2. 帶頭結(jié)點的單鏈表head為空的判定條件是 。3. 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為 。4. 線性表（a, a,a）以鏈接方式存儲時，訪問第i 位置元素的時間復雜性為 。5.棧是 的線性表，其運算遵循 的原則。 6.一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是 。 7.用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為 。 8.隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是 。部分

9、參考答案三、 單選題1 D 2. D 3. B 4. B 5. D 6. C 7.A 8.C 9.B 10.B四、 填空題1. n-i 2.head->next= =NULL3. O(n) 4.O(1) 5. 訪問受限，后進先出 6. 3,1,2 7. S XSSXSXX 8.先進先出數(shù)據(jù)結(jié)構(gòu)課程平時作業(yè)3一單項選擇題 1下面關(guān)于串的的敘述中，哪一個是不正確的？（ ） A串是字符的有限序列 B空串是由空格構(gòu)成的串 C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈式存儲 2串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A可以順序存儲 B數(shù)據(jù)元素是一個字符 C可以鏈接存儲

10、D數(shù)據(jù)元素可以是多個字符 3串的長度是指（ ） A串中所含不同字母的個數(shù) B串中所含字符的個數(shù) C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù) 4設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（ ） A求子串 B聯(lián)接 C匹配 D求串長 5若串S=“software”,其子串的個數(shù)是（ ）。 A8 B37 C36 D96. 廣義表（a,b,c,d）的表頭是（ ），表尾是（ ）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 7. 設(shè)廣義表L=（a,b,c），則L的長度和深度分別為（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 8.

11、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。 A. 13 B. 33 C. 18 D. 40 9. 設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當用以列為主存放時，元素A5，8的存儲首地址為( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+22510. 假設(shè)以行序為主序存儲二維數(shù)組A=array1.100，1.100，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC5，5=（ ）。 A

12、. 808 B. 818 C. 1010 D. 1020 二.填空題（將正確的答案填在相應的空中）1含零個字符的串稱為( )串。任何串中所含( )的個數(shù)稱為該串的長度。 2當且僅當兩個串的( )相等并且各個對應位置上的字符都( )時，這兩個串相等。一個串中任意個連續(xù)字符組成的序列稱為該串的( )串。 3INDEX（DATASTRUCTURE， STR）=（ ）。4. 數(shù)組的存儲結(jié)構(gòu)采用（ ）存儲方式。 5. 設(shè)二維數(shù)組A-20.30,-30.20, 每個元素占有4 個存儲單元, 存儲起始地址為200。如按行優(yōu)先順序存儲,則元素 A25,18的存儲地址為（ ）；如按列優(yōu)先順序存儲,則元素A-18

13、,-25的存儲地址為（ ）。 6. 將整型數(shù)組A1.8，1.8按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A7，3的地址是（ ）。 7.設(shè)廣義表L=(),(), 則head(L)是（ ）；tail(L)是（ ）；L的長度是（ ）；深度是（ ）。 8. 廣義表(a,(a,b),d,e,(i,j),k)的長度是（ ），深度是（ ）。部分參考答案五、 單選題1 B 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. （），（），

14、2,2 8. 5 , 3數(shù)據(jù)結(jié)構(gòu)課程平時作業(yè)4一單項選擇題 1. 按照二叉樹的定義，具有3個結(jié)點的二叉樹有（）種。A3 B. 4 C. D. 62. 有關(guān)二叉樹下列說法正確的是（ ）A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個結(jié)點的度為2 D二叉樹中任何一個結(jié)點的度都為23若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ ）A9 B11 C15 D不確定 4. 深度為的二叉樹至多有（）個結(jié)點。A. 16 B. 32 C.31 D.105在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（ ）A2k-1 B2k C2k-1 Dlog2k+11.設(shè)有無向圖6.

15、G=（V，E）和G=（V,E）,如G為G的生成樹，則下面不正確的說法是（ ）AG為G的子圖 BG為G的連通分量 CG為G的極小連通子圖且V=V DG是G的無環(huán)子圖7.任何一個帶權(quán)的無向連通圖的最小生成樹（ ）A只有一棵 B有一棵或多棵 C一定有多棵 D可能不存在8以下說法正確的是（ ）A連通分量是無向圖中的極小連通子圖。B強連通分量是有向圖中的極大強連通子圖。C在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>。D對有向圖G,如果從任意頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖。9圖中有關(guān)路徑的定義是（ ）。A由頂點和相鄰頂點

16、序偶構(gòu)成的邊所形成的序列 B由不同頂點所形成的序列C由不同邊所形成的序列 D上述定義都不是10設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（ ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2二.填空題（將正確的答案填在相應的空中）樹是n個結(jié)點的有限集合，當n=0時稱為（）。2 具有256個結(jié)點的完全二叉樹的深度為（ ）。3. 如果結(jié)點A有 3個兄弟，而且B是A的雙親，則B的度是( )。4. 設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應的二叉樹為B,已知T1,T2,T3的結(jié)點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有( )個結(jié)點，右子樹中有( )個結(jié)點。 5. 具有N個

17、結(jié)點的二叉樹，采用二叉鏈表存儲，共有（ ）個空鏈域。6具有10個頂點的無向圖，邊的總數(shù)最多為( )。7對于一個具有n個頂點e條邊的無向圖的鄰接表的表示，則表頭向量大小為（ ），鄰接表的邊結(jié)點個數(shù)為（ ）。8. 在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要（ ）條弧。9下圖中的強連通分量的個數(shù)為（ ）個。10N個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有（ ）個非零元素。三.簡答題1.已知某二叉樹的前序遍歷序列為：A B C D E F G和中序遍歷序列為：C B E D A F G，求后續(xù)遍歷。 （1）每個頂點的入度、出度；（2）鄰接矩陣；（3）鄰接表；（4）逆鄰接表； （

18、5）強連通分量。2. 已知如圖所示的有向圖，請給出該圖的： 部分參考答案一、單選題1 C 2. B 3. B 4. C 5. A 6. B 7.B 8.B 9.A 10.B二、填空題3. 空樹 2. 93. 4 4. n1 , n2+n3 5. N+1 6. 45 7. n , 2e 8. n 9. 3 10. 2(N-1)3、 簡答題1.CEDBAGF 2. （1）頂點 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3（2）      鄰接矩陣  （3）鄰接表（4）逆鄰接表（5）強連通分量數(shù)據(jù)結(jié)構(gòu)課

19、程平時作業(yè)5一單項選擇題 1.若在線性表中采用二分查找法查找元素，該線性表應該(     )。A元素按值有序    B采用順序存儲結(jié)構(gòu)C元素按值有序，且采用順序存儲結(jié)構(gòu)D元素按值有序，且采用鏈式存儲結(jié)構(gòu)2.利用逐點插入法建立序列(51，71，43，81，74，20，34，45，64，30)對應的二叉排序樹以后，查找元素34要進行(    )元素間的比較。 A4次    B5次    C. 7次    D103.散列函

20、數(shù)有一個共同性質(zhì)，即函數(shù)值應按(    )取其值域的每一個值。A.最大概率   B.最小概率   C.同等概率   D.平均概率4.一個哈希函數(shù)被認為是“好的”，如果它滿足條件( )。A哈希地址分布均勻 B.保證不產(chǎn)生沖突C. 所有哈希地址在表長范圍內(nèi) D.滿足B和C5.平均查找長度最短的查找方法是( )。A.折半查找 B.順序查找 C.哈希查找 D.其他6. 若對n個元素進行直接插入排序，在進行第i趟排序時，假定元素ri+1的插入位置為rj，則需要移動元素的次數(shù)為（ ）。 A. j-i B. i-j-1

21、 C. i-j D. i-j+1 7. 若對n個元素進行直接插入排序，則進行任一趟排序的過程中，為尋找插入位置而需要的時間復雜度為（ ）。 A. O(1) B. O(n) C. O(n2) D. O(log2n) 8. 在對n個元素進行冒泡排序的過程中，第一趟排序至多需要進行（ ）對相鄰元素之間的交換。 A. n B. n-1 C. n+1 D. n/29. 在對n個元素進行冒泡排序的過程中，最好情況下的時間復雜度為（ ）。 A. O(1) B. O(log2n) C. O(n2) D. O(n) 10. 在對n個元素進行快速排序的過程中，第一次劃分最多需要移動（ ）次元素，包括開始把支點元素

22、移動到臨時變量的一次在內(nèi)。 A. n/2 B. n-1 C. n D. n+1 二.填空題（將正確的答案填在相應的空中）1.( )法構(gòu)造的哈希函數(shù)肯定不會發(fā)生沖突。2. 線性有序表（a1，a2，a3，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索( )次。設(shè)有100個結(jié)點，用二分法查找時，最大比較次數(shù)是( )。3.對n個關(guān)鍵字進行冒泡排序，時間復雜度為（ ）。4折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素( )比較大小。5. 在各種查找方法中，平均查找長度與結(jié)

23、點個數(shù)n無關(guān)的查找方法是( )。6.若待排序的序列中存在多個記錄具有相同的鍵值，經(jīng)過排序，這些記錄的相對次序仍然保持不變，則稱這種排序方法是（ ）的，否則稱為（ ）的。7.按照排序過程涉及的存儲設(shè)備的不同，排序可分為（ ）排序和（ ）排序。8.直接插入排序用監(jiān)視哨的作用是（ ）。9.對n個記錄的表r1.n進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)為（ ）。10.在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用（ ）較好。三.簡答題1對于給定的一組鍵值：83，40，63，13，84，35，96，57，39，79，61，15，分別畫出應用直接插入排序、直接選擇排序、快速排序、歸并排序?qū)ι鲜鲂?/p>

24、列進行排序中各趟的結(jié)果。部分參考答案一、單選題2 C 2. A 3. C 4. D 5. C 6. D 7.C 8.B 9.D 10.B二、填空題4. 直接定址法 2. 9 ，73. O(n2) 4. 28, 12 ,20 5. 哈希表 6. 穩(wěn)定的，非穩(wěn)定的 7. 內(nèi)部排序，外部排序 8. 防止數(shù)組越界 9. n(n-1)/2 10. 插入排序4、 簡答題直接插入排序序號123456789101112 關(guān)鍵字83 40 63 13 84 35 96 57 39 79 61 15i = 2 40 83 63 13 84 35 96 57 39 79 61 15 i = 3 40 63 83 1

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