【文章內(nèi)容簡(jiǎn)介】 nt num。//帳號(hào) char name[8]。//姓名 struct node date。//開(kāi)戶(hù)年月日 int tag。//儲(chǔ)蓄類(lèi)型，如：0 零存，1 一年定期…… float put。//存入累加數(shù)； float interest。//利息 float total。//帳面總數(shù) }count； 19．(1)n (2)n+1 (3)n (4)(n+4)(n1)/2 (5)(n+2)(n1)/2 (6)n1 這是一個(gè)遞歸調(diào)用，因k的初值為1，由語(yǔ)句（6）知，每次調(diào)用k增1，故第(1)語(yǔ)句執(zhí)行n次。（2）是FOR循環(huán)語(yǔ)句，在滿(mǎn)足(1)的條件下執(zhí)行，該語(yǔ)句進(jìn)入循環(huán)體(3)n次，加上最后一次判斷出界，故執(zhí)行了n+1次。(4)也是循環(huán)語(yǔ)句，當(dāng)k=1時(shí)判斷n+1次（進(jìn)入循環(huán)體(5)n次），k=2時(shí)判斷n次，最后一次k=n1時(shí)判斷3次，故執(zhí)行次數(shù)是（n+1）+n+…+3=(n+4)(n1)/2次。語(yǔ)句(5)是(4)的循環(huán)體，每次比(4)少一次判斷，故執(zhí)行次數(shù)是n+(n1)+…+2=(n+2)(n1)/2次。注意分析時(shí)，不要把(2)分析成n次，更不是1次。20．4 （這時(shí)i=4， s=100） REPEAT語(yǔ)句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時(shí)退出循環(huán)。21．算法在最好情況下，即二進(jìn)制數(shù)的最后一位為零時(shí)，只作一次判斷，未執(zhí)行循環(huán)體，賦值語(yǔ)句A[i]執(zhí)行了一次；最壞情況出現(xiàn)在二進(jìn)制數(shù)各位均為1（最高位為零，因題目假設(shè)無(wú)溢出），這時(shí)循環(huán)體執(zhí)行了n1次，時(shí)間復(fù)雜度是O(n)，循環(huán)體平均執(zhí)行n/2次，時(shí)間復(fù)雜度仍是O(n)。22．該算法功能是將原單循環(huán)鏈表分解成兩個(gè)單循環(huán)鏈表：其一包括結(jié)點(diǎn)h到結(jié)點(diǎn)g的前驅(qū)結(jié)點(diǎn)；另一個(gè)包括結(jié)點(diǎn)g到結(jié)點(diǎn)h的前驅(qū)結(jié)點(diǎn)。時(shí)間復(fù)雜度是O(n)。23．第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為(n+(n1)+(n2)+…+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表： i= 1 2 3 … n j=n n n n … n j=n1 n1 n1 n1 … … … … …j=3 3 3j=2 2 2j=1 1執(zhí)行次數(shù)為(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2n(n21)/6。在n=5時(shí)，f(5)=55，執(zhí)行過(guò)程中，輸出結(jié)果為：sum=15,sum=29,sum=41,sum=50,sum=55（每個(gè)sum= 占一行,為節(jié)省篇幅，這里省去換行）。24．O(n2),m的值等于賦值語(yǔ)句m:=m+1的運(yùn)行次數(shù)，其計(jì)算式為25．(1)O(1) (2)O(n2) (3)O(n3) 26．(1)O(n) (2)O(n2)27.（1）由斐波那契數(shù)列的定義可得：Fn=Fn1+Fn2 =2Fn2+Fn3 =3Fn3+2Fn4 =5Fn4+3Fn5 =8Fn5+5Fn6 …… =pF1+qF0設(shè)Fm的執(zhí)行次數(shù)為Bm(m=0、…、n1)，由以上等式可知，F(xiàn)n1被執(zhí)行一次，即Bn1=1；Fn2被執(zhí)行兩次，即Bn2=2；直至F1被執(zhí)行p次、F0被執(zhí)行q次，即B1=p，B0=q。Bm的執(zhí)行次數(shù)為前兩等式第一因式系數(shù)之和，即Bm=Bm1+Bm2，再有Bn1=1和Bn2=2，這也是一個(gè)斐波那契數(shù)列?？梢越獾茫築m=[()nm+2()nm+2] (m=0,1,2,…,n1)（2）時(shí)間復(fù)雜度為O(n)28．從小到大排列為：logn, n1/2+logn, n, nlogn, n2+logn，n3, nn3+7n5, 2n/2, (3/2)n, n!, 第2章 線(xiàn)性表一 選擇題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)于線(xiàn)性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ ）【北方交通大學(xué) 2001 一、14（2分）】A．線(xiàn)性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B．線(xiàn)性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C．線(xiàn)性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D．線(xiàn)性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3．線(xiàn)性表是具有n個(gè)（ ）的有限序列（n0）。 【清華大學(xué) 1998 一、4（2分）】A．表元素 B．字符 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)項(xiàng) E．信息項(xiàng)4．若某線(xiàn)性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間?！竟枮I工業(yè)大學(xué) 2001 二、1（2分）】A．順序表 B．雙鏈表 C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D．單循環(huán)鏈表5．某線(xiàn)性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間?！灸祥_(kāi)大學(xué) 2000 一、3】A．單鏈表 B．僅有頭指針的單循環(huán)鏈表 C．雙鏈表 D．僅有尾指針的單循環(huán)鏈表6．設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用( )最節(jié)省時(shí)間。A. 單鏈表 C. 帶尾指針的單循環(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．?dāng)?shù)組下標(biāo) C．下一元素地址 D．左、右孩子地址9. 鏈表不具有的特點(diǎn)是（ ） 【福州大學(xué) 1998 一、8 (2分)】A．插入、刪除不需要移動(dòng)元素 B．可隨機(jī)訪問(wèn)任一元素 C．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與線(xiàn)性長(zhǎng)度成正比10. 下面的敘述不正確的是（ ）【南京理工大學(xué) 1996 一、10（2分）】A．線(xiàn)性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比 B. 線(xiàn)性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)C. 線(xiàn)性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比D. 線(xiàn)性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)11. 線(xiàn)性表的表元存儲(chǔ)方式有(（1）)和鏈接兩種。試指出下列各表中使用的是何種存儲(chǔ)方式：表1是(（2）)存儲(chǔ)方式；表2是(（3）)存儲(chǔ)方式；表3是(（4）)存儲(chǔ)方式；表4是(（5）)存儲(chǔ)方式。表左的s指向起始表元。 表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系1 618 40 2 2 205 2 3 3 103 15 4 4 501 20 5 5 781 17 6 6 910 24 0表1s→ 表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 2 5 781 17 6 6 910 24 3表2s→ 表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系 1 618 40 5 2 205 2 13 103 15 4 4 501 20 0 5 781 17 6 6 910 24 3表3s→ 表元編號(hào)貨號(hào)數(shù)量表元間聯(lián)系 1 2 1 618 40 5 2 2 205 2 1 0 3 103 15 4 6 4 501 20 0 3 5 781 17 6 1 6 910 24 3 5表4s→ 供選擇的答案： 【上海海運(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無(wú)關(guān)。 (2) 靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。 (3) 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類(lèi)似，不需做元素的移動(dòng)。以上錯(cuò)誤的是（ ）【南京理工大學(xué) 2000 一、3（）】 A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）13. 若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）(1=i=n+1)?！颈本┖娇蘸教齑髮W(xué) 1999 一、1（2分）】A. O(0) B. O(1) C. O(n) D. O(n2) 14. 對(duì)于順序存儲(chǔ)的線(xiàn)性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)【青島大學(xué) 2000 五、1（2分）】15．線(xiàn)性表（ a1,a2,…,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（ ）A．O（i） B．O（1） C．O（n） D．O（i1）【中山大學(xué) 1999 一、2】16．非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p↑滿(mǎn)足（ ）?！疚錆h大學(xué) 2000 二、10】A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head17．循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是（ ）?！局猩酱髮W(xué) 1998 二、2（2分）】 A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT C．P:=H D．P:=H^.NEXT18．在一個(gè)以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（）【南京理工大學(xué)1998 一、15（2分）】 A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=119．完成在雙循環(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． 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:=p； p↑.llink：=q；p↑.llink：=q；（編者按：原題如此）21．在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的鏈結(jié)點(diǎn)的過(guò)程依次為:rlink(p) ← q。 llink(