商學(xué)院專業(yè)課數(shù)據(jù)結(jié)構(gòu)商大

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)和動態(tài)結(jié)構(gòu) B) 物理結(jié)構(gòu)和存儲結(jié)構(gòu)C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 虛擬結(jié)構(gòu)和抽象結(jié)構(gòu)一.單選題2. 順序存儲方式的優(yōu)點是_。A) 存儲密度大B) 插入、刪除運(yùn)算方便C) 可進(jìn)行動態(tài)存儲分配D) 可方便地用于各種邏輯結(jié)構(gòu)的存儲表示一.單選題3. 下面關(guān)于線性表的敘述中，錯誤的是 _。A) 線性表采用順序存儲，必須占用一片連

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

3、 _ 。A) PL B) P-next=NULLC) P.next:L D) Pnil一.單選題8.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置及個數(shù)無關(guān)的是數(shù)據(jù)的 _ 。A) 存儲結(jié)構(gòu)B) 存儲實現(xiàn) C) 邏輯結(jié)構(gòu)D) 運(yùn)算實現(xiàn)一.單選題9.單鏈表中，增加頭結(jié)點的目的是 _ 。A) 使單鏈表至少有一個結(jié)點B) 表示單鏈表中首結(jié)點的位置C) 方便運(yùn)算的實現(xiàn) D) 說明單鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)一.單選題10. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的_以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。 A）操作對象 B）計算方法 C）邏輯存儲 D）數(shù)據(jù)映像一.單選題11.算法分析的目的是_。 A）找出數(shù)

4、據(jù)結(jié)構(gòu)的合理性 B）分析算法的效率以求改進(jìn) C）研究算法中的輸入和輸出的關(guān)系 D）分析算法的易懂性和文檔性一.單選題12.在長度為n的順序表的第i（1in+1）個位置上插入一個元素，元素的移動次數(shù)為_。A）n-i+1 B）n - i C）i D）i-1一.單選題13. 不帶頭結(jié)點的單鏈表 head為空的判斷條件為_。 A）head =Null B） head -next = Null C） head -next = head D） head ! = Null 一.單選題14. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D，S)，其中D是數(shù)據(jù)元素的有限集合，S是D上_的有限結(jié)合。A）操作 B）關(guān)系 C）存儲D）映

5、像一.單選題15.線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種 的存儲結(jié)構(gòu)。A）隨機(jī)存取B）順序存取C）索引存取D）散列存取一.單選題16.組成數(shù)據(jù)的基本單位是_。 A）數(shù)據(jù)項B）數(shù)據(jù)類型C）數(shù)據(jù)元素D）數(shù)據(jù)變量一.單選題17. 雙循環(huán)鏈表的*p結(jié)點之后插入*s結(jié)點的操作是 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=p-next；C）s-prior=p，s-next=p-next，p-next=s，p-next-prior=s；D）s-prior=p，s-next=p

6、-next，p-next-prior=s，p-next=s；一.單選題18.一維數(shù)組和線性表的共同點是 。兩者都是相同類型數(shù)據(jù)的集合兩者都允許不同類型數(shù)據(jù)共存兩者長度均固定兩者長度均可變一.單選題19. 線性鏈表中各鏈接結(jié)點之間的地址_。A）連續(xù)與否都可以 B）必須連續(xù)C）一定不連續(xù)D）部分地址必須連續(xù)一.單選題20. 對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為 。A）單鏈表B）用頭指針表示的單循環(huán)鏈表 C）用帶尾指針表示的單循環(huán)鏈表D）順序表二.多選題1. 下列關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的敘述中，正確的是_。 A) 結(jié)點除自身信息外還包括指針域，因此存儲密度小于 順序存儲結(jié)構(gòu) B)

7、 可以通過計算直接確定第i個結(jié)點的存儲地址 C) 邏輯上相鄰的結(jié)點物理上不必相鄰 D) 插入、刪除操作方便，不必移動結(jié)點ACD二.多選題2. 下面的敘述正確的是_。(06)A）線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比B）線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)C）線性表在順序存儲時，查找第i個元素的時間同i 的值成正比D）線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)AD二.多選題3. 鏈表具有的特點是_。A）插入、刪除不需要移動元素B）不必事先估計存儲空間C）可隨機(jī)訪問任一元素D）所需空間與鏈表長度成正比ABD二.多選題4. 下列關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的敘述中，正確

8、的是_。A) 結(jié)點除自身信息外還包括指針域，因此存儲密度小于順序存儲結(jié)構(gòu)B) 可以通過計算可以直接確定第i個結(jié)點的存儲地址C) 邏輯上相鄰的結(jié)點物理上必須相鄰D) 插入、刪除操作方便，不必移動結(jié)點AD二.多選題5. 數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中的表示方法有_。 A）順序映像 B）線性結(jié)構(gòu) C）非線性結(jié)構(gòu)D) 非順序映像AD三、判斷題1. 數(shù)據(jù)結(jié)構(gòu)中與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的邏輯結(jié)構(gòu)。2. 線性表是一個有序序列，其中可包含相同的元素，也允許各個元素可以是不同的數(shù)據(jù)類型。3. 鏈表的每個結(jié)點都含有兩個指針。4.線性結(jié)構(gòu)的基本特征是：每個結(jié)點有且僅有一個直接前趨和一個后繼。5.線性表中各元素類型

9、必須是相同的。 6.數(shù)據(jù)結(jié)構(gòu)的操作一定是定義在邏輯結(jié)構(gòu)上，實現(xiàn)在存儲結(jié)構(gòu)上。 7.數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系的整體。正確 1 5 6 7四、填空題1. 數(shù)據(jù)結(jié)構(gòu)包括的三個方面的內(nèi)容是 、 和 。2. 通常衡量算法效率的一般標(biāo)準(zhǔn)為 和 。3. 算法是對特定問題求解步驟的一種描述，它具有有窮性、確定性、可行性、_及一個或多個輸出等重要特征。4. 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種關(guān)系的_集合。5. 線性結(jié)構(gòu)中元素的關(guān)系是_的關(guān)系。 答案：1 邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算 2 時間復(fù)雜度、空間復(fù)雜度 3 具有零個或多個輸入 4 數(shù)據(jù)元素 5 一對一四、填空題6. 用一維數(shù)組表示線性表L=(

10、a1,a2,an)，假定刪除表中任一元素的概率相同（都為1/n），則刪除一個元素平均需移動的元素個數(shù)為_ 。(n-1)/2 7.當(dāng)線性表采用順序存儲結(jié)構(gòu)進(jìn)行存儲時，其主要特點是 _ 。邏輯結(jié)構(gòu)相鄰的結(jié)點存儲結(jié)構(gòu)也相鄰8.鏈?zhǔn)酱鎯Y(jié)構(gòu)最顯著的優(yōu)點是 _。 方便插入、刪除操作四、填空題9.單循環(huán)鏈表的最顯著的優(yōu)點是 _ 。答：從任意結(jié)點出發(fā)都可以訪問鏈表中的每個元素10.一個線性表第一個元素的存儲地址是100，每個元素的長度為2，則第6個元素的地址是_ 。答：110五、簡答題1解釋數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的概念，并討論他們之間的關(guān)系；參考答案：數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素

11、的集合。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)描述數(shù)據(jù)之間的邏輯關(guān)系。包括集合、線性、樹形和網(wǎng)狀結(jié)構(gòu)。存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示稱存儲結(jié)構(gòu)。包括順序、索引、鏈?zhǔn)胶蜕⒘小Ｈ哧P(guān)系：在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)密切相關(guān)的；存儲結(jié)構(gòu)不僅存儲數(shù)據(jù)元素，還要存儲數(shù)據(jù)元素的邏輯關(guān)系；邏輯結(jié)構(gòu)與計算機(jī)無關(guān)；邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。五、簡答題2線性表的順序存儲具有如下缺點：(1).在進(jìn)行插入或刪除操作時，需要移動大量元素；(2).由于難以估計其大小，必須預(yù)先分配較大的存儲空間，往往使存儲空間得不到充分利用；(3).表的容量難以擴(kuò)充。試問線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是否一定能克服上述缺點？試做簡

12、要討論。參考答案：鏈?zhǔn)酱鎯Y(jié)構(gòu)一般克服的順序結(jié)構(gòu)的三個弱點： 首先，鏈?zhǔn)酱鎯Y(jié)構(gòu)插入、刪除不需要移動元素，只需修改指針，時間復(fù)雜度為O(1)；其二，不需要預(yù)先分配存儲空間，可根據(jù)需要動態(tài)申請；其三，表容量只受內(nèi)存空間的限制；缺點：因指針增加了內(nèi)存空間開銷，當(dāng)空間不允許時，就不能克服順序存儲的優(yōu)點。六、編程題1已知兩個帶頭結(jié)點的單鏈表La和Lb中的元素按非遞減順序排列，試用C語言編寫一個函數(shù)將這兩個有序表合并成一個有序單鏈表保存在La中，而不改變其排序性。設(shè)帶頭結(jié)點的單鏈表的結(jié)點結(jié)構(gòu)說明及函數(shù)名如下：typedef struct node /*定義結(jié)點結(jié)構(gòu)*/ datatype data; st

13、ruct 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 & pb) If(pa-data data) /*移動ha, hb頭指針, 修改r指向 r-next =pa; r=pa; pa= pa-next ； else r-next =pb; r

14、=pb; pb= pb-next ； if(pa=NULL) r-next=pb; if(pb=NULL) r-next=pa; return h； 1題參考答案六、編程題2 設(shè)計算法求兩個遞增有序的順序表L1和L2中的公共元素，并將其置入順序表L3中，用C語言實現(xiàn)。設(shè)順序表存儲結(jié)構(gòu)說明如下：typedef struct ElemType *elem; Int length ;sqlist;sqlist L1,L2,L3;函數(shù)首部為： status complist(sqlist L1, sqlist L2, sqlist L3)status complist(sqlist L1, sqlist L2, sql