數(shù)據(jù)結構復習題

1、一判斷題（下列各題，正確的請在前面的括號內(nèi)打；錯誤的打）第1章（）（1）數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。（）（2）一個數(shù)據(jù)結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。（）（3）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）（4）數(shù)據(jù)項是數(shù)據(jù)的基本單位。（）（5）數(shù)據(jù)的邏輯結構和數(shù)據(jù)的存儲結構是相同的。（）（6）數(shù)據(jù)的邏輯結構是各數(shù)據(jù)元素之間的邏輯關系，是用戶按使用需要而建立的。（）（7）數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。（）（8）從邏輯關系上講，數(shù)據(jù)結構主要分為線性結構和非線性結構兩類。（）（9）數(shù)據(jù)的存儲結構是數(shù)據(jù)的邏輯結構的存儲映像。（）（10）算法是對解題

2、方法和步驟的描述。第2章（）（1）鏈表的物理存儲結構具有同鏈表一樣的順序。（）（2）鏈表的每個結點都恰好包含一個指針域。（）（3）線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此屬于同一數(shù)據(jù)對象。（）（4）鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。（）（5）順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。 （）（6）數(shù)組元素的存儲位置是下標的線性函數(shù)。（）（7）在單鏈表中，元素的存儲位置用指針聯(lián)系，所以可以從頭結點開始查找任何一個元素。（）（8）順序存儲線性表的插入和刪除操作不需要付出很大的代價，因為平均每次移動

3、僅一半的元素。（）（9）順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。（）（10）在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結構。第3章（）（1）大多數(shù)排序算法都有比較關鍵字大小和改變指向記錄的指針或移動記錄本身兩種基本操作。（）（2）快速排序在任何情況下都比其它排序方法速度快。（）（3）快速排序算法在每一趟排序中都能找到一個元素放在其最終位置上。（）（4）如果某種排序算法不穩(wěn)定，則該排序方法就沒有實際應用價值。（）（5）對n個記錄的進行快速排序，所需要的平均時間是O（nlog2n）。（）（6）冒泡排序是不穩(wěn)定的排序。（）（7）冒泡排序的時間復雜度是O

4、（n2）。（）（8）堆排序所需的時間與待排序的記錄個數(shù)無關。（）（9）對快速排序來說，初始序列為正序或反序都是最壞情況。（）（10）對于n個記錄的集合進行歸并排序，所需的平均時間為O (nlog2n)。第4章（）（1）棧是運算受限制的線性表。（）（2）在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢出。（）（3）棧一定是順序存儲的線性結構。（）（4）空棧就是所有元素都為0的棧。（）（5）一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。（）（6）一個棧的輸入序列為：A，B，C，D，通過入出棧操作可以輸出序列：A，B，C，D。（）（7）在C或C+語言中設順序棧的長度為MAXLEN

5、，則top=MAXLEN時表示隊滿。（）（8）鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。（）（9）在棧中插入或刪除一個元素應遵守的“后進先出”的原則。（）（10）進位制的換算算法是棧的應用。（）（11）隊列是限制在兩端進行操作的線性表。（）（12）判斷順序隊列為空的標準是頭指針和尾指針均指向同一個結點。（）（13）在鏈隊列做出隊操作時，會改變front指針的值。（）（14）在循環(huán)隊列中，若尾指針rear大于頭指針front，其元素個數(shù)為rear- front。（）（15）隊列是一種“先進先出”的線性表。（）（16）在循環(huán)鏈隊列中無上溢出現(xiàn)象。（）（17）棧和隊列都是順序存儲的線性結

6、構。（）（18）棧和隊列都是屬于線性結構。（）（19）順序隊和循環(huán)隊的隊滿和隊空的判斷條件是一樣的。（）（20）在隊列中插入或刪除一個元素應遵守的”先進先出”的原則。第5章（）（1）串的長度是指串中不同字符的個數(shù)。（）（2）串是n個字母的有限序列。（）（3）空串不等于空格串。（）（4）如果兩個串含有相同的字符，則說明它們相等。（）（5）如果一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。（）（6）串的堆分配存儲是一種動態(tài)存儲結構。（）（7）“DT”是“DATA”的子串。（）（8）空串與空格串是相同的。（）（9）串中任意個字符組成的子序列稱為該串的子串。（）（10）子串的定位運算稱

7、為模式匹配。（）（11）n維的多維數(shù)組可以視為n-1維數(shù)組元素組成的線性結構。（）（12）稀疏矩陣中非零元素的個數(shù)遠小于矩陣元素的總數(shù)。（）（13）若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算。（）（14）在稀疏矩陣的三元組表表示法中，每個三元組表示矩陣中數(shù)據(jù)元素的行號、列號和值。（）（15）上三角矩陣主對角線以上（不包括主對角線中的元素），均為常數(shù)C。（）（16）對稱矩陣、三角矩陣、稀疏矩陣都可以進行壓縮存儲。（）（17）任何矩陣都可以進行壓縮存儲。（）（18）在稀疏矩陣的三元組表表示法中，每個三元組表示矩陣中非零元素的行號、列號和值。（）

8、（19）數(shù)組元素可以由若干個數(shù)據(jù)項組成。（）(20）稀疏矩陣壓縮存儲就是為矩陣中非零元素分配一個存儲空間。第6章（）（1）樹結構中每個結點最多只有一個直接前驅(qū)。（）（2）完全二叉樹一定是滿二查樹。（）（3）由樹轉(zhuǎn)換成二叉樹，其根結點的右子樹一定為空。（）（4）在前序遍歷二叉樹的序列中，任何結點的子樹的所有結點都是直接跟在該結點之后。（）（5）用一維數(shù)組來存儲二叉樹時，總是以前序遍歷存儲結點。（）（6）已知二叉樹的前序遍歷和后序遍歷并不能唯一確定這棵二叉樹，因為不知道根結點是哪一個。（）（7）二叉樹的前序遍歷中，任意一個結點均處于其子女結點的前面。（）（8）由二叉樹的前序遍歷序列和中序遍歷序列，

9、可以推導出后序遍歷的序列。（）（9）不使用遞歸，也可以實現(xiàn)二叉樹的前序、中序和后序遍歷。（）（10）在完全二叉樹中，若一個結點沒有左孩子，則它必然是葉子結點。第7章（）（1）圖可以沒有邊，但不能沒有頂點。（）（2）在無向圖中，（V1，V2）與（V2，V1）是兩條不同的邊。（）（3）鄰接表只能用于有向圖的存儲。（）（4）用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中頂點個數(shù)有關，而與圖的邊數(shù)無關。（）（5）一個圖的鄰接矩陣表示是唯一的。（）（6）有向圖不能進行廣度優(yōu)先遍歷。（）（7）一個圖的最小生成樹是該圖所有生成樹中權最小的生成樹。（）（8）存儲無向圖的鄰接矩

10、陣是對稱的，因此只要存儲鄰接矩陣的上三角（或下三角）部分就可以了。（）（9）有向圖的鄰接矩陣一定是對稱的。（）（10）一個圖的深度優(yōu)先遍歷的序列是唯一的。第8章（）（1）二分查找法要求待查表的關鍵字值必須有序。（）（2）哈希法是一種將關鍵字轉(zhuǎn)換為存儲地址的存儲方法。（）（3）在二叉排序樹中，根結點的值都小于孩子結點的值。（）（4）對有序表而言采用二分查找總比采用順序查找法速度快。（）（5）二叉排序樹是一種特殊的線性表。（）（6）散列存儲法的基本思想是由關鍵字的值決定數(shù)據(jù)的存儲地址。（）（7）哈希法的查找效率主要取決于哈希表構造時選取的哈希函數(shù)和處理沖突的方法。（）（8）一般說來用哈希函數(shù)得到的

11、地址，沖突不可能避免，只能盡可能減少。（）（9）選擇好的哈希函數(shù)就可以避免沖突的發(fā)生。（）（10）在二叉排序樹上刪除一個結點時，不必移動其它結點，只要將該結點的父結點的相應的指針域置空即可。二填空題第1章1數(shù)據(jù)結構是一門研究非數(shù)值計算程序設計中計算機的操作對象以及它們之間的 關系 和運算的學科。2數(shù)據(jù)的存儲結構形式包括：順序存儲、鏈式存儲、 散列存儲 、索引存儲 。3數(shù)據(jù)結構按邏輯結構可分為兩大類，它們分別是：線性結構和 非線性 結構。4一個算法的空間復雜度是指該算法所耗費的 存儲空間 ，它是該算法求解問題規(guī)模n的函數(shù)。5數(shù)據(jù)結構有邏輯結構和 存儲結構 兩種結構。6數(shù)據(jù)的存儲結構形式包括：順序

12、存儲、鏈式存儲、散列存儲、 索引存儲 。7一個算法的效率可分為 時間 效率和空間效率。8數(shù)據(jù)元素是數(shù)據(jù)的 基本單位 。9數(shù)據(jù)結構主要研究數(shù)據(jù)的 邏輯結構 、存儲結構和算法。11數(shù)據(jù)的 邏輯結構 是獨立于計算機的。12數(shù)據(jù)結構被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的 關系 的有限集合。13樹形結構結構中的元素之間存在 一對多 的關系。14若一個算法中的語句頻度之和為T（n）=125n+3nlog2n，則算法的時間復雜度為 O（nlog2n） 。15數(shù)據(jù)結構主要研究數(shù)據(jù)的邏輯結構、 存儲結構 和算法。第2章1順序表中邏輯上相鄰的元素在物理位置上 必須 相連。2在單鏈表中要在已知結點*

13、P之前插入一個新結點，需找到*P的直接前趨結點的地址，其查找的時間復雜度為 O (n) 。3線性表是n個結點的 有限 集合。4鏈表相對于順序表的優(yōu)點有 插入、刪除 方便；缺點是存儲密度小。5鏈表相對于順序表的優(yōu)點有插入、刪除方便；缺點是存儲密度 小 。6順序表相對于鏈表的優(yōu)點是： 節(jié)省存儲 和隨機存取。7對于一個具有n個結點的單鏈表，在已知p所指結點后插入一個新結點的時間復雜度是 O（1） 。8在鏈表中邏輯上相鄰的元素的物理位置 不必 相連。9線性表中第一個結點沒有直接前趨，稱為 開始 結點。10在順序表中訪問任意一個結點的時間復雜度均為 O (1) 。11在n個結點的單鏈表中要刪除已知結點*

14、P，其時間復雜度為 O (1) 。12在單鏈表中需知道 頭指針 才能遍歷整個鏈表。13在一個單鏈表中，在指針p所指向的結點之后插入指針s所指向的結點時，應執(zhí)行s-next=p-next和p-next=s 操作。14在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n- i +1 個元素。 15在雙向鏈表中，每個結點都有兩個指針域，它們一個指向其前趨結點，另一個指向其 后繼 結點。第3章1 根據(jù)被處理的數(shù)據(jù)在計算機中使用不同的存儲設備，排序可分為： 內(nèi)排序 和外排序。2 評價排序算法優(yōu)劣的主要標準是 時間復雜性 和算法所需的附加空間。3插入排序、堆排序、歸并排序中，排序是不穩(wěn)定

15、的有： 堆排序 。4在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較 3 次。5對n個關鍵字進行冒泡排序，其可能的最小比較次數(shù)為： n-1 次。6內(nèi)排序是指整個排序過程，全部在計算機的 內(nèi)存 中進行。7大多數(shù)排序算法都有兩個基本的操作： 比較 和移動。8在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序 較好。9在排序前，關鍵字值相等的不同記錄，排序后相對位置變化的排序方法，稱為 不穩(wěn)定 的排序方法。10若原始數(shù)據(jù)接近無序，則選用 快速排序 最好。11對于n個記錄的集合進行歸并排序，所需要的

16、平均時間為： O（log2n） 。12在插入排序、歸并排序、快速排序中，排序是不穩(wěn)定的有： 快速排序 。13對一組記錄（54，35，96，21，12，72，60，44，80）進行直接選擇排序時，第四次選擇和交換后，未排序記錄是 54，72，60，96，80 。14對于n個記錄的集合進行，若對其進行快速排序，在最壞的情況下所需要的時間是 O(n2) 。15在最壞情況下，在第i趟直接插入排序中，要進行 i-1 次關鍵字的比較。第4章1在棧中存取數(shù)據(jù)遵從的原則是： 后進先出 。2在有n個元素的棧中，進棧操作的時間復雜度為 O（1）。3后進先出的線性表稱為 棧 。4在順序棧中，當top=MAXLEN-

17、1時，表示 棧滿 。5. 棧是輸入、輸出受限制的 線性表 。6在有n個元素的棧中，出棧操作的時間復雜度為 O（1）。7在棧結構中，允許插入、刪除的一端稱為 棧頂 。8順序棧S存在數(shù)組S-data0.MAXLEN-1中，出棧操作時要執(zhí)行的語句有：S-top - 。9在順序棧中，當棧頂指針top=-1時，表示 ?？?。10向一個棧頂指針為top的鏈棧插入一個新結點*p時，應執(zhí)行 p-next=top； 和top=p； 操作。11同一棧的各元素的類型 相同 。12棧只能在 棧頂 插入和刪除元素。13已知順序棧S，在對S進行出棧操作之前首先要判斷 棧是否空 。14若進棧的次序是A、B、C、D、E，執(zhí)行

18、三次出棧操作以后，棧頂元素為 B 。15從一個棧刪除元素時，首先取出棧頂元素，然后再移動 棧頂指針 。16在隊列中存取數(shù)據(jù)應遵從的原則是 先進先出 。17設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設頭指針，則入隊操作的時間復雜度為 O（n）。18在隊列中，允許插入的一端稱為 隊尾 。19設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設頭指針，則出隊操作的時間復雜度為 0（1） 。20設循環(huán)隊列的頭指針front指向隊頭元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，則隊空的標志為 front=rear 。21隊列在進行出隊操作時，首先要判斷隊列是否為 空 。22設循環(huán)隊

19、列的頭指針front指向隊頭元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，則隊滿標志為 front=(rear+1)% MAXLEN 。23在一個鏈隊列中，若隊頭指針為front，隊尾指針為rear，則判斷該隊列只有一個結點的條件為： front=rear & front NULL 。24隊列結構的元素個數(shù)是 可變的 。25設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設尾指針，則出隊操作的時間復雜度為 0（1） 。26設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設尾指針，則入隊操作的時間復雜度為 0（1） 。27鏈隊列為空時，LQ-front-next= NULL 。

20、28設循環(huán)隊列的頭指針front指向隊頭元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，當rearfront時，隊列長度是 MAXLEN-front 。29向一個循環(huán)隊列中插入元素時，首先要移動隊尾指針，然后再向指針所指位置 寫入 新的元素。30隊列Q經(jīng)過InitQueue (Q)；InQueue (Q，a)； InQueue (Q，b)；GetHead (Q，x)后，x的值是 a 。第5章1長度為零的字符串稱為 空串 。2在串的運算中，EqualStr(aaa，aabb)的值為 0 。3串的順序存儲結構簡稱為 順序串 。4串的鏈式存儲結構簡稱為 鏈式串 。5求

21、子串函數(shù)SubStr(Today is 30 July,2005,13,4)的結果是： July 。6設S=A:/document/mary.doc，則len(s)= _ 20 。7由零個或多個字符組成的有限序列稱為 字符串 （或串）。8字符串按存儲方式可以分為：順序存儲、鏈接存儲和 堆分配存儲 。9設S=“A:/mydocument/text1.doc”，則strlen(S)= 23 。10在空串和空格串中，長度不為0的是 空格串 。11串順序存儲緊湊格式的優(yōu)點是： 空間利用率高 ,對串的字符處理效率低。12兩個串相等是指兩個串相長度等，且對應位置的 字符都相同 。13串順序存儲緊湊格式的缺

22、點是對串的字符處理 效率低 。14模式匹配成功的起始位置稱為： 有效位移 。15所有模式匹配不成功的起始位置稱為： 無效位移 。16.多維數(shù)組的順序存儲方式有行優(yōu)先順序存儲和 列優(yōu)先順序存儲 兩種。17.同一數(shù)組中各元素的長度 相等 。18.在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過地址計算公式算出，所以多維數(shù)組是一種 隨機 存取結構。19. 在n維數(shù)組中的每一個元素最多可以有 n 個直接前驅(qū)。20.輸出二維數(shù)組Amn中所有元素值的時間復雜度為 O(m*n) 。數(shù)組元素a0.20.3的實際地址上2000，元素長度是4，則Loc1,2=2024 。21.數(shù)組的三元組存儲是對 稀疏矩陣 的壓縮存

23、儲22.稀疏矩陣的三元組有 3 列。23.稀疏矩陣的三元組中第1列存儲的是數(shù)組中非零元素所在的 行數(shù) 。24.n階對稱矩陣，如果只存儲下三角元素，只需要 n（n-1）/2 個存儲單元。25.稀疏矩陣A如下圖所示，其非零元素存于三元組表中，三元組（4，1，5）按行優(yōu)先順序存儲在三元組表的第 6 項。8 0 0 0 0 00 11 0 0 0 00 0 0 6 0 00 3 0 07 0 0 5 0 00 00 0 0 09 0稀疏矩陣AA=26.稀疏疏矩陣的壓縮存儲方法通常有三元組表和 十字鏈表 兩種。27 n階下三角矩陣，因為對角線的上方是同一個常數(shù)，需要 n（n-1）/2+1 個存儲單元。2

24、8稀疏矩陣中有n個非零元素，則三元組有 n 行。29.稀疏矩陣的三元組中第2列存儲的是數(shù)組中非零元素所在的 列數(shù) 。30.稀疏矩陣的三元組中，第3列存儲的是稀疏數(shù)組中的 非零元素 。第6章1在樹中，一個結點所擁有的子樹數(shù)稱為該結點的 度 。2一棵含有n個結點的完全二叉樹，它的高度是 | log2n |+1 。 （下取整）3度為零的結點為 葉子結點（或葉結點） 。4一棵深度為h的完全二叉樹上的結點總數(shù)最少為 2 h-1 個。5樹內(nèi)各結點度的最大值稱為 樹的度 。6一棵深度為h的完全二叉樹上的結點總數(shù)最多為 2 h-1 個。7樹中結點的最大層次稱為樹的 深度（或高度） 。8三個結點可以組成 2 種

25、不同形態(tài)的樹。9由樹轉(zhuǎn)換成二叉樹時，其根結點沒有 右子樹 。10有20個結點的完全二叉樹，編號為10的結點的左兒子結點的編號是 20 。11在樹中，一個結點的直接子結點的個數(shù)稱為該結點的 度 。12由二叉樹的后序和 中序 遍歷序列，可以唯一確定一棵二叉樹。13給定如下圖所示的二叉樹，其前序遍歷序列為： ABEFHCG 。ABFGHDCE14給定如下圖所示的二叉樹，其層次遍歷序列為： ABCEFGH 。ABFGHDCE15將一棵完全二叉樹按層次編號，對于任意一個編號為i的結點，該結點右孩子的編號為： 2*i+1 。第7章1圖有： _鄰接矩陣_ 和鄰接表等存儲結構。2n個頂點e條邊的圖若采用鄰接矩

26、陣存儲，深度優(yōu)先遍歷算法的時間復雜度為： O（n2） 。3圖的遍歷有：深度優(yōu)先搜和 _廣度優(yōu)先搜 _等方法。4n個頂點e條邊的圖若采用鄰接矩陣存儲，則空間復雜度為： _ O（n2）_。5圖有：鄰接矩陣和 鄰接表 等存儲結構。6若圖G中每條邊都 _無 方向，則G為無向圖。7在具有n個頂點的圖的生成樹中，含有 n-1 條邊。8有向圖的邊也稱為 _弧_ 。9圖的鄰接矩陣表示法是表示 _頂點_之間相鄰關系的矩陣。10有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的 _出度_。11圖的深度優(yōu)先遍歷序列 _不是_唯一的。12設有一稀疏圖G，則G采用 _鄰接表_存儲比較節(jié)省空間。13從圖中某一頂點

27、出發(fā)，訪遍圖中其余頂點，且使每一頂點僅被訪問一次，稱這一過程為圖的遍歷（或遍歷） 。14遍歷圖的兩種基本方法是： 深度優(yōu)先遍歷 和廣度優(yōu)先遍歷。15有向圖的鄰接表表示適于求頂點的 出度 。第8章1順序查找法，表中元素可以 任意 存放。2 散列表 查找法的平均查找長度與元素個數(shù)n無關。3快速排序是對 冒泡 排序的一種改進。4在哈希函數(shù)H(key)=key % P中，P一般應取 質(zhì)數(shù) 。5二分查找的存儲結構僅適用于 順序存儲 結構，而且關鍵字有序的。6在分塊查找方法中，首先查找 索引 ，然后再查找相應的塊。7二分查找法，表中元素必須按關鍵字 有序 存放。8在分塊查找方法中，表中元素每塊內(nèi)的元素可以

28、 任意存放 ，塊與塊之間必須有序存放。9順序查找、二分查找、分塊查找都屬于 靜態(tài) 查找。10順序查找法，其平均查找長度為： (n+1)/2 。11理想情況下，在散列表中查找一個元素的時間復雜度為： O（1） 。12散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和 處理沖突 的方法。13二叉排序樹是一種 動態(tài) 查找表。14處理沖突的兩類主要方法是開放定址法和 拉鏈法 （或鏈地址法） 。15設有100個元素，用二分查找時，最少的比較次數(shù)是 1 次。三選擇題第1章1數(shù)據(jù)結構通常是研究數(shù)據(jù)的（ A ）及它們之間的相互聯(lián)系。 A. 存儲結構和邏輯結構 B. 存儲和抽象 C. 聯(lián)系和抽象 D. 聯(lián)系

29、與邏輯2執(zhí)行下列語句的時間復雜度為：（ B ）。s=0;for (i=1;i=n; i+) s=s+i; A. O（1） B. O（n） C. O（n2） D. O（n3）3數(shù)據(jù)結構中，在邏輯上可以把數(shù)據(jù)結構分成：（ C ）。 A. 動態(tài)結構和靜態(tài)結構 B. 緊湊結構和非緊湊結構 C. 線性結構和非線性結構 D. 內(nèi)部結構和外部結構4某程序的時間復雜度為（3n+log2n+n2+15）其數(shù)量級表示為（ B ） A. O（n） B. O（n2） C. O（log2n） D. O（nlog2n）5非線性結構的數(shù)據(jù)元素之間存在（ B ）。 A. 一對多關系 B. 多對多關系 C. 多對一關系 D.

30、一對一關系6下列時間復雜度中最壞的是（ D ） A. O（1） B. O（ n） C. O（log2n） D. O（n2）7以下任何兩個結點之間都沒有邏輯關系的是（ D ） A. 圖型結構 B. 線性結構 C. 樹型結構 D. 集合8鏈接存儲的存儲結構所占存儲空間（ A ）。 A 分兩部分，一部分存放結點的值，另一部分存放表示結點間關系的指針 B 只有一部分，存放結點值 C 只有一部分，存儲表示結點間關系的指針 D 分兩部分，一部分存放結點值，另一部分存放結點所占單元素9一個存儲結點存放一個（ B ） A. 數(shù)據(jù)項 B. 數(shù)據(jù)元素 C. 數(shù)據(jù)結構 D. 數(shù)據(jù)類型10下列時間復雜度中最好的是（

31、A ） A. O（1） B. O（ n） C. O（log2n） D. O（n2）11每一個存儲結點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（ B ）存儲方式 A. 順序 B. 鏈式C. 索引 D. 散列12下列算法的實際復雜度是（ D ） for (i=0;in;i+) for (j=0;in;j+) cij=i+j; A. O（1） B. O（ n） C. O（log2n） D. O（n2）13數(shù)據(jù)元素是數(shù)據(jù)的基本單位，其內(nèi)（ B ）數(shù)據(jù)項。 A. 只能包括一個 B. 可以包括多個 C. 不包括 D. 可以包括也可以不包括14. 數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（ C

32、）結構；A. 存儲 B. 物理 C. 邏輯 D. 物理和存儲15數(shù)據(jù)的邏輯結構是（ A ）關系的整體A. 數(shù)據(jù)元素之間邏輯 B. 數(shù)據(jù)項之間邏輯C. 數(shù)據(jù)類型之間 D. 存儲結構之間第2章1用單鏈表方式存儲的線性表，存儲每個結點需要兩個域，一個數(shù)據(jù)域，另一個是（ B ）。A 當前結點所在地址域 B 指針域 C 空指針域D 空閑域2在具有n個結點的單鏈表中，實現(xiàn)（ A ）的操作，其算法的時間復雜度都是O（n）。A遍歷鏈表和求鏈表的第i個結點B在地址為P的結點之后插入一個結點C刪除開始結點D刪除地址為P的結點的后繼結點3設a，b，c為三個結點，p，10，20，代表地址，則如下存儲結構稱為（ B ）

33、。a 10 c b 20 PA 循環(huán)鏈表 B 單鏈表 C雙向循環(huán)鏈表 D 雙向鏈表4已知一個順序存儲的線性表，設每個結點需占m個存儲單元，若第一個結點的地址B，則第i個結點的地址為（ A ）。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m5單鏈表的存儲密度（ C ）。 A 大于1 B 等于1 C小于1 D 不能確定6在n個結點的順序表中，算法的時間復雜度是O (1)的操作是（ A ）。A 訪問第i個結點(1=i-n)和求第i個結點的直接前驅(qū)(2=i=n)B 在第i個結點之后插入一個新結點(1=i=n)C 刪除第i個結點(1=inext= = P CP-next=

34、= NULL DP-next= = L9一維數(shù)組和線性表的區(qū)別是（ A ）。A 前者長度固定，后者長度可變 B 后者長度固定，前者長度可變C 兩者長度都固定 D 兩者長度都可變10指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（ D ）。AP= = L BP-prori= = L CP= = NULL DP-next= =L11一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ B ）A110 B108 C100 D12012兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是（ ）。AP-next= =Q-next BP-next= =

35、QCQ-next= = P DP= = Q13向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ B ）個元素。A8 B63.5 C63 D714用鏈表存儲的線性表，其優(yōu)點是（ C ）。A 便于隨機存取 B 花費的存儲空間比順序表少C 便于插入和刪除 D 數(shù)據(jù)元素的物理順序與邏輯順序相同15單鏈表的示意圖如下： LABCD P Q R 指向鏈表Q結點的后繼的指針是（ D ）AL BP CQ DR第3章1每次從無序表中取出一個元素，把它插入到有序表中的適當位置，這種排序方法叫（ C ）。 A選擇 B交換 C插入 D歸并2快速排序方法在（ C ）情況下最不利于發(fā)揮其長處。

36、 A要排序的數(shù)據(jù)量太大 B要排序的數(shù)據(jù)中含有多個相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù)3排序方法中，從無序序列中選擇關鍵字最小的記錄，將其與無序區(qū)（初始為空）的第一個記錄交換的排序方法，稱為: ( D )。A希爾排序 B歸并排序 C插入排序 D. 選擇排序4在待排序的元素序列基本有序的前提下，效率最高的排序方法是：（ A ）。A直接插入 B冒泡排序 C希爾排序 D選擇排序5每次把待排序方的區(qū)間劃分為左、右兩個區(qū)間，其中左區(qū)間中元素的值不大于基準元素的值，右區(qū)間中元素的值不小于基準元素的值，此種排序方法叫做（ C ）。A冒泡排序 B堆排序 C快速排序 D. 歸并排序6

37、排序是根據(jù)（ A ）的大小重新安排各元素的順序。 A關鍵字 B數(shù)組 C元素件 D結點7堆的形狀是一棵（ D ）。A二叉排序樹 B滿二叉樹 C不是二叉樹 D. 完全二叉樹8穩(wěn)定的排序方法是指在排序前后，關鍵字值相等的不同記錄間的前后相對位置（ B ）。 A保持相反 B保持不變 C不定 D無關9下述幾種排序方法中，要求內(nèi)存量最大的是：（ D ）。 A插入排序 B選擇排序 C快速排序 D. 歸并排序10直接插入排序的方法是（ B ）的排序方法。 A不穩(wěn)定 B穩(wěn)定 C外部 D選擇11直接插入排序的方法要求被排序的數(shù)據(jù)（ B ）存儲。 A必須鏈表 B必須順序 C順序或鏈表 D可以任意12設有1000個無

38、序元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用（ B ）排序法。A冒泡排序 B堆排序 C快速排序 D. 歸并排序13用快速排序法對n個元素進行排序時，最壞情況下的執(zhí)行時間為（ A ）AO（n2） BO（log2n） CO（nlog2n） D. O（n）14一個數(shù)據(jù)序列的關鍵字為：（46，79，56，38，40，84），采用快速排序，并以第一個數(shù)為基準得到第一次劃分的結果為：（ C ）A （38，40，46，56，79，84） B（40，38，46，79，56，84） C（40，38，46，56，79，84） D（40，38，46，56，79，84）15用某種排序方法對關鍵字序列

39、（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ D ）。 A選擇排序 B希爾排序 C歸并排序 D.快速排序第4章1順序棧判空的條件是（ C ） Atop=0 Btop=1 Ctop=-1 Dtop=m2設有編號為1，2，3，4的四輛列車，順序進入一個棧式結構的站臺，下列不可能的出站順序為 ( D ) A1234 B1243 C1324 D14233插入和刪除只能在一端進

40、行的線性表，稱為( C )。 A隊列 B循環(huán)隊列 C棧 D循環(huán)棧4鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（ B ）。A插入操作根加方便 B通常不會出現(xiàn)棧滿的情況。C不會出現(xiàn)?？盏那闆r D刪除操作根加方便5在棧中，出棧操作的時間復雜度為( A )。 AO(1) BO(log2n) C0(n) DO(n2)6帶頭結點的鏈棧LS的示意圖如下，棧頂元素是（ A ） LSHABCD AA BB CC DD7元素A,B,C,D依次進棧以后，棧頂元素是（ D ） AABB CC DD8順序棧存儲空間的實現(xiàn)使用（ B ）存儲棧元素。 A鏈表B數(shù)組 C循環(huán)鏈表 D變量9在C或C+語言中，一個順序棧一旦被聲明，

41、其占用空間的大小（ A ）。 A已固定 B不固定 C可以改變 D動態(tài)變化10當棧中的元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為（ C ）。 An-1 Bn+1 Cn Dn/211棧與一般線性表的區(qū)別在于 ( B )。 A數(shù)據(jù)元素的類型不同 B運算是否受限制 C數(shù)據(jù)元素的個數(shù)不同 D邏輯結構不同12設有一個順序棧S，元素A,B,C,D,E,F,依次進棧，如果六個元素出棧的順序是B，D，C，F(xiàn)，E，A，則棧的容量至少應是 ( A )。 A3 B4 C5 D 613在棧頂一端可進行（ D ）操作。 A插入 B刪除 C進棧 D插入和刪除14從一個棧頂指針為top的鏈棧中刪除一個結點時，用

42、x保存被刪除的結點，應執(zhí)行下列 ( D )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;top=top-next;15在一個棧頂指針為HS的鏈棧中，將一個S指針所指的結點入棧，應執(zhí)行下列 ( B )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next;16在隊列中存取數(shù)據(jù)應遵循的原則是( A )。 A先進先出 B后進先出 C先進后出 D隨意進出17設長度為n的鏈隊列用單循

43、環(huán)鏈表表示，若只設頭指針，則人隊操作的時間復雜度為( C )。 AO(1) BO(log2n) CO(n) DO(n2)18一個循環(huán)隊列一旦說明，其占用空間的大小（ A ）。 A已固定 B可以變動 C不能固定 D動態(tài)變化19當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標為（ B ）。 An-2 Bn-1 Cn Dn+120設長度為n的鏈隊列用單循環(huán)鏈表表示，若只設尾指針，則出隊操作的時間復雜度為( A )。 AO(1) BO (log2n) CO(n) DO(n2)21隊列是限定在（ D ）進行操作的線性表。 A中間 B隊頭 C隊尾 D端點22若進隊的序列為：A，B，C，D

44、，則出隊的序列是（ C ）。 AB，C，D，ABA，C，B，D CA，B，C，DDC，B，D，A23從一個順序循環(huán)隊列刪除一個元素時，首先需要做的操作是（ B ）。 A隊頭指針減1 B取出隊頭指針所指的元素 C隊頭指針加1 D取出隊尾指針所指的元素24. 在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的（ A ）位置。 A前一個 B后一個 C后面 D當前25四個元素按：A，B，C，D順序連續(xù)進隊Q，執(zhí)行一次OutQueue(Q)操作后，隊頭元素是（ B ）。 A AB B C C D D26隊列中的元素個數(shù)是( B )。 A不變的B可變的C任意的D027設鏈棧中結點的結構：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。若想在鏈棧的棧頂插入一個由指針s所指的結點，則應執(zhí)行下