基本概念和術語
資料：資料是資訊的載體，計算機程式加工的原料
資料元素：資料的基本單位，若干資料項組成，資料項是資料元素的不可分割的最小單位
資料物件：具有相同性質的資料元素的集合，資料的子集
資料型別
原子型別：其值不可再分的資料型別
結構型別：可以再分解為若干成分的資料型別
抽象資料型別：抽象資料組織及與之相關的操作
資料結構：相互之間存在一種或多種特定關系的資料元素的集合
資料結構三要素
【1】資料的邏輯結構：資料之間的邏輯關系，分為線性結構和非線性結構
【2】資料的存盤結構
| 順序存盤 |
邏輯上相鄰的元素存盤在物理位置上也相鄰的存盤單元中 |
|
優點：實作隨機存取，每個元素占用最少的存盤空間 |
|
|
缺點：只能使用相鄰的一整塊存盤單元，可能產生較多的外部碎片 |
|
| 鏈式存盤 |
借助指示元素存盤地址的指標來表示元素之間的邏輯關系 |
|
優點：不會出現碎片現象，充分利用所有存盤單元 |
|
|
缺點：占用額外的存盤空間，且只能實作順序存盤 |
|
| 索引存盤 |
存盤資訊的同時，建立附加的索引表，索引表中的每項稱為索引項 |
|
優點：檢索速度快 |
|
|
缺點：索引表占用了額外的存盤空間，增加洗掉資料要修改索引表，花費較多的時間 |
|
| 散列存盤 |
根據元素的關鍵字直接計算元素存盤地址 |
|
優點：檢索、增加洗掉節點操作快 |
|
|
缺點：散列函式要求較高，容易出現存盤單元沖突 |
【3】資料的運算：施加在資料上的運算包括運算的定義和實作
試題精選
單項選擇題
1.可以用( )定義一個完整的資料結構，
A.資料元素
B.資料物件
C.資料關系
D.抽象資料型別
【解答】【D】
抽象資料型別【ADT】描述了資料的邏輯結構和抽象運算
通常用【資料物件，資料關系，基本操作集】這樣的三元組表示
從而構成一個完整地資料結構定義
2. 以下資料結構中，( )是非線性資料結構，
A.樹
B.字串
C.佇列
D.堆疊
【解答】【A】
樹和圖是典型的非線性結構
3.以下屬于邏輯結構的是( )，
A.順序表
B.哈希表
C.有序表
D.單鏈表
【解答】【C】
邏輯結構：資料之間的邏輯關系，分為線性結構和非線性結構
順序表、哈希表和單鏈表是三種不同的資料結構，既描述邏輯結構，又描述存盤結構和資料運算
有序表是指關鍵字有序的線性表，僅描述元素之間的邏輯關系，它既可以鏈式存盤，又可以順序存盤，故屬于邏輯結構
4.以下與資料的存盤結構無關的術語是( ).
A.回圈佇列
B.鏈表
C.哈希表
D.堆疊
5.以下關于資料結構的說法中，正確的是( )，
A.資料的邏輯結構獨立于其存盤結構
B.資料的存盤結構獨立于其邏輯結構
C.資料的邏輯結構唯一決定 其存盤結構
D.資料結構僅由其邏輯結構和存盤結構決定
6.在存盤資料時，通常不僅要存盤各資料元素的值，而且要存盤( ).
A.資料的操作方法
B.資料元素的型別
C.資料元素之間的關系
D. 資料的存取方法
7.鏈式存盤設計時，結點內的存盤單元地址( )，
A.一定連續.
B.一定不連續
C.不一定連續
D.部分連續，部分不連續
綜合應用題
1.對于兩種不同的資料結構，邏輯結構或物理結構一定不相同嗎?
2.試舉一例，說明對相同的邏輯結構，同一種運算在不同的存盤方式下實作時，其運算效率不同，
在黑夜里夢想著光，心中覆寫悲傷，在悲傷里忍受孤獨，空守一絲溫暖， 我的淚水是無底深海，對你的愛已無言，相信無盡的力量，那是真愛永在， 我的信仰是無底深海，澎湃著心中火焰，燃燒無盡的力量，那是忠誠永在轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/449780.html
標籤：其他
上一篇：nmap使用指南
下一篇：區域敏感哈希-向量相似搜索