1、綜合練習(xí)一,課堂練習(xí),設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ ）。 A) a，b，c，e，d B) b，c，a，e，d C) a，e，c，b，d D) d，c，e，b，a,一.單選題,1. 數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為_。 A) 靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu) B) 物理結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 虛擬結(jié)構(gòu)和抽象結(jié)構(gòu),一.單選題,2. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是_。 A) 存儲(chǔ)密度大 B) 插入、刪除運(yùn)算方便 C) 可進(jìn)行動(dòng)態(tài)存儲(chǔ)分配 D) 可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示,一.單選題,3. 下面關(guān)于線性表的敘述中，錯(cuò)誤的是 _。 A) 線

2、性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元 B) 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作 C) 線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元 D) 線性表采用鏈接存儲(chǔ)，可以動(dòng)態(tài)分配存儲(chǔ)空間,一.單選題,4. 用數(shù)組存儲(chǔ)線性表的優(yōu)點(diǎn)是_。 A) 便于插入和刪除操作 B) 便于隨機(jī)存取 C) 可以方便地改變表的長度 D) 不需要占用一片連續(xù)的存儲(chǔ)空間,一.單選題,5. 線性表中各元素之間呈_關(guān)系。 A) 層次 B) 網(wǎng)狀 C) 有序 D) 集合,一.單選題,6. 一維數(shù)組和線性表的區(qū)別是_。 A) 前者長度固定，后者長度可變 B) 后者長度固定，前者長度可變 C) 兩者長度均固定 D) 兩

3、者長度均可變,一.單選題,7.單鏈表L中，P所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件為 _ 。 A) PL B) P-next=NULL C) P.next:L D) Pnil,一.單選題,8.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置及個(gè)數(shù)無關(guān)的 是數(shù)據(jù)的 _ 。 A) 存儲(chǔ)結(jié)構(gòu) B) 存儲(chǔ)實(shí)現(xiàn) C) 邏輯結(jié)構(gòu) D) 運(yùn)算實(shí)現(xiàn),一.單選題,9.單鏈表中，增加頭結(jié)點(diǎn)的目的是 _ 。 A) 使單鏈表至少有一個(gè)結(jié)點(diǎn) B) 表示單鏈表中首結(jié)點(diǎn)的位置 C) 方便運(yùn)算的實(shí)現(xiàn) D) 說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),一.單選題,10. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì) 算機(jī)的_以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。 A

4、）操作對象 B）計(jì)算方法 C）邏輯存儲(chǔ) D）數(shù)據(jù)映像,一.單選題,11.算法分析的目的是_。 A）找出數(shù)據(jù)結(jié)構(gòu)的合理性 B）分析算法的效率以求改進(jìn) C）研究算法中的輸入和輸出的關(guān)系 D）分析算法的易懂性和文檔性,一.單選題,12.在長度為n的順序表的第i（1in+1）個(gè)位置上插入一 個(gè)元素，元素的移動(dòng)次數(shù)為_。 A）n-i+1 B）n - i C）i D）i-1,一.單選題,13. 不帶頭結(jié)點(diǎn)的單鏈表 head為空的判斷條件為_。 A）head =Null B） head -next = Null C） head -next = head D） head ! = Null,一.單選題,14.

5、數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D，S)，其中D是數(shù)據(jù)元素的有 限集合，S是D上_的有限結(jié)合。 A）操作 B）關(guān)系 C）存儲(chǔ) D）映像,一.單選題,15.線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種 的存儲(chǔ)結(jié)構(gòu)。 A）隨機(jī)存取 B）順序存取 C）索引存取 D）散列存取,一.單選題,16.組成數(shù)據(jù)的基本單位是_。 A）數(shù)據(jù)項(xiàng) B）數(shù)據(jù)類型 C）數(shù)據(jù)元素 D）數(shù)據(jù)變量,一.單選題,17. 雙循環(huán)鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是 A）p-next=s，s-prior=p， p-next-prior=s，s-next=p-next； B）p-next=s，p-next-prior=s， s-prior=p，s-next

6、=p-next； C）s-prior=p，s-next=p-next， p-next=s，p-next-prior=s； D）s-prior=p，s-next=p-next， p-next-prior=s，p-next=s；,一.單選題,18.一維數(shù)組和線性表的共同點(diǎn)是 。 兩者都是相同類型數(shù)據(jù)的集合 兩者都允許不同類型數(shù)據(jù)共存 兩者長度均固定 兩者長度均可變,一.單選題,19. 線性鏈表中各鏈接結(jié)點(diǎn)之間的地址_。 A）連續(xù)與否都可以 B）必須連續(xù) C）一定不連續(xù) D）部分地址必須連續(xù),一.單選題,20. 對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采 用的存儲(chǔ)結(jié)構(gòu)為 。 A）單鏈表 B）用

7、頭指針表示的單循環(huán)鏈表 C）用帶尾指針表示的單循環(huán)鏈表 D）順序表,二.多選題,1. 下列關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述中，正確的是_。 A) 結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于 順序存儲(chǔ)結(jié)構(gòu) B) 可以通過計(jì)算直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址 C) 邏輯上相鄰的結(jié)點(diǎn)物理上不必相鄰 D) 插入、刪除操作方便，不必移動(dòng)結(jié)點(diǎn) ACD,二.多選題,2. 下面的敘述正確的是_。(06) A）線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比 B）線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān) C）線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比 D）線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素

8、的時(shí)間同i的值無關(guān) AD,二.多選題,3. 鏈表具有的特點(diǎn)是_。 A）插入、刪除不需要移動(dòng)元素 B）不必事先估計(jì)存儲(chǔ)空間 C）可隨機(jī)訪問任一元素 D）所需空間與鏈表長度成正比 ABD,二.多選題,4. 下列關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述中，正確的是_。 A) 結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于順序 存儲(chǔ)結(jié)構(gòu) B) 可以通過計(jì)算可以直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址 C) 邏輯上相鄰的結(jié)點(diǎn)物理上必須相鄰 D) 插入、刪除操作方便，不必移動(dòng)結(jié)點(diǎn) AD,二.多選題,5. 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示方法有_。 A）順序映像 B）線性結(jié)構(gòu) C）非線性結(jié)構(gòu) D) 非順序映像 AD,三、判斷題,1.

9、數(shù)據(jù)結(jié)構(gòu)中與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的邏輯結(jié)構(gòu)。 2. 線性表是一個(gè)有序序列，其中可包含相同的元素，也允許各 個(gè)元素可以是不同的數(shù)據(jù)類型。 3. 鏈表的每個(gè)結(jié)點(diǎn)都含有兩個(gè)指針。 4.線性結(jié)構(gòu)的基本特征是：每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前 趨和一個(gè)后繼。 5.線性表中各元素類型必須是相同的。 6.數(shù)據(jù)結(jié)構(gòu)的操作一定是定義在邏輯結(jié)構(gòu)上，實(shí)現(xiàn)在存儲(chǔ) 結(jié)構(gòu)上。 7.數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系的整體。 正確 1 5 6 7,四、填空題,1. 數(shù)據(jù)結(jié)構(gòu)包括的三個(gè)方面的內(nèi)容是 、 和 。 2. 通常衡量算法效率的一般標(biāo)準(zhǔn)為 和 。 3. 算法是對特定問題求解步驟的一種描述，它具有有窮性、 確定性

10、、可行性、_及一個(gè)或多個(gè)輸出等重要特征。 4. 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種關(guān)系的_集合。 5. 線性結(jié)構(gòu)中元素的關(guān)系是_的關(guān)系。 答案：1 邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算 2 時(shí)間復(fù)雜度、空間復(fù)雜度 3 具有零個(gè)或多個(gè)輸入 4 數(shù)據(jù)元素 5 一對一,四、填空題,6. 用一維數(shù)組表示線性表L=(a1,a2,an)，假定刪除表中 任一元素的概率相同（都為1/n），則刪除一個(gè)元素平均需移 動(dòng)的元素個(gè)數(shù)為_ 。 (n-1)/2 7.當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)時(shí)，其主要特點(diǎn)是 _ 。 邏輯結(jié)構(gòu)相鄰的結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)也相鄰 8.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)最顯著的優(yōu)點(diǎn)是 _。 方便插入、刪除操作,四、填空題,9.單循環(huán)

11、鏈表的最顯著的優(yōu)點(diǎn)是 _ 。 答：從任意結(jié)點(diǎn)出發(fā)都可以訪問鏈表中的每個(gè)元素 10.一個(gè)線性表第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度 為2，則第6個(gè)元素的地址是_ 。 答：110,五、簡答題,1解釋數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的概念，并討論他 們之間的關(guān)系； 參考答案：數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的 數(shù)據(jù)元素的集合。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)描述數(shù)據(jù)之間的邏輯 關(guān)系。包括集合、線性、樹形和網(wǎng)狀結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù) 結(jié)構(gòu)在計(jì)算機(jī)中的表示稱存儲(chǔ)結(jié)構(gòu)。包括順序、索引、鏈?zhǔn)?和散列。三者關(guān)系：在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ) 結(jié)構(gòu)密切相關(guān)的；存儲(chǔ)結(jié)構(gòu)不僅存儲(chǔ)數(shù)據(jù)元素，還要存儲(chǔ)數(shù) 據(jù)元素的邏輯

12、關(guān)系；邏輯結(jié)構(gòu)與計(jì)算機(jī)無關(guān)；邏輯結(jié)構(gòu)相同 但存儲(chǔ)結(jié)構(gòu)不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。,五、簡答題,2線性表的順序存儲(chǔ)具有如下缺點(diǎn)：(1).在進(jìn)行插入或刪除 操作時(shí)，需要移動(dòng)大量元素；(2).由于難以估計(jì)其大小，必須 預(yù)先分配較大的存儲(chǔ)空間，往往使存儲(chǔ)空間得不到充分利用 ；(3).表的容量難以擴(kuò)充。試問線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一 定能克服上述缺點(diǎn)？試做簡要討論。 參考答案：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一般克服的順序結(jié)構(gòu)的三個(gè)弱點(diǎn)： 首先，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)插入、刪除不需要移動(dòng)元素，只需修改 指針，時(shí)間復(fù)雜度為O(1)；其二，不需要預(yù)先分配存儲(chǔ)空間 ，可根據(jù)需要?jiǎng)討B(tài)申請；其三，表容量只受內(nèi)存空間的限制 ； 缺點(diǎn)：因指針增加

13、了內(nèi)存空間開銷，當(dāng)空間不允許時(shí)，就不能 克服順序存儲(chǔ)的優(yōu)點(diǎn)。,六、編程題,1已知兩個(gè)帶頭結(jié)點(diǎn)的單鏈表La和Lb中的元素按非遞減順 序排列，試用C語言編寫一個(gè)函數(shù)將這兩個(gè)有序表合并成一 個(gè)有序單鏈表保存在La中，而不改變其排序性。設(shè)帶頭結(jié)點(diǎn) 的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說明及函數(shù)名如下： typedef struct node /*定義結(jié)點(diǎn)結(jié)構(gòu)*/ datatype data; struct node next; lklist; typedef struct node *pointer; 函數(shù)首部為： pointer mergelklist(lklist ha,lklist hb),pointer mergelklist(lklist ha,lklist hb) pointer *h, *pa, *pb ; pa=ha-next, pb=hb-next； h= r = ha； while(pa return h； ,1題參考答案,六、編程題,2 設(shè)計(jì)算法求兩個(gè)遞增有序的順序表L1和L2中的公共元素 ，并將其置入順序表L3中，用C語言實(shí)現(xiàn)。設(shè)順序表存儲(chǔ)結(jié) 構(gòu)說明如下： typedef struct ElemType *elem; Int length ; sqlist; sqlist L1,L2,L3; 函數(shù)首部為： status complist(sqlist L1, sqlist