數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組和廣義表練習(xí)題

1、第5章數(shù)組和廣義表一、選擇題1 .設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，aii為第一元素，其存儲地址為1,每個元素占一個地址空間，則a85的地址為（）。A.13B.33C.18D.402 .有一個二維數(shù)組A1:6,0:7每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址，那么這個數(shù)組的體積是（）個字節(jié)。假設(shè)存儲數(shù)組元素A1,0的第一個字節(jié)的地址是0,則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是（）。若按行存儲，則A2,4的第一個字節(jié)的地址是（）。若按列存儲，則A5,7的第一個字節(jié)的地址是（）。就一般情況而言，當(dāng)（）時，按行存儲的AI,J地址與按列存儲的AJ,I地址相等

2、。供選擇的答案：-：A.12B.66C.72D.96E.114F.120G.156H.234I.276J.282K.283L.288：A.行與列的上界相同B.行與列的下界相同C.行與列的上、下界都相同D.行的元素個數(shù)與列的元素個數(shù)相同3 .設(shè)有數(shù)組Ai,j,數(shù)組的每個元素長度為3字節(jié)，i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A5,8的存儲首地址為（）。A.BA+141B.BA+180C.BA+222D.BA+2254 .假設(shè)以行序為主序存儲二維數(shù)組A=array1.100,1.100，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10,則LOC5,5

3、=（）。A.808B.818C.1010D.10205 .數(shù)組A0.5,0.6的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A5,5的地址是（）。A.1175B.1180C.1205D.12106 .有一個二維數(shù)組A0:8,1:5,每個數(shù)組元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址，假設(shè)存儲數(shù)組元素A0,1的第一個字節(jié)的地址是0,存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是（）。若按行存儲，則A3,5和A5,3的第一個字節(jié)的地址是（）和（）。若按列存儲，則A7,1和A2,4的第一個字節(jié)的地址是（）和（）。-：A.28B.44C.76D.92E.108F.11

4、6G.132H.176I.184J.1887 .將一個A1.100,1.100的三對角矩陣，按行優(yōu)先存入一維數(shù)組B1-298中，A中元素A6665（即該元素下標(biāo)i=66,j=65）,在B數(shù)組中白位置K為（）。供選擇的答案：A.198B.195C.1978 .二維數(shù)組A的元素都是6個字符組成的串，行下標(biāo)i的范圍從0到8,列下標(biāo)j的范圈從1到10。從供選擇的答案中選出應(yīng)填入下列關(guān)于數(shù)組存儲敘述中（）內(nèi)的正確答案。（1）存放A至少需要（）個字節(jié)；（2） A的第8列和第5行共占（）個字節(jié)；（3）若A按行存放，元素A8,5的起始地址與A按列存放時的元素（）的起始地址一致。供選擇的答案：（1）A.90B.

5、180C.240D.270E.540（3） A.A8,5B.A3,10C.A5,8D.A0,99 .二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0,1,8,列下標(biāo)j=1,2,10。若A按行先存儲，元素A8,5的起始地址與當(dāng)A按列先存儲時的元素()的起始地址相同。設(shè)每個字符占一個字節(jié)。A.A8,5B.A3,10C.A5,8D.A0,910 .若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aj(i<j)的位置k的關(guān)系為()。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)

6、/2+jD.j*(j+1)/2+i11 .設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B1.n(n+1)/2中，對上述任一元素aj(1wi,jwn,且iwj)在B中的位置為()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112 .AN,N是對稱矩陣，將下面三角(包括對角線)以行序存儲到一維數(shù)組TN(N+1)/2中，則對任一上三角元素aij對應(yīng)Tk的下標(biāo)卜是()。A.i(i-1)/2+jB.j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+113 .設(shè)二維數(shù)組A1.m1.n(即m行n

7、歹U)按行存儲在數(shù)組B1.m*n中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為()。A.(i-1)*n+jB.(i-1)*n+j-1C.i*(j-1)D.j*m+i-114 .有一個100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是()。A.60B.66C.18000D.3315 .數(shù)組A0.4,-1.-3,5.7中含有元素的個數(shù)()。A.55B.45C.36D.1616 .用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中結(jié)點，使j沿鏈移動的操作為()。A.j=rj.nextB.j=j+1C.j=j->nextD.j

8、=rj->next17 .對稀疏矩陣進行壓縮存儲目的是()。A.便于進行矩陣運算B.便于輸入和輸出C.節(jié)省存儲空間D.降低運算的時間復(fù)雜度18 .已知廣義表L=(x,y,z),a,(u,t,w),從L表中取出原子項t的運算是()。A.head(tail(tail(L)B.tail(head(head(tail(L)C.head(tail(head(tail(L)D.head(tail(head(tail(tail(L)19.已知廣義表LS=(a,b,c),(d,e,f),運用head和tail函數(shù)取出LS中原子e的運算是()。A.head(tail(LS)B.tail(head(LS)C

9、.head(tail(head(tail(LS)D.head(tail(tail(head(LS)20 .廣義表A=(a,b,(c,d),(e,(f,g),則下面式子的值為()。Head(Tail(Head(Tail(Tail(A)A.(g)B.(d)C.cD.d21 .已知廣義表：A=(a,b),B=(A,A),C=(a,(b,A),B),求下列運算的結(jié)果：tail(head(tail(C)=()。A.(a)B.AC.aD.(b)E.bF.(A)22 .廣義表運算式Tail(a,b),(c,d)的操作結(jié)果是()。A.(c,d)B.c,dC.(c,d)D.d23.廣義表L=(a,(b,c),進

10、行Tail（L）操作后的結(jié)果為（）。【中山大學(xué)199910】A.cB.b,cC.24.廣義表(a,b,c,d)的表頭是(（b,c）D.）,表尾是（）。(b,c)A.aB.()C.(a,b,c,d25 .廣義表(a,(b,c),d,e)的表頭為()。A.aB.a,(b,c)C.(a,(b,c)D.(a)26 .設(shè)廣義表L=(a,b,c),則L的長度和深度分別為(D.(b,c,d)A.1和1B.1和3C.127 .下面說法不正確的是（）。A.廣義表的表頭總是一個廣義表B.和2D.2和3廣義表的表尾總是一個廣義表C.廣義表難以用順序存儲結(jié)構(gòu)、判斷題D.廣義表可以是一個多層次的結(jié)構(gòu)1 .數(shù)組不適合作為

11、任何二叉樹的存儲結(jié)構(gòu)。（）2 .從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個元素均屬于n個向量。（3 .稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（）4 .數(shù)組是同類型值的集合。（）5 .數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（）6 .一個稀疏矩陣Am*n采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換,并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運算。（）7 .二維以上的數(shù)組其實是一種特殊的廣義表。（）8 .廣義表的取表尾運算，其結(jié)果通常是個表，但有時也可是個單元素值。（）9 .若一個廣義表的表頭為空表，則此廣義表亦為空表。（）10 .廣義表中的元素或者是

12、一個不可分割的原子，或者是一個非空的廣義表。（）11 .所謂取廣義表的表尾就是返回廣義表中最后一個元素。（）12 .廣義表的同級元素（直屬于同一個表中的各元素）具有線性關(guān)系。（）13 .對長度為無窮大的廣義表，由于存儲空間的限制，不能在計算機中實現(xiàn)。（）14 .一個廣義表可以為其它廣義表所共享。（）三、填空題1 .數(shù)組的存儲結(jié)構(gòu)采用存儲方式。2 .設(shè)二維數(shù)組A-20.30,-30.20,每個元素占有4個存儲單元，存儲起始地址為200.如按行優(yōu)先順序存儲，則元素A25,18的存儲地址為（1）;如按列優(yōu)先順序存儲，則元素A-18,-25的存儲地址為（2）。3 .設(shè)數(shù)組a1.50,1.80的基地址為

13、2000,每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a45,68的存儲地址為（1）;若以列序為主序順序存儲,則元素a45,68的存儲地址為。4 .將整型數(shù)組A1.8,1.8按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A7,3的地址是：。5 .二維數(shù)組a456（下標(biāo)從0開始計，a有4*5*6個元素），每個元素的長度是2,則a234的地址是。（設(shè)a000的地址是1000,數(shù)據(jù)以行為主方式存儲）100,6 .設(shè)有二維數(shù)組A0.9,0.19,其每個元素占兩個字節(jié)，第一個元素的存儲地址為若按列優(yōu)先順序存儲，則元素A6,6存儲地址為。7 .已知數(shù)組A0.9,0.9的每個元素占

14、5個存儲單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A6,8的地址為。8 .已知二維數(shù)組A1.10,0.9中每個元素占4個單元，在按行優(yōu)先方式將其存儲到起始地址為1000的連續(xù)存儲區(qū)域時，A5,9的地址是：。9 .用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素Ai,j(1<i<n,i-2<j<i+2),B中的第8個元素是A中的第(1)行，第(2)列的元素。10 .設(shè)數(shù)組A0.8,1.10,數(shù)組中任一元素Ai,j均占內(nèi)存48個二進制位，從首地址2000開始連續(xù)存放在主內(nèi)存里，主內(nèi)存字長為16位，那么(1)存放該數(shù)組至少需要的單元數(shù)是；(2)存放

15、數(shù)組的第8列的所有元素至少需要的單元數(shù)是;(3)數(shù)組按列存儲時，元素A5,8的起始地址是。11 .設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組B1.n*(n+1)/2中，若按行為主序存儲，則Ai,j對應(yīng)的B中存儲位置為。12 .n階對稱矩陣a滿足aij=aji,i,j=1.n,，用一維數(shù)組t存儲時，t的長度為.(1)一，當(dāng)i=j,aij=t(2),i>j,aij=t(3),i<j,aij=t(4)。13 .己知三對角矩陣A【1.9,1.9】的每個元素占2個單元，現(xiàn)將其三條對角線上的元素逐行存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A7,8的地址為。14 .設(shè)有一個10階對稱矩陣

16、A采用壓縮存儲方式(以行為主序存儲：an=1),則a85的地址為。15 .所謂稀疏矩陣指的是。16 .對矩陣壓縮是為了。17 .上三角矩陣壓縮的下標(biāo)對應(yīng)關(guān)系為：。18 .假設(shè)一個15階的上三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，則非零元素4,9在B中的存儲位置k=。(注：矩陣元素下標(biāo)從1開始)-a11a21a22a31a32a3319 .設(shè)下三角矩陣A=_an1an2-ann-如果按行序為主序?qū)⑾氯窃谹j(i,j)存儲在一個一維數(shù)組B1.n(n+1)/2中，對任一個三角矢I陣元素A,它在數(shù)組B中的下標(biāo)為。20 .當(dāng)廣義表中的每個元素都是原子時，廣義表便成了。21 .廣義表的表尾是指除

17、第一個元素之外，22 .廣義表簡稱表，是由零個或多個原子或子表組成的有限序列，原子與表的差別僅在于。為了區(qū)分原子和表，一般用表不表，用(3)表本原子。一個表的長度是指(4),而表的深度是指23 .廣義表的定義為廣義表中括弧的重數(shù)。24 .設(shè)廣義表L=(),(),則head(L)是;tail(L)是;L的長度是;深度是(4)。25 .已知廣義表A=(9,7,(8,10,(99),12)，試用求表頭和表尾的操作Head()和Tail()將原子元素99從A中取出來。26.27.廣義表的深度是的長度是(1)深度是(2)。廣義表(a,(a,b),d,e,(i,j),k)分)】28 .已知廣義表LS=(a

18、,(b,c,d),e),運用head和tail函數(shù)取出LS中原子b的運算是29 .廣義表A=(a,b),(c,d,e),取出A中的原子e的操作是：。30 .設(shè)某廣義表H=(A(a,b,c),運用head函數(shù)和tail函數(shù)求出廣義表H中某元素b的運算式。31 .廣義表A(),(a,(b),c),head(tail(head(tail(head(A)等于。32 .廣義表運算式HEAD(TAIL(a,b,c),(x,y,z)的結(jié)果是。33 .已知廣義表A=(a,b),(c),(d,e),head(tail(tail(head(A)的結(jié)果34 .利用廣義表的GetHead和GetTail操作，從廣義表

19、L=(apple,pear)“banana,orange)中分離出原子banana的函數(shù)表達式是。35 .已知a數(shù)組元素共5個，依次為12,10,5,3,1;b數(shù)組元素共4個，依次為4,6,8,15,則執(zhí)行如下所示的過程語句sort后得到c數(shù)組各元素依次為15,12,10,8,6,5,4,3,1;數(shù)組a,b,c的長度分別為l=5,m=4,n=9請在程序中方框內(nèi)填入正確的成分，完成上述要求。PROCEDUREsort;VARi,j,k,x:integer;d:ARRAY1.mOFinteger;BEGINFORi:=1TOmDOdi:=(1);i:=1;j:=1;k:=1;WHILE(i<

20、=l)AND(j<=m)DOBEGINIFai>djTHENBEGIN(2);(3)ENDELSEBEGIN(4)_;(5)_END;ck:=x;(6)END;WHILE(7)DOBEGINck:=ai;k:=k+1;i:=i+1;END;WHILE(8)DOBEGINck:=dj;k:=k+1;j:=j+1;END;END.sort36 .下列程序段search(a,n,k)在數(shù)組a的前n(n>=1)個元素中找出第k(1<=k<=n)小的值。這里假設(shè)數(shù)組a中各元素的值都不相同。#defineMAXN100intaMAXN,n,k;intsearch_c(inta

21、,intn,intk)intlow,high,i,j,m,t;k-,;low=0;high=n-1;doi=low;j=high;t=alow;dowhile(i<j&&t<aj)j-;if(i<j)ai+=aj;while(i<j&&t>=ai)i+if(i<j)aj-=ai;while(i<j);ai=t;if(1)if(i<k)low=(2);elsehigh=(3);while(4);return(ak);37 .完善下列程序，每小題在PASCA匿言(a)和C語言(b)中任選一題。下面是一個將廣義表逆置的過

22、程。例如原來廣義表為(a,b),c,(d,e),經(jīng)逆置后為：(e,d),c,(b,a)。(a)算法的PASCA陰言過程描述(編者略)：(b)算法的C語言過程描述：typedefstructglistnodeinttag;structglistnode*next;unionchardata;structstructglistnode*hp,*tp;ptr;val;*glist,gnode;glistreverse(p)glistp;glistq,h,t,s;if(p=NULL)q=NULL;elseif(1)q=(glist)malloc(sizeof(gnode);q->tag=0;q-

23、>val.data=p->val.data;else(2)ift=reverse(p->val.ptr.tp);s=t;while(s->val.ptr.tp!=NULL)s=s->val.ptr.tp;s->val.ptr.tp=(glist)malloc(sizeof(gnode);s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL;s->val.ptr.hp=h;(4)_elseq=(glist)malloc(sizeof(gnode);q->tag=1;q->val.ptr.tp

24、=NULL;(5);return(q);38 .完善下列程序，每小題在PASCA匿言（a）和C語言（b）中任選一題。下面的程序?qū)?shù)列1,2,3，,n*n,依次按蛇型方式存放在二維數(shù)組A1.n,1.n中。即（示意圈編者略）。（a）算法的PASCAL語言程序描述（編者略）：（b）算法的C語言程序描述：#defineNMAX10main()inti,j,n,k,p,q,m;intaNMAXNMAX;scanf("%d'，&n);m=1;for(k=1;(1);k+)if(k<n)q=k;else(2);for(p=1;p<=q;p+)if(3)i=q-p+1；j

25、=p；elsei=p;j=q-p+1;if(4)i=i+n-q;j=j+n-q;aij=m;for(i=1;i<=n;i+)for(j=1;j<=n;j+)printf("%4d,aij);printf("n");39 .約瑟夫環(huán)問題：設(shè)有n個人圍坐一圈，并按順時針方向1n編號。從第s個人開始進行報數(shù)，報數(shù)到第m個人，此人出圈，再從他的下一個人重新開始從1到m的報數(shù)進行下去，直到所有的人都出圈為止。PROCEDUREJosef(A:ARRAY1.nOFinteger;s,m:integer);BEGINFORi:=1TOnDOAi:=i;sl:=s;F

26、ORi:=nDOWNTO2DOBEGINsl:=(1)_;計算出圈人s1IFsl=0THEN(2)_;w:=Asl;/As1出圈FORj:=DOAj:=Aj+1;Ai:=w;END;write(,出圈序列為：)；輸出出圈序列FORi:=nDOWNTO1DOwrite(Ai);writeln;END;40 .設(shè)有一個背包可以放入的物品重量為S,現(xiàn)有n件物品，重量分別為W,W2,.,W。問能否從這n件物品中選擇若干件放入背包，使得放入的重量之和正好是So設(shè)布爾函數(shù)Knap(S,n)表示背包問題的解，W(i=1,2,.,n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在下列算法的下劃線處填空，使其正確求

27、解背包問題。Knap(S,n)若S=0否則若(S<0)或(S>0且n<1)則Kna尸false否則若Knap，=true則print(Wn);Knaptrue否貝UKnapKnap(2),四應(yīng)用題1 .數(shù)組A1.8,-2.6,0.6以行為主序存儲，設(shè)第一個元素的首地址是78,每個元素的長度為4,試求元素A4,2,3的存儲首地址。2 .已知b對角矩陣(aij)n*n,以行主序?qū)條對角線上的非零元存儲在一維數(shù)組中，每個數(shù)據(jù)元素占L個存儲單元，存儲基地址為S,請用i,j表示出aij的存儲位置。3 .數(shù)組A中，每個元素Ai,j的長度均為32個二進位，行下標(biāo)從-1到9,列下標(biāo)從1到1

28、1,從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：(1)存放該數(shù)組所需多少單元？(2)存放數(shù)組第4列所有元素至少需多少單元？(3)數(shù)組按行存放時，元素A7,4的起始地址是多少？(4)數(shù)組按列存放時，元素A4,7的起始地址是多少？4 .假設(shè)按低下標(biāo)優(yōu)先存儲整型數(shù)組A(-3:8,3:5,-4:0,0:7)時，第一個元素的字節(jié)存儲地址是100,每個整數(shù)占4個字節(jié)，問A(0,4,-2,5)的存儲地址是什么？5 .設(shè)有三維數(shù)組A-2:4,0:3,-5:1按列序存放，數(shù)組的起始地址為1210,試求A(1,3,-2)所在的地址。6 .三維數(shù)組A1.10,-2.6,2.8的每個元素的長度為4個字

29、節(jié)，試問該數(shù)組要占多少個字節(jié)的存儲空間？如果數(shù)組元素以行優(yōu)先的順序存貯，設(shè)第一個元素的首地址是100,試求元素A5,0,7的存貯首地址。7 .設(shè)有五對角矩陣A=(au)20*20,按特殊矩陣壓縮存儲的方式將其五條對角線上的元素存于數(shù)組A-10:m中，計算元素A15,16的存儲位置。【東北大學(xué)1999一、2(4分)】8 .數(shù)組A0.8,1.10的元素是6個字符組成的串，則存放A至少需要多少個字節(jié)？A的第8列和第5行共占多少個字節(jié)？若A按行優(yōu)先方式存儲，元素A8,5的起始地址與當(dāng)A按列優(yōu)先方式存儲時的哪個元素的起始地址一致？9 .若按照壓縮存儲的思想將nxn階的對稱矩陣A的下三角部分(包括主對角線

30、元素)以行序為主序方式存放于一維數(shù)組B1.n(n+1)/2中，那么，A中任一個下三角元素aij(i>j),在數(shù)組B中的下標(biāo)位置k是什么？10 .設(shè)mxn階稀疏矩陣A有t個非零元素，其三元組表表示為LTMA1.(t+1),1.3,試問：非零元素的個數(shù)t達到什么程度時用LTMAa示A才有意義？11 .利用三元組存儲任意稀疏數(shù)組時，在什么條件下才能節(jié)省存儲空間。12 .對一個有t個非零元素的Ann矩陣，用B0.t1.3的數(shù)組來表示，其中第0行的三個元素分別為m,n,t,從第一行開始到最后一行，每行表示一個非零元素；第一列為矩陣元素的行號，第二列為其列號，第三列為其值。對這樣的表示法，如果需要經(jīng)

31、常進行該操作-確定任意一個元素Aij在B中的位置并修改其值，應(yīng)如何設(shè)計算法可以使時間得到改13 .有一個二維數(shù)組A0:8,1:5,每個數(shù)組元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址假設(shè)存儲數(shù)組元素A0,1的第一個字節(jié)的地址是0,那么存儲數(shù)組的最后一個元素的第一個字節(jié)的地址是多少？若按行存儲，則A3,5和A5,3的第一個字節(jié)的地址是多少？若按列存儲,則A7,1和A2,4的第一個字節(jié)的地址是多少？14.設(shè)有三對角矩陣（ai,j）m<n,將其三條對角線上的元素逐行的存于數(shù)組B（1:3n-2）中，使得Bk=ai,j,求：（1）用i,j表示k的下標(biāo)變換公式；（2）若n=103,每個元素占用L個單元

32、，則用BK方式比常規(guī)存儲節(jié)省多少單元。15.已知A為稀疏矩陣，試從空間和時間角度，比較采用兩種不同的存儲結(jié)構(gòu)（二維數(shù)組和n“aii三元組表）完成求匕運算的優(yōu)缺點。16 .特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機存取的功能？為什么？17 .試敘述一維數(shù)組與有序表的異同。18 .一個nXn的對稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為多少？19 .給出數(shù)組A:ARRAY3.8,2.6OFINTEGER;當(dāng)它在內(nèi)存中按行存放和按列存放時，分別寫出數(shù)組元素Ai,j地址計算公式（設(shè)每個元素占兩個存儲單元）。20 .已知n階下三角矩陣A（即當(dāng)i<j時，有aij=0）,按照壓縮存儲的思想，可以將

33、其主對角線以下所有元素（包括主對角線上元素）依次存放于一維數(shù)組B中，請寫出從第一列開始采用列序為主序分配方式時在B中確定元素aij的存放位置的公式。21 .設(shè)有三對角矩陣（au）n*n,將其三條對角線上的元素逐行地存于數(shù)組B（1:3n-2）中，使得Bk=aij,求：（1）用i,j表示k的下標(biāo)變換公式；（2）用k表示i,j的下標(biāo)變化公式。22 .算法Print及所引用的數(shù)組A的值如下，寫出調(diào)用Print（1）的運行結(jié)果（其中n=15）。123456789101112131415ABCDEFGOOH0IJKLPROCEDUREprint(i：integer);BEGINIF(i<=nAND(

34、Ai<>'0')THENBEGINPrint(2*i);write(Ai);Print(2*i+1);END;END;23 .設(shè)數(shù)組A的長度為2N,前N個元素A1.N遞減有序，后N個元素AN+1.2N遞增有序，且2N是2的整數(shù)次哥，即k=log22N為整數(shù)。例如A1.8=90,85,50,10,30,65,80,100滿足上述要求，這里N=4,k=3,A的前4個元素和后4個元素分別遞減和遞增有序。用此例調(diào)用如下的Demod±程，并要求：(1)給出for循環(huán)中每次執(zhí)行PerfectShuffle(A,N)和CompareExchange(A,N)的結(jié)果;(2

35、)解釋Demo的功能；(3)給出Demo的時間復(fù)雜度。PROCEDUREPerfectShuffle(VARA:arraytype;N:integer)i:=1;j:=1;WHILEi<=NDOBj:=Ai;Bj+1:=Ai+N;i:=i+1;j:=j+2;A1.2N:=B1.2N;/BcopytoAPROCEDURECompareExchange(VARA:arraytype;N:integer)j:=1;WHILEj<2NDO>Aj+1;/交換Aj和Aj+1IFAj>Aj+1THENAjj：可+2；PROCEDUREDemo(VARA:arraytype;N:int

36、eger)/A的長度為2N,k=log22N為整數(shù)FORi:=1TOlog22NDOPerfectShuffle(A,N);CompareExchange(A,N);24 .現(xiàn)有算法及正整數(shù)n和數(shù)組A如下，求數(shù)組C的值。VARA,B,C:Array1.100ofinteger;FUNCAAA(s,t:integer):integer;IFs=tTHENIFBs=0THENAAA:=SELSEAAA:=-sELSEBEGINl:=AAA(s,(s+t)DIV2);r:=AAA(s+t)DIV2+1,t);IFl>0THENAAA:=lELSEAAA:=r;IF(r>0)AND(Al&

37、gt;Ar)THENAAA:=rENDENDF;PROCBBB;FORi:=1TOnDOBi:=0;FORi:=1TOnDOBAAA(1,n):=i;FORi:=1TOnDOCBi:=Ai;ENDP;初始值：n=10,A=121,22,323,212,636,939,828,424,55,262;2 133 3125 .設(shè)有矩陣a且a=J21-執(zhí)行下列語句后，矩陣c和a的結(jié)果分別是什么？(1) FORi:=1TO3DOFORj:=1TO3DOci,j:=aai,j,aj,i(2) FORi:=1TO3DOFORj:=1TO3DOai,j:=aai,j,aj,i21333126 .設(shè)矩陣A為12

38、1-(1)執(zhí)行語句FORi:=1TO3DOFORj:=1TO3DOCi,j:=AAi,j,Aj川結(jié)果C矩陣的值是什么？(2)所選擇的下標(biāo)i,j的次序有關(guān)系嗎？(3)在語句中，用A代替C,A的結(jié)果值是什么?(4)對i,j這對下標(biāo)取反序，即(3,3),(3,2),(3,1),，(1,3),(1,2),(1,1)重復(fù)執(zhí)行(3),把所得結(jié)果與(3)中所得結(jié)果作比較。27 .指出下列算法中錯誤、低效之處，并將其改成一個正確且高效的算法。PROCEDUREdelk(A,m,last,i,k);從數(shù)組A1.last中刪除第i個元素起的k個元素，m為A上限BEGINIF(i<1)OR(i>last

39、)OR(k<0)OR(last>m)THENwrite('error')ELSEFORcount:=1TOkTOFORj:=lastDOWNTOi+1DOAj-1:=Aj;last:=last-1ENDP;delk28 .設(shè)輸入為整數(shù)數(shù)組A1.n，其中1<=Ai<=k(1<=i<=n);輸出數(shù)組為b1.n;c1.k是臨時工作空間；閱讀下述算法后，回答下列問題：PROCDemo(A,B,k)(1)FORi:=1TOkDOCi:=0;(2)FORj:=1TOnDOCAj:=CAj+1;(3)FORi:=2TOkDOCi:=Ci+Ci-1(4)FO

40、Rj:=nDOWNTO1DO(5) BCA皿kAj;(6)CAj:=CAj-1(a) .當(dāng)標(biāo)號(2)行的循環(huán)執(zhí)行完后，Ci(1<=i<=n)的值有何意義？(b) .當(dāng)標(biāo)號(3)行的循環(huán)執(zhí)行完后，Ci(1<=i<=n)的值有何意義？(c) .算法執(zhí)行后，B的內(nèi)容有何特點？(d) .當(dāng)k=O(n)時，算法的時間復(fù)雜度是多少？29 .上三角陣A(N*N)按行主序壓縮存放在數(shù)組B中，其中Ai,j=Bk.寫出用i,j表示的k。30 .設(shè)有上三角矩陣(aij)n*n,將其上三角中的元素按先行后列的順序存于數(shù)組B(1:m)中，使得Bk=aj且k=f1(i)+f2(j)+c,請推導(dǎo)出函

41、數(shù)f1,f2和常數(shù)c,要求f1和f2中不含常數(shù)項。20040030030031.設(shè)矩陣A”40001(1)若將A視為對稱矩陣，畫出對其壓縮存儲的存儲表，并討論如何存取A中元素aij(0<=i,j<4)；(2)若將A視為稀疏矩陣，畫出A的十字鏈表結(jié)構(gòu)。10020300000532,設(shè)對稱矩陣A=_20501(2)若將A視為稀疏矩陣時,畫出其三元組表形式壓縮存儲表。一110033,設(shè)對角線矩陣A=j020000100210000010035行列下標(biāo)i,j滿足：1Wi,j<5)(1)若將A中包括主對角線的下三角元素按列的順序壓縮到數(shù)組S中，即S:1002300050下標(biāo)：12345

42、678910試求出A中任一元素的行列下標(biāo)i,j(1<=i,j<=4)與S中元素的下標(biāo)K之間的關(guān)系(1)若將矩陣A壓縮存儲到數(shù)組S中:1210121000135下標(biāo)：12345678910111213試求出A中已存儲之元素的行列下標(biāo)(i,j)與S中元素的下標(biāo)K之間的關(guān)系(2)若將A視為稀疏距陣時，請畫出其行邏輯鏈接順序表。34.設(shè)有一個三維數(shù)組ac1:d1,c2:d2,c3:d3,其中ci:di是第i維的界偶，如該數(shù)組在的地址,內(nèi)存中按行排列，且ac1,c2,c3的地址為a0,那么請導(dǎo)出下標(biāo)變量ai1,i2,i3假設(shè)每個元素占L個單元。35假定有下列n為奇數(shù))a1100a22八n1n

43、10a,220a1na2,n-10.00A=-an1ann如果用一維數(shù)組B按行主次序存儲A的非零元素,問:A12A13A1nA22A23A2nA33，.A3n(1)A中非零元素的行下標(biāo)與列下標(biāo)的關(guān)系；(2)給出A中非零元素aij的下標(biāo)(i,j)與B中的下標(biāo)R的關(guān)系;(3)假定矩陣中每個元素占一個存貯單元且B的起始地址為A,給出利用a.的下標(biāo)(i,j)定位在B中的位置公式。36.對于一個對稱矩陣采用壓縮存儲，只存放它的上三角部分，并按列存放。例如對于一個n*n的對稱矩陣A(如右圖)，用一個一維數(shù)組B來存放它的上三角部分：B=An,A12,A22,A13,A23,A33,A14)An,A2n,Ai

44、n同時有兩個函數(shù)：MAX(i,j)和MIN(i,j),分別計算下標(biāo)i和j中的大者與小者。試利用它們給出求任意一個Aij在B中存放位置的公式。(若式中沒有MAX(I,j)和MIN(i,j)則不給分)37.用三元數(shù)組表示稀疏矩陣的轉(zhuǎn)置矩陣，并簡要寫出解題步驟。38 .簡述廣義表屬于線性結(jié)構(gòu)的理由。39 .數(shù)組，廣義表與線性表之間有什么樣的關(guān)系？40 .什么是廣義表？請簡述廣義表和線性表的主要區(qū)別。41 .求下列廣義表的運算結(jié)果。(1) CAR(CDR(a,b),(c,d),(e,f)(2) CDR(CAR(a,b),(c,d),(e,f)(3) CAR(CDR(CAR(a,b),(e,f)(4)

45、CDR(CAR(CDR(a,b),(e,f)(5) CDR(CDR(CAR(a,b),(e,f)注：CAR!算相當(dāng)于有些教材中的Head運算，CDR!算相當(dāng)于Tail運算。42 .利用廣義表的Head和Tail運算，把原子d分別從下列廣義表中分離出來，L1=(a),b),d),e)；L2=(a,(b,(d),e)。類似本題的另外敘述有：(1)已知廣義表L=(a),(b),(c),d)，試利用head和tail運算把原子項c從L中分離出來。(2)畫出下列廣義表的存儲結(jié)構(gòu)圖，并利用取表頭和取表尾的操作分離出原子e。(a,(),b),(e)。(3)已知廣義表A=(a,b,c),(d,e,f)試寫出從

46、表A中取出原子元素e的運算。(4)請將香蕉banana用工具H()Head(),T()Tail()從L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)(5) 試利用廣義表取表頭head(ls)和取表尾tail(ls)的基本運算，將原子d從下列表中分解出來，請寫出每一步的運算結(jié)果。L=(a,(b),(c,d),(e,f)(6)畫出廣義表A=(a,(b,(),(),c)的第一種存儲結(jié)構(gòu)(表結(jié)點第二指針指向余表)圖，并用取首元(head()和取尾元(tail()函數(shù)表示原子c。43 .畫出下列廣義表的兩種存儲結(jié)構(gòu)圖(),A,(B,(C,D)

47、,(E,F)。44 .假設(shè)采用以下兩種結(jié)點的鏈表作為廣義表的存貯結(jié)構(gòu)，表結(jié)點：(tag=1,hp,tp),元素結(jié)點；(tag=0,data)。請畫出下列廣義表的存儲結(jié)構(gòu)圖，并求它的深度和長度。(),(),()45 .知廣義表A=(a),(b),c,(a),(d,e)(1)畫出其一種存貯結(jié)構(gòu)圖；(2)寫出表的長度與深度；(3)用求頭部，尾部的方式求出e。【東北大學(xué)1997一、2(5分)46 .畫出具有共享結(jié)構(gòu)廣義表(b,c),d),(a),(a),(b,c),d),e,()的存貯表示。47 .廣義表的結(jié)點結(jié)構(gòu)如下：(TAG,DATA,LINK)。其中LINK為指向表中下一元素的指針；TAG為標(biāo)志

48、域；DATA為數(shù)據(jù)域，具體含義如下：TAG=0a示該結(jié)點為原子結(jié)點，DATA為其數(shù)據(jù)；TAG=1表示該結(jié)點為一個子表，DATA為指向該子表的指針。(1)說明下列算法A的功能(注：算法中p,t,m,n,r,q為指針；算法中的NIL對應(yīng)圖中的人)PROCEDUREA(p,t)q:=NIL;WHILEp<>NILDOBEGINIFp'TAG<>0THENBEGINm:=pA.DATA;A(m,n);pA.DATA:=n;END;r:=pA.LINK;pA.LINK:=q;q：=p;p:=rEND;t：=q;END.(2)對于p所指的廣義表，畫出執(zhí)行算法A后的表結(jié)構(gòu)以及

49、p,t的值:類似本題的另外敘述有：題目基本相同，差別僅在于子表(b,c)與原子d的前后順序顛倒?！菊憬髮W(xué)1994六(7分)】48 .寫出對廣義表A=(x,(a,b),c,d)作運算head(head(tail(A)后的結(jié)果。49 .寫出廣義表的運算結(jié)果:TAILHEADTAIL(a,b),(c,d)二?50 .廣義表中原子個數(shù)是否即為廣義表的長度？51 .給出下列所示的3元多項式的廣義表表示(分別以Xi,X2,X3第一到第三層變元)P(X1X2X3)=X5X23Xi+2Xi5X22Xi4+5X5X23X33+3XiX24X32+X2X3+652 .設(shè)某表H如下：ABCXa1a2b1c1c2其

50、中A,B,C為子表名，a1,a2,b1,c1,c2,x為其元素。(1)試用廣義表形式表示H,并寫出運算HEAD(H和TAIL(H)函數(shù)從H中取出單元素a2的運算；(2)畫出表H的鏈?zhǔn)酱鎯Y(jié)構(gòu)；五算法設(shè)計題1 .設(shè)有大小不等的n個數(shù)據(jù)組(n個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m),順序存放在空間區(qū)D內(nèi)，每個數(shù)據(jù)占一個存儲單元，數(shù)據(jù)組的首地址由數(shù)組S給出，(如下圖所示)，試編寫將新數(shù)據(jù)x插入到第i個數(shù)據(jù)組的末尾且屬于第i個數(shù)據(jù)組的算法，插入后，空間區(qū)D和數(shù)組S的相互關(guān)系仍保持正確。JJ2 .以三元組表存貯的稀疏矩陣A,B非零元個數(shù)分別為m和n。試用類PASCA用言編寫時間復(fù)雜度為O(m+力的算法將矩陣B加到矩陣

51、A上去。A的空間足夠大，不另加輔助空間。要求描述所用結(jié)構(gòu)。3 .設(shè)整數(shù)Xi,X2，,Xn已存放在數(shù)組A中，編寫一PASCAU1歸過程，出從這n個數(shù)中取出所有k個數(shù)的所有組合(k<=n)。例：若A中存放的數(shù)是1,2,3,4,5,k為3,則輸出結(jié)果應(yīng)為：543,542,541,532,531,521,432,431,421,321。類似本題的另外敘述有：(1)題目基本相同，只是敘述不同，要求用PASCA匿言。【東南大學(xué)2001三(10分)】4.編寫一個過程，對一個nxn矩陣，通過行變換，使其每行元素的平均值按遞增順序排列。5 .設(shè)原來將N個自然數(shù)1,2,N按某個順序存于數(shù)組A中，經(jīng)過下面的語

52、句計算，使AI的值變?yōu)锳1到AI-1中小于原AI值的個數(shù)。FORI:=NDOWNTO1DOBEGINC:=0;FORJ:=1TOI-1DOIFAJ<AITHENC:=C+1;AI:=CEND;編程將經(jīng)過上述處理后的A還原成原來的Ao6 .請編寫完整的程序。如果矩陣A中存在這樣的一個元素Ai,j滿足條件：Ai,j是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點。請編程計算出m*n的矩陣A的所有馬鞍點。7 .給定一個整數(shù)數(shù)組b0.N-1,b中連續(xù)的相等元素構(gòu)成的子序列稱為平臺。試設(shè)計算法，求出b中最長平臺的長度。8 .給定nxm矩陣Aa.b,c.d,并設(shè)Ai,j

53、<Ai,j+1(awiwb,cwjwd-1)和Ai,j<Ai+1,j(a<i<b-1,c<j<d).設(shè)計一算法判定X的值是否在A中，要求時間復(fù)雜度為O(m+n)。類似本題的另外敘述有：(1)給定整型數(shù)組B0.m,0.n。已知B中數(shù)據(jù)在每一維方向上都按從小到大的次序排列，且整型變量x在B中存在。試設(shè)計一個程序段找出一對滿足Bi,j=x的(i,j)值，要求比較次數(shù)不超過m+n.(2)給定nxm矩陣Aa.b,c.d,并設(shè)Ai,j<=Ai,j+1(a<=i<=b,c<=j<=d-1)知Ai,j<=Ai+1,j,(a<=i<=b-1,c<=j<=d)。設(shè)計一算法以比O(n*m)小的最壞時間復(fù)雜性判定值x是否在A中。9.編寫算法，將自然數(shù)1M按“蛇形”填入nxn矩陣中。例(14之)如圖所示：(用13410259116812157131416程序?qū)崿F(xiàn))10.設(shè)二維數(shù)組