數(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ù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象。典典型的存儲(chǔ)結(jié)構(gòu)：型的存儲(chǔ)結(jié)構(gòu)：順序和鏈?zhǔn)巾樞蚝玩準(zhǔn)?. ADT：是對(duì)數(shù)據(jù)結(jié)構(gòu)的一種更準(zhǔn)確的抽象描述，它：是對(duì)數(shù)據(jù)結(jié)構(gòu)的一種更準(zhǔn)確的抽象描述，它忽略了數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)步驟，將更多的注意力忽略了數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)步驟，將更多的注意力放在數(shù)據(jù)的基本操作上，通過基本操作描述數(shù)據(jù)的放在數(shù)據(jù)的基本操作上，通過基本操作描述數(shù)據(jù)的邏輯關(guān)系。它包括三個(gè)部分：邏輯關(guān)系。它包括三

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

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

4、問題規(guī)模的（）題規(guī)模的（） A. 4倍倍 B. 8倍倍 C. 64倍倍 D. 16倍倍 5、下面程序段的時(shí)間復(fù)雜度為（）、下面程序段的時(shí)間復(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個(gè)具有個(gè)具有相同類型相同類型的數(shù)據(jù)元素構(gòu)成的的數(shù)據(jù)元素構(gòu)成的有限有限序列序列線性表的存儲(chǔ)線性表的存儲(chǔ)鏈序存儲(chǔ)鏈序存儲(chǔ)(鏈表鏈表)順序存儲(chǔ)順序存儲(chǔ)(順序表順序表)雙向循環(huán)鏈表雙向循環(huán)鏈表單向循環(huán)鏈表單向循環(huán)鏈表單鏈表單鏈表

5、鏈表的靜態(tài)存儲(chǔ)鏈表的靜態(tài)存儲(chǔ)結(jié)構(gòu)性結(jié)構(gòu)性操作操作ListEmpty( L ) /判斷線性表是否為空判斷線性表是否為空ListLength( L ) /求線性表的長度求線性表的長度GetElem( L, i, &e ) /讀取第讀取第i個(gè)元素的值個(gè)元素的值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 ) /初始化一個(gè)線性表初始化一個(gè)線性表DestroyList( &L ) /刪除線性表刪除線性表 0 1 . i-2 i-1 . n-1a1a2ai-1aiantypedef struct ElemType *elem; / 存儲(chǔ)空間基址存儲(chǔ)空間基址 int length; / 當(dāng)前長度當(dāng)前長度 int listsize; / 當(dāng)前分配的存儲(chǔ)容量當(dāng)前分配的存儲(chǔ)容量 / (以以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個(gè)元素個(gè)元素后移后移一一位位3) 將新元素將新元素e寫入寫入到第到第i個(gè)位置個(gè)位置4) 將表的長度將表的長度加加1操作步驟操作步驟1) 判斷位置合法判斷位置合法性性2)將第將第i個(gè)位置的個(gè)位置的值賦給變量值賦給變量e3)依次后依次后length-i+1個(gè)元素個(gè)元素前移前移一一位

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

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

10、 1、設(shè)置一個(gè)計(jì)數(shù)器、設(shè)置一個(gè)計(jì)數(shù)器j j； 2 2、設(shè)置一個(gè)依次向后移動(dòng)的指針、設(shè)置一個(gè)依次向后移動(dòng)的指針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個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)修改其后繼指針修改其后繼指針ListDelete(&L, i, e)找到線性表中第找到線性表中第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)修改其后繼指針修改其后繼指針ai-1aiai+1ai-1pq = pnext; pnext = qnext ;free(

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

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

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

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

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

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

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

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

19、 an na a2 2a a1 1棧頂棧頂棧底棧底出棧出棧進(jìn)棧進(jìn)棧 隊(duì)列：隊(duì)列： 一端插入，另一端刪一端插入，另一端刪除除 從尾進(jìn)，從頭出從尾進(jìn)，從頭出 隊(duì)列的特點(diǎn)：隊(duì)列的特點(diǎn)： 先進(jìn)先出的線性表先進(jìn)先出的線性表 FIFO-First in First outa a1 1a an-1n-1a an n出隊(duì)列出隊(duì)列進(jìn)隊(duì)列進(jìn)隊(duì)列隊(duì)首隊(duì)首隊(duì)尾隊(duì)尾 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)：在鏈表開始插入一個(gè)新節(jié)點(diǎn)：在鏈表開始插入一個(gè)新節(jié)點(diǎn) Pop(&S, &e)：刪除鏈表第一個(gè)節(jié)點(diǎn)：刪除鏈表第一個(gè)節(jié)點(diǎn)topa1 .ana2 EnQueue(&Q, e)，DeQueue(&Q, &e) 鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列 EnQueue(&Q, e)：在鏈表

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

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

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

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

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

26、C. 僅修改隊(duì)頭指針僅修改隊(duì)頭指針 D. 僅修改隊(duì)尾指針僅修改隊(duì)尾指針 9、一個(gè)棧的輸入序列為：一個(gè)棧的輸入序列為：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. 在單鏈表中在單鏈表中,指向第一個(gè)結(jié)點(diǎn)的指針定義了該鏈表指向第一個(gè)結(jié)點(diǎn)的指針定義了該鏈表2. 能夠通過在鏈表的表頭不斷插入新結(jié)點(diǎn)來創(chuàng)建一個(gè)能夠通過在鏈表的

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

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

29、個(gè)結(jié)點(diǎn)之間的地址 。 A必須連續(xù)必須連續(xù) B不一定連續(xù)不一定連續(xù) C任意任意 6、在非空鏈表中，在由、在非空鏈表中，在由p指向的結(jié)點(diǎn)后面插入一個(gè)指向的結(jié)點(diǎn)后面插入一個(gè)由由q指向的結(jié)點(diǎn)過程是：指向的結(jié)點(diǎn)過程是： 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é)點(diǎn)的直接后繼所指向的結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的過程是：結(jié)點(diǎn)的過程是： 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é)點(diǎn)前插入指向結(jié)點(diǎn)前插入一個(gè)由一個(gè)由p指向的結(jié)點(diǎn)的過程是：指向的結(jié)點(diǎn)的過程是： 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)鏈表實(shí)現(xiàn)的隊(duì)列如用靜態(tài)鏈表實(shí)現(xiàn)的隊(duì)列如右圖所示右圖所示:front = 9, rear = 7. 隊(duì)列有頭結(jié)點(diǎn)隊(duì)列有頭結(jié)點(diǎn) 當(dāng)執(zhí)行下列操作時(shí)當(dāng)執(zhí)行下列操作時(shí),隊(duì)列隊(duì)列有什么變化有什么變化? 1) 元素元素S入隊(duì)入隊(duì) 2) 隊(duì)首元素出隊(duì)隊(duì)首元素出隊(duì)0A11B32C43D64E105F76G87H08I09J210K5spacefrontrear0A31S02C43D64E105F76G87H18I09J210K5spacefrontrear0A21S02C33D64E105F76G87H18I09J410K5spacefrontrear1) 元素元素S入隊(duì)入隊(duì)2) 隊(duì)首元素

32、出隊(duì)隊(duì)首元素出隊(duì)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)。請(qǐng)將線性。請(qǐng)將線性表轉(zhuǎn)換為表轉(zhuǎn)換為A=(an, an-1, , a1)。 1）請(qǐng)寫出順序表求逆的算法）請(qǐng)寫出順序表求逆的算法 2）請(qǐng)寫出單鏈表求逆的算法）請(qǐng)寫出單鏈表求逆的算法/順序表求逆順序表求逆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）已知線性表中的元素以值遞增有序排列，并以單）已知線性表中的元素以值遞增有序排列，并以單鏈表為存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有鏈表為存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有值大于值大于mink且小于且小于maxk的元素的元素.aiai+1ax 2）已知線性表中的元素以值遞增有序排列，并以順）已知線性

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