數(shù)據(jù)結(jié)構(gòu)第五章習(xí)題課

1、1、 特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后會(huì)失去隨機(jī)存取的功能?為什么?答：后者在采用壓縮存儲(chǔ)后將會(huì)失去隨機(jī)存儲(chǔ)的功能。因?yàn)樵谶@種矩陣中，非零元素的分布是沒(méi)有規(guī)律的，為了壓縮存儲(chǔ)，就將每一個(gè)非零元素的值和它所在的行、列號(hào)作為一個(gè)結(jié)點(diǎn)存放在一起，這樣的結(jié)點(diǎn)組成的線(xiàn)性表中叫三元組表，它已不是簡(jiǎn)單的向量，所以無(wú)法用下標(biāo)直接存取矩陣中的元素。2、二維數(shù)組M的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲(chǔ)時(shí)元素M35的起始地址與M按列存儲(chǔ)時(shí)元素（ ）的起始地址相同。 A、M24B、M34C、M35D、M443、設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓

2、縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。A. 13 B. 33 C. 18 D. 404、若對(duì)n階對(duì)稱(chēng)矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線(xiàn)上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aij（i<j）的位置k的關(guān)系為( )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i5、設(shè)A是n*n的對(duì)稱(chēng)矩陣，將A的對(duì)角線(xiàn)及對(duì)角線(xiàn)上方的元素以列為主的次序存放在一維數(shù)組B1.n(n+1)/2中，對(duì)上述任一元素aij(1i，

3、jn，且ij)在B中的位置為( )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-16、設(shè)二維數(shù)組A1. m，1. n（即m行n列）按行存儲(chǔ)在數(shù)組B1. m*n中，則二維數(shù)組元素Ai，j在一維數(shù)組B中的下標(biāo)為( )。A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-17、有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是（ ）。A. 60 B. 66 C. 18000 D. 33 8、已知廣義表L=（x,y,z），a，（u，t

4、，w），從L表中取出原子項(xiàng)t的運(yùn)算是（ ）。A.head（tail（tail（L） B.tail（head（head（tail（L） C.head（tail（head（tail（L） D.head（tail(head（tail（tail（L）)）9、下面說(shuō)法不正確的是( )。 A. 廣義表的表頭總是一個(gè)廣義表 B. 廣義表的表尾總是一個(gè)廣義表C. 廣義表難以用順序存儲(chǔ)結(jié)構(gòu) D. 廣義表可以是一個(gè)多層次的結(jié)構(gòu)10、若采用按行優(yōu)先順序存儲(chǔ)，試寫(xiě)出三維數(shù)組A323所有元素在內(nèi)存中的存儲(chǔ)次序。答：A000，A001，A002，A010，A011，A012，A100，A101，A102，A110，A11

5、1，A112，A200，A201，A202，A210，A211，A212 11、二維數(shù)組Amn采用按行存儲(chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的存儲(chǔ)地址是LOC（A00），則Aij的存儲(chǔ)地址是 。答：LOC（A00）+（n*i+j）*k12、三維數(shù)組a456（下標(biāo)從0開(kāi)始計(jì)，a有4*5*6個(gè)元素），每個(gè)元素的長(zhǎng)度是2，則a234的地址是_。(設(shè)a000的地址是1000,數(shù)據(jù)以行為主方式存儲(chǔ)) 答：1164 公式：LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-c2)+(k-c3)*l (l為每個(gè)元素所占單元數(shù))13、假設(shè)一個(gè)15階的上三角矩陣A按行優(yōu)先順序壓縮存儲(chǔ)

6、在一維數(shù)組B中，則非零元素A9,9在B中的存儲(chǔ)位置k=_。 （ 注：矩陣元素下標(biāo)從1開(kāi)始 ）答：9314、設(shè)廣義表L=(),(), 則head(L)是(1)_；tail(L)是(2)_；L的長(zhǎng)度是(3)_；深度是 (4)_。答：（1）（） （2）（） （3）2 （4）215、廣義表A=（a，b），（c，d，e），取出A中的原子e的操作是: _。答：head(tail(tail(head(tail(head(A)16、設(shè)對(duì)稱(chēng)矩陣A=（1）若將A中包括主對(duì)角線(xiàn)的下三角元素按列的順序壓縮到數(shù)組S中, 即S:1002300050下標(biāo)： 1 2 3 4 5 6 7 8 9 10試求出A中任一元素的行列下

7、標(biāo)i,j(1<=i,j<=4)與S中元素的下標(biāo)K之間的關(guān)系.（2）若將A視為稀疏矩陣時(shí),畫(huà)出其三元組表形式壓縮存儲(chǔ)表。答：（1）k=(2n-j+2)(j-1)/2+i-j+1 （當(dāng)ij時(shí)，本題n=4）k=(2n-i+2)(i-1)/2+j-i+1 （當(dāng)i<j時(shí)，本題n=4） （2）稀疏矩陣的三元組表為：s=(4,4,6),(1,1,1),(1,4,2),(2,2,3),(3,4,5),(4,1,2),(4,3,5)。其中第一個(gè)三元組是稀疏矩陣行數(shù)、列數(shù)和非零元素個(gè)數(shù)。其它三元組均為非零元素行值、列值和元素值。17、設(shè)任意n個(gè)整數(shù)存放于數(shù)組A(1:n)中，試編寫(xiě)程序，將所有正數(shù)

8、排在所有負(fù)數(shù)前面（要求算法復(fù)雜性為0( n)）。 類(lèi)似本題的另外敘述有：（1）已知數(shù)組A1.n的元素類(lèi)型為整型，設(shè)計(jì)算法調(diào)整A，使其左邊的所有元素小于零，右邊的所有元素大于等于零。（要求算法的時(shí)間復(fù)雜度和空間復(fù)雜度均為0（n）（2）設(shè)計(jì)一個(gè)算法，把整數(shù)數(shù)組中所有的偶數(shù)放到所有的奇數(shù)之前。要求時(shí)間、空間效率盡可能高。（3）設(shè)一系列正整數(shù)存放在一個(gè)數(shù)組中，試設(shè)計(jì)算法，將所有奇數(shù)存放在數(shù)組的前半部分，將所有的偶數(shù)存放在數(shù)組的后半部分。要求盡可能少用臨時(shí)存儲(chǔ)單元并使時(shí)間最少。請(qǐng)?jiān)囍治瞿銓?shí)現(xiàn)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。（4）設(shè)計(jì)算法將數(shù)組A1.n調(diào)整為左右兩部分，使的左邊所有的元素小于右邊的所有元

9、素，并給出這一劃分的分界位置。要求算法的時(shí)間復(fù)度為O(n)。 答：題目分析本題屬于排序問(wèn)題，只是排出正負(fù)，不排出大小?？稍跀?shù)組首尾設(shè)兩個(gè)指針i和j，i自小至大搜索到負(fù)數(shù)停止，j自大至小搜索到正數(shù)停止。然后i和j所指數(shù)據(jù)交換，繼續(xù)以上過(guò)程，直到 i=j為止。void Arrange(int A,int n) /n個(gè)整數(shù)存于數(shù)組A中，本算法將數(shù)組中所有正數(shù)排在所有負(fù)數(shù)的前面 int i=0,j=n-1,x; /用類(lèi)C編寫(xiě)，數(shù)組下標(biāo)從0開(kāi)始 while(i<j)while(i<j && Ai>0) i+;while(i<j && Aj<0

10、) j-; if(i<j) x=Ai; Ai+=Aj; Aj-=x; /交換Ai 與Aj /算法Arrange結(jié)束.算法討論對(duì)數(shù)組中元素各比較一次，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負(fù)數(shù)在后)不發(fā)生交換，最差情況(負(fù)數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類(lèi)c編寫(xiě)，數(shù)組界偶是0.n-1。空間復(fù)雜度為O(1).類(lèi)似本題的其它題的解答:：（1）與上題同，因要求空間復(fù)雜度也是O(n)，可另設(shè)一數(shù)組C，對(duì)A數(shù)組從左到右掃描，小于零的數(shù)在C中從左（低下標(biāo)）到右（高下標(biāo)）存，大于等于零的數(shù)在C中從右到左存。（2）將19題中判定正數(shù)(Ai>0)改為判偶數(shù)(Ai%2=0)，將判負(fù)數(shù)(Aj<

11、;0)改為(Aj%2!=0)。（3）同（2），只是要求奇數(shù)排在偶數(shù)之前。（4）利用快速排序思想，進(jìn)行一趟劃分。int Partition(int A,int n) /將n個(gè)元素的數(shù)組A調(diào)整為左右兩部分，且左邊所有元素小于右邊所有元素，返回分界位置。int i=0,j=n-1,rp=A0; /設(shè)數(shù)組元素為整型 while(i<j) while(i<j &&Aj>=rp) j-; while(i<j &&Ai<=rp) i+; if(i<j) x=Ai;Ai=Aj; Aj=x; Ai=rp; return(i); /分界元素/ P

12、artition18、在數(shù)組 A1.n中有n個(gè)數(shù)據(jù)，試建立一個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復(fù)的數(shù)據(jù)在鏈中只保存一個(gè)。答：題目分析本題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出Ai（0<=i<n）,然后到鏈表中去查找值為Ai的結(jié)點(diǎn)，若查找失敗，則插入。LinkedList creat(ElemType A,int n)/由含n個(gè)數(shù)據(jù)的數(shù)組A生成循環(huán)鏈表，要求鏈表有序并且無(wú)值重復(fù)結(jié)點(diǎn) LinkedList h;h=(LinkedList) malloc(sizeof(LNode);/申請(qǐng)結(jié)點(diǎn)h->next=h; /形成空循環(huán)鏈表for(i=

13、0;i<n;i+) pre=h;p=h->next; while(p!=h && p->data<Ai) pre=p; p=p->next; /查找Ai的插入位置 if(p=h | p->data!=Ai) /重復(fù)數(shù)據(jù)不再輸入 s=(LinkedList) malloc(sizeof(LNode); s->data=Ai; pre->next=s; s->next=p;/將結(jié)點(diǎn)s鏈入鏈表中/for return(h);/ creat19、編寫(xiě)程序，統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為

14、A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字）。問(wèn)題分析由于字母共26個(gè)，加上數(shù)字符號(hào)10個(gè)共36個(gè)，所以設(shè)一長(zhǎng)36的整型數(shù)組，前10個(gè)分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。從字符串中讀出數(shù)字字符時(shí)，字符的ASCII代碼值減去數(shù)字字符0的ASCII代碼值，得出其數(shù)值(0.9)，字母的ASCII代碼值減去字符A的ASCII代碼值加上10，存入其數(shù)組的對(duì)應(yīng)下標(biāo)分量中。遇其它符號(hào)不作處理，直至輸入字符串結(jié)束。void Count（）/統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)int i，num36；char ch；for（i0；i<36；i+）numi0；/ 初始化while（chget

15、char（）!=#） /#表示輸入字符串結(jié)束if（0<=ch<=9）i=ch48;numi+； / 數(shù)字字符 elseif（A<=ch<=Z）i=ch-65+10;numi+；/ 字母字符for（i=0；i<10；i+） / 輸出數(shù)字字符的個(gè)數(shù)printf（“數(shù)字d的個(gè)數(shù)dn”，i，numi）；for（i10；i<36；i+）/ 求出字母字符的個(gè)數(shù)printf（“字母字符c的個(gè)數(shù)dn”，i55，numi）；/算法結(jié)束7. 假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積

16、（存儲(chǔ)量）為 288 B ；末尾元素A57的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為 (8+4)×6+1000=1192 ；若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為 (6×74)×61000）1276 。9. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。10.求下列廣義表操作的結(jié)果：（1） GetHead【(a,b),(c,d)】= (a, b) ; /頭元素不必加括號(hào)（2） GetHead【GetTail【(a,b),(c,d)】= (c,d) ;（

17、3） GetHead【GetTail【GetHead【(a,b),(c,d)】= b ;（4） GetTail【GetHead【GetTail【(a,b),(c,d)】= （d） ;（A）4.01年計(jì)算機(jī)系考研題假設(shè)有60行70列的二維數(shù)組a160, 170以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a32,58的存儲(chǔ)地址為 。（無(wú)第0行第0列元素）16902 16904 14454 答案A, B, C均不對(duì)答：（57列×60行31行）×2字節(jié)10000=16902(B)5.設(shè)矩陣A是一個(gè)對(duì)稱(chēng)矩陣，為了節(jié)省存儲(chǔ)，將其下三角部

18、分（如下圖所示）按行序存放在一維數(shù)組B 1, n(n-1)/2 中，對(duì)下三角部分中任一元素ai,j(ij), 在一維數(shù)組B中下標(biāo)k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j解：注意B的下標(biāo)要求從1開(kāi)始。先用第一個(gè)元素去套用，可能有B和C；再用第二個(gè)元素去套用B和C，B=2而C3（不符）；所以選B6.【91初程P78】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址。假設(shè)存儲(chǔ)數(shù)組元素

19、A0,1的第一個(gè)字節(jié)的地址是0。存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 A 。若按行存儲(chǔ)，則A3,5和A5,3的第一個(gè)字節(jié)的地址分別是 B 和 C 。若按列存儲(chǔ)，則A7,1和A2,4的第一個(gè)字節(jié)的地址分別是 D 和 E 。供選擇的答案AE：28 44 76 92 108 116 132 176 184 188答案：ABCDE=8, 3, 5, 1, 67.【94程P12】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組

20、的體積是 A 個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A1,0的第一個(gè)字節(jié)的地址是0，則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 B 。若按行存儲(chǔ)，則A2,4的第一個(gè)字節(jié)的地址是 C 。若按列存儲(chǔ)，則A5,7的第一個(gè)字節(jié)的地址是 D 。供選擇的答案AD：12 66 72 96 114 120 156 234 276 282 （11）283 （12）288答案：ABCD=12, 10, 3, 92.已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個(gè)元素占K個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址為L(zhǎng)oc(a11)，請(qǐng)寫(xiě)出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出，此處雖是方陣，但行列

21、公式仍不相同；按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11) + (i-1)*m+(j-1) * K按列存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11) + (j-1)*m+(i-1) * K3.【全國(guó)專(zhuān)升本資格考試】遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對(duì)嗎？為什么？答：不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān)，是指最深層的執(zhí)行語(yǔ)句耗費(fèi)時(shí)間，而遞歸算法與非遞歸算法在最深層的語(yǔ)句執(zhí)行上是沒(méi)有區(qū)別的，循環(huán)的次數(shù)也沒(méi)有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同，遞歸用棧隱含循環(huán)次數(shù)，非遞歸用循環(huán)變量來(lái)顯示循環(huán)次數(shù)而已。4.用三元組表表示下列稀疏矩陣： 解：三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。所以（1）可列表為： （2）可列表為：8866416-225943565353233685467858125.下列各三元組表分別表示一個(gè)稀疏矩陣，試寫(xiě)出它們的稀疏矩陣。 解：（1）為6×4矩陣，非零元素有6個(gè)，但其中一數(shù)下標(biāo)有誤？（2）為4×5矩陣，非零元素有5個(gè)1