數(shù)據(jù)結(jié)構(gòu)單元練習(xí)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上單元練習(xí)6一判斷題（下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打；錯(cuò)誤的打 ）（）（1）n維的多維數(shù)組可以視為n-1維數(shù)組元素組成的線性結(jié)構(gòu)。（）（2）稀疏矩陣中非零元素的個(gè)數(shù)遠(yuǎn)小于矩陣元素的總數(shù)。（）（3）上三角矩陣主對(duì)角線以上（不包括主對(duì)角線中的元素），均為常數(shù)C。（）（4）數(shù)組元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。（）（5）數(shù)組的三元組表存儲(chǔ)是對(duì)稀疏矩陣的壓縮存儲(chǔ)。（）（6）任何矩陣都可以進(jìn)行壓縮存儲(chǔ)。（）（7）廣義表是線性表的推廣，所以廣義表也是線性表。（）（8）廣義表LS=（a0,a1,an-1），則an-1是其表尾。（）（9）廣義表(a,b),a,b)的表頭和表尾是相等的。（

2、）（10）一個(gè)廣義表的表尾總是一個(gè)廣義表。二填空題（1） 多維數(shù)組的順序存儲(chǔ)方式有按行優(yōu)先順序存儲(chǔ)和 按列優(yōu)先順序存儲(chǔ) 兩種。（2） 在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過地址計(jì)算公式算出，所以多維數(shù)組是一種 隨機(jī) 存取結(jié)構(gòu)。（3） 在n維數(shù)組中的每一個(gè)元素最多可以有 n 個(gè)直接前驅(qū)。（4） 輸出二維數(shù)組Anm中所有元素值的時(shí)間復(fù)雜度為 O(n*m) 。（5） 數(shù)組元素a0.20.3的實(shí)際地址上2000，元素長(zhǎng)度是4，則LOC1,2= 2024 。 LOC1,2=2000+（1*4+2）*4（6）稀疏矩陣的三元組有 3 列。（7）稀疏矩陣的三元組中第1列存儲(chǔ)的是數(shù)組中非零元素所在的 行數(shù)

3、 。（8）n階對(duì)稱矩陣，如果只存儲(chǔ)下三角元素，只需要 n（n-1）/2 個(gè)存儲(chǔ)單元。（9）稀疏矩陣A如下圖所示，其非零元素存于三元組表中，三元組（4，1，5）按列優(yōu)先順序存儲(chǔ)在三元組表的第 4 項(xiàng)。8 0 0 0 0 00 11 0 0 0 00 0 0 6 0 00 3 0 07 0 0 5 0 00 00 0 0 09 0稀疏矩陣AA=（10）稀疏疏矩陣的壓縮存儲(chǔ)方法通常有三元組表和 十字鏈表 兩種。（11）任何一個(gè)非空廣義表的表尾必定是 廣義表（或子表） 。（12）tail(head(a,b),(c,d)= b 。（13） 設(shè)廣義表(a,b,c)，則將c分離出來的運(yùn)算是 head(tai

4、l(tail(head(L) 。（14） 廣義表(a,b),c,d)，表尾是 （c,d） 。（15） n階下三角矩陣，因?yàn)閷?duì)角線的上方是同一個(gè)常數(shù)，需要 n（n-1）/2+1 個(gè)存儲(chǔ)單元。（16）稀疏矩陣中有n個(gè)非零元素，則三元組有 n 行。（17） 廣義表LS=（a,(b),(c,(d)）的長(zhǎng)度是 3 。（18） 廣義表LS=（a,(b),(c,(d)）的深度是 4 。（19） 廣義表L=（），L），則L的深度是 。（20） 廣義表LS=（a,(b),(c,(d)）的表尾是 (b),(c,(d) 。三選擇題（1）在一個(gè)m維數(shù)組中，（ D ）恰好有m個(gè)直接前驅(qū)和m個(gè)直接界后繼。A.開始結(jié)點(diǎn) B

5、總終端結(jié)點(diǎn) C.邊界結(jié)點(diǎn) D內(nèi)部結(jié)點(diǎn)（2）對(duì)下述矩陣進(jìn)行壓縮存儲(chǔ)后，失去隨機(jī)存取功能是（ D ）。 A對(duì)稱矩陣 B三角矩陣 C三對(duì)角矩陣 D稀疏矩陣（3）在按行優(yōu)先順序存儲(chǔ)的三元組表中，下述陳述錯(cuò)誤的是（ D ）。A 同一行的非零元，是按列號(hào)遞增次序存儲(chǔ)的B 同一列的非零元，是按行號(hào)遞增次序存儲(chǔ)的C 三元組表中三元組行號(hào)遞增的D 三元組表中三元組列號(hào)遞增的（4）對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（ B ）。 A降低運(yùn)算時(shí)間 B節(jié)約存儲(chǔ)空間 C便于矩陣運(yùn)算 D便于輸入和輸出（5）若數(shù)組A0.m0.n按列優(yōu)先順序存儲(chǔ)，則aij的地址為（ A ）。 ALOC(a00)+j*m+i BLOC(a00)+j*

6、n+i CLOC(a00)+(j-1)*n+i-1 DLOC(a00)+(j-1)*m+i-1（6）下列矩陣是一個(gè)（ B ） A對(duì)稱矩陣 B三角矩陣 C稀疏矩陣 D帶狀矩陣（7）在稀疏矩陣的三元組表示法中，每個(gè)三元組表示（ D ）。A 矩陣中非零元素的值B 矩陣中數(shù)據(jù)元素的行號(hào)和列號(hào)C 矩陣中數(shù)據(jù)元素的行號(hào)、列號(hào)和值D 矩陣中非零數(shù)據(jù)元素的行號(hào)、列號(hào)和值（8）已知二維數(shù)組A610，每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存放數(shù)組元素a35的存儲(chǔ)地址是1000，則a00的存儲(chǔ)地址是（ B ）。A872 B860 C868D8641000=B+(3*10+5)*4 B=1000-(3*10+5)

7、*4=1000-140=860（9）廣義表是線性表的推廣，它們之間的區(qū)別在于（ A ）。 A能否使用子表 B能否使用原子項(xiàng) C是否能為空 D表的長(zhǎng)度（10）下列廣義表屬于線性表的是（ B ）。 AE=(a,E) BE=(a,b,c) CE=(a,(b,c) DE=(a,L)；L=()（11）廣義表(a,b),c,d)的表尾是( D )。Aa Bd C(a,b)D(c,d)（12）廣義表A=(x,(a,b),(x,(a,b),y),則運(yùn)算head(head(tail(A)為（ A ）。Ax B（a，b） C(x,(a,b)DA（13）tail(head(a,b),c,(c,d)的結(jié)果是（ B ）

8、。Ab B（b） C(a,b)D(d)（14）若廣義表滿足head（L）=tail（L），則L的形式是（ B ）A空表 B若L=(a1,an),則a1=(a2,an)C若L=(a1,an),則a1=a2=an) D(a1),(a1)（15）數(shù)組是一個(gè)（ B ）線性表結(jié)構(gòu)。 A非 B推廣了的 C加了限制的 D不加限制的（16）數(shù)組A0:1,0:1,0:1共有（ D ）元素。A4 B5 C6 D8（17）廣義表(a,b),c,d)的表頭是( C )。Aa Bd C(a,b)D(c,d)（18）廣義表A=(a),則表尾為( C )。Aa B() C空表D(a)（19）以下（ C ）是稀疏矩陣的壓縮存

9、儲(chǔ)方法。 A一維數(shù)組 B二維數(shù)組 C三元組表 D廣義表（20）設(shè)廣義表D=(a,b,c,D),其深度為（ D ）。A2 B3 C4 D四算法閱讀題1 已知A是一個(gè)下三角矩陣，下述算法的功能是什么？int f1(int A,int n) / 設(shè)B0.(n+1)n/2-1存放下三角元素int i,k,s=0;k=0;s=A0;for (i=0;i<n-1;i+) k=k+i+2; s=s+Ak;return s;算法功能：求矩陣主對(duì)角線上元素之和。分析：注意k的變化依次為：0，2，5，9，14，正好是aii在A中的存儲(chǔ)位置。在循環(huán)中k每次增加i+2。第i行主對(duì)角線上的元素aii，其在A中的位

10、置為:i(i+1)/2+i； (1)第i+1行主對(duì)角線上的元素ai+1 i+1，其在A中的位置為: (i+1)(i+2)/2+(i+1), (2)(2)-(1)得i-2。2 在按行優(yōu)先順序存儲(chǔ)的三元組表中，求某列非零元素之和的算法如下，填空以完成算法。#define SMAX 100 / 定義一個(gè)足夠大的三元組表typedef struct int i,j,v; / 非零元素的行、列、值SPNode; / 三元組類型typedef struct / 定義稀疏矩陣 int m,n,t; / 矩陣的行、列及非零元素的個(gè)數(shù) SPNode dataSMAX; / 三元組表SPMatrix; / 三元組

11、表的存儲(chǔ)類型if f2(SPNode *a,col) / 求第col列非零元素之和int k,sum=0;if ( a->t<=0 ) printf(“a<=0”);if ( col<0 | col >=a->n )printf(“列錯(cuò)！”);for ( k=0 ; k<a->t ; k+ ) if (a->tadak.j=n) sum= sum + a->datak.v ;return sum; 五編程題1 試編寫求一個(gè)三元組表的稀疏矩陣對(duì)角線元素之和的算法。#include "stdio.h"#define E

12、RROR 99999typedef struct int row;int col; int data; Triple; int MDSum(Triple *a) int i;int sum=0;if (a0.row!=a0.col) return ERROR;for (i=1;i<=a0.data;i+) if (ai.row=ai.col) sum+=ai.data;return sum;2 試編寫求廣義表中原子元素個(gè)數(shù)的算法。j=解：設(shè)j為原子個(gè)數(shù)，則求廣義表中原子元素個(gè)數(shù)的算法可遞歸定義如下：0LS為空表尾原子元素個(gè)數(shù)+1 LS非空且表頭為原子元素表頭子表原子元素個(gè)數(shù)+表尾原子元素

13、個(gè)數(shù)+1LS非空且表頭子表int atomnum(Gnode *head) if (head=NULL) return 0; if (head->tag=0) return(atomnum(head->next)+1); else return(atomnum(head->next)+atomnum(head->val.sublist);3 試編寫求廣義表最大中原子元素個(gè)數(shù)的算法。int maxele(Gnode *head)int m=0,a;while(head) if (head->tag=1) a=maxele(head->val.sublist);

14、 if (a>m) m=a; else if (head->val.data>m) m=head->val.data; head=head->next; return m;【例7】 在按行存儲(chǔ)的三元組表中，求某列（col）的非零元素之和的算法如下，請(qǐng)?zhí)羁找酝瓿伤惴ā?define SMAX 100 / 定義一個(gè)足夠大的三元組表struct SPNode / 定義三元組int i,j,v; / 三元組非零元素的行、列和值;struct sparmatrix / 定義稀疏矩陣int row,col,terms; / 稀疏矩陣行、列和非零元素的個(gè)數(shù)SPNode dataSMAX; / 三元組表TTT; int f2 (TTT *a, col) / 求第col列非零元素之和 int i,sum=0;if ( )Error(“非零元素的個(gè)數(shù)是不大于0”);if ( )Error(“列號(hào)