一選擇題
BCCBBDCCDDAC
DDACAC
二判斷題
× ××× √ × × √××× √
×
三填空題
數據元素 數據元素間關系 集合 線性結構 樹形結構 圖狀結構或網狀結構
數據的組織形式即數據元素之間邏輯關系的總體而邏輯關系是指數據元素之間的關聯方式或稱鄰接關系
表示(又稱映像) ()邏輯特性 ()在計算機內部如何表示和實現 ()數學特性
算法的時間復雜度和空間復雜度()邏輯結構()物理結構()操作(運算)()算法
()有窮性 ()確定性()可行性
()n+ ()n ()n(n+)/ ()n(n+)/
+(+++(++)+…+(++…+n)=n(n+)(n+)/ O(n)
logn nlogn logn (n+)(n)/ O(n)
① () () ()f(mn) ()n ② n(n)/
四應用題
數據結構是一門研究在非數值計算的程序設計問題中計算機的操作對象及對象間的關系和施加於對象的操作等的學科
四種表示方法
()順序存儲方式數據元素順序存放每個存儲結點只含一個元素存儲位置反映數據元素間的邏輯關系存儲密度大但有些操作(如插入刪除)效率較差
()鏈式存儲方式每個存儲結點除包含數據元素信息外還包含一組(至少一個)指針指針反映數據元素間的邏輯關系這種方式不要求存儲空間連續便於動態操作(如插入刪除等)但存儲空間開銷大(用於指針)另外不能折半查找等
()索引存儲方式除數據元素存儲在一地址連續的內存空間外尚需建立一個索引表索引表中索引指示存儲結點的存儲位置(下標)或存儲區間端點(下標)兼有靜態和動態特性
()散列存儲方式通過散列函數和解決沖突的方法將關鍵字散列在連續的有限的地址空間內並將散列函數的值解釋成關鍵字所在元素的存儲地址這種存儲方式稱為散列存儲其特點是存取速度快只能按關鍵字隨機存取不能順序存取也不能折半存取
數據類型是程序設計語言中的一個概念它是一個值的集合和操作的集合如C語言中的整型實型字符型等整型值的范圍(對具體機器都應有整數范圍)其操作有加減乘除求余等實際上數據類型是廠家提供給用戶的已實現了的數據結構抽象數據類型(ADT)指一個數學模型及定義在該模型上的一組操作抽象的意義在於數據類型的數學抽象特性抽象數據類型的定義僅取決於它的邏輯特性而與其在計算機內部如何表示和實現無關無論其內部結構如何變化只要它的數學特性不變就不影響它的外部使用抽象數據類型和數據類型實質上是一個概念此外抽象數據類型的范圍更廣它已不再局限於機器已定義和實現的數據類型還包括用戶在設計軟件系統時自行定義的數據類型使用抽象數據類型定義的軟件模塊含定義表示和實現三部分封裝在一起對用戶透明(提供接口)而不必了解實現細節抽象數據類型的出現使程序設計不再是藝術而是向科學邁進了一步
()數據的邏輯結構反映數據元素之間的邏輯關系(即數據元素之間的關聯方式或鄰接關系)數據的存儲結構是數據結構在計算機中的表示包括數據元素的表示及其關系的表示數據的運算是對數據定義的一組操作運算是定義在邏輯結構上的和存儲結構無關而運算的實現則是依賴於存儲結構
[] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22751.html
