第一章 概論 測驗(yàn)

( B ) 1. 下列不屬于線性結(jié)構(gòu)的是：

Which one of the followings does not belong to linear structure: (There is only one correct answer)

A. 隊(duì)列(queue)

B. 圖(graph)

C. 向量(vector)

D. 散列表(hash table)

解析：A. 隊(duì)列：是線性表按操作分類的一種（先入先出）；B. 圖：無序；C. 向量：直接訪問型線性結(jié)構(gòu)；D. 散列表：目錄索引型線性結(jié)構(gòu)

( D ) 2. 以下哪種結(jié)構(gòu)是邏輯結(jié)構(gòu)，而與存儲(chǔ)和運(yùn)算無關(guān)：

Which of the following structure is a logical structure regardless of the storage or algorithm: (There is only one correct answer)

A. 雙鏈表(doubly linked list)

B. 順序表(Sequential list)

C. 數(shù)組(array)

D. 隊(duì)列(queue)

解析：A. 雙鏈表：鏈?zhǔn)酱鎯?chǔ)；B. 順序表：按索引值從小到大存放在一片相鄰的連續(xù)區(qū)域，定義了存儲(chǔ)結(jié)構(gòu)；C. 數(shù)組：按索引值從小到大存放在一片相鄰的連續(xù)區(qū)域，定義了存儲(chǔ)結(jié)構(gòu)；D. 隊(duì)列：可以是順序或鏈?zhǔn)酱鎯?chǔ)，是邏輯結(jié)構(gòu)

( AB ) 3. 關(guān)于算法特性描述正確的有：

Which one is right about algorithm’s characterization: (there are more than one correct answers)

A. 算法保證計(jì)算結(jié)果的正確性。Algorithm will ensure the correctness of the calculation results.

B. 算法的有窮性指算法必須在有限步驟內(nèi)結(jié)束。The finite nature of algorithms means algorithm must be completed within a limited step.

C. 組成算法的指令可以有限也可能無限。 Instructions which composite algorithms can be infinite or finite

D. 算法描述中下一步執(zhí)行的步驟不確定。 The next step in the implementation of the algorithm described is uncertain.

解析：A. 算法保證計(jì)算結(jié)果的正確性；B. 算法不能含有死循環(huán)，必須在有限步驟內(nèi)結(jié)束；C. 指令必須有限；D. 算法具有確定性

( CD ) 4. 下列說法正確的是：

Which options may be correct?（there are more than one correct answers）

A. 函數(shù)f(n)是O(g(n))，當(dāng)常數(shù)a足夠大時(shí)，一定有函數(shù)g(n)是O(af(n))【if f(n)是O(g(n))，When constant a is big enough ，there must be g(n) is O(af(n))】

B. 如果a>b>1,是，但不一定是【if a>b>1, is ，? may not be 】

C. 如果函數(shù)f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)是O(h(n))【? if f(n) is O(g(n))，g(n) is O(h(n))，then? f(n) is O(h(n))】

D. 如果函數(shù)f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)+g(n)是O(h(n))【if f(n) is O(g(n))，g(n) is O(h(n))，so f(n)+g(n) is O(h(n))】

解析：A. (4)當(dāng)f(n)=n,g(n)=n*2, 無論a多大，g(n)都不可能是O(af(n)).；B. (3)logan=log(n)/log(a),logbn=log(n)/log(b),所以前者與后者只差了一個(gè)常數(shù)項(xiàng)，所以logbn一定是O(logan). C. (1) 根據(jù)O()定義可知.；D. (2) 如果f(n)是O(g(n))，g(n)是O(h(n)), 則f(n)是O(h(n)),所以f(n)+g(n)是O(h(n))

( CD ) 5. 已知一個(gè)數(shù)組a的長度為n，求問下面這段代碼的時(shí)間復(fù)雜度:?

An array of a, its length is known as n. Please answer the time complexity of the following code.（There are more than one answers.）

for (i = 0, length = 1; i < n - 1; i++) {

? ? for (j = i + 1; j < n && a[j - 1] <= a[j]; j++)

? ? ? ? if(length<j-i+1)

? ? ? ? ? ? length=j-i+1;

}

A. θ(n * n)

B. O(n)

C. O(n * n)

D. Ω(n)

解析：D. 本代碼實(shí)際上是求a中有序子數(shù)組中最長的長度。譬如，在[1, 8, 1, 2, 5, 0, 11, 9]中，最長的是[1, 2, 5]，長度為3 。其時(shí)間復(fù)雜度與a中元素的實(shí)際取值狀態(tài)相關(guān)。 1)若a的所有元素是按照降序方式排列。則外層循環(huán)n-1次，每次內(nèi)層只執(zhí)行一次，整個(gè)開銷為θ(n) 2)若a的所有元素是按照升序方式排列。則外層循環(huán)n-1次，每次內(nèi)層需要執(zhí)行n-i-1次，整個(gè)開銷為θ(n^2) 所以，一般來說，時(shí)間復(fù)雜度是Ω(n)的，也是O(n^2)

6. 計(jì)算運(yùn)行下列程序段后m的值：

Calculate the value of m after running the following program segment

n = 9; m = 0;?

for (i=1;i<=n;i++)

? for (j = 2*i; j<=n; j++)

? ? m=m+1;

答案：20

解析：注意i從1到9全部遍歷，j分別從2，4，6,...開始遍歷到9，當(dāng)i大于5時(shí)，循環(huán)不再對m進(jìn)行操作.

i=1結(jié)束循環(huán)時(shí)，m=8；

i=2結(jié)束循環(huán)時(shí)，m=8+6=14；

i=3結(jié)束循環(huán)時(shí)，m=14+4=18；

i=4結(jié)束循環(huán)時(shí)，m=18+2=20；

7. 由大到小寫出以下時(shí)間復(fù)雜度的序列： 答案直接寫標(biāo)號(hào)，如：(1)(2)(3)(4)(5) （提示：系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）

Write the following time complexity in descending sequence:Write down the answer labels such as (1)(2)(3)(4)(5). （Hint：This problem is judged by string matching, Please make sure your answer don't contain any blanks. ）

(1) 2 ** n (pow(2, n))

(2) n ** 2.5 (pow(n, 2.5))

(3) n * log(a=5, x=4) ** 4 (n * pow(log(a=5, x=n), 4))

(4) 5 * n ** 2 (5 * pow(n, 2))

(5) 2 ** 2 ** n (pow(2, pow(2, n)))

答案：(5)(1)(2)(4)(3)

解析：計(jì)算復(fù)雜度時(shí)，系數(shù)是可以忽略的。(5)和(1)是指數(shù)級(jí)復(fù)雜度，大于(2)(3)(4)多項(xiàng)式級(jí)復(fù)雜度，區(qū)別在于指數(shù)中是否有n。而(5)的指數(shù)里還有指數(shù)級(jí)復(fù)雜度的表達(dá)式，(1)的指數(shù)是n，為多項(xiàng)式級(jí)，故(5)比(1)復(fù)雜。對于(2)(3)(4)，(2)的指數(shù)最大，為2.5，(4)的指數(shù)居中，為2，(3)的指數(shù)最小，解釋如下：logn的任意實(shí)數(shù)次方的復(fù)雜度都小于n，故(logn)^4比n復(fù)雜度低，故n*(logn)^4比n*n復(fù)雜度低，故(4)比(3)復(fù)雜，故答案為(5)(1)(2)(4)(3)

第二章 線性表測驗(yàn)

( ACD ) 1. 下面關(guān)于線性表的敘述中，正確的是哪些？

Which of the followings about linear list are correct?（There are more than one answers.）

Select the answer that matches

A. 線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。Linear lists using the linked storage, do not occupy a continuous memory units.

B. 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。Linear lists using sequential storage, it is easy to do insert and delete operations.

C. 線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。Linear lists using the linked storage, it is easy for insert and deleting operations.

D. 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。Linear lists use sequential storage which must occupy a continuous memory units.

解析：?A. 線性表采用鏈接存儲(chǔ)，在結(jié)點(diǎn)中存儲(chǔ)link信息，不需占用連續(xù)存儲(chǔ)單元；B. 采用鏈接存儲(chǔ)，便于插入和刪除操作，如果采用順序存儲(chǔ)，插入和刪除時(shí)需要大量移動(dòng)元素，參考數(shù)組的元素刪除；C. 采用鏈接存儲(chǔ)，便于插入和刪除操作；D. 順序存儲(chǔ)是按索引值從小到大存放在一片相鄰的連續(xù)區(qū)域

( CD ) 2. 下面的敘述中正確的是：

Select the answer that matches （There are more than one correct answers）

A. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值無關(guān)。When the linear list stored in linked form, the time to find the i-th element is regardless of the value of i.

B. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值成正比。When the linear list stored sequentially, the time to find the i-th element is proportional to value with i.

C. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，插入第i個(gè)元素的時(shí)間與i的數(shù)值成正比。When linear lists stored in the linked form, the time to insert the i-th element is proportional to value with i.

D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值無關(guān)。When the linear list stored sequentially, the time to find the i-th element is regardless of the value of i.

解析：?A. 因?yàn)榇鎯?chǔ)空間是不連續(xù)的，需要從頭或者尾結(jié)點(diǎn)開始查找元素，i越大，時(shí)間越長，時(shí)間不可能與i無關(guān)；C. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，插入第i個(gè)元素的時(shí)間與i的數(shù)值成正比。 因?yàn)榇鎯?chǔ)空間是不連續(xù)的，插入第i個(gè)元素不需要移動(dòng)其他元素。但是在插入之前從頭搜索到第i個(gè)元素的指針，所以插入時(shí)間跟i相關(guān)；D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間與i的數(shù)值無關(guān)。 因?yàn)榇鎯?chǔ)空間是連續(xù)的，直接由i可以得到元素位置

( AC ) 3. 完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作為：

The operation to insert s after the doubly circular linked list’s node p is: (There are more than one answers.)

A.p->next->prev=s; s->prev=p; s->next=p->next; p->next=s;?

B.p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

C.s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

D.s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

解析：?A. p->next->prev=s; s->prev=p; s->next=p->next; p->next=s; 最后更改p->next是正確的，否則會(huì)造成原來的p結(jié)點(diǎn)后來的next信息丟失；B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next; 先更改會(huì)造成原來的p結(jié)點(diǎn)后來的next信息丟失；C. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s; 最后更改p->next是正確的，否則會(huì)造成原來的p結(jié)點(diǎn)后來的next信息丟失；D. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s; 先更改p->next成s再更改p->next->prev，會(huì)造成原來的p結(jié)點(diǎn)后來的next信息丟失

4. 對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(___),在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(___)。（請依次填入,格式為(a)(b),如果您的答案中出現(xiàn)字母，請使用小寫;后一空系統(tǒng)基于字符匹配來判定答案，所以您的答案中不要出現(xiàn)空格）

For a single linked list with n nodes, and after a known node *p to insert a new node, the time complexity is O (___); after a given node with x value insert a new node, the time complexity is O (___). (If your answer contains letters, use lowercase one.The second blank is judged by string matching, Please make sure your answer don't contain any blanks. )

答案：(1)(n)

解析：已知結(jié)點(diǎn)后插入，不需要移動(dòng)其他結(jié)點(diǎn)位置，所以為O(1) 2. 先要查找到值為x的結(jié)點(diǎn)，需要O(n),再插入，不需要移動(dòng)其他結(jié)點(diǎn)位置，需要O(1)，總共需要O(n)+O(1)=O(n)

5. 設(shè)某循環(huán)鏈表長度為n，并設(shè)其中一節(jié)點(diǎn)為p1，然后按照鏈表的順序?qū)⒑竺娴墓?jié)點(diǎn)依次命名為p2,p3,...,pn，那么請問pn.next=____(答案為一個(gè)節(jié)點(diǎn)名，注意所有字母為小寫且答案中不包含空格)

答案：p1

解析：循環(huán)鏈表尾結(jié)點(diǎn)的next會(huì)指向頭結(jié)點(diǎn)

第三章 棧與隊(duì)列測驗(yàn)

( B ) 1. 設(shè)棧S 和隊(duì)列Q 的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6 個(gè)元素出隊(duì)的序列是e2，e4，e3，e6，e5，e1則棧S的容量至少應(yīng)該是_____________。

Assume that the stack S and queue Q’s initial state is empty, the elements e1, e2, e3, e4, e5 and e6 followed through stack S, an element out the stack means into the queue Q. If the sequence the six elements out of the queue is e2, e4, e3, e6, e5, e1 then stack S of capacity should be at least _____________. （There is only one correct answer）

A. 2

B. 3

C. 4

D. 6

解析：? B、隊(duì)列的特點(diǎn)是先進(jìn)先出，因此出隊(duì)的順序就是入隊(duì)的順序，也就是出棧的順序。因此，可以得到棧的狀態(tài)變化：

棧頂<-空 (初始狀態(tài))

棧頂<-e1 (e1入棧)

棧頂<-e2|e1 (e2入棧)

棧頂<-e1 (e2出棧)

棧頂<-e3|e1 (e3入棧)

棧頂<-e4|e3|e1 (e4入棧)

棧頂<-e3|e1 (e4出棧)

棧頂<-e1 (e3出棧)

棧頂<-e5|e1 (e5入棧)

棧頂<-e6|e5|e1 (e6入棧)

棧頂<-e5|e1 (e6出棧)

棧頂<-e1 (e5出棧)

棧頂<-空 (e1出棧)

可以看到，棧的容量至少為3。

( B ) 2. 現(xiàn)有中綴表達(dá)式E=((100-4)/3+3*(36-7))*2。以下哪個(gè)是與E等價(jià)的后綴表達(dá)式？

Existing infix expression E = ((100-4) / 3 + 3 * (36-7)) * 2. Which of the following is the equivalent postfix expression of E? （There is only one correct answer）

A. ( ( 100 4 – ) 3 / 3 ( 36 7 – ) * + ) 2 *

B. 100 4 – 3 / 3 36 7 – * + 2 *

C. * ( + / ( – 100 4 ) 3 * 3 ( – 36 7 ) ) 2

D. * + / – 100 4 3 * 3 – 36 7 2

( AB ) 3. 隊(duì)列的特點(diǎn)包括：

Queue’ features include:（There are more than one answers.）

A. 先進(jìn)先出First-in first-out (FIFO)

B. 后進(jìn)后出 Last-in last-out (LILO)

C. 后進(jìn)先出Last-in first-out (LIFO)

D. 先進(jìn)后出First-in last-out (FILO)

解析：? A、隊(duì)列的特點(diǎn)是先進(jìn)先出，后進(jìn)后出

( CD ) 4. 以下循環(huán)隊(duì)列的實(shí)現(xiàn)方式中，長度為n的隊(duì)列，所能容納的元素個(gè)數(shù)也為n的有:

In the following realizing ways of circular queue, the queue whose length is n can also contain the number of n elements is:（There are more than one answers.）

A. 只用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，兩個(gè)指針均為實(shí)指Only use front and rear as the queue’s head and tail pointers and the two pointers are actually referring to.

B. 只用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，兩個(gè)指針均為虛指Only use front and rear as the queue’s head and tail pointers and the two pointers are virtually referring to.

C. 用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，并用布爾型變量empty記錄隊(duì)列是否為空With the queue’s head and tail pointers marked as front and rear, use Boolean variable empty record whether the queue is empty.

D. 用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，并用整型變量len記錄隊(duì)列元素?cái)?shù)With the queue’s head and tail pointers marked as front and rear, use the integer variable len to record the number of elements.

解析：? D、只用front和rear兩個(gè)指針標(biāo)記隊(duì)列的頭和尾，無法區(qū)分空隊(duì)列和滿隊(duì)列兩種狀態(tài)，所以只能容納n-1個(gè)元素。而增加len或empty都可以區(qū)分這兩種狀態(tài)，因此可以容納n個(gè)元素

5. 編號(hào)為1，2，3，4的四輛列車，順序開進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)；則開出車站的順序有______種可能。 注釋：例如 1, 2, 3, 4 或 4, 3, 2，1 就是其中兩種可能出站序列；而 4, 3, 1, 2 是 非法序列。

Numbered 1,2,3,4 four trains, orderly entered a stack structure station. How many possible leaving sequences of that four trains ? ______ . Note: For instance, the leaving sequence could be 1,2,3,4 or 4,3,2,1 these two possibilities, but 4, 3, 1, 2 is not a possible sequence.

答案：14

解析： 出棧次序是經(jīng)典的問題，與組合數(shù)學(xué)中的卡特蘭數(shù)密切相關(guān)，以下只介紹樸素的思路。

先進(jìn)站的車可以先開，也可以后開。只有一種情況不可能：編號(hào)大的車開出后，比其編號(hào)小的車反序開出。也即編號(hào)大的車開出后，編號(hào)比其小的車只能由大到小依次開出（中間可以插入編號(hào)更大的車，但此車后面的編號(hào)小的車也要遵守此規(guī)則）。例如312的開出順序是不可能的。對所有車進(jìn)行全排列共有24種出法。但4開頭的只能有一種：4321。所以少了3的全排列-1=5種。三開頭的時(shí)候，必須先2后1開出，先1后2時(shí)4的位置有三種：3124、3142、3412，所以少了三種。1或2開頭的時(shí)候，后面的車如果是4，則最后兩輛必須是3、2或3、1。所以又少了1423、2413兩種?？偣采倭?+3+2=10種，有24-10=14種開出法。

下面用+表示進(jìn)站，-表示出站：

1234：1+ ;1- ;2+ ;2- ;3+ ;3- ;4+ ;4-

1243：1+ ;1- ;2+ ;2- ;3+ ;4+ ;4- ;3-

1324：1+ ;1- ;2+ ;3+ ;3- ;2- ;4+ ;4-

1342：1+ ;1- ;2+ ;3+ ;3- ;4+ ;4- ;2-

1432：1+ ;1- ;2+ ;3+ ;4+ ;4- ;3- ;2-

2134：1+ ;2+ ;2- ;1- ;3+ ;3- ;4+ ;4-

2143：1+ ;2+ ;2- ;1- ;3+ ;4+ ;4- ;3-

2314：1+ ;2+ ;2- ;3+ ;3- ;1- ;4+ ;4-

2341：1+ ;2+ ;2- ;3+ ;3- ;4+ ;4- ;1-

2431：1+ ;2+ ;2- ;3+ ;4+ ;4- ;3- ;1-

3214：1+ ;2+ ;3+ ;3- ;2- ;1- ;4+ ;4-

3241：1+ ;2+ ;3+ ;3- ;2- ;4+ ;4- ;1-

3421：1+ ;2+ ;3+ ;3- ;4+ ;4- ;2- ;1-

4321：1+ ;2+ ;3+ ;4+ ;4- ;3- ;2- ;1-;

6填空(2分)

雙端隊(duì)列可以在隊(duì)列的兩端進(jìn)行插入和刪除操作，既可在隊(duì)尾進(jìn)行插入/刪除，又可在隊(duì)頭進(jìn)行插入/刪除。現(xiàn)有4個(gè)不同的元素順序輸入到雙端隊(duì)列，那么可以得到_____種不同的排列。

double-ended queue can insert and delete operations on both ends of the queue. That it can insert / delete at its tail, but also at the head. Existing 4 different elements sequentially input to the double-ended queue, you can get _____ different permutations.

答案：8

解析： 第一個(gè)元素從左或右入隊(duì)沒有區(qū)別，以后每個(gè)元素都有從左和從右兩種入隊(duì)方式，即有2^{x-1}種方法