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

習(xí)題五 數(shù)組和廣義表一、單項選擇題1常對數(shù)組進(jìn)行的兩種基本操作是（ ）A.建立與刪除 B. 索引與修改 C. 查找與修改 D. 查找與索引2對于C語言的二維數(shù)組DataType Amn,每個數(shù)據(jù)元素占K個存儲單元，二維數(shù)組中任意元素ai,j 的存儲位置可由( )式確定.A.Loci,j=Am,n+(n+1)*i+j*kB.Loci,j=loc0,0+(m+n)*i+j*kC.Loci,j=loc0,0+(n+1)*i+j*kD.Loci,j=(n+1)*i+j*k3稀疏矩陣的壓縮存儲方法是只存儲 ( )A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j4. 數(shù)組A0.5,0.6的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A5，5的地址是( )。A. 1175 B. 1180 C. 1205 D. 12105. AN，N是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組TN（N+1）/2中，則對任一上三角元素aij對應(yīng)Tk的下標(biāo)k是（ ）。A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+16. 用數(shù)組r存儲靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中結(jié)點(diǎn)，使j 沿鏈移動的操作為( )。 A. j=rj.next B. j=j+1 C. j=j-next D. j=rj- next7. 對稀疏矩陣進(jìn)行壓縮存儲目的是（ ）。A便于進(jìn)行矩陣運(yùn)算 B便于輸入和輸出 C節(jié)省存儲空間 D降低運(yùn)算的時間復(fù)雜度8. 已知廣義表LS(a,b,c),(d,e,f),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是( )。 A. head(tail(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)9. 廣義表（a,b,c,d）的表頭是（ ），表尾是（ ）。A. a B.（） C.（a,b,c,d） D.（b,c,d）10. 設(shè)廣義表L=（a,b,c），則L的長度和深度分別為（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和311. 下面說法不正確的是( )。 A. 廣義表的表頭總是一個廣義表 B. 廣義表的表尾總是一個廣義表C. 廣義表難以用順序存儲結(jié)構(gòu) D. 廣義表可以是一個多層次的結(jié)構(gòu)二、填空題1通常采用_存儲結(jié)構(gòu)來存放數(shù)組 。對二維數(shù)組可有兩種存儲方法：一種是以_為主序的存儲方式，另一種是以_為主序的存儲方式。2. 用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素Ai,j (1in,i-2ji+2),B中的第8個元素是A 中的第_ _行，第_ _列的元素。3設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組B1.n*（n+1）/2中，若按行為主序存儲，則Ai,j對應(yīng)的B中存儲位置為_。4. 所謂稀疏矩陣指的是_ 。5. 廣義表簡稱表，是由零個或多個原子或子表組成的有限序列，原子與表的差別僅在于_ 。為了區(qū)分原子和表，一般用 _表示表，用 _表示原子。一個表的長度是指 _，而表的深度是指_ _6設(shè)廣義表L=(),(), 則head(L)是 ；tail(L)是 ；L的長度是 ；深度是 _。7基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種，以下運(yùn)算按照矩陣A的列序來進(jìn)行轉(zhuǎn)置，請在_處用適當(dāng)?shù)木渥佑靡蕴畛?。Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) q=1; for(col=1; _;col+) for(p=1;ptag=0; q-val.data=p-val.data; else (2) if (3) t=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) _ else q=(glist)malloc(sizeof(gnode);q-tag=1; q-val.ptr.tp=NULL; (5) ; return(q);三、應(yīng)用題1. 數(shù)組A1.8，-2.6，0.6以行為主序存儲，設(shè)第一個元素的首地址是78，每個元素的長度為4，試求元素A4,2,3的存儲首地址。2. 特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機(jī)存取的功能？為什么？3. 數(shù)組，廣義表與線性表之間有什么樣的關(guān)系？ 4. 設(shè)有三對角矩陣(aij)n*n，將其三條對角線上的元素逐行地存于數(shù)組B(1:3n-2)中，使得Bk=aij，求：（1）用i,j表示k的下標(biāo)變換公式；（2）用k表示i,j的下標(biāo)變化公式。5畫出下面廣義表的兩種存儲結(jié)構(gòu)圖示： (a), b), ( ), d), (e, f)6求下列廣義表運(yùn)算的結(jié)果：（1） HEAD(a,b),(c,d); （2） TAIL(a,b),(c,d); （3） TAILHEAD(a,b),(c,d); （4） HEADTAILHEAD(a,b),(c,d); （5） TAILHEADTAIL(a,b),(c,d); 7. 利用廣義表的Head和ail運(yùn)算，把原子d分別從下列廣義表中分離出來，L1(a),b),d),e)；L2（a,(b,(d),e)）。 四、算法設(shè)計題1. 給定nxm矩陣Aa.b,c.d,并設(shè)Ai,jAi,j+1(aib,cjd-1)和Ai,jAi+1,j(aib-1,cjd).設(shè)計一算法判定X的值是否在A中,要求時間復(fù)雜度為O(m+n)。2. 設(shè)二維數(shù)組a1.m, 1.n 含有m*n 個整數(shù)。(1) 寫出算法：判斷a中所有元素是否互不相同?輸出相關(guān)信息(yes/no)；(2) 試分析算法的時間復(fù)雜度。3. 設(shè)A1.100是一個記錄構(gòu)成的數(shù)組，B1.100是一個整數(shù)數(shù)組，其值介于1至100之間，現(xiàn)要求按B1.100的內(nèi)容調(diào)整A中記錄的次序，比如當(dāng)B1=ll時，則要求將A1的內(nèi)容調(diào)整到A11中去。規(guī)定可使用的附加空間為O(1)。4稀疏矩陣用三元組的表示形式，試寫一算法實(shí)現(xiàn)兩個稀疏矩陣相加，結(jié)果仍用三元組表示。5. 試編寫建立廣義表存儲結(jié)構(gòu)的算法，要求在輸入廣義表的同時實(shí)現(xiàn)判斷、建立。設(shè)廣義表按如下形式輸入（a1,a2,a3,an） n=0，其中ai或?yàn)閱巫帜副硎镜脑踊驗(yàn)閺V義表，n=0時為只含空格字符的空表。第5章 數(shù)組和廣義表一、單項選擇題1 C2 C3 A4 A5 B6 A7 C8 C9 C10 C11 A二、填空題1順序、列序、行序2. 第1行 第3列3i(i-1)/2+j (1=i,j=n)4. 非零元很少(tm*n)且分布沒有規(guī)律5 （1） 原子（單元素）是結(jié)構(gòu)上不可再分的，可以是一個數(shù)或一個結(jié)構(gòu)；而表帶結(jié)構(gòu)，本質(zhì)就是廣義表，因作為廣義表的元素故稱為子表。 （2）大寫字母 （3）小寫字母 （4）表中元素的個數(shù)（5）表展開后所含括號的層數(shù)6（1）（） （2）（） （3）2 （4）27 coltag=0) /處理原子（2）h=reverse(p-val.ptr.hp) /處理表頭（3）(p-val.ptr.tp) /產(chǎn)生表尾的逆置廣義表（4）s-val.ptr.tp=t; /連接（5）q-val.ptr.hp=h /頭結(jié)點(diǎn)指向廣義表三、應(yīng)用題1. 958 三維數(shù)組以行為主序存儲，其元素地址公式為：LOC(Aijk)=LOC(Ac1c2c3)+(i-c1)V2V3+(j-c2)V3+(k-c3)*L+1其中ci,di是各維的下界和上界，Vi=di-ci+1是各維元素個數(shù)，L是一個元素所占的存儲單元數(shù)。2. 特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對非零元素分配單元（對值相同元素只分配一個單元），將非零元素存儲在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡單公式表示，仍具有隨機(jī)存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很小（tm*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機(jī)存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存取下標(biāo)為i和j的元素時，要掃描三元組表，下標(biāo)不同的元素，存取時間也不同，最好情況下存取時間為O(1)，最差情況下是O(n)，因此也失去了隨機(jī)存取的功能。3. 數(shù)組是具有相同性質(zhì)的數(shù)據(jù)元素的集合，同時每個元素又有唯一下標(biāo)限定，可以說數(shù)組是值和下標(biāo)偶對的有限集合。n維數(shù)組中的每個元素，處于n個關(guān)系之中，每個關(guān)系都是線性的，且n維數(shù)組可以看作其元素是n-1維數(shù)組的一個線性表。廣義表中的元素，可以是原子，也可以是子表，即廣義表是原子或子表的有限序列，滿足線性結(jié)構(gòu)的特性：在非空線性結(jié)構(gòu)中，只有一個稱為“第一個”的元素，只有一個成為“最后一個”的元素，第一元素有后繼而沒有前驅(qū)，最后一個元素有前驅(qū)而沒有后繼，其余每個元素有唯一前驅(qū)和唯一后繼。從這個意義上說，廣義表屬于線性結(jié)構(gòu)。 4. 三對角矩陣第一行和最后一行各有兩個非零元素，其余每行均有三個非零元素，所以共有3n-2個元素。（1）主對角線左下對角線上的元素下標(biāo)間有i=j+1關(guān)系，k與i和j的關(guān)系為k=3(i-1);主對角線上元素下標(biāo)間有關(guān)系i=j，k與i和j的關(guān)系為k=3(i-1)+1; 主對角線右上那條對角線上元素下標(biāo)間有關(guān)系i=j-1，k與i和j的關(guān)系為k=3(i-1)+2。綜合以上三等式，有k=2(i-1)+j (1=i,j=n, |i-j|x， 這情況下向j 小的方向繼續(xù)查找；二是Ai,jx，下步應(yīng)向i大的方向查找；三是Ai,j=x，查找成功。否則，若下標(biāo)已超出范圍，則查找失敗。void search(datatype A , int a,b,c,d, datatype x) /n*m矩陣A,行下標(biāo)從a到b,列下標(biāo)從c到d,本算法查找x是否在矩陣A中. i=a; j=d; flag=0; /flag是成功查到x的標(biāo)志 while(i=c) if(Aij=x) flag=1;break; else if (Aijx) j-; else i+; if(flag) printf(“A%d%d=%d”,i,j,x); /假定x為整型. else printf(“矩陣A中無%d 元素”，x)； 算法search結(jié)束。算法討論算法中查找x的路線從右上角開始，向下（當(dāng)xAi,j）或向左（當(dāng)xAi,j）。向下最多是m，向左最多是n。最佳情況是在右上角比較一次成功，最差是在左下角（Ab,c），比較m+n次，故算法最差時間復(fù)雜度是O(m+n)。2.題目分析判斷二維數(shù)組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結(jié)論為不是互不相同。如何達(dá)到每個元素同其它元素比較一次且只一次？在當(dāng)前行，每個元素要同本行后面的元素比較一次（下面第一個循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。int JudgEqual(ing amn,int m,n) /判斷二維數(shù)組中所有元素是否互不相同，如是，返回1；否則，返回0。for(i=0;im;i+) for(j=0;jn-1;j+) for(p=j+1;pn;p+) /和同行其它元素比較 if(aij=aip) printf(“no”); return(0); /只要有一個相同的，就結(jié)論不是互不相同 for(k=i+1;km;k+) /和第i+1行及以后元素比較 for(p=0;pn;p+) if(aij=akp) printf(“no”); return(0); / for(j=0;jn-1;j+)printf(yes”); return(1); /元素互不相同/算法JudgEqual結(jié)束（2）二維數(shù)組中的每一個元素同其它元素都比較一次，數(shù)組中共m*n個元素，第1個元素同其它m*n-1個元素比較，第2個元素同其它m*n-2 個元素比較，第m*n-1個元素同最后一個元素(m*n)比較一次,所以在元素互不相等時總的比較次數(shù)為 (m*n-1)+(m*n-2)+2+1=（m*n）(m*n-1)/2。在有相同元素時,可能第一次比較就相同,也可能最后一次比較時相同,設(shè)在(m*n-1)個位置上均可能相同,這時的平均比較次數(shù)約為（m*n）(m*n-1)/4，總的時間復(fù)雜度是O(n4)。3. 題目分析題目要求按B數(shù)組內(nèi)容調(diào)整A數(shù)組中記錄的次序，可以從i=1開始，檢查是否Bi=i。如是，則Ai恰為正確位置，不需再調(diào)；否則，Bi=ki，則將Ai和Ak對調(diào)，Bi和Bk對調(diào)，直到Bi=i為止。void CountSort (rectype A,int B)/A是100個記錄的數(shù)組，B是整型數(shù)組，本算法利用數(shù)組B對A進(jìn)行計數(shù)排序int i,j,n=100;i=1;while(in) if(Bi!=i) /若Bi=i則Ai正好在自己的位置上，則不需要調(diào)整 j=i; while (Bj!=i) k=Bj; Bj=Bk; Bk=k; / Bj和Bk交換 r0=Aj;Aj=Ak; Ak=r0; /r0是數(shù)組A的元素類型,Aj和Ak交換i+; /完成了一個小循環(huán)，第i個已經(jīng)安排好/算法結(jié)束4解答：本題首先判斷三元組A，B表示的矩陣是否行列相同，若相同才能進(jìn)行矩陣的加法運(yùn)算。若三元組表示的矩陣能進(jìn)行相加運(yùn)算，其思路如下： 若a,b表的指針均沒有到表尾，重復(fù)下列步驟：（1） 若a表元素的i 域值小于b表元素的i域值，將a表當(dāng)前元素插入到c表表尾， a表指針后移。（2） 若a表元素的i 域值大于b表元素的i域值，將b表當(dāng)前元素插入到c表表尾， b表指針后移。（3） 若a表元素的i域值等于b表元素的i域值，又分以下幾種情況討論：若a表元素的j域值小于b表元素的j域值，將a表當(dāng)前元素插入到c表表尾，a表指針后移。若a表元素的j域值大于b表元素的j域值，將b表當(dāng)前元素插入到c表表尾，b表指針后移。若a表元素的j域值等于b表元素的j域值，若a,b表當(dāng)前元素的v域值和非零，則在c表表尾播入元素的Ij域值等于a表當(dāng)前元素的Ij域 的值，域v的值等于a,b表的域值的和，將a,b表當(dāng)前指針后移。(4) 若a表的指針沒到表尾，b表的指針到表尾，將a表剩余元素依次插入到c表表尾，否則，將b表剩余元素依次插入到c表表尾.SpMaterixTp trsxsum(SpMaterixTp a, SpMaterixTp b , SpMaterixTp c)if ( (a .mu=b. mu)&(a.nu=b.mu) /*a，b為同行同列矩陣*/ c.mu=a.mu ;c.nu=a.nu; I=1; j=1; p=0;if (a.tu&b.tu) /*a，b為非空矩陣*/ cola=a.dataI.i; rowa = a.dataI .j; /*取三元組a的元素的行、列下標(biāo)*/ colb= b.dataj.i; rowb =b.dataj .j; /*取三元組b的元素的行、列下標(biāo)