數(shù)據(jù)結構習題1

《數(shù)據(jù)結構》試卷及答案1．算法分析的目的是(

c

)。A.找出數(shù)據(jù)結構的合理性

B.研究算法中輸入和輸出的關系

C.分析算法的效率以求改進

D.分析算法的易懂性和文檔性

2．（

b

）是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

A.數(shù)據(jù)符號

B.數(shù)據(jù)對象

C.數(shù)據(jù)

D.數(shù)據(jù)結構3．用鏈表表示線性表的優(yōu)點是(

C

)。A.便于隨機存取

B.花費的存儲空間比順序表少

C.便于插入與刪除

D.數(shù)據(jù)元素的物理順序與邏輯順序相同

4．輸入序列為（A,B,C,D）不可能的輸出有（d

）。

A.(A,B,C,D)

B.

(D,C,B,A)

C.

(A,C,D,B)

D

.

(C,A,B,D)5．在數(shù)組表示的循環(huán)隊列中，front、rear分別為隊列的頭、尾指針，maxSize為數(shù)組的最大長度，隊滿的條件是(

b

)。A.

front=maxSize

B.

(rear+1)%maxSize=front

C.

rear=maxSize

D.

rear=front

6．設有串t='I

am

a

good

student

'，那么Substr(t,6,6)=（D

）包含第六個A.

student

B.

a

good

s

C.

good

D.

a

good7．設有一個對稱矩陣A，采用壓縮存儲方式，以行序為主序存儲a11為第一個元素，其存儲地址為1，每個元素占一個地址空間，則a85地址為（

B

）。

A.23

B.33

C.18

D.

408．已知廣義表

LS=(A,(B,C,D),E)運用head和tail函數(shù)，取出LS中原子b的運算（C

）。

A.

Gethead(Gethead(LS))

B.

Gettail(Gethead(LS))

C.

Gethead(Gethead(Gettail(LS)))

D.

Gethead(Gettail(LS))

9．若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為(A

)

。ABECDFA.

CDBGFEA

B.

CDBFGEA

GC.

CDBAGFE

D.

BCDAGFE

10．下列存儲形式中，(c

)

不是樹的存儲形式。A.雙親表示法

B.左子女右兄弟表示法C.廣義表表示法

D.順序表示法

11．對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是(C

)。A.直接選擇排序

B.直接插入排序C.快速排序

D.起泡排序

12．采用折半查找方法進行查找，數(shù)據(jù)文件應為（A

），且限于（

）。A.有序表

順序存儲結構

B.有序表

鏈式存儲結構

C.隨機表

順序存儲結構

D.隨機表

鏈式存儲結構

13．就平均查找速度而言，下列幾種查找速度從慢至快的關系是（B

）A.順序折半哈希分塊

B.順序分塊折半哈希

C.分塊折半哈希順序

D.順序哈希分塊折半14．執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為（D

）for(int

I=1;I<=n;I++)

for(int

j=1;j<=I;j++)

S;

A.

n2

B.

n2/2

C.

n(n+1)

D.

n(n+1)/2

15．串是一種特殊的線性表，其特殊性體現(xiàn)在（B）A.可以順序存儲

B.數(shù)據(jù)元素是一個字符

C.可以鏈接存儲

D.數(shù)據(jù)元素可以是多個字符

16．樹的基本遍歷策略分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。結論(A

)是正確的。A.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同

B.樹的后根遍歷序列與其對應的二叉樹的先序遍歷序列相同

C.樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同

D.以上都不對

17．由五個分別帶權值為9，2，3，5，14的葉子結點構成的一棵哈夫曼樹，該樹的帶權路徑長度為(C

)。

A.

60

B.

66

C.

67

D.

50

18．一棵二叉樹有67個結點，這些結點的度要么是0，要么是2。這棵二叉樹中度為2的結點有(

A)個A.

33

B.

34

C.

32

D.

30

19．有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當二分查找值82為的結點時，（C）次比較后查找成功。A.

1

B.

2

C.

4

D.

8

20．若有文件的關鍵字序列為：D[265]

[301]

[751]

[129]

[937]

[863]

[742]

[694]

[076]

[438]，以下為二路歸并排序過程。第二趟為:

A.[265

301]

[129

751]

[863

937]

[694

742]

[076

438]

B.[076

129

265

301

438

694

742

751

863

937]

C.[129

265

301

694

742

751

863

937]

[076

438]

D.[129

265

301

751]

[694

742

863

937]

[076

438]

二、填空題（本大題共6小題，每空2分，共12分；答案填在下表內）

1

算法是指令的有限序列，其中每一條指令表示一個或多個操作，此外，一個算法還具有五個重要特性，它們分別是_______

、______

、________

、有零或多個輸入和有一或多個輸出。

2

算法優(yōu)劣的五個標準是正確性、可使用性、______、______、_____。

3

有n個球隊參加的足球聯(lián)賽按主客場制進行比賽，共需進行_________場比賽。4

設有串t='I

am

a

student

'，s='good'，那么Concat(t,s)=

'I

am

a

student

good'，Substr(t,8,7)=

__________。

5

在解決計算機主機與打印機之間速度不匹配時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應該是一個_________

結構，其主要特點是__________。

6

廣義表((a),a)的表頭是_______，表尾是_______。

三、判斷題（對的打“√”，錯的打“×”。每小題1分，共10分;答案填在下表內）1數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內容和形式無關。2

三個結點的二叉樹和三個結點的樹一樣，都具有三種不同的形態(tài)。3中序序列和后序序列相同的二叉樹為：空樹和缺右子樹的單支樹。4對于兩棵具有相同關鍵字集合而形狀不同的二叉排序樹，中序遍歷后得到的關鍵字排列順序相同。5

序列{30，40，50，15，25，35，38，10}是堆。6

對于無向圖的生成樹，從同一頂點出發(fā)所得的生成樹相同。7

若設哈希表長m=14，哈希函數(shù)H(key)=key%11，表中已有4個結點。addr(15)=4

addr(38)=5

addr(61)=6

addr(84)=7

其余地址為空，如用二次探測再散列處理沖突，關鍵字為49的結點的地址是9。8一個深度為k的，具有最少結點數(shù)的完全二叉樹按層次，(同層次從左向右)用自然數(shù)依此對結點編號則，則編號最小的葉子的序號是2k-2+1

；編號是i的結點所在的層次號是「log2i|+1。（「log2i|表示向上取整」（根所在的層次號規(guī)定為1層）。9在一棵7階B樹中，一個結點中最多有6棵子樹，最少有3棵子樹。10算法可以沒有輸入，但是必須有輸出。五、要求題（本大題共2小題，共12分）設關鍵字的輸入序列為{4，5，7，2，1，3，6}1．（8分）從空樹開始構造平衡二叉樹，畫出每加入一個新結點時二叉樹的形態(tài)，若發(fā)生不平衡，指明需做的平衡旋轉類型及平衡旋轉的結果。（4分）上面的數(shù)據(jù)作為待排序的數(shù)據(jù)，寫出用快速排序進行一趟劃分后的數(shù)據(jù)序列數(shù)據(jù)結構試卷A答案選擇題（本大題共20小題，每題1分，共20分；答案填在下表內）12345678910C

B:

C:

D:

B:

D:

B:

C:

A:

C11121314151617181920:

CA:

B:

D:

B:

A:

C:

ACD

二、填空題（本大題共5小題，每空1分，共12分；答案填在下表內）

1

有窮性

確定性

可行性

2

可讀性

健壯性

效率

3

n(n-1)

4

'student'

5

隊列

先進先出

6

(a)

(a)

三、判斷題（對的打“√”，錯的打“×”。每小題1分，共10分）1）true

;

2）flase;

3）true;

4）true;

5）flase;6）flase

;

7）true;

8）true;

9）flase;

10）true

第2

學期

數(shù)據(jù)結構試卷A

選擇題（本大題共15小題，每題2分，共30分；答案填在下表內）1.從一個長度為100的順序表中刪除第30個元素時需向前移動

個元素A、70

B、71

C、69

D、302.在一個具有N個單元的順序表中,假定以地址低端(即下標為1的單元)作為底,以top作為頂指針,則當做進棧處理時top變化為______。A、top不變

B、top=0

C、top=top-1

D、top=top+13.從一個具有n個結點的單鏈表中查找其值等于x結點時,在查找成功情況下,則平均比較____個結點。

A、n

B、n/2

C、(n-1)/2

D、(n+1)/24.在一個單鏈表中,若要刪除p指針所指結點的后繼結點,則執(zhí)行A、p->

next;

p->

next=p->

next->

next;B、p->

next=p->

next->

next;C、p=p->

next;D、p=p->

next->>next;5.在一個鏈隊列中,假定front和rear分別為隊首和隊后指針,則進行插入S結點的操作時應執(zhí)行___。A、front->

next=s；

front=s；B、s->

next=rear;

rear=s；C、rear->

next=s;

rear=s；D、s->

next=front;

front=s；6.在一棵度為3的樹中度為3的結點數(shù)為3個,度為2的結點數(shù)為1個,度為1的結點數(shù)為1個,那么度為0的結點數(shù)為____個A、6

B、7

C、8

D、97.假定一棵二叉樹的結點數(shù)為33個,則它的最小高度為__,最大高度為___A、4,33

B、5,33

C、6,33

D、6,328.

在一棵完全二叉樹中,若編號為i的結點有右孩子,則該結點的右孩子編號為___。A、2i

B、2i+1

C、2i-1

D、i/29.在一個有向圖中,所有頂點的入度之和等于所有弧數(shù)和___倍。

A、1

B、2

C、3

D、410.對于一個具有N個頂點的圖,若用鄰接矩陣表示,則該矩陣的大小為___。

A、

N

B、(N-1)2

C、(N+1)2

D、

N211.已知一個圖如圖所示，在該圖的最小生成樹中各邊上數(shù)值之和為____。A、21

B、26

C、28

D、33

12.已知一個圖如圖所示，由該圖行到的一種拓樸序列為

A、v1

v4

v6

v2

v5

v3

B、v1

v2

v3

v4

v5

v6

C、v1

v4

v2

v3

v6

v5

D、v1

v2

v4

v6

v3

v5

13.二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M[2][4]的起始地址與M按列存儲時元素

的起始地址相同。

A、m[2][4]

B、M[4][2]

C、M[3][1]

D、M[3][1]14.具有6個結點的無向圖至少應有

條邊才能保證是連通圖。5

B、6

C、

7

D、

8

15.采用鄰接表存儲的圖的深度優(yōu)先遍歷類似于二叉樹的

。A

先序遍歷B中序遍歷

C.

后序遍歷

D.

按層遍歷

二、填空題（本大題共5小題，每空1分，共8分；答案填在下表內）12345678

1.數(shù)據(jù)結構是研究數(shù)據(jù)元素之間抽象化的相互關系和這種關系在計算機中的存儲結構表示，根據(jù)數(shù)據(jù)元素之間關系的不同特性，通常有下列四類基本結構：集合、線性結構、（1）

和

（2）

。2.評價算法的標準很多，通常是以執(zhí)行算法所需要的

（3）和所占用的（4）來判別一個算法的優(yōu)劣。3.線性表的順序存儲結構特點是表中邏輯關系相鄰的元素在機器內的（5）也是相鄰的。4.空格串的長度為串中所包含

（6）

字符的個數(shù)，空串的長度為

（7）

5.加上表示指向前驅和

（8）

的線索的二叉數(shù)稱為線索二叉樹。

三、判斷題（對的打“√”，錯的打“×”。每小題1分，共10分）（

）1.線性表的唯一存儲形式是鏈表。（

）2.已知指針P指向鍵表L中的某結點，執(zhí)行語句P=P-〉next不會刪除該鏈表中的結點。（

）3.在鏈隊列中，即使不設置尾指針也能進行入隊操作。（

）4.如果一個串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（

）5.設與一棵樹T所對應的二叉樹為BT，則與T中的葉子結點所對應的BT中的結點也一定是葉子結點。（

）6.快速排序是不穩(wěn)定排序。（

）7.任一AOE網中至少有一條關鍵路徑，且是從源點到匯點的路徑中最短的一條。（

）8.若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1，并且權值最小的邊有多條（其中n為G的頂點數(shù)）。（

）9.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（）10.基數(shù)排序是多關鍵字排序。從最低位關鍵字起進行排序。

四、應用題。（共44分）2.假設用于通信的電子由字符集{a,b,c,d,e,f,g,h}中的字母構成，這8個字母在電文中出現(xiàn)的概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}畫出哈夫曼樹，并為這8個字母設計哈夫曼編碼。（8分）

3.

已知序列{70，73，69，23，93，18,11，68}請給出直接插入排序作升序排序每一趟的結果和快速排序作升序排序時一趟的結果。（10分）

4.設有一組關鍵字關鍵碼集為{47，7，29，11，16，92，22，8，3}，哈希表表長為11，Hash(key)=key

mod

11，用線性探測法處理沖突，構造哈希表，并求它成功查找的ASL。（8分）

5.

二叉樹的先序遍歷序列為

A

B

C

D

E

F

G

H

I，中序遍歷序列為

B

C

A

E

D

G

H

F

I，畫出這棵二叉樹。(6分)參考答案及評分標準選擇題本大題共15小題，每題2分，共30分

123456789101112131415ADDBCCCBADBADAA填空題（本大題共5小題，每空1分，共8分）

12345678樹型結構圖型結構時間空間位置空格零后繼

三、判斷題（每小題1分，共10分）12345678910×√√××√××××

應用題44分）1.（12分）011000101000100001010010000101001010DFS序列:ABDEFCBFS序列:ABCDFE2.

（8分）7192632321100010100000000010100001110113.

（10分）

直接插入排序70，73，69，23，93，18,11，68[70，73]，69，23，93，18,11，68

[70，69，73]，23，93，18,11，68

[23,70，69，73]，93，18,11，68

[23,70，69，73，93]，18,11，68

[18,23,70，69，73，93]，11，68[11，18,23,70，69，73，93]，68[11，18,23,68,70，69，73，93]快速排序[68,11,69,23,18]

,70,[93,73]4.

（8分）

0

1

2

3

4

5

6

7

8

9

101122

47921637298

ASL=5/3第一部分選擇題一、單項選擇題（本大題共14小題，每小題1分，共14分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內。1.算法分析的目的是()A.找出數(shù)據(jù)結構的合理性B.研究算法中的輸入/輸出關系C.分析算法的效率以求改進D.分析算法的易讀性2.在需要經常查找結點的前驅與后繼的場合中，使用()比較合適。A.單鏈表B.雙鏈表C.順序表D.循環(huán)鏈表3.下面關于線性表的敘述中，錯誤的為()A.順序表使用一維數(shù)組實現(xiàn)的線性表B.順序表必須占用一片連續(xù)的存儲單元C.順序表的空間利用率高于鏈表D.在鏈表中，每個結點只有一個鏈域4.帶頭結點的單鏈表head為空的判斷條件是()A.head=NILB.head↑.next=NILC.head↑.next=headD.head<>NIL5.隊列通常采用兩種存儲結構是()A.順序存儲結構和鏈表存儲結構B.散列方式和索引方式C.鏈表存儲結構和數(shù)組D.線性存儲結構和非線性存儲結構6.按照二叉樹的定義，具有3個結點的二叉樹有()種。A.3B.4C.5D.68.深度為5的二叉樹至多有()個結點。A.16B.32C.31D.109.對于一個具有n個頂點的無向圖，若采用鄰接表表示，則存放表頭結點的數(shù)組的大小為()A.nB.n+1C.n-1D.n+邊數(shù)10.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要()條邊。A.nB.n+1C.n-1D.n/211.靜態(tài)查找表與動態(tài)查找表二者的根本差別在于()A.它們的邏輯結構不一樣B.施加在其上的操作不同C.所包含的數(shù)據(jù)元素的類型不一樣D.存儲實現(xiàn)不一樣12.散列文件使用散列函數(shù)將記錄的關鍵字值計算轉化為記錄的存放地址。因為散列函數(shù)不是一對一的關系，所以選擇好的()方法是散列文件的關鍵。A.散列函數(shù)B.除余法中的質數(shù)C.沖突處理D.散列函數(shù)和沖突處理13.對于大文件的排序要研究在外設上的排序技術，即()A.快速排序法B.內排序法C.外排序法D.交叉排序法14.設有5000個無序的元素，希望用最快的速度挑選出其中前50個最大的元素，最好選用()法。A.冒泡排序B.快速排序C.堆排序D.基數(shù)排序二、判斷題(判斷下列各題，正確的在題干后面括號內打“√”，錯誤的打“×”。每小題2分，共20分)1.所謂數(shù)據(jù)的邏輯結構指的是數(shù)據(jù)元素之間的邏輯關系。()2.在線性結構中，每個結點都有一個直接前驅和一個直接后繼。()3.插入和刪除是數(shù)組的兩種基本操作。()4.在鏈棧的頭部必須要設置頭結點。()5.在二叉樹中插入結點則該二叉樹便不再是二叉樹。()6.查找表的邏輯結構是集合。()7.靜態(tài)查找表的檢索與修改被分成兩個不交叉的階段分別進行。()8.在索引順序文件中插入新的記錄時，必須復制整個文件。()9.如果某種排序算法是不穩(wěn)定的，則該方法沒有實際的應用價值。()10.對于n個記錄的集合進行冒泡排序，在最壞情況下所需要的時間是0(n2)()三、填空題(每小題2分，共30分)1.程序設計的實質是________和________。2.設由字符串a=′data′、b=′structure′、c=′-′,則a與c連接然后與b連接的結果為：________。3.通常單鏈表的頭結點指的是________；單鏈表的首結點指的是________。4.一個隊列的入隊序列是a、b、c、d，則隊列的輸出序列為________。5.棧結構通常采用的兩種存儲結構是________和________。6.具有N個結點的完全二叉樹的深度為________。7.樹的三種主要的遍歷方法是：________、________和層次遍歷。8.在無向圖的鄰接矩陣A中，若A〔i,j〕等于1，則A〔j,i〕等于________。9.采用散列技術實現(xiàn)散列表時，需要考慮的兩個主要問題是：構造________和解決________。10.索引順序表上的查找分兩個階段：(1)________；(2)________。11.散列文件中的記錄通常是成組存放的。若干的記錄組成一個存儲單位，稱作________。12.就文件而言，按用戶的觀點所確定的基本存儲單元稱為________。按外設的觀點所確定的基本存儲單元稱為________。13.文件的檢索有三種方式：________存取、________存取和按關鍵字存取。14.最簡單的交換排序方法是________排序。15.外排序的基本方法是________。四、應用題(每小題6分，共18分)2.有一份電文中共使用五個字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為8、14、10、4、18，請構造相應的哈夫曼樹(左子樹根結點的權小于等于右子樹根結點的權)，求出每個字符的哈夫曼編碼。3.有初始的無序序列為{98,65,38,40,12,51,100,77,26,88},給出對其進行歸并排序(升序)的每一趟的結果。五、設計題(每小題6分，共18分)1.假設用一個循環(huán)單鏈表來表示隊列(稱為循環(huán)鏈隊)，該隊列中只設一個隊尾指針rear,不設隊首指針。請編寫向循環(huán)鏈隊中插入一個元素X的過程。2.以鄰接表為存儲結構，寫出連通圖的深度優(yōu)先搜索算法。3.設有一組關鍵字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函數(shù)：H(key)=keyMOD13,采用線性探測法解決沖突，試在0～18的散列地址空間中對該關鍵字序列構造散列表。數(shù)據(jù)結構導論試題參考答案一、單項選擇題(每小題1分，共14分)1.C2.B3.D4.B5.A6.C7.B8.C9.A10.C11.B12.D13.C14.C二、判斷題(每小題2分，共20分)1.×2.×3.×4.×5.×6.√7.√8.×9.×10.√三、填空題(每小題2分，共30分)1.(1)數(shù)據(jù)表示(2)數(shù)據(jù)處理。2.′data-structure′。3.(1)在單鏈表第一個結點之前增設的一個類型相同的結點(2)表結點中的第一個結點。4.a、b、c、d。5.(1)順序存儲結構(2)鏈表存儲結構。6.〔log2N〕+1。7.(1)先根遍歷(2)后根遍歷。8.1。9.(1)散列函數(shù)(2)沖突。10.(1)確定待查元素所在的塊(2)在塊內查找待查的元素。11.桶。12.(1)邏輯結構(2)物理結構。13.(1)順序(2)直接。14.冒泡排序。15.歸并。四、相應的哈夫曼編碼為：a:001b:10c:01d:000e:11畫出正確的哈夫曼樹給4分，寫出相應哈夫曼編碼給2分3.初始無序序列：986538401251100772688｛98｝｛65｝｛38｝｛40｝｛12｝｛51｝｛100｝｛77｝｛26｝｛88｝第一次歸并：｛6598｝｛3840｝｛1251｝｛77100｝｛2688｝第二次歸并：｛38406598｝｛125177100｝｛2688｝第三次歸并：｛12384051657798100｝｛2688｝第四次歸并：｛122638405165778898100｝3.構造過程如下：H(19)=19MOD13=6H(01)=01MOD13=1H(23)=23MOD13=10H(14)=14MOD13=1(沖突)H(14)=(1+1)MOD19=2H(55)=55MOD13=3H(20)=20MOD13=7H(84)=84MOD13=6(沖突)H(84)=(6+1)MOD19=7(仍沖突)H(84)=(6+2)MOD19=8H(27)=27MOD13=1(沖突)H(27)=(1+1)MOD19=2(沖突)H(27)=(1+2)MOD19=3(仍沖突)H(27)=(1+3)MOD19=4H(68)=68MOD13=3(沖突)H(68)=(3+1)MOD19=4(仍沖突)H(68)=(3+2)MOD19=5H(11)=11MOD13=11H(10)=10MOD13=10(沖突)H(10)=(10+1)MOD19=11(仍沖突)H(10)=(10+2)MOD19=12H(77)=77MOD13=12(沖突)H(77)=(12+1)MOD19=13因此，各關鍵字相應的地址分配如下：address(01)=1address(14)=2address(55)=3address(27)=4address(68)=5address(19)=6address(20)=7address(84)=8address(23)=10address(11)=11address(10)=12address(77)=13其余的地址中為空。第一章緒論一、選擇題

1.組成數(shù)據(jù)的基本單位是（）

（A）數(shù)據(jù)項（B）數(shù)據(jù)類型（C）數(shù)據(jù)元素（D）數(shù)據(jù)變量

2.數(shù)據(jù)結構是研究數(shù)據(jù)的（）以及它們之間的相互關系。

（A）理想結構，物理結構（B）理想結構，抽象結構

（C）物理結構，邏輯結構（D）抽象結構，邏輯結構

3.在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（）

（A）動態(tài)結構和靜態(tài)結構（B）緊湊結構和非緊湊結構

（C）線性結構和非線性結構（D）內部結構和外部結構

4.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的（①）以及它們之間的（②）和運算等的學科。

①（A）數(shù)據(jù)元素（B）計算方法（C）邏輯存儲（D）數(shù)據(jù)映像

②（A）結構（B）關系（C）運算（D）算法

5.算法分析的目的是（）。

（A）找出數(shù)據(jù)結構的合理性（B）研究算法中的輸入和輸出的關系

（C）分析算法的效率以求改進（D）分析算法的易懂性和文檔性

6.計算機算法指的是（①）,它必須具備輸入、輸出和（②）等5個特性。

①（A）計算方法（B）排序方法（C）解決問題的有限運算序列（D）調度方法

②（A）可執(zhí)行性、可移植性和可擴充性（B）可行性、確定性和有窮性

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

二、判斷題

1.數(shù)據(jù)的機內表示稱為數(shù)據(jù)的存儲結構。（）

2.算法就是程序。（）

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

4.算法的五個特性為：有窮性、輸入、輸出、完成性和確定性。（）

5.算法的時間復雜度取決于問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（）

三、填空題

1.數(shù)據(jù)邏輯結構包括________、________、_________和_________四種類型,其中樹形結構和圖形結構合稱為_____。

2.在線性結構中,第一個結點____前驅結點,其余每個結點有且只有______個前驅結點；最后一個結點______后續(xù)結點,其余每個結點有且只有_______個后續(xù)結點。

3.在樹形結構中,樹根結點沒有_______結點,其余每個結點有且只有_______個前驅結點；葉子結點沒有________結點,其余每個結點的后續(xù)結點可以_________。

4.在圖形結構中,每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以_________。

5.線性結構中元素之間存在________關系,樹形結構中元素之間存在______關系,圖形結構中元素之間存在_______關系。

6.算法的五個重要特性是_______、_______、______、_______、_______。

7.數(shù)據(jù)結構的三要素是指______、_______和________。

8.鏈式存儲結構與順序存儲結構相比較,主要優(yōu)點是________________________________。

9.設有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結構宜用_________結構,為了方便插入一個元素,數(shù)據(jù)結構宜用____________結構。四、算法分析題

1.求下列算法段的語句頻度及時間復雜度參考答案：一、選擇題1.C2.C3.C4.A、B5.C6.C、B二、判斷題:1、√2、×3、×4、×5、√三、填空題1、線性、樹形、圖形、集合?；非線性（網狀）2、沒有；1；沒有；13、前驅；1；后繼；任意多個4、任意多個5、一對一；一對多；多對多6、有窮性；確定性；可行性；輸入；輸出7、數(shù)據(jù)元素；邏輯結構；存儲結構8、插入、刪除、合并等操作較方便9、順序存儲；鏈式存儲四、算法分析題for(i=1;i<=n;i++)

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

x=x+1;

分析：該算法為一個二重循環(huán)，執(zhí)行次數(shù)為內、外循環(huán)次數(shù)相乘，但內循環(huán)次數(shù)不固定，與外循環(huán)有關，因些，時間頻度T(n)=1+2+3+…+n=n*(n+1)/2

有1/4≤T(n)/n2≤1，故它的時間復雜度為Ｏ(n2),即Ｔ(n)與n2數(shù)量級相同。2、分析下列算法段的時間頻度及時間復雜度

for（i=1;i<=n;i++）

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

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

x=i+j-k;

分析算法規(guī)律可知時間頻度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)

由于有1/6≤T（n）/n3≤1，故時間復雜度為Ｏ(n3)第二章線性表一、選擇題

1.一個線性表第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是()

（A）110（B）108（C）100（D）120

2.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（）個元素。

（A）64（B）63（C）63.5（D）7

3.線性表采用鏈式存儲結構時，其地址（）。

(A)必須是連續(xù)的(B)部分地址必須是連續(xù)的

(C)一定是不連續(xù)的(D)連續(xù)與否均可以

4.在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行（）

（A）s->next=p;p->next=s;（B）s->next=p->next;p->next=s;

（C）s->next=p->next;p=s;（D）p->next=s;s->next=p;

5.在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(zhí)行（）

（A）p->next=p->next->next;（B）p=p->next;p->next=p->next->next;

（C）p->next=p->next;（D）p=p->next->next;

6.下列有關線性表的敘述中，正確的是（）

（A）線性表中的元素之間隔是線性關系

（B）線性表中至少有一個元素

（C）線性表中任何一個元素有且僅有一個直接前趨

（D）線性表中任何一個元素有且僅有一個直接后繼

7.線性表是具有n個（）的有限序列（n≠0)

（A）表元素（B）字符（C）數(shù)據(jù)元素（D）數(shù)據(jù)項

二、判斷題

1.線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。（）

2.如果沒有提供指針類型的語言，就無法構造鏈式結構。（）

3.線性結構的特點是只有一個結點沒有前驅，只有一個結點沒有后繼，其余的結點只有一個前驅和后繼。（）

4.語句p=p->next完成了指針賦值并使p指針得到了p指針所指后繼結點的數(shù)據(jù)域值。（）

5.要想刪除p指針的后繼結點，我們應該執(zhí)行q=p->next；p->next=q->next；free(q)。（）

三、填空題

1.已知P為單鏈表中的非首尾結點，在P結點后插入S結點的語句為：_______________________。

2.順序表中邏輯上相鄰的元素物理位置()相鄰，單鏈表中邏輯上相鄰的元素物理位置_________相鄰。

3.線性表L＝（a1，a2，...，an）采用順序存儲，假定在不同的n＋1個位置上插入的概率相同，則插入一個新元素平均需要移動的元素個數(shù)是________________________

4.在非空雙向循環(huán)鏈表中，在結點q的前面插入結點p的過程如下：

p->prior=q->prior;

q->prior->next=p;

p->next=q;

______________________;

5.已知L是無表頭結點的單鏈表，是從下列提供的答案中選擇合適的語句序列，分別實現(xiàn)：

（1）表尾插入s結點的語句序列是_______________________________

(2)表尾插入s結點的語句序列是_______________________________p->next=s;p=L;L=s;p->next=s->next;s->next=p->next;s->next=L;s->next=null;while(p->next!=Q)?p=p-next;while(p->next!=null)p=p->next;四、算法設計題

1.試編寫一個求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)（數(shù)據(jù)域數(shù)據(jù)類型為整型）。

2.已知帶有頭結點的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數(shù)據(jù)域值為x的所有結點的c函數(shù)。

3.某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成一個循環(huán)鏈表，每個結點有價格、數(shù)量和鏈指針三個域?，F(xiàn)出庫（銷售）m臺價格為h的電視機，試編寫算法修改原鏈表。

4.某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成一個循環(huán)鏈表，每個結點有價格、數(shù)量和鏈指針三個域?，F(xiàn)新到m臺價格為h的電視機，試編寫算法修改原鏈表。

5.線性表中的元素值按遞增有序排列，針對順序表和循環(huán)鏈表兩種不同的存儲方式，分別編寫C函數(shù)刪除線性表中值介于a與b（a≤b）之間的元素。

6.設A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是兩個給定的線性表,它們的結點個數(shù)分別是n和m,且結點值均是整數(shù)。

若n=m，且ai=bi（0≤i<n），則A=B；

若n<m，且ai=bi（0≤i<n），則A<B；

若存在一個j，j<m，j<n，且ai=bi（0≤i<j），若aj<bj，則A<B，否則A>B。

試編寫一個比較A和B的C函數(shù)，該函數(shù)返回-1或0或1，分別表示A<B或A=B或A>B。

7.試編寫算法,刪除雙向循環(huán)鏈表中第k個結點。

8.線性表由前后兩部分性質不同的元素組成(a0,a1,...,an-1,b0,b1,...,bm-1),m和n為兩部分元素的個數(shù),若線性表分別采用數(shù)組和鏈表兩種方式存儲,編寫算法將兩部分元素換位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析兩種存儲方式下算法的時間和空間復雜度。

9.用循環(huán)鏈表作線性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存儲結構,頭指針分別為ah和bh，設計C函數(shù)，把兩個線性表合并成形如（a0,b0,a1,b1,…）的線性表，要求不開辟新的動態(tài)空間,利用原來循環(huán)鏈表的結點完成合并操作,結構仍為循環(huán)鏈表,頭指針為head,并分析算法的時間復雜度。

10.試寫出將一個線性表分解為兩個帶有頭結點的循環(huán)鏈表，并將兩個循環(huán)鏈表的長度放在各自的頭結點的數(shù)據(jù)域中的C函數(shù)。其中,線性表中序號為偶數(shù)的元素分解到第一個循環(huán)鏈表中,序號為奇數(shù)的元素分解到第二個循環(huán)鏈表中。

11.試寫出把線性鏈表改為循環(huán)鏈表的C函數(shù)。

12.己知非空線性鏈表中x結點的直接前驅結點為y,試寫出刪除x結點的C函數(shù)。

參考答案：一、選擇題1.B2.C3.D4.B5.A6.A7、C二、判斷題:參考答案：1、×2、√3、×4、×5、√三、填空題1、s->next=p->next;p->next=s;2、一定；不一定3、n/24、q->prior=p;5、(1)6)3)

(2)2)9）1)7)四、算法設計題1、

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{intdata;

structnode*link;

}NODE;

intaver(NODE*head)

{inti=0,sum=0,ave;NODE*p;

p=head;

while(p!=NULL)

{p=p->link;++i;

sum=sum+p->data;}

ave=sum/i;

return(ave);}2、

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{

intdata;/*假設數(shù)據(jù)域為整型*/

structnode*link;

}NODE;

voiddel_link(NODE*head,intx)/*刪除數(shù)據(jù)域為x的結點*/

{

NODE*p,*q,*s;

p=head;

q=head->link;

while(q!=head)

{if(q->data==x)

{p->link=q->link;

s=q;

q=q->link;

free(s);}

else

{

p=q;

q=q->link;

}

}

}3、

voiddel(NODE*head,floatprice,intnum)

{

NODE*p,*q,*s;

p=head;q=head->next;

while(q->price<price&&q!=head)

{

p=q;

q=q->next;

}

if(q->price==price)

q->num=q->num-num;

else

printf("無此產品");

if(q->num==0)

{

p->next=q->next;

free(q);

}

}4、

#include"stdio.h"

#include"malloc.h"

typedefstructnode

{

floatprice;

intnum;

structnode*next;

}NODE;

voidins(NODE*head,floatprice,intnum)

{

NODE*p,*q,*s;

p=head;q=head->next;

while(q->price<price&&q!=head)

{

p=q;

q=q->next;

}

if(q->price==price)

q->num=q->num+num;

else

{

s=(NODE*)malloc(sizeof(NODE));

s->price=price;

s->num=num;

s->next=p->next;

p->next=s;

}

}5、順序表：

算法思想：從0開始掃描線性表，用k記錄下元素值在a與b之間的元素個數(shù)，對于不滿足該條件的元素，前移k個位置，最后修改線性表的長度。

voiddel（elemtypelist[]，int*n，elemtypea，elemtypeb）

{

inti=0，k=0；

while（i<n)

{

if(list[i]>=a&&list[i]<=b)k++;

else

list[i-k]=list[i];

i++;

}

*n=*n-k;/*修改線性表的長度*/

}

循環(huán)鏈表:

voiddel(NODE*head,elemtypea,elemtypeb)

{

NODE*p,*q;

p=head;q=p->link;/*假設循環(huán)鏈表帶有頭結點*/

while(q!=head&&q->data<a)

{

p=q;

q=q->link;

}

while(q!=head&&q->data<b)

{

r=q;

q=q->link;

free(r);

}

if(p!=q)

p->link=q;

}6、

#defineMAXSIZE100

intlistA[MAXSIZE],listB[MAXSIZE];

intn,m;

intcompare(inta[],intb[])

{

inti=0;

while(a[i]==b[i]&&i<n&&i<m)

i++;

if(n==m&&i==n)return(0);

if(n<m&&i==n)return(-1);

if(n>m&&i==m)return(1);

if(i<n&&i<m)

if(a[i]<b[i])return(-1);

elseif(a[i]>b[i])return(1);

}7、

voiddel(DUNODE**head,inti)

{

DUNODE*p;

if(i==0)

{

*head=*head->next;

*head->prior=NULL;

return(0);

}

Else

{for(j=0;j<i&&p!=NULL;j++)

p=p->next;

if(p==NULL||j>i)return(1);

p->prior->next=p->next;

p->next->prior=p->proir;

free(p);

return(0);

}8.

順序存儲:

voidconvert(elemtypelist[],intl,inth)/*將數(shù)組中第l個到第h個元素逆置*/

{

inti;

elemtypetemp;

for(i=h;i<=(l+h)/2;i++)

{

temp=list[i];

list[i]=list[l+h-i];

list[l+h-i]=temp;

}

}

voidexchange(elemtypelist[],intn,intm);

{

convert(list,0,n+m-1);

convert(list,0,m-1);

convert(list,m,n+m-1);

}

該算法的時間復雜度為O(n+m),空間復雜度為O(1)

鏈接存儲:(不帶頭結點的單鏈表)

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voidconvert(NODE**head,intn,intm)

{

NODE*p,*q,*r;

inti;

p=*head;

q=*head;

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

q=q->link;/*q指向an-1結點*/

r=q->link;

q->link=NULL;

while(r->link!=NULL)

r=r->link;/*r指向最后一個bm-1結點*/

*head=q;

r->link=p;

}

該算法的時間復雜度為O(n+m),但比順序存儲節(jié)省時間(不需要移動元素,只需改變指針),空間復雜度為O(1)

9.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

NODE*union(NODE*ah,NODE*bh)

{

NODE*a,*b,*head,*r,*q;

head=ah;

a=ah;

b=bh;

while(a->link!=ah&&b->link!=bh)

{

r=a->link;

q=b->link;

a->link=b;

b->link=r;

a=r;

b=q;

}

if(a->link==ah)/*a的結點個數(shù)小于等于b的結點個數(shù)*/

{

a->link=b;

while(b->link!=bh)

b=b->link;

b->link=head;

}

if(b->link==bh)/*b的結點個數(shù)小于a的結點個數(shù)*/

{

r=a->link;

a->link=b;

b->link=r;

}

return(head);

}

該算法的時間復雜度為O(n+m),其中n和m為兩個循環(huán)鏈表的結點個數(shù).

10.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voidanalyze(NODE*a）

{

NODE*rh，*qh，*r,*q,*p；

inti=0，j=0；/*i為序號是奇數(shù)的結點個數(shù)j為序號是偶數(shù)的結點個數(shù)*/

p=a；

rh=（NODE*）malloc（sizeof（NODE））；/*rh為序號是奇數(shù)的鏈表頭指針*/

qh=(NODE*)malloc(sizeof(NODE));/*qh為序號是偶數(shù)的鏈表頭指針*/

r=rh;

q=qh;

while(p!=NULL)

{

r->link=p;

r=p;

i++;

p=p->link;

if(p!=NULL)

{

q->link=p;

q=p;

j++;

p=p->link;

}

}

rh->data=i;

r->link=rh;

qh->data=j;

q->link=qh;

}

11.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voidchange(NODE*head)

{

NODE*p;

p=head;

if(head!=NULL)

{

while(p->link!=NULL)

p=p->link;

p->link=head;

}

}

12.

typedefstructnode

{

elemtypedata;

structnode*link;

}NODE;

voiddel(NODE*x,NODE*y)

{

NODE*p,*q;

elemtyped1;

p=y;

q=x;

while(q->next!=NULL)/*把后一個結點數(shù)據(jù)域前移到前一個結點*/

{

p->data=q->data;

q=q->link;

p=q;

p->link=NULL;/*刪除最后一個結點*/

free(q);

}

第三章棧和隊列

一、選擇題

1.一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（）。

（A）edcba（B）decba（C）dceab（D）abcde

2.棧結構通常采用的兩種存儲結構是（）。

（A）線性存儲結構和鏈表存儲結構（B）散列方式和索引方式

（C）鏈表存儲結構和數(shù)組（D）線性存儲結構和非線性存儲結構

3.判定一個棧ST(最多元素為m0)為空的條件是（）。

（A）ST-〉top!=0（B）ST-〉top==0

（C）ST-〉top!=m0（D）ST-〉top=m0

4.判定一個棧ST(最多元素為m0)為棧滿的條件是（）。

（A）ST->top!=0（B）ST->top==0

（C）ST->top!=m0-1（D）ST->top==m0-1

5.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是（）。

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

6.循環(huán)隊列用數(shù)組A[0,m-1]存放其元素值,已知其頭尾指針分別是front和rear則當前隊列中的元素個數(shù)是（）

（A）(rear-front+m)%m（B）rear-front+1（C）rear-front-1（D）rear-front

7.棧和隊列的共同點是（）

（A）都是先進后出（B）都是先進先出

（C）只允許在端點處插入和刪除元素（D）沒有共同點

8.表達式a*(b+c)-d的后綴表達式是（）。

（A）abcd*+-（B）abc+*d-（C）abc*+d-（D）-+*abcd

9.4個元素a1，a2，a3和a4依次通過一個棧，在a4進棧前，棧的狀態(tài)，則不可能的出棧序是（）

(A)a4，a3，a2，a1(B)a3，a2，a4，a1

(C)a3，a1，a4，a2(D)a3，a4，a2，a1

10.以數(shù)組Q[0..m－1]存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當前隊列中元素的個數(shù)，隊列第一個元素的實際位置是（）

(A)rear－qulen(B)rear－qulen＋m

(C)m－qulen(D)1＋（rear＋m－qulen）%m

二、填空題

1.棧的特點是_______________________,隊列的特點是__________________________。

2.線性表、棧和隊列都是_____________________結構,可以在線性表的______________位置插入和刪除元素，對于棧只能在________插入和刪除元素，對于隊列只能在_______插入元素和_________刪除元素。

3.一個棧的輸入序列是12345,則棧有輸出序列12345是____________。(正確/錯誤)

4.設棧S和隊列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個棧，一個元素出棧后即進入隊列Q，若6個元素出隊列的順序是a3，a5，a4，a6，a2，a1則棧S至少應該容納_____個元素。

三、算法設計題

1.假設有兩個棧s1和s2共享一個數(shù)組stack[M],其中一個棧底設在stack[0]處，另一個棧底設在stack[M-1]處。試編寫對任一棧作進棧和出棧運算的C函數(shù)push（x,i)和pop(i),i=l,2。其中i=1表示左邊的棧，,i=2表示右邊的棧。要求在整個數(shù)組元素都被占用時才產生溢出。

2.利用兩個棧s1,s2模擬一個隊列時,如何用棧的運算來實現(xiàn)該隊列的運算?寫出模擬隊列的插入和刪除的C函數(shù)。

一個棧s1用于插入元素,另一個棧s2用于刪除元素.參考答案：

一、選擇題1.C2.A3.B4.B5.B6.B7、C8、C9、C10、D二、填空題1、先進先出；先進后出2、線性；任何；棧頂；隊尾；對頭3、正確的4、3

三、算法設計題1.

#defineM100

elemtypestack[M];

inttop1=0,top2=m-1;

intpush(elemtypex,inti)

{

if(top1-top2==1)return(1);/*上溢處理*/

else

if(i==1)stack[top1++]=x;

if(i==2)stack[top2--]=x;

return(0);

}

intpop(elemtype*px,inti)

{

if(i==1)

if(top1==0)return(1);

else

{

top1--;

*px=stack[top1];

return(0);

}

else

if(i==2)

if(top2==M-1)return(1);

else

{

top2++;

*px=stack[top2];

return(0);

}

}

2.

elemtypes1[MAXSIZE],s2[MAZSIZE];

inttop1,top2;

voidenqueue(elemtypex)

{

if(top1==MAXSIZE)return(1);

else

{

push(s1,x);

return(0);

}}

voiddequeue(elemtype*px)

{

elemtypex;

top2=0;

while(!empty(s1))

{

pop(s1,&x);

push(s2,x);

}

pop(s2,&x);

while(!empty(s2))

{

pop(s2,&x);

push(s1,x);

}

}第四章串

一、選擇題

1.下列關于串的敘述中，正確的是（）

(A)一個串的字符個數(shù)即該串的長度(B)一個串的長度至少是1

(C)空串是由一個空格字符組成的串(D)兩個串S1和S2若長度相同，則這兩個串相等

2.字符串"abaaabab"的nextval值為(?)

(A)(0,1,01,1,0,4,1,0,1)(B)(0,1,0,0,0,0,2,1,0,1)

(C)(0,1,0,1,0,0,0，1,1)(D)(0,1,0,1,0,1,0,1,1)

3.字符串滿足下式,其中head和tail的定義同廣義表類似,如head(‘xyz’)=‘x’,tail(‘xyz’)=‘yz’,則s=()。concat(head(tail(s)),head(tail(tail(s))))=‘dc’。

(A)abcd(B)acbd(C)acdb(D)adcb

4.串是一種特殊的線性表,其特殊性表現(xiàn)在（）

(A)可以順序存儲(B)數(shù)據(jù)元素是一個字符

(C)可以鏈式存儲(D)數(shù)據(jù)元素可以是多個字符

5．設串S1=‘ABCDEFG’,s2=‘PQRST’,函數(shù)CONCAT（X，Y）返回X和Y串的連接串，SUBSTR（S，I，J）返回串S從序號I開始的J個字符組成的字串，LENGTH（S）返回串S的長度，則CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的結果串是（）

（A）BCDEF(B)BCDEFG(C)BCPQRST(D)BCDEFEF

二、算法設計

1.分別在順序存儲和一般鏈接存儲兩種方式下,用C語言寫出實現(xiàn)把串s1復制到串s2的串復制函數(shù)strcpy(s1,s2)。

2.在一般鏈接存儲(一個結點存放一個字符)方式下,寫出采用簡單算法實現(xiàn)串的模式匹配的C語言函數(shù)intL_index(t,p)。參考答案：一、選擇題1.A2.B3.D4.D5.D二、算法設計1.

順序存儲：

#include"string.h"

#defineMAXN100

chars[MAXN];

intS_strlen(chars[])

{

inti;

for(i=0;s[i]!='\0';i++);

return(i);

}

voidS_strcpy(chars1[],chars2[])//4.3題

{

inti;

for(i=0;s1[i]!='\0';i++)

s2[i]=s1[i];

s2[i]='\0';

}

一般鏈接存儲：

#include"stdio.h"

typedefstructnode

{

chardata;

structnode*link;

}NODE;

NODE*L_strcpy(NODE*s1)

{

NODE*s2,*t1,*t2,*s;

if(s1==NULL)return(NULL);

else

{

t1=s1;

t2=(NODE*)malloc(sizeof(NODE));

s2=t2;

while(t1!=NULL)

{

s=(NODE*)malloc(sizeof(NODE));

s->data=t1->data;

t2->link=s;

t2=s;

t1=t1->link;

}

t2->link=NULL;

s=s2;

s2=s2->link;

free(s);

return(s2);

}

}

2.

#include"stdio.h"

typedefstructnode

{

chardata;

structnode*link;

}NODE;

intL_index(NODE*t,NODE*p)

{

NODE*t1,*p1,*t2;

?inti;

t1=t;i=1;

while(t1!=NULL)

{

p1=p;

t2=t1->link;

while(p1->data==t1->data&&p1!=NULL)

{

p1=p1->link;

t1=t1->link;

}

if(p1==NULL)return(i);

i++;

t1=t2;

}

return(0);

}第五章數(shù)組和廣義表

一、選擇題

1.常對數(shù)組進行的兩種基本操作是（）

（A）建立與刪除（B）索引和修改（C）查找和修改（D）查找與索引

2.二維數(shù)組M的元素是4個字符(每個字符占一個存儲單元)組成的串,行下標i的范圍從0到4,列下標j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素()的起始地址相同。

（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4]

3.數(shù)組A[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內,存放該數(shù)組至少需要的單元數(shù)是（）。

（A）80（B）100（C）240（D）270

4.數(shù)組A[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內,該數(shù)組按行存放時,元素A[7][4]的起始地址為（）。

（A）SA+141（B）SA+144（C）SA+222（D）SA+225

5.數(shù)組A[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內,該數(shù)組按列存放時,元素A[4][7]的起始地址為（）。

（A）SA+141（B）SA+180（C）SA+222（D）SA+225

6.稀疏矩陣一般的壓縮存儲方法有兩種,即（）。

（A）二維數(shù)組和三維數(shù)組（B）三元組和散列

（C）三元組和十字鏈表（D）散列和十字鏈表

7.若采用三元組壓縮技術存儲稀疏矩陣,只要把每個元素的行下標和列下標互換,就完成了對該矩陣的轉置運算,這種觀點（）。

（A）正確（B）錯誤

8.設矩陣A是一個對稱矩陣,為了節(jié)省存儲,將其下三角部分按行序存放在一維數(shù)組B[1,n(n-1)/2]中,對下三角部分中任一元素ai,j(i<=j),在一組數(shù)組B的下標位置k的值是（）。

（A）i(i-1)/2+j-1（B）i(i-1)/2+j（C）i(i+1)/2+j-1(D)i(i+1)/2+j

二、填空題

1.己知二維數(shù)組A[m][n]采用行序為主方式存儲,每個元素占k個存儲單元,并且第一個元素的存儲地址是LOC(A[0][0]),則A[0][0]的地址是_____________________。

2.二維數(shù)組A[10][20]采用列序為主方式存儲,每個元素占一個存儲單元,并且A[0][0]的存儲地址是200,則A[6][12]的地址是________________。

3.有一個10階對稱矩陣A,采用壓縮存儲方式(以行序為主,且A[0][0]=1),則A[8][5]的地址是__________________。

4.設n行n列的下三角矩陣A已壓縮到一維數(shù)組S[1..n*(n+1)/2]中,若按行序為主存儲,則A[i][j]對應的S中的存儲位置是________________。

5.若A是按列序為主序進行存儲的4×6的二維數(shù)組,其每個元素占用3個存儲單元,并且A[0][0]的存儲地址為1000,元素A[1][3]的存儲地址為___________,該數(shù)組共占用_______________個存儲單元。

三、算法設計

1.如果矩陣A中存在這樣的一個元素A[i][j]滿足條件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,則稱之為該矩陣的一個馬鞍點。編寫一個函數(shù)計算出1×n的矩陣A的所有馬鞍點。

2.n只猴子要選大王,選舉辦法如下:所有猴子按1,2,...,n編號圍坐一圈,從1號開始按1、2、...、m報數(shù),凡報m號的退出到圈外,如此循環(huán)報數(shù),直到圈內剩下只猴子時,這只猴子就是大王。n和m由鍵盤輸入,打印出最后剩下的猴子號。編寫一程序實現(xiàn)上述函數(shù)。

3.數(shù)組和廣義表的算法驗證程序

編寫下列程序:

(1)求廣義表表頭和表尾的