歷界數(shù)據(jù)結(jié)構(gòu)考研試題集

歷界數(shù)據(jù)結(jié)構(gòu)考研試題集

第1章緒論

一、選擇題

1.算法的計(jì)算量的大小稱為計(jì)算的（）?！颈本┼]電大學(xué)2000二、3（20/8分）】

A.效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度

2.算法的時(shí)間復(fù)雜度取決于（）【中科院計(jì)算所1998二、1（2分）】

A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B

3.計(jì)算機(jī)算法指的是（1）,它必須具備（2）這三個(gè)特性。

（1）A.計(jì)算方法B.排序方法C.解決問題的步驟序列D.調(diào)度方法

（2）A.可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性

C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性

【南京理工大學(xué)1999、1（2分）【武漢交通科技大學(xué)1996一、1（4分）】

4.一個(gè)算法應(yīng)該是（）?！局猩酱髮W(xué)1998二、1（2分）】

A.程序B.問題求解步驟的描述C.要滿足五個(gè)基本特性D.A和C.

5.下面關(guān)于算法說法錯(cuò)誤的是（）【南京理工大學(xué)2000一、1（1.5分）】

A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)

B.為解決某問題的算法同為該問題編寫的程序含義是相同的

C.算法的可行性是指指令不能有二義性D.以上幾個(gè)都是錯(cuò)誤的

6.下面說法錯(cuò)誤的是（）【南京理工大學(xué)2000一、2（1.5分）】

（1）算法原地工作的含義是指不需要任何額外的輔助空間

（2）在相同的規(guī)模n下，復(fù)雜度0（n）的算法在時(shí)間上總是優(yōu)于復(fù)雜度0（2"）的算法

（3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界

（4）同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低

A.（1）B.（1）,（2）C.（1）,（4）D.（3）

7.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。【武漢交通科技大學(xué)1996一、4（2分）】

A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

8.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（）?！颈狈浇煌ù髮W(xué)2000二、1（2分）】

A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧

9.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）?【北方交通大學(xué)2001一、1（2分）】

A.廣義表B.二叉樹C.稀疏矩陣D.串

10.以下那一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（）【北方交通大學(xué)2001一、2（2分）】

A.棧B.哈希表C.線索樹D.雙向鏈表

11.在下面的程序段中，對(duì)x的賦值語句的頻度為（）【北京工商大學(xué)2001一、10（3

分）】

FORi:=lTOnDO

FORj:=lTOnDO

x:=x+l;

2

A.0（2n）B.0（n）C.0（n）D.0（log2"）

12.程序段FORi:=n-lDOWNTO1DO

FORj:=lTOiDO

IFA[j]>A[j+l]

THENA[j]與A[j+1]對(duì)換；

其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）

A.0（n）B.O（nlogn）C.0（n3）D.0（n2）【南京理工大學(xué)1998-、1（2分）】

13.以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）【中山大學(xué)1999一、3（1分）】

A.棧B.廣義表C.有向圖D.字符串

14.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)【中山大學(xué)1999一、4]

A.樹B.字符串C.隊(duì)D.棧

15.下列數(shù)據(jù)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。【北京理工大學(xué)2001六、1（2分）】

A.棧B.隊(duì)列C.完全二叉樹D.堆

16.連續(xù)存儲(chǔ)設(shè)計(jì)時(shí).，存儲(chǔ)單元的地址（）。【中山大學(xué)1999一、1（1分）】

A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)I）.部分連續(xù)，部分不連續(xù)

17.以下屬于邏輯結(jié)構(gòu)的是（）?！疚靼搽娮涌萍即髮W(xué)應(yīng)用2001一、1】

A.順序表B.哈希表C.有序表D.單鏈表

二、判斷題

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

【北京郵電大學(xué)1998一、1（2分）】【青島大學(xué)2000一、1（1分）】

【上海交通大學(xué)1998一、1]【山東師范大學(xué)2001一、1（2分）】

2.記錄是數(shù)據(jù)處理的最小單位。（）【上海海運(yùn)學(xué)院1998—、5（1分）】

3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；（）【北京郵電大學(xué)2002—、

1（1分）】

4.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）

【大連海事大學(xué)2001一、10（1分）】

5.健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（）

【大連海事大學(xué)2001一、11（1分）】

6.算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級(jí)語言來描述，則算法

實(shí)際上就是程序了。（）【西安交通大學(xué)1996二、7（3分）】

7.程序一定是算法?（）【燕山大學(xué)1998二、2（2分）并改錯(cuò)】

8.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。（）【山東師范大學(xué)2001—、

2（2分）】

9.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。（）【華南理工大學(xué)2002一、1（1分）】

10.在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（）

【華南理工大學(xué)2002一、2（1分）】

11.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）

【上海海運(yùn)學(xué)院1999一、1（1分）】

12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。（）

【華南理工大學(xué)2002一、5（1分）】

13.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu).（）

【上海海運(yùn)學(xué)院1998一、1（1分）】

三、填空

1.數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示?！狙嗌酱髮W(xué)1998一、1（2

分）】

2.對(duì)于給定的n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（1）,⑵，（3）,

（4）四種。

【中科院計(jì)算所1999二、1（4分）】

3.數(shù)據(jù)的邏輯結(jié)構(gòu)是指。【北京郵電大學(xué)2001二、1（2分）】

4.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中稱為存儲(chǔ)結(jié)構(gòu)。【華中理工大學(xué)2000一、1（1分）】

5.抽象數(shù)據(jù)類型的定義僅取決于它的一組（1）,而與（2）無關(guān),即不論其內(nèi)部結(jié)構(gòu)

如何變化，只要它的（3）不變,都不影響其外部使用?！旧綎|大學(xué)2001三、3（2分）】

6.數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是【北京理工大學(xué)2001七、1（2分）】

7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的（1）和（2）,以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)

定義相應(yīng)的（3）,設(shè)計(jì)出相應(yīng)的（4）?！疚靼搽娮涌萍即髮W(xué)1998二、2（3分）】

8.一個(gè)算法具有5個(gè)特性：（1）、⑵、⑶，有零個(gè)或多個(gè)輸入、有一個(gè)或多

個(gè)輸出。

【華中理工大學(xué)2000一、2（5分）】【燕山大學(xué)1998一、2（5分）】

9.已知如下程序段

FORi:=nDOWNTO1DO{語句1}

BEGIN

x:=x+l；{語句2}

FORj:=nDOWNTOiDO{語句3}

y:=y+l;{語句4}

END；

語句1執(zhí)行的頻度為（1）;語句2執(zhí)行的頻度為（2）；語句3執(zhí)行的頻度為（3）；

語句4執(zhí)行的頻度為（4）?！颈狈浇煌ù髮W(xué)1999二、4（5分）】

10.在下面的程序段中，對(duì)x的賦值語句的頻度為（表示為n的函數(shù)）

FORi：=1TOnDO

FORj：=1TOiDO

FORk：=1TOjDO

x：=x+delta；

【北京工業(yè)大學(xué)1999一、6（2分）】

11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是：【合肥工業(yè)大學(xué)1999三、1（2分）】

i：=1；WHILEi<nDOi：=i*2;

12.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（）?！竞戏使I(yè)大學(xué)2000三、

1（2分）】

i:=1;

WHILEi<nBEGINFORj:=lTOnDOx:=x+l;i:=i*2END；

13.下面程序段中帶有下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（）【合肥工業(yè)大學(xué)2001

三、1（2分）】

i：=n*nWHILEiOlDOi:=idiv2;

14.計(jì)算機(jī)執(zhí)行下面的語句時(shí)，語句s的執(zhí)行次數(shù)為?！灸暇├砉ご髮W(xué)2000二、1

（1.5分）】

FOR（i=l；i<n-l；i++）

FOR（j=n;j>=i;j—）

s：

15.下面程序段的時(shí)間復(fù)雜度為o（n>l）

sum=l；

for(i=0;sum<n;i++)sum+=l;【南京理工大學(xué)2001二、1(2分)】

16.設(shè)m.n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f(m,n)為這種表示方式的

數(shù)目。例f(5,3)=5,有5種表示方式：3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1?

①以卜是該函數(shù)的程序段，請(qǐng)將未完成的部分填入，使之完整

intf(m,n)

intm,n;

{if(m==l)

return(1);

if(n==l){

return(2);}

if(m<n)

{returnf(m,m);}

if(m==n)

{return1+(3);)

returnf(m.n-l)+f(m-n,(4));

)

②執(zhí)行程序，f(6,4)=o【中科院軟件所1997二、1(9分)】

17.在有n個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行場(chǎng)比賽。【合肥工業(yè)大學(xué)1999三、

8(2分)】

四、應(yīng)用題

1.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？【燕山大學(xué)1999二、1(4分)】

2.數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？【燕山大學(xué)1999二、

2(4分)】

3.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主

要特點(diǎn)是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？【北京郵電大學(xué)1994一(8分)】

4.回答問題(每題2分)【山東工業(yè)大學(xué)1997-(8分)】

(1)在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算之間存在著

怎樣的關(guān)系？

(2)若邏輯結(jié)構(gòu)相同但存儲(chǔ)結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對(duì)嗎？舉例

說明之。

(3)在給定的邏輯結(jié)構(gòu)及其存儲(chǔ)表示上可以定義不同的運(yùn)算集合，從而得到不同的數(shù)

據(jù)結(jié)構(gòu)。這樣說法對(duì)嗎？舉例說明之。

(4)評(píng)價(jià)各種不同數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么？

5.評(píng)價(jià)?個(gè)好的算法，您是從哪兒方面來考慮的？

【大連海事大學(xué)1996二、3(2分)】【中山大學(xué)1998三、1(5分)】

6.解釋和比較以下各組概念【華南師范大學(xué)2000一(10分)】

(1)抽象數(shù)據(jù)類型及數(shù)據(jù)類型(2)數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)

(3)抽象數(shù)據(jù)類型【哈爾濱工業(yè)大學(xué)2000一、1(3分)】

(4)算法的時(shí)間復(fù)雜性【河海大學(xué)1998一、2(3分)】

(5)算法【吉林工業(yè)大學(xué)1999一、1(2分)】

(6)頻度【吉林工業(yè)大學(xué)1999一、2(2分)】

7.根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般有哪兒類基本的數(shù)據(jù)結(jié)構(gòu)？

【北京科技大學(xué)1998一、1】【同濟(jì)大學(xué)1998】

8.對(duì)于■個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？【北京科技大學(xué)1999一、1（2分）】

9.當(dāng)你為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？【西安電子北京科技大學(xué)

2000]

10.若將數(shù)據(jù)結(jié)構(gòu)定義為一個(gè)二元組（D,R），說明符號(hào)D,R應(yīng)分別表示什么？

【北京科技大學(xué)2001一、1（2分）】

11.數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？【哈爾濱工業(yè)大學(xué)2001三、1（3分）】

12.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)由哪四種基本的存儲(chǔ)方法實(shí)現(xiàn)？【山東科技大學(xué)2001一、1（4分）】

13.若有100個(gè)學(xué)生，每個(gè)學(xué)生有學(xué)號(hào)，姓名，平均成績(jī)，采用什么樣的數(shù)據(jù)結(jié)構(gòu)最方便，

寫出這些結(jié)構(gòu)？

【山東師范大學(xué)1996二、2（2分）】

14.運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。試舉例，說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)方式

完全相同，只是對(duì)于運(yùn)算的定義不同。因而兩個(gè)結(jié)構(gòu)具有顯著不同的特性，是兩個(gè)不同的結(jié)

構(gòu)。

【北京大學(xué)1998—、1（5分）】

15.在編制管理通訊錄的程序時(shí)，什么樣的數(shù)據(jù)結(jié)構(gòu)合適？為什么？【長(zhǎng)沙鐵道學(xué)院1998

四、3（6分）】

16.試舉一例，說明對(duì)相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，其運(yùn)算效率

不同。

【北京理工大學(xué)2000三、1（4.5分）】

17.有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2,其中A1的時(shí)間復(fù)雜度為Tl=0（2"）,A2的時(shí)間復(fù)

雜度為T2=0（r?）,僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析這兩個(gè)算法哪一個(gè)好?！颈本┖娇蘸教?/p>

大學(xué)2000二（10分）】

18.設(shè)計(jì)嗷據(jù)結(jié)構(gòu)，用來表示某一銀行儲(chǔ)戶的基本信息：賬號(hào)、姓名、開戶年月日、儲(chǔ)

蓄類型、存入累加數(shù)、利息、帳面總數(shù)?！菊憬髮W(xué)1994一、3（5分）】

19.寫出下面算法中帶標(biāo)號(hào)語句的頻度。

TYPEar=ARRAY[l..n]OFdatatype;

PROCEDUREperm（a:ar;k,n:integer）;

VARx:datatype;i:integer;

BEGIN

（1）IFk=n

THENBEGIN

（2）FORi:=lTOnDO

（3）write（a[i]）;

writein;

END

ELSEBEGIN

（4）FORi:=kTOnDO

（5）a[i]:=a[i]+i*i;

（6）perm（a,k+1,n）;

END;

END;

設(shè)k的初值等于10

【北京郵電大學(xué)1997二（10分）】

20.分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。

i:=0;s:=0;n:=100;

REPEAT

i:=i+l;

s:=s+10*i;

UNTILNOT((i<n)AND(s<n));

【北京郵電大學(xué)1998四、1(5分)】

21.下列算法對(duì)一n位二進(jìn)制數(shù)加1,假如無溢出，該算法的最壞時(shí)間復(fù)雜性是什么？并分

析它的平均時(shí)間復(fù)雜性。

TYPEnum=ARRAY[1..n]of[0..1]；

PROCEDUREInc(VARa：num)；

VARi：integer；

BEGINi：=n；

WHILEA[i]=lDO

BEGINA[i]：=0；i：=i-l；END；

END；

A[i]：=1；

ENDInc；

【東南大學(xué)1998三(8分)1994二(15分)】

22.閱讀下列算法，指出算法A的功能和時(shí)間復(fù)雜性

PROCEDUREA(h,g:pointer);

(h,g分別為單循環(huán)鏈表(singlelinkedcircularlist)中兩個(gè)結(jié)點(diǎn)指針)

PROCEDUREB(s,q:pointer)；

VARp:pointer;

BEGIN

P：=s;

WHILEp^.nextOqDOp:=p\next;

p\next:=s;

END;(ofB)

BEGIN

B(h,g);B(g,h);

END;(ofA)

【東南大學(xué)1999二(10分)】

23.調(diào)用下列C函數(shù)f(n)或PASACAL函數(shù)f(n)回答下列問題：

(1)試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程；

(2)假定n=5,試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果o

C函數(shù)：intf(intn)

{inti,j,k,sum=0;

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

{for(j=n;j>i-l;j-)

for(k=l;k<j+l;k++)

sum++;

printf(〃sum=%d\n〃，sum)；

)

return(sum);

｝【華中理工大學(xué)2000六(10分)】

24.設(shè)n是偶數(shù)，試計(jì)算運(yùn)行下列程序段后m的值并給出該程序段的時(shí)間復(fù)雜度。

m:=0;

FORi:=lTOnDO

FORj:=2*iTOnDO

【南京郵電大學(xué)2000一、1】

25.有下列運(yùn)行時(shí)間函數(shù)：

232

(1)T,(n)=1000;(2)T2(n)=n+1000n;(3)T3(n)=3n+100n+n+l;

分別寫出相應(yīng)的大0表示的運(yùn)算時(shí)間。

【吉林工業(yè)大學(xué)1999二(12分)】

26.試給出下面兩個(gè)算法的運(yùn)算時(shí)間。

(1)fori-1tondo

x-x+1

END

(2)fori-1tondo

forj-1tondo

x-x+1

end

end

【中科院自動(dòng)化研究所1995二、2(6分)】

27.斐波那契數(shù)列Fn定義如下

F()=0,F|=l,Fn=Fn.1+Fn.2,n=2,3...

請(qǐng)就此斐波那契數(shù)列，回答下列問題。

(1)(7分)在遞歸計(jì)算F”的時(shí)候，需要對(duì)較小的F*”Fn一2，…,R,Fo精確計(jì)算多少次?

(2)(5分)如果用大。表示法，試給出遞歸計(jì)算可時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度錄多少？

【清華大學(xué)2000二(12分)】

28.將下列函數(shù)，按它們?cè)趎-8時(shí)的無窮大階數(shù)，從小到大排序。

(2〃、

n,n-n：i+7n0,nlogn,2"2,n\logn,n12+logn,(3/2)",),n!,n2+logn

【中科院計(jì)算所1995]

第2章線性表

-選擇題

1.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（）【北方交通大學(xué)2001一、4（2分）】

A.存儲(chǔ)密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)

的存儲(chǔ)表示

2.下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（）【北方交通大學(xué)2001一、14

（2分）】

A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。

B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。

C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。

D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。

3.線性表是具有n個(gè)（）的有限序列（n>0）o【清華大學(xué)1998一、4（2分）】

A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)E.信息項(xiàng)

4.若某線性表最常用的操作是存取任指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算,

則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。【哈爾濱工業(yè)大學(xué)2001二、1（2分）】

A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表

5.某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，

則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間?！灸祥_大學(xué)2000一、3]

A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的

單循環(huán)鏈表

6.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用（）最節(jié)省時(shí)

間。

A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

【合肥工業(yè)大學(xué)2000―、1（2分）】

7.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則

采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。【北京理工大學(xué)2000一、1（2分）】

A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

8.靜態(tài)鏈表中指針表示的是（）.【北京理工大學(xué)2001六、2（2分）】

A.內(nèi)存地址B.數(shù)組下標(biāo)C.下一元素地址D.左、右孩子地址

9.鏈表不具有的特點(diǎn)是（）【福州大學(xué)1998一、8（2分）】

A.插入、刪除不需要移動(dòng)元素B.可隨機(jī)訪問任一元素

C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性長(zhǎng)度成正比

10.下面的敘述不正確的是（）【南京理工大學(xué)1996一、10（2分）】

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è)元素的時(shí)間同i的值無關(guān)

11.線性表的表元存儲(chǔ)方式有（（1））和鏈接兩種。試指出下列各表中使用的是何種存

儲(chǔ)方式：表1是（（2））存儲(chǔ)方式；表2是（（3））存儲(chǔ)方式；表3是（（4））存儲(chǔ)方式；表

4是（（5））存儲(chǔ)方式。表左的s指向起始表元。

化m

表元編號(hào)貝節(jié)數(shù)量表元間聯(lián)系

1618402

220523

3103154表1

4501205S->

5781176

6910240

表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系表2

1618405

220521

3103154

4501202

5781176

6910243

表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系

1618405

220521

3103154

4501200

5781176

6910243

表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系

12

16184052

2205210

31031546

45012003

57811761

69102435

供選擇的答案：

A.連續(xù)B.單向鏈接C.雙向鏈接D.不連接E.循環(huán)鏈接

F.樹狀G.網(wǎng)狀H.隨機(jī)I.順序J.順序循環(huán)

【上海海運(yùn)學(xué)院1995二、1(5分)】

12.(1)靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，乂有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元

素的時(shí)間與i無關(guān)。

(2)靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。

(3)靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。

以上錯(cuò)誤的是()【南京理工大學(xué)2000一、3(1.5分)】

A.(1),(2)B.(1)C.(1),(2),(3)D.(2)

13.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入?個(gè)新元素的算法的時(shí)間

復(fù)雜度為()(l<=i<=n+l)?！颈本┖娇蘸教齑髮W(xué)1999一、1(2分)】

A.0(0)B.0(1)C.0(n)D.0(n2)

14.對(duì)于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為()。

A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)

【青島大學(xué)2000五、1(2分)】

15.線性表(al,a2,…,an)以鏈接方式存儲(chǔ)時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為()

A.0(i)B.0(1)C.0(n)D.0(i-1)【中山大學(xué)1999一、

2]

16.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)pt滿足()?！疚錆h大學(xué)2000二、10]

A.pt.link=headB.pt.link=NILC.p=NILD.p=head

17.循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是()。【中山大學(xué)1998二、2(2分)】

A.P".NEXT:=HB.P\NEXT:=H\NEXTC.P:=HD.P:=I「.NEXT

18.在一個(gè)以h為頭的單循環(huán)鏈中，p指針指向鏈尾的條件是()【南京理工大學(xué)1998一、

15(2分)】

A.p”.next=hB.p-.next=NILC.p-.next.八next=hD.p".data=-l

19.完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作是()；【北方交通大學(xué)1999一、4(3

分)】

A.p*.next:=s;s*.priou:=p;p*.next*.priou:=s;s*.next:=p\next;

B.p.next".priou:=s;p".next:=s;s".priou:=p;s.next:=p-.next;

C.s*.priou:=p;s*.next:=p".next;p".next:=s;p.next*.priou:=s;

D.s".priou:=p;s*.next:=p\next;p.next".priou:=s;p二next:=s;

20.在雙向循環(huán)鏈表中，在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指

針的操作是()?！颈本┼]電大學(xué)1998二、2(2分)】

注:雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(llink,data,rlink)。供選擇的答案：

A.pt.llink：=q；qt.rlink：=p；pt.llinkf.rlink：=q；qt.llink：

二q；

B.pt.llink：=q；pt.llinkt.rlink：=q；qt.rlink：=p；qt.llink:=p

t.llink；

C.qt.rlink：=p；qt.llink：=pt.llink；pt.llinkt.rlink：=q;pt.llink：

二q；

D.qf.llink:=pt.llink；qt.rlink:=p；pf.llink：=q；pt.llink：=q；(編者

按：原題如此)

21.在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的鏈結(jié)點(diǎn)的過程依次為：

rlink(p)-q;llink(p)-llink(q);llink(q)-p;()

A.rlink(q)-pB.rlink(llink(q))-pC.rlink(llink(p))-p

D.rlink(rlink(p))-p

【北京航空航天大學(xué)2000一、1(2分)】

22.雙向鏈表中有兩個(gè)指針域，llink和rlink,分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的

一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在P前插入q，則正確的插入為()【南京理工大

學(xué)1996一、1(2分)】

A.p.llink:=q;q人.rlink:=p;p人.llink八.rlink:二q;

q二llink:=p.llink;

B.q.llink:=p\llink;p八.llink.rlink:=q;q人.rlink:=p;

p二llink:=q.rlink;

C.rlink:=p;p\rlink:=q;p\llink.rlink:=q;q^.rlink:=p;

D.p二llink.rlink:=q;q\rlink:二p;q二llink:=p*.llink;p\llink:=q;

23.在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是()。【青島大學(xué)2000五、

2（2分）】

A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；

B.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

24.在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：()。

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

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

【青島大學(xué)2001五、3(2分)】

25.對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是()

A.head==NULLB.head-*-next==NULLC.head-next==headD.head!=NULL

【北京工商大學(xué)2001-、5（3分）】

26.在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。

A.(p-.llink)rlink:=p-.rlink(p".rlink)llink:=p\llink;

B.p".llink:=(p*,llink)llink(p*.llink)rlink:=p;

C.(p-.rlink)llink:=pp.rlink:=(p-.rlink)\rlink

D.p*.rlink:=(p*.llink)*.llinkp*.1link:=(p-.rlink)*.rlink;

【西安電子科技大學(xué)1998—、(2分)】

27.雙向鏈表中有兩個(gè)指針域，llink和rlink分別指向前趨及后繼，設(shè)p指向鏈表中的一

個(gè)結(jié)點(diǎn)，現(xiàn)要求刪去P所指結(jié)點(diǎn)，則正確的刪除是（）（鏈中結(jié)點(diǎn)數(shù)大于2,p不是第一

個(gè)結(jié)點(diǎn)）

A.p".llink".rlink:=p-.llink;p\llink".rlink:=p-.rlink;dispose(p);

B.dispose(p);p*.llink'.rlink:=p*.llink;p*.llink",rlink:=p*.rlink;

C.p.llink".rlink:=p.llink;dispose(p);p".llink".rlink:=p-.rlink;

D.以上A,B,C都不對(duì)?！灸暇├砉ご髮W(xué)1997一、1(2分)】

二、判斷

1.鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。（）【南京航空航天大學(xué)1997、1（1分）】

2.順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。（）【南京航空航天大學(xué)1997—、

2（1分）】

3.線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（）

【北京郵電大學(xué)1998一、2（2分）】

4.順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（）

【北京郵電大學(xué)2002-、2（1分）】

5.對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（）【南京航空航天大學(xué)1997

一、3（1分）】

6.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（）

【中科院軟件所1999六、1-2（2分）】【上海海運(yùn)學(xué)院1997一、1（1分）】

7.集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。（）【大連海事大學(xué)2001->5（1

分）】

8.所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。（）【合肥工業(yè)大學(xué)2000二、1（1分）】

9.線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（）【合肥工業(yè)大學(xué)2001二、1

（1分）】

10.取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān).（）【南京理工大學(xué)1997二、9（2

分）】

11.循環(huán)鏈表不是線性表.（）【南京理工大學(xué)1998二、1（2分）】

12.線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。（）【青島大學(xué)2001四、2（1分）】

13.線性表就是順序存儲(chǔ)的表。（）【青島大學(xué)200211（1分）】

14.為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（）

【上海海運(yùn)學(xué)院1995—,1（1分）】【上海海運(yùn)學(xué)院1997—、2（1分）】

15.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）

【上海海運(yùn)學(xué)院1996—>1（1分）】【上海海運(yùn)學(xué)院1999一、1（1分）】

16.鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)

構(gòu)中效率高。（）【上海海運(yùn)學(xué)院1998-、2（1分）】

三、填空

1.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取

線性表中的元素時(shí)，應(yīng)采用存儲(chǔ)結(jié)構(gòu)?！颈狈浇煌ù髮W(xué)2001二、4]

2.線性表L=（al,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一

個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是?！颈狈浇煌ù髮W(xué)2001二、9]

3.設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為（data,next）,next為指針域，己知指針px指向單鏈表中data

為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行

以下語句:；;【華中理工大學(xué)2000一、4（2分）】

4.在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（l〈=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)

個(gè)元素。

【北京工商大學(xué)2001二、4（4分）】

5.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是?！竟枮I工業(yè)大學(xué)2000二、1（1分）】

6.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入?個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為

_,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為?！竟枮I工業(yè)大

學(xué)2001一、1（2分）】

7.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成和

而又根據(jù)指針的連接方式，鏈表又可分成和?！疚靼搽娮涌萍即?/p>

學(xué)1998二、4（3分）】

8.在雙向循環(huán)鏈表中，向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是、

、、?！局袊V業(yè)大學(xué)2000一、1（3分）】

9.在雙向鏈表結(jié)構(gòu)中，若要求在p指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s所指的結(jié)點(diǎn)，則需執(zhí)

行下列語句：

s".next:=p；s".prior:=；p.prior:=s；:=s；

【福州大學(xué)1998二、7（2分）】

10.鏈接存儲(chǔ)的特點(diǎn)是利用來表示數(shù)據(jù)元素之間的邏輯關(guān)系?！局猩酱髮W(xué)1998-、

1（1分）】

H.順序存儲(chǔ)結(jié)構(gòu)是通過一一表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過—表

示元素之間的關(guān)系的?！颈本├砉ご髮W(xué)2001七、2（2分）】

12.對(duì)于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共個(gè)，單鏈表為

_______個(gè)。

【南京理工大學(xué)2000二、2（3分）】

13.循環(huán)單鏈表的最大優(yōu)點(diǎn)是：?！靖Ｖ荽髮W(xué)1998二、3（2分）】

14.已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是：

【合肥工業(yè)大學(xué)1999三、2(2分)】

15.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：一

【合肥工業(yè)大學(xué)1999三、32000三、2(2分)】

16.在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：【合肥工業(yè)大學(xué)2001三、

3(2分)】

17.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：o

【北京理工大學(xué)2000二、1(2分)】【青島大學(xué)2002三、1(2分)】

18.在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是：?！厩鄭u大學(xué)2002三、2(2分)】

19.請(qǐng)?jiān)谙铝兴惴ǖ臋M線上填入適當(dāng)?shù)恼Z句。【清華大學(xué)1994五(15分)】

FUNCTIONinclusion(ha,hb:linklisttp):boolean;

{以ha和hb