熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第五章 答案[23]

2013-11-15 15:11:49  來源: 數據結構 

   設用munu和tu表示稀疏矩陣行數列數和非零元素個數則轉置矩陣的行數列數和非零元素的個數分別是numu和tu轉置可按轉置矩陣的三元組表中的元素順序進行即按稀疏矩陣的列序從第列到第nu列每列中按行值遞增順序找出非零元素逐個放入轉置矩陣的三元組表中轉時行列值互換元素值復制按這種方法列到第個非零元素一定是轉置後矩陣的三元組表中的第個元素列非零元素在第列非零元素的前面這種方法時間復雜度是O(n*P)其中p是非零元素個數當p和m*n同量級時時間復雜度為O(n)

  另一種轉置方法稱作快速轉置使時間復雜度降為O(m*n)它是按稀疏矩陣三元組表中元素的順序進行按順序取出一個元素放到轉置矩陣三元組表的相應位置這就要求出每列非零元素個數和每列第一個非零元素在轉置矩陣三元組表中的位置設置了兩個附加向量

   廣義表中的元素可以是原子也可以是子表即廣義表是原子或子表的有限序列滿足線性結構的特性在非空線性結構中只有一個稱為第一個的元素只有一個成為最後一個的元素第一元素有後繼而沒有前驅最後一個元素有前驅而沒有後繼其余每個元素有唯一前驅和唯一後繼從這個意義上說廣義表屬於線性結構

   數組是具有相同性質的數據元素的集合同時每個元素又有唯一下標限定可以說數組是值和下標偶對的有限集合n維數組中的每個元素處於n個關系之中每個關系都是線性的且n維數組可以看作其元素是n維數組的一個線性表而廣義表與線性表的關系見上面題的解釋

  .線性表中的元素可以是各種各樣的但必須具有相同性質屬於同一數據對象廣義表中的元素可以是原子也可以是子表其它請參見

  )(cd)  ()(b)  ()b   ()(f)   ()()

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23032.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.