【正文】 3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 7 0 0 0 2 0 0 0 0 6 0 0 0 具有6行7列的一個稀疏矩陣(1) 寫出它的三元組線性表； (2) 給出它的順序存儲表示；
(3) 給出它的轉置矩陣的三元組線性表和順序存儲表示； 2. 畫出下列每個廣義表的帶表頭附加結點的鏈接存儲結構圖并分別計算出它們的長度和深度。 10．在廣義表的存儲結構中，單元素結點與表元素結點有一個域對應不同，各自分別為________域和________域。 8．一個廣義表的深度等于________嵌套的最大層數(shù)。 6．在稀疏矩陣的十字鏈接存儲中，每個結點的down指針域指向________相同的下一個結點，right指針域指向________相同的下一個結點。 4. 在稀疏矩陣的順序存儲中，利用一個數(shù)組來存儲非零元素，該數(shù)組的長度應________對應三元組線性表的長度。 2. 在稀疏矩陣所對應的三元組線性表中，每個三元組元素按________為主序、________為輔序的次序排列。 A、 行號 B、 列號 C、 元素值 D、 地址 2. 設一個廣義表中結點的個數(shù)為n，則求廣義表深度算法的時間復雜度為_______。(4) 統(tǒng)計出單鏈表中結點的值等于給定值x的結點數(shù)。 (2) 在有序單鏈表中插入一個元素x的結點。 4．對于結點類型為LNode的單鏈表，編寫出下列每個算法。 (3) 向線性表中第i個元素位置插入一個元素。(1) 從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個元素填補，若線性表為空則顯示出錯信息并退出運行。 i++ ) InsertFront(HL,a[i])。for ( int i=0。 InsertRear(HL,50)。 HL){ InitList(HL)。2．寫出下面函數(shù)被調用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數(shù)據(jù)元素序列。 Insert(La,a[5]/2)。 Delete(La, a[5])。 i6。 (3) ClearList(La)。 i++) Insert(La,a[i])。 for(i=0。 TraverseList(La)。 i6。 int a[]={48,26,57,34,62,79}。 三、應用題 1．在下面的每個程序段中，假定線性表La的類型為List，元素類型ElemType為int，并假定每個程序段是連續(xù)執(zhí)行的，試寫出每個程序段執(zhí)行后所得到的線性表La。 9．在循環(huán)雙向鏈表中表頭結點的左指針域指向 結點，最后一個結點的右指針域指向 結點。 7．在循環(huán)單鏈表中，最后一個結點的指針指向 結點。5．在線性表的順序存儲中，若一個元素的下標為i，則它的前驅元素的下標為 ，后繼元素的下標為 。 3．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間復雜度為 。 二、填空題1．在線性表的單鏈接存儲結構中，每個結點包含有兩個域，一個叫 域，另一個叫 域。 D、qnext = qnextnext。 C、p = qnext 。 B、p = qnext 。 A、p = qnext 。 qnext = p。 pnext = q。 q = p。 pnext = q。 5．在一個單鏈表HL中，若要在指針q所指的結點的后面插入一個由指針p所指的結點，則執(zhí)行 。 D、pnext = HLnext。 C、pnext = HL。 B、pnext = HL。 A、HL = p。 A、ni B、ni+1 C、ni1 D、i 3．在一個長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 。第二章 線性表 一、單選題 1．在一個長度為n的順序存儲線性表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移 個元素。 s=s+p。j=i。 while(++i=n) { int p=1。 15. 在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為________，p*=j語句的執(zhí)行次數(shù)為________，該程序段的時間復雜度為________。 13. 若對象ra和rb中至少有一個是屬于用戶定義的類型，則執(zhí)行ra==rb時，需要調用__________重載函數(shù)，該函數(shù)的第一個參數(shù)應與__________的類型相同，第二個參數(shù)應與__________的類型相同。 11. 函數(shù)重載要求____________、____________或____________有所不同。 9. 在包含有________________頭文件的程序文件中，使用________________能夠產(chǎn)生出0～20之間的一個隨機整數(shù)。 7. 在函數(shù)中對引用形參的修改就是對相應__________的修改，對__________形參的修改只局限在該函數(shù)的內(nèi)部，不會反映到對應的實參上。 5. 當一個形參類型的長度較大時，應最好說明為_________，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。 3. 在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間分別存在著________、________和________的聯(lián)系。 } A、 O(1) B、 O(n) C、 O(n2) D、 O(n!) 二、填空題 1. 數(shù)據(jù)的邏輯結構被分為__________、_________、__________和__________四種。 int f( unsigned int n ) { if ( n==0 || n==1 ) return 1。 j++) S。 i++) for(int j=1。 for(int i=1。 j++) a[i][j]=i*j。 i++) for(int j=0。 for(int i=0。a+i 2. 對于兩個函數(shù)，若函數(shù)名相同，但只是____________不同則不是重載函數(shù)。數(shù)據(jù)結構期末復習練習題( 適用范圍：廣西電大開放?？朴嬎銠C類專業(yè) )廣西電大理工教學部計算中心第一章 緒 論 一、單選題 1. 一個數(shù)組元素a[i]與________的表示等價。 A、 *(a+i) B、 a+i C、 *a+i D、 amp。 A、 參數(shù)類型 B、 參數(shù)個數(shù) C、 函數(shù)類型 3. 若需要利用形參直接訪問實參，則應把形參變量說明為________參數(shù) A、 指針 B、 引用 C、 值 4. 下面程序段的時間復雜度為____________。 im。 jn。 A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n) 5. 執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為____________。 i=n。 j=i。 A、 n2 B、 n2/2 C、 n(n+1) D、 n(n+1)/2 6. 下面算法的時間復雜度為____________。 else return n*f(n1)。 2. 數(shù)據(jù)的存儲結構被分為__________、_________、__________和__________四種。 4. 一種抽象數(shù)據(jù)類型包括__________和__________兩個部分。 6. 當需要用一個形參訪問對應的實參時，則該形參應說明為__________。 8. 當需要進行標準I/O操作時，則應在程序文件中包含________________頭文件，當需要進行文件I/O操作時，則應在程序文件中包含________________頭文件。 10. 一個數(shù)組a所占有的存儲空間的大小即數(shù)組長度為____________，下標為i的元素a[i]的存儲地址為__________，或者為______________________________。 12. 對于雙目操作符，其重載函數(shù)帶有__________個參數(shù)，其中至少有一個為____________的類型。 14. 從一維數(shù)組a[n]中順序查找出一個最大值元素的時間復雜度為________，輸出一個二維數(shù)組b[m][n]中所有元素值的時間復雜度為________。 int i=0,s=0。 for(int j=1。j++) p*=j。 } 16. 一個算法的時間復雜度為(3n2+2nlog2n+4n7)/(5n)，其數(shù)量級表示為________。 A、ni B、ni+1 C、ni1 D、i 2．在一個長度為n的順序存儲線性表中，刪除第i個元素(1≤i≤n+1)時，需要從前向后依次前移 個元素。 A、n B、n/2 C、(n+1)/2 D、(n1)/2 4．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執(zhí)行 。 pnext = HL。 HL = p。 p = HL。 HLnext = p。 A、qnext = pnext 。 B、pnext = qnext。 C、qnext = pnext。 D、pnext = qnext 。 6．在一個單鏈表HL中，若要刪除由指針q所指向結點的后繼結點，則執(zhí)行 。 pnext = qnext。 qnext = p。 qnext = pnext。 qnext = q。 2．在下面數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[0].next，則該線性表為 。 4．對于一個長度為n的單鏈接存儲的線性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間復雜度為 。 6．在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為 ，若假定p為一個數(shù)組a中的下標，則其后繼結點的下標為 。 8．在雙向鏈表中每個結點包含有兩個指針域，一個指向其 結點，另一個指向其 結點。 10．在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為 和 。 (1) InitList(La)。 for(i=0。 i++) InsertFront(La,a[i])。 (2) InitList(La)。 i6。 TraverseList(La)。 for(i=0。 i++) InsertRear(La,a[i])。 Sort(La)。 TraverseList(La)。void AA(LNode * amp。 InsertRear(HL,30)。int a[5] = {15,8,9,26,12}。 i5。 } 3．對于List類型的線性表，編寫出下列每個算法。 (2) 從線性表中刪除第i個元素并由函數(shù)返回。 (4) 從線性表中刪除具有給定值x的所有元素。(1) 刪除單鏈表中的第i個結點。 (3) 從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯信息并停止運行。第三章 稀疏矩陣和廣義表 一、單選題 1. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結點都具有相同的_______