數(shù)據(jù)結(jié)構(gòu)高春曉復(fù)習(xí)

1、1. 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)：描述數(shù)據(jù)間的邏輯關(guān)系描述數(shù)據(jù)間的邏輯關(guān)系。典型的典型的邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：集合、線性、樹、圖集合、線性、樹、圖2. 數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲器中的映象邏輯結(jié)構(gòu)在存儲器中的映象。典典型的存儲結(jié)構(gòu)：型的存儲結(jié)構(gòu)：順序和鏈?zhǔn)巾樞蚝玩準(zhǔn)?. ADT：是對數(shù)據(jù)結(jié)構(gòu)的一種更準(zhǔn)確的抽象描述，它：是對數(shù)據(jù)結(jié)構(gòu)的一種更準(zhǔn)確的抽象描述，它忽略了數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)步驟，將更多的注意力忽略了數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)步驟，將更多的注意力放在數(shù)據(jù)的基本操作上，通過基本操作描述數(shù)據(jù)的放在數(shù)據(jù)的基本操作上，通過基本操作描述數(shù)據(jù)的邏輯關(guān)系。它包括三個部分：邏輯關(guān)系。它包括三

2、個部分：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作和基本操作。4. 什么是算法的時間復(fù)雜度？如何計算？什么是算法的時間復(fù)雜度？如何計算？5. 什么是算法的空間復(fù)雜度？如何計算？什么是算法的空間復(fù)雜度？如何計算？ 1、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）的（） A. 存儲結(jié)構(gòu)存儲結(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、數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指（）、數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指（） A. 數(shù)據(jù)元素的結(jié)構(gòu)數(shù)據(jù)元素的結(jié)構(gòu) B. 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) C. 數(shù)據(jù)的存儲結(jié)構(gòu)

3、數(shù)據(jù)的存儲結(jié)構(gòu) D. 數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)元素之間的關(guān)系 3、算法時間復(fù)雜度的含義是指算法的（）、算法時間復(fù)雜度的含義是指算法的（） A. 執(zhí)行時間的長短執(zhí)行時間的長短 B. 執(zhí)行時間的增長率執(zhí)行時間的增長率 C. 執(zhí)行語句的多少執(zhí)行語句的多少 D. 需要的存儲空間需要的存儲空間 4、如果某算法對于規(guī)模為、如果某算法對于規(guī)模為 n 的問題的時間耗費為的問題的時間耗費為 T（n）= n3 ，在一臺計算機上運行時間為，在一臺計算機上運行時間為 t 秒，則在另一臺運行速度秒，則在另一臺運行速度是其是其 64 倍的機器上，用同樣的時間能解決的問題規(guī)模是原問倍的機器上，用同樣的時間能解決的問題規(guī)模是原

4、問題規(guī)模的（）題規(guī)模的（） A. 4倍倍 B. 8倍倍 C. 64倍倍 D. 16倍倍 5、下面程序段的時間復(fù)雜度為（）、下面程序段的時間復(fù)雜度為（） for ( i=0; im; i+ ) for ( j=0; jn; j+ ) Aij = i*j; A. O (m * m) B. O (m * n) C. O (m + n) D. O (n * n) 線性表是線性表是n n個具有個具有相同類型相同類型的數(shù)據(jù)元素構(gòu)成的的數(shù)據(jù)元素構(gòu)成的有限有限序列序列線性表的存儲線性表的存儲鏈序存儲鏈序存儲(鏈表鏈表)順序存儲順序存儲(順序表順序表)雙向循環(huán)鏈表雙向循環(huán)鏈表單向循環(huán)鏈表單向循環(huán)鏈表單鏈表單鏈表

5、鏈表的靜態(tài)存儲鏈表的靜態(tài)存儲結(jié)構(gòu)性結(jié)構(gòu)性操作操作ListEmpty( L ) /判斷線性表是否為空判斷線性表是否為空ListLength( L ) /求線性表的長度求線性表的長度GetElem( L, i, &e ) /讀取第讀取第i個元素的值個元素的值LocateElem( L, e, compare( ) ) /定位定位eListTraverse(L, visit( ) /遍歷線性表遍歷線性表屬性類屬性類操作操作ListInsert( &L, i, e ) /插入數(shù)據(jù)元素插入數(shù)據(jù)元素ListDelete(&L, i, &e) /刪除數(shù)據(jù)元素刪除數(shù)據(jù)元素引用性引用性操作操作加工性加工性操作操

6、作InitList( &L ) /初始化一個線性表初始化一個線性表DestroyList( &L ) /刪除線性表刪除線性表 0 1 . i-2 i-1 . n-1a1a2ai-1aiantypedef struct ElemType *elem; / 存儲空間基址存儲空間基址 int length; / 當(dāng)前長度當(dāng)前長度 int listsize; / 當(dāng)前分配的存儲容量當(dāng)前分配的存儲容量 / (以以sizeof(ElemType)為單位為單位) SqList; / 俗稱順序表俗稱順序表elemlength listsizeLSqList L;L.elem+L. length1L.elem+

7、L. listsize134161182531341612531341613018253134161182531ListInsert(&L, 5, 30)123456789ListDelete (&L, 5, &e)123456789操作步驟操作步驟1) 判斷位置合法判斷位置合法性性2) 依次后依次后length-i+1個元素個元素后移后移一一位位3) 將新元素將新元素e寫入寫入到第到第i個位置個位置4) 將表的長度將表的長度加加1操作步驟操作步驟1) 判斷位置合法判斷位置合法性性2)將第將第i個位置的個位置的值賦給變量值賦給變量e3)依次后依次后length-i+1個元素個元素前移前移一一位

8、位4) 將表的長度將表的長度減減12) 1(1111ninnEniisn若假定在線性表中任何若假定在線性表中任何一個位置上進行一個位置上進行插入的插入的概率概率都是都是相等相等的，則的，則移移動元素的期望值動元素的期望值為為：n若假定在線性表中任若假定在線性表中任何一個位置上進行何一個位置上進行刪除刪除的概率的概率都是都是相等相等的，則的，則移動元素的期望值移動元素的期望值為為：21)(11ninnEnidl 用一組用一組地址任意地址任意的存儲單元的存儲單元存放存放線性表中的線性表中的數(shù)據(jù)元素數(shù)據(jù)元素a1 .ana2L:頭指針頭指針表尾表尾:空指針空指針頭結(jié)點頭結(jié)點 typedef struc

9、t LNode ElemType data; / / 數(shù)據(jù)域數(shù)據(jù)域 struct LNode *next; / / 指針域指針域 LNode, *LinkList; LinkList L； / L 為單鏈表的頭指針為單鏈表的頭指針a1 .ana2L:頭指針頭指針表尾表尾:空指針空指針頭結(jié)點頭結(jié)點 GetElem(L, i, &e) /取第取第i i個數(shù)據(jù)元素個數(shù)據(jù)元素a1 .ana2基本操作：基本操作：移動指針移動指針 i i 次次。 結(jié)束條件：結(jié)束條件：1 1、找到第找到第i i個結(jié)點個結(jié)點 2 2、i i大于鏈表的長度大于鏈表的長度, ,即即p pnullnull基本方法基本方法: : 1

10、 1、設(shè)置一個計數(shù)器、設(shè)置一個計數(shù)器j j； 2 2、設(shè)置一個依次向后移動的指針、設(shè)置一個依次向后移動的指針p p 。 主循環(huán)：主循環(huán)：while (p & ji) p = pnext; +j; ai-1 eaipss next = pnext; pnext = s;ListInsert(&L, i, e)找到線性表中第找到線性表中第i-1i-1個結(jié)點個結(jié)點修改其后繼指針修改其后繼指針ListDelete(&L, i, e)找到線性表中第找到線性表中第i-1i-1個結(jié)點個結(jié)點修改其后繼指針修改其后繼指針ai-1aiai+1ai-1pq = pnext; pnext = qnext ;free(

11、q);q正確連接正確連接指針指針找到正確找到正確位置位置不要丟失不要丟失結(jié)點結(jié)點 單向循環(huán)鏈表單向循環(huán)鏈表 雙向鏈表雙向鏈表 雙向循環(huán)鏈表雙向循環(huán)鏈表a1a2an a1 a2 . an a1 a2 . an 靜態(tài)鏈表：用靜態(tài)鏈表：用數(shù)組數(shù)組實現(xiàn)的鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)的鏈?zhǔn)浇Y(jié)構(gòu)08122ZHAO33QIAN44SUN55LI96ZHOU0708109WAN6107數(shù)據(jù)鏈表尾結(jié)點數(shù)據(jù)鏈表尾結(jié)點數(shù)據(jù)鏈表頭結(jié)點數(shù)據(jù)鏈表頭結(jié)點space(1)備用空間鏈表頭結(jié)點備用空間鏈表頭結(jié)點space(0)備用空間鏈表尾結(jié)點備用空間鏈表尾結(jié)點space同時維護兩個鏈表：備用空間鏈表同時維護兩個鏈表：備用空間鏈表完成對一個鏈表

12、的插入操作完成對一個鏈表的插入操作同時完成對另一個鏈表的刪除操作同時完成對另一個鏈表的刪除操作 1、在下列各項敘述中，正確的說法是（）、在下列各項敘述中，正確的說法是（） A. 在線性表中，每個元素有且僅有一個直接前趨，在線性表中，每個元素有且僅有一個直接前趨，有且僅有一個直接后繼有且僅有一個直接后繼 B. 線性表中至少有一個元素線性表中至少有一個元素 C. 在線性表中，除第一個元素和最后一個元素之在線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼有一個直接后繼 D. 線性表中元素必須從大到小或從小到大排列

13、線性表中元素必須從大到小或從小到大排列 3、對于經(jīng)常要存取線性表任意指定位置元素的應(yīng)用，、對于經(jīng)常要存取線性表任意指定位置元素的應(yīng)用，線性表應(yīng)采用的存儲結(jié)構(gòu)是線性表應(yīng)采用的存儲結(jié)構(gòu)是（）（） a. 鏈?zhǔn)芥準(zhǔn)?b. 線性鏈表線性鏈表 c. 棧棧 d. 順序順序 2、用線性鏈表存儲線性表時，要求存儲空間（）、用線性鏈表存儲線性表時，要求存儲空間（） A. 連續(xù)不連續(xù)都可以連續(xù)不連續(xù)都可以 B. 部分元素的存儲空間必須是連續(xù)的部分元素的存儲空間必須是連續(xù)的 C. 必須是連續(xù)的必須是連續(xù)的 D. 必須是不連續(xù)的必須是不連續(xù)的 5、線性表的順序存儲結(jié)構(gòu)是通過何種方式表示元素之間的關(guān)系、線性表的順序存儲結(jié)

14、構(gòu)是通過何種方式表示元素之間的關(guān)系（）（） A. 保存左、右孩子地址保存左、右孩子地址 B. 后繼元素的數(shù)組下標(biāo)后繼元素的數(shù)組下標(biāo) C. 元素的存儲順序元素的存儲順序 D. 保存后繼元素地址保存后繼元素地址 4、在下列對順序表進行的操作中，算法時間復(fù)雜度為、在下列對順序表進行的操作中，算法時間復(fù)雜度為 O(1) 的是的是（）（） a. 訪問第訪問第i個元素的前驅(qū)（個元素的前驅(qū)（1 next; p-next = s; s-next = r; b. p-next = s; s-next = p; c. s-next = p-next; p-next = s; d. 以上都不對以上都不對 8、在鏈?zhǔn)?/p>

15、存儲結(jié)構(gòu)中，體現(xiàn)數(shù)據(jù)之間關(guān)系的是（）、在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，體現(xiàn)數(shù)據(jù)之間關(guān)系的是（） a. 數(shù)據(jù)在內(nèi)存的相對位置數(shù)據(jù)在內(nèi)存的相對位置 b. 指示數(shù)據(jù)元素的指針指示數(shù)據(jù)元素的指針 c. 指針指針 d. 數(shù)據(jù)的存儲地址數(shù)據(jù)的存儲地址9、靜態(tài)鏈表與動態(tài)鏈表相比，其缺點是（）、靜態(tài)鏈表與動態(tài)鏈表相比，其缺點是（） a. 插入、刪除時需移動較多數(shù)據(jù)插入、刪除時需移動較多數(shù)據(jù) b. 不能隨機存取不能隨機存取 c. 有可能浪費較多存儲空間有可能浪費較多存儲空間 d. 以上都不是以上都不是 10、若某線性表最常用的操作是在最后一個結(jié)點之、若某線性表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則

16、采用存儲后插入一個結(jié)點或刪除最后一個結(jié)點，則采用存儲結(jié)構(gòu)算法的時間效率最高的是（）結(jié)構(gòu)算法的時間效率最高的是（） a. 單鏈表單鏈表 b. 給出表尾指針的單循環(huán)鏈表給出表尾指針的單循環(huán)鏈表 c. 雙向鏈表雙向鏈表 d. 給出表尾指針雙向循環(huán)鏈表給出表尾指針雙向循環(huán)鏈表 11、算法指的是算法指的是_。(A) (A) 計算方法計算方法 (B) (B) 排序方法排序方法 (C) (C) 查找方法查找方法 (D) (D) 解決問題的有限運算序列解決問題的有限運算序列 1212、算法設(shè)計需要達到的目標(biāo)是算法設(shè)計需要達到的目標(biāo)是 。（A A）正確性）正確性 （B B）高效率）高效率（C C）低存儲）低存儲

17、 （D D）全是）全是 1313、以下、以下 操作不是棧的基本運算。操作不是棧的基本運算。（A A） 刪除棧頂元素刪除棧頂元素 （B B） 刪除棧底元素刪除棧底元素（C C） 判斷棧是否為空判斷棧是否為空 （D D） 將棧置為空棧將棧置為空棧 1414、在順序存儲結(jié)構(gòu)中，只要知道、在順序存儲結(jié)構(gòu)中，只要知道 ，就可，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。在相同時間內(nèi)求出任一結(jié)點的存儲地址。（A A）基地址）基地址（B B）結(jié)點大小）結(jié)點大?。– C）向量大?。┫蛄看笮。― D）基地址和結(jié)點大?。┗刂泛徒Y(jié)點大小 15、對于給定的對于給定的n n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)個元素，可以構(gòu)造出的

18、邏輯結(jié)構(gòu)有有 、 、 、 四種。四種。 16、單鏈表中指針單鏈表中指針P P所指結(jié)點不為尾結(jié)點的條件所指結(jié)點不為尾結(jié)點的條件是是 。 1717、在有頭結(jié)點的單鏈表中，第、在有頭結(jié)點的單鏈表中，第1 1個結(jié)點的地址存放個結(jié)點的地址存放 在（在（ ）中，其他結(jié)點的存儲地址存放在前驅(qū)結(jié)中，其他結(jié)點的存儲地址存放在前驅(qū)結(jié)點的點的 域中。域中。 棧和隊列都是操作受限的棧和隊列都是操作受限的線性表線性表 棧：棧： 限定僅能在表尾一端進限定僅能在表尾一端進行插入、刪除操作的線行插入、刪除操作的線性表；性表； 棧的特點棧的特點： 后進先出后進先出的線性表的線性表 LIFO-Last In First Outa

19、 an na a2 2a a1 1棧頂棧頂棧底棧底出棧出棧進棧進棧 隊列：隊列： 一端插入，另一端刪一端插入，另一端刪除除 從尾進，從頭出從尾進，從頭出 隊列的特點：隊列的特點： 先進先出的線性表先進先出的線性表 FIFO-First in First outa a1 1a an-1n-1a an n出隊列出隊列進隊列進隊列隊首隊首隊尾隊尾 Pop(&S, &e) ,Push(&S, e) 順序棧：順序棧： Push(&S, e)： *S.top+ = e Pop(&S, &e)： e = *-S.top;a a2 2a a1 1an-1basetop #define STACK_INIT_S

20、IZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; /棧底棧底 SElemType *top; /棧頂棧頂 int stacksize; /棧的大小棧的大小 SqStack; Pop(&S, &e) , Push(&S, e) 鏈?zhǔn)綏ｆ準(zhǔn)綏?Push(&S, e)：在鏈表開始插入一個新節(jié)點：在鏈表開始插入一個新節(jié)點 Pop(&S, &e)：刪除鏈表第一個節(jié)點：刪除鏈表第一個節(jié)點topa1 .ana2 EnQueue(&Q, e)，DeQueue(&Q, &e) 鏈?zhǔn)疥犃墟準(zhǔn)疥犃?EnQueue(&Q, e)：在鏈表

21、最后插入一個新節(jié)點：在鏈表最后插入一個新節(jié)點 DeQueue(&Q, &e)：刪除鏈表第一個節(jié)點：刪除鏈表第一個節(jié)點a1a2anfrontrear 順序隊列順序隊列 EnQueue(&Q, e)：隊列尾指針加：隊列尾指針加1 DeQueue(&Q, &e)：隊列頭指針加：隊列頭指針加1Q.baseQ.rearQ.front1 14 40 01 14 43 32 25 5J7J7J6J6J5J5Q.rearQ.front J1J1 J2J2 J3J3 Q.base循環(huán)順序隊列：注意判斷隊列循環(huán)順序隊列：注意判斷隊列空和滿的條件空和滿的條件 1、隊列和棧的共同點是、隊列和棧的共同點是 【 】 A.

22、 LIFO B. 都是線性表都是線性表 C. 無共同點無共同點 D. FIFO 2、若用一個大小為若用一個大小為 6 的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前 rear 和和 front 的值分別為的值分別為0和和3 。當(dāng)從隊列中刪除一個元素，再加入兩。當(dāng)從隊列中刪除一個元素，再加入兩個元素后，個元素后， rear 和和 front 的值分別為的值分別為 【 】 A. 5和和1 B. 1和和5 C. 4和和2 D. 2和和4 3、向一個棧頂指針為向一個棧頂指針為 h 的帶頭結(jié)點鏈棧中插入指針的帶頭結(jié)點鏈棧中插入指針 s 所指的結(jié)點時，應(yīng)執(zhí)行的語句序列是所指的結(jié)點時，應(yīng)執(zhí)行的語句

23、序列是【 】 A. snext = h；h = hnext； B. snext = hnext；hnext = s； C. hnext = s； D. snext = h；4、對于循環(huán)隊列，正確的是對于循環(huán)隊列，正確的是 【 】 A. 無法判斷隊列是否為滿無法判斷隊列是否為滿 B. 循環(huán)隊列不會滿循環(huán)隊列不會滿 C. 無法判斷隊列是否為空無法判斷隊列是否為空 D. 以上說法都是錯誤的以上說法都是錯誤的 5、設(shè)、設(shè) 棧棧 S 和隊列和隊列 Q 的初始狀態(tài)均為空，元素的初始狀態(tài)均為空，元素 a, b, c, d, e, f, g 依次進入棧依次進入棧 S 。若每個元素出棧后立即進入隊列。若每個元素

24、出棧后立即進入隊列 Q ，且，且 7 個元素出隊的順序是個元素出隊的順序是 b, d, c, f, e, a, g ，則棧，則棧 S 的容量至少是的容量至少是 【 】 A. 2 B. 1 C. 3 D. 4 6、為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)、為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是，結(jié)構(gòu)應(yīng)該是，【 】 A. 棧棧 B. 圖圖 C. 樹樹 D

25、. 隊列隊列 7、若一個棧的輸入序列為、若一個棧的輸入序列為 1 ， 2 ， 3 ， n ，輸出序列，輸出序列的第的第 1 個元素為個元素為 n ，則第，則第 i 個輸出的元素是個輸出的元素是( ) A. i B. ni C. ni+1 D. 可是其他任意元素可是其他任意元素 8、用不帶頭結(jié)點的單鏈表存儲隊列，其隊頭指針指向隊頭、用不帶頭結(jié)點的單鏈表存儲隊列，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時，結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時，( ) A. 隊頭，隊尾指針都要修改隊頭，隊尾指針都要修改 B. 隊頭，隊尾指針都可能要修改隊頭，隊尾指針都可能要修改

26、C. 僅修改隊頭指針僅修改隊頭指針 D. 僅修改隊尾指針僅修改隊尾指針 9、一個棧的輸入序列為：一個棧的輸入序列為：1 2 3 4 5 ，則下列序列中，則下列序列中不可能的輸出序列是，不可能的輸出序列是， 【 】 A. 1 5 4 3 2 B. 5 4 2 3 1 C. 2 3 4 1 5 D. 2 3 1 4 5 10、在算符優(yōu)先算法中，算符在算符優(yōu)先算法中，算符和和（的優(yōu)的優(yōu)先關(guān)系應(yīng)是，先關(guān)系應(yīng)是， 【 】 A. （ 判斷正誤判斷正誤1. 在單鏈表中在單鏈表中,指向第一個結(jié)點的指針定義了該鏈表指向第一個結(jié)點的指針定義了該鏈表2. 能夠通過在鏈表的表頭不斷插入新結(jié)點來創(chuàng)建一個能夠通過在鏈表的

27、表頭不斷插入新結(jié)點來創(chuàng)建一個單向鏈表單向鏈表3. 堆棧和隊列不屬于線性表堆棧和隊列不屬于線性表4. 循環(huán)隊列是一種物理結(jié)構(gòu)循環(huán)隊列是一種物理結(jié)構(gòu)5. 刪除單鏈表的最后一個結(jié)點需要遍歷整個鏈表刪除單鏈表的最后一個結(jié)點需要遍歷整個鏈表YYNNY 1、向具有、向具有n個不同元素的鏈表中插入一個數(shù)據(jù)元素個不同元素的鏈表中插入一個數(shù)據(jù)元素,最壞情況下需要訪問最壞情況下需要訪問 個元素個元素? A n B n/2 C1 Dn/3 2、若鏈表中的元素有序、若鏈表中的元素有序,下列敘述哪一個正確下列敘述哪一個正確? A 找第找第k個元素的時間復(fù)雜度是個元素的時間復(fù)雜度是O(1) B 插入一個給定元素的時間復(fù)雜

28、度是插入一個給定元素的時間復(fù)雜度是O(n2) C 刪除一個給定元素的時間復(fù)雜度是刪除一個給定元素的時間復(fù)雜度是O(1) D 查找一個元素查找一個元素a是否屬于鏈表的時間復(fù)雜度是是否屬于鏈表的時間復(fù)雜度是O(n)AD 3、設(shè)棧的輸入序列是、設(shè)棧的輸入序列是1、2、3、4，則，則 不可能是不可能是其出棧序列：其出棧序列： A 1234 B 2134 C1432 D4312 4、若頻繁地對線性表進行插入和刪除操作，該線性、若頻繁地對線性表進行插入和刪除操作，該線性表應(yīng)該采用表應(yīng)該采用 存儲結(jié)構(gòu)。存儲結(jié)構(gòu)。 A散列散列 B順序順序 C鏈表鏈表 D任意任意DC 5、線性表中各個結(jié)點之間的地址、線性表中各

29、個結(jié)點之間的地址 。 A必須連續(xù)必須連續(xù) B不一定連續(xù)不一定連續(xù) C任意任意 6、在非空鏈表中，在由、在非空鏈表中，在由p指向的結(jié)點后面插入一個指向的結(jié)點后面插入一個由由q指向的結(jié)點過程是：指向的結(jié)點過程是： A p = q-next; p-next = q; B q-next = p-next; p-next = q; C q-next = p-next; p = q; D p-next = q; q-next = p;BB 7、若刪除非空鏈表中由、若刪除非空鏈表中由p所指向的結(jié)點的直接后繼所指向的結(jié)點的直接后繼結(jié)點的過程是：結(jié)點的過程是： A r = p-next; p-next = r;

30、 free(r); B r = p-next; p-next = r-next; free(r); C r = p-next; p = r-next; free(r); D p-next = p-next -next -next; 8、在非空雙向循環(huán)鏈表中，在由、在非空雙向循環(huán)鏈表中，在由q指向結(jié)點前插入指向結(jié)點前插入一個由一個由p指向的結(jié)點的過程是：指向的結(jié)點的過程是： p-right = q; p-left = q-left; q-left = p, ( ) . A q-left = p; B q-left-right = p; C p-right-right D p-left-right

31、 = p;BD 用靜態(tài)鏈表實現(xiàn)的隊列如用靜態(tài)鏈表實現(xiàn)的隊列如右圖所示右圖所示:front = 9, rear = 7. 隊列有頭結(jié)點隊列有頭結(jié)點 當(dāng)執(zhí)行下列操作時當(dāng)執(zhí)行下列操作時,隊列隊列有什么變化有什么變化? 1) 元素元素S入隊入隊 2) 隊首元素出隊隊首元素出隊0A11B32C43D64E105F76G87H08I09J210K5spacefrontrear0A31S02C43D64E105F76G87H18I09J210K5spacefrontrear0A21S02C33D64E105F76G87H18I09J410K5spacefrontrear1) 元素元素S入隊入隊2) 隊首元素

32、出隊隊首元素出隊cp = head;for( int i=1; idata); p = p-next; p = p-next;p = head;for( int i=1; idata); p = p-next; p = p-next; p = p-next;AECBDheadCEDABCBADE 已知長度為已知長度為n的線性表的線性表A=(a1, a2, , an)。請將線性。請將線性表轉(zhuǎn)換為表轉(zhuǎn)換為A=(an, an-1, , a1)。 1）請寫出順序表求逆的算法）請寫出順序表求逆的算法 2）請寫出單鏈表求逆的算法）請寫出單鏈表求逆的算法/順序表求逆順序表求逆void SqReverse(L

33、) / SqReversea1a2a3a4a5a6a7a8a9 m=n/2; ElemType tpElem; for( i=0; inext;r=NULL; while(p) q = p-next; p-next = r; r = p; p = q; L-next = r;a1 .ana2 1）已知線性表中的元素以值遞增有序排列，并以單）已知線性表中的元素以值遞增有序排列，并以單鏈表為存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有鏈表為存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有值大于值大于mink且小于且小于maxk的元素的元素.aiai+1ax 2）已知線性表中的元素以值遞增有序排列，并以順）已知線性

34、表中的元素以值遞增有序排列，并以順序表為存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有序表為存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有值大于值大于mink且小于且小于maxk的元素的元素 。aiaxax+1 3）若線性表中的元素排列是隨機的，并以順序表為）若線性表中的元素排列是隨機的，并以順序表為存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有值大于存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有值大于mink且小于且小于maxk的元素的元素 。 mink = 7 maxk =16371561211094148 球鐘：一種通過小球來計時的設(shè)備。球鐘：一種通過小球來計時的設(shè)備。 假設(shè)有一臺機器，其中有一根管子，管子里順序放假設(shè)有一臺機器，其中有一根管子，管子里順序放有有n個球，每分鐘吐出一個球，現(xiàn)在通過它來計時個球，每分鐘吐出一個球，現(xiàn)在通過它來計時 球鐘有三個指示器：球鐘有三個指示器：分鐘指示器分鐘指示器五分鐘指示器五分鐘指示器小時指示器小時指示器5:32 球鐘的工作原理：球鐘的工作原理： 1）每分鐘機器從管子里吐出一個小球放到分鐘指示）每分鐘機器從管子里吐出一個小球放到分鐘指示器。當(dāng)放入第器。當(dāng)放入第5個小球時