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

1、2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題1 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題2 一、一、 判斷題判斷題 1線性表的邏輯順序與存儲(chǔ)順序總是一致的。 2順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。 3順序表的插入和刪除操作不需要付出很大的時(shí) 間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲脑匦枰?移動(dòng)。 4線性表中的元素可以是各種各樣的，但同一線 性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同 一數(shù)據(jù)對(duì)象。 5在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩 個(gè)元素在物理位置上并不一定緊鄰。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題3 6在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元 素在物理位置上不一定相鄰。 7線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。 8在

2、線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)， 移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。 9線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單 元來存儲(chǔ)線性表中數(shù)據(jù)元素的。 10在單鏈表中，要取得某個(gè)元素，只要知道該元 素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié) 構(gòu)。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題4 二二 、單選題、單選題 (請(qǐng)從下列請(qǐng)從下列A，B，C，D選項(xiàng)選項(xiàng) 中選擇一項(xiàng)中選擇一項(xiàng)) 1線性表是( ) 。 一個(gè)有限序列，可以為空； (B) 一個(gè)有限序列，不能為空； (C) 一個(gè)無限序列，可以為空； (D) 一個(gè)無序序列，不能為空。 A 2對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入 或刪除操作都是等概率的

3、。插入一個(gè)元素時(shí)平均要移動(dòng)表 中的（ ）個(gè)元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n A 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題5 3線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址( ) 。 (A) 必須是連續(xù)的； (B) 部分地址必須是連續(xù)的； (C) 一定是不連續(xù)的； (D) 連續(xù)與否均可以。 D 4用鏈表表示線性表的優(yōu)點(diǎn)是 （ ）。 (A)便于隨機(jī)存取 (B)花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少 (C)便于插入和刪除 (D)數(shù)據(jù)元素的物理順序與邏輯順序相同 C 某鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè) 元素和刪除最后一個(gè)元素，則采用( )存儲(chǔ)方式最節(jié)省運(yùn)算時(shí) 間。 (A)單鏈表 (B

4、)雙鏈表 (C)單循環(huán)鏈表 (D)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題6 6下面關(guān)于線性表的敘述錯(cuò)誤的是( )。 (A)線性表采用順序存儲(chǔ)，必須占用一片地址連續(xù)的單元； (B)線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作； (C)線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片地址連續(xù)的單元； (D)線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作； B 7單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了（）。 (A)使單鏈表至少有一個(gè)結(jié)點(diǎn) (B)標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 (C)方便運(yùn)算的實(shí)現(xiàn) (D)說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ) C 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題7 8若某線性表中最常用的操作是在最后一個(gè)元素之后

5、插 入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié) 省運(yùn)算時(shí)間。 (A)單鏈表 (B)僅有頭指針的單循環(huán)鏈表 (C)雙鏈表 (D)僅有尾指針的單循環(huán)鏈表 D 9若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元 素的前驅(qū)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 (A)單鏈表 (B)順序表 (C)雙鏈表 (D)單循環(huán)鏈表 B 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題8 1設(shè)線性表存放在向量Aarrsize的前elenum個(gè) 分量中，且遞增有序。試寫一算法，將x 插入到 線性表的適當(dāng)位置上，以保持線性表的有序性。 并且分析算法的時(shí)間復(fù)雜度。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題9 int insert(int

6、 Aarrsize,int elenum,int x) if(elenum=arrsize) return(-1); i=elenum-1; while(i=0 i-; Ai+1=x; elenum+; return(1); 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題10 2已知一順序表A，其元素值非遞減有序排 列，編寫一個(gè)函數(shù)刪除順序表中多余的值相同 的元素。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題11 typedef struct datatype datamaxsize; int last; seqlist; void delete(seeqlist *A) i=0; while(ilast) k=i+1; w

7、hile(klast n=k-i-1; for(j=k;jlast;j+) A-dataj-n=A-dataj; A-last=A-last-n; i+; 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題12 3. 編寫一個(gè)函數(shù)，從一給定的順序表A中刪除值 在xy(x=y)之間的所有元素，要求以較高的效率 來實(shí)現(xiàn)。 提示：提示：可以先將順序表中所有值在xy之間的 元素置成一個(gè)特殊的值，并不立即刪除它們，然 后從最后向前依次掃描，發(fā)現(xiàn)具有特殊值的元素 后，移動(dòng)其后面的元素將其刪除掉。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題13 typedef struct datatype datamaxsize; int last; se

8、qlist; void delete(seeqlist *A,int x,int y) for (i=0;ilast;i+) if (A-dataix for(i=A-last;i=0;i-) if (A-datai=0) for(k=i+1;klast;k+) Ak-1=Ak; A-last-; 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題14 typedef struct datatype datamaxsize; int last; seqlist; void delete(seeqlist *A,int x,int y) j=0; for (i=0;ilast;i+) if (A-dataix 202

9、1-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題15 4. 線性表中有n個(gè)元素，每個(gè)元素是一個(gè)字符， 現(xiàn)存于向量Rn中，試寫一算法，使R中的字 符按字母字符、數(shù)字字符和其它字符的順序排 列。要求利用原來的存儲(chǔ)空間，元素移動(dòng)次數(shù) 最小。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題16 int fch(char c) if (c=a else return (0); void process(char Rn) low=0; high=n-1; while (lowhigh) while (lowhigh while (lowhigh if (lowhigh) k=Rlow;Rlow=Rhigh;Rhigh=k; low=low+1; h

10、igh=n-1; while (lowhigh) while (lowhigh while (lowhigh if (lowhigh) k=Rlow;Rlow=Rhigh;Rhigh=k; 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題17 5. 線性表用順序存儲(chǔ)，設(shè)計(jì)一個(gè)算法，用盡可能少 的輔助存儲(chǔ)空間將順序表中前m個(gè)元素和后n個(gè)元素 進(jìn)行整體互換。即將線性表 （a1, a2, , am, b1, b2, , bn） 改變?yōu)椋?（b1, b2, , bn , a1, a2, , am）。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題18 void process(seqlist *L,int m,int n) if (m=n

11、) for(i=1;idata0; for (k=1;klast;k+) L-datak-1=L-datak; L-dataL-last=x; else for(i=1;idataL-last; for (k=L-last-1;k=0;k-) L-datak+1=L-datak; L-data0=x; 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題19 6. 已知帶頭結(jié)點(diǎn)的單鏈表L中的結(jié)點(diǎn)是按整數(shù)值 遞增排列的，試寫一算法，將值為x 的結(jié)點(diǎn)插入 到表L中， 使得L仍然有序。 并且分析算法的時(shí) 間復(fù)雜度。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題20 typedef struct node int data; struct

12、node *next; lnode,*linklist; linklist insert(linklist L,int x) p=L; while(p-next s=(lnode *)malloc(sizeof(lnode); s-data=x; s-next=p-next; p-next=s; return(L); 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題21 7. 假設(shè)有兩個(gè)已排序的單鏈表A和B，編寫 一個(gè)函數(shù)將它們合并成一個(gè)鏈表C而不改變 其排序性。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題22 typedef struct node datatype data; struct node *next; lnod

13、e,linklist; linklist combine(linklist A,linklist B) C=A;rc=C; pa=A-next;pb=B-next;free(B); while(parc=pa;pa=pa-next; else rc-next=pb;rc=pb;pb=pb-next; if (pa) rc-next=pa; else rc-next=pb; return(C); 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題23 8. 假設(shè)長(zhǎng)度大于1的循環(huán)單鏈表中，既無 頭結(jié)點(diǎn)也無頭指針，p 為指向該鏈表中某 一結(jié)點(diǎn)的指針，編寫一個(gè)函數(shù)刪除該結(jié)點(diǎn) 的前趨結(jié)點(diǎn)。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題24

14、linklist delete(linklist p) q=p; while(q-next-next!=p) q=q-next; r=q-next; q-next=p; free(r); return(p); 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題25 9. 已知兩個(gè)單鏈表A和B分別表示兩個(gè)集 合，其元素遞增排列，編寫一個(gè)函數(shù)求出 A和B的交集C， 要求C同樣以元素遞增的 單鏈表形式存儲(chǔ)。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題26 linklist process(linklist A,linklist B) pa=A-next; pb=B-next; pc=C=(lnode *)malloc(sizeof(l

15、node); while(pa else if (pa-datapb-data) pb=pb-next; else s=(lnode *)malloc(sizeof(lnode); s-data=pa-data; pc-next=s; pc=s; pa=pa-next; pb=pb-next; pc-next=NULL; return(c); 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題27 10. 設(shè)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有prior、 data和next域外，還有一個(gè)訪問頻度freq域，在 鏈表被起用之前，該域其值初始化為零。每當(dāng) 在鏈表進(jìn)行一次Locata(L,x)運(yùn)算后，令值為x的 結(jié)點(diǎn)中的freq域增1，并調(diào)整表中結(jié)點(diǎn)的次序， 使其按訪問頻度的遞減序列排列，以便使頻繁 訪問的結(jié)點(diǎn)總是靠近表頭。試寫一個(gè)算法滿足 上述要求的Locata(L,x)算法。 2021-7-2數(shù)據(jù)結(jié)構(gòu)習(xí)題28 typedef struct dnode datatype data; int freq; struct