計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課后題答案_第1頁
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課后題答案_第2頁
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課后題答案_第3頁
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課后題答案_第4頁
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課后題答案_第5頁
已閱讀5頁,還剩59頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題答案第一節(jié) 概 論一、選擇題1 要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性,這意味著 ( ) 。A.數(shù)據(jù)元素具有同一的特點(diǎn)*B .不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同,而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致 C 每個(gè)數(shù)據(jù)元素都一樣D 數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等2數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 ( (1) ) 以及它們之間的 ( (2) ) 和運(yùn)算的學(xué)科。(1) A 操作對象B 計(jì)算方法*C 物理存儲(chǔ)D.數(shù)據(jù)映像(2) A 結(jié)構(gòu) *B 關(guān)系 C 運(yùn)算 D 算法(3) 據(jù)結(jié)構(gòu)被形式地定義為(D, R),其中口是(1) 的有限集合,R是D上(2)的有限集合。(1) A

2、 算法 *B 數(shù)據(jù)元素 C 數(shù)據(jù)操作D.邏輯結(jié)構(gòu)(2)A 操作 B 映像 C 存儲(chǔ) *D 關(guān)系4 在數(shù)據(jù)結(jié)構(gòu)中, 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 ( ) 。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B .緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)*C 線性結(jié)構(gòu)和非線性結(jié)構(gòu)D 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)5線性表的順序存儲(chǔ)結(jié)構(gòu)是一種( ) 的存儲(chǔ)結(jié)構(gòu)。*A 隨機(jī)存取B 順序存取 C 索引存取 D Hash存取6算法分析的目的是( ) 。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B .研究算法中的輸入和輸出的關(guān)系 *C 分析算法的效率以求改進(jìn)D 分析算法的易懂性和文檔性7計(jì)算機(jī)算法指的是( (1) ) ,它必須具備輸入、輸出和 ( (2) ) 等五個(gè)特征。(1) A 計(jì)

3、算方法B 排序方法*C 解決某一問題的有限運(yùn)算序列 D 調(diào)度方法(2) A 可行性、可移植性和可擴(kuò)充性 *B 可行性、確定性和有窮性 C 確定性, 有窮性和穩(wěn)定性 D 易讀性、穩(wěn)定性和安全性8線性表若采用鏈表存儲(chǔ)結(jié)構(gòu),要求內(nèi)存中可用存儲(chǔ)單元的地址( ) 。A.必須是連續(xù)的 B .部分必須是連續(xù)的C . 一定是不連續(xù)的 *D 連續(xù)不連續(xù)都可以9在以下的敘述中,正確的是( ) 。A 線 性 表 的 線 性 存 儲(chǔ) 結(jié) 構(gòu) 優(yōu) 于 鏈 式 存 儲(chǔ) 結(jié) 構(gòu)*B 二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表 C 棧的操作方式是先進(jìn)先出 D 隊(duì)列的操作方式是先進(jìn)后出10 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性,

4、以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式,其中解釋錯(cuò)誤的是( ) 。*A.集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散 B 線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條 “鎖鏈” C 樹形結(jié)構(gòu)具有分支、 層次特性,其形態(tài)有點(diǎn)像自然界中的樹D 圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞,任何兩個(gè)結(jié)點(diǎn)都可以鄰接11 以下說法正確的是( ) 。A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位B .數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 C 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合 *D 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合二、判斷題X1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。V2.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。,3.數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)

5、在計(jì)算機(jī)中的映像分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。X4.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。V5.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系,是用戶按使用需要建立的。,6.數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中實(shí)際的存儲(chǔ)形式。X7.算法和程序沒有區(qū)別,所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。,8 .順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)。三、填空題1所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的 邏輯關(guān)系 。2,數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,它包括三方面的內(nèi)容_數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、對數(shù)據(jù)施加的操作_。3數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)_、 線性結(jié)構(gòu)_、 樹型結(jié)構(gòu) 和_圖狀結(jié)構(gòu) 四種類型。

6、4在線性結(jié)構(gòu)中,開始結(jié)點(diǎn)_沒有 _前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_一個(gè) _個(gè)前驅(qū)結(jié)點(diǎn)。5在樹形結(jié)構(gòu)中,根結(jié)點(diǎn)只有_一個(gè) _,其余每個(gè)結(jié)點(diǎn)有且只有_一個(gè)_前驅(qū)結(jié)點(diǎn);葉結(jié)點(diǎn)沒有_后繼 _結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以有_ 任意個(gè)6在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)可以有 _任意個(gè)_。7 算法的五個(gè)重要特性是_可行性_ 、 _確定性_ 、 _有窮性_、 _輸入 _ 、 _輸出_。8下列程序段的時(shí)間復(fù)雜度是_O( n ) _。for (i=1; i<=n ; i+) Ai , i=0 ;9下列程序段的時(shí)間復(fù)雜度是_ O ( n2) _。S=0 ;for(i=1 ; i<=n ;

7、i+)for(j=1 ; j<=n ; j+) s=s+Bi,j ;sum=s ;10 存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的_物理 _實(shí)現(xiàn)。11 從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)看,通常所說的“數(shù)據(jù)”應(yīng)分成三個(gè)不同的層次,即_數(shù)據(jù)_、 _數(shù)據(jù)元素_和_數(shù)據(jù)項(xiàng) 。12 根據(jù)需要,數(shù)據(jù)元素又被稱為_、 _元素 _或_頂點(diǎn) _。_結(jié)點(diǎn) _ 、 _記錄順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)_ 、 _散列存儲(chǔ)_四種關(guān)13 通常,存儲(chǔ)結(jié)點(diǎn)之間可以有 聯(lián)方式,稱為四種基本存儲(chǔ)方式。14 通常從_確定性_、 _可讀性_、 _健壯性_ 、_高效性_等幾方面評(píng)價(jià)算法 ( 包括程序 ) 的質(zhì)量。15 一個(gè)算法的時(shí)空性能是指該算法的_ 時(shí)間復(fù)雜度_和_空

8、間復(fù)雜度_,前者是算法包含的_計(jì)算量_,后者是算法需要的_存儲(chǔ)量_。16 在一般情況下,一個(gè)算法的時(shí)間復(fù)雜度是_ 問題規(guī)模 _的函數(shù)。17 常見時(shí)間復(fù)雜度的量級(jí)有:常數(shù)階O(_1_) 、對數(shù)階 O(_log 2n_) 、線性階O(_n_)、平方階O(_n2_)和指數(shù)階O(_2n_) 。通常認(rèn)為,具有指數(shù)階量級(jí)的算法是 _不可行_ 的。18 數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的_ 設(shè)計(jì) _ 和 _實(shí)現(xiàn) _。19 數(shù)據(jù)對象是性質(zhì)相同的_數(shù)據(jù)元素_的集合。20 抽象數(shù)據(jù)類型是指一個(gè)_數(shù)學(xué)模型_以及定義在該模型上的一組操作。四、應(yīng)用題1分析下列程序段的時(shí)間復(fù)雜度。i=1 ;WHILE (i<=n) i

9、=i*2答: O(log 2n)2敘述算法的定義及其重要特性。答:算法是對特定問題求解步驟的一種描述,是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。算法應(yīng)該具有下列特性:可行性、確定性、有窮性、輸入和輸出。3簡述下列術(shù)語:數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)對象。答:數(shù)據(jù)是信息的載體,是描述客觀事物的數(shù)、字符,以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下,數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。4邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是什么關(guān)系?答:在數(shù)據(jù)結(jié)構(gòu)中

10、,邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的,存儲(chǔ)結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)中,而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計(jì)算機(jī)無關(guān),存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示。5 .將數(shù)量級(jí) 210, n, n2, n3, nlog2n, log 2n, 2n, n!, (2/3)n, n2,3按增長率進(jìn)行排列。答:(2/3)n, 210, log 2n, n2 3, n, nlog 2n, n2, n3, 2n, n!6 .設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為:D=k1, k2, k3,,k9,R=<k1, k3>, <k1, k8>, <k2, k3>, <k2,

11、 k4>, <k2, k5>, <k3, k9>, <k5, k6>, <k8, k9>, <k9, k7>, <k4, k6>,畫出這個(gè)邏輯結(jié)構(gòu)的圖示,并確定相對于關(guān)系R 哪些結(jié)點(diǎn)是開始結(jié)點(diǎn),哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)? 答:圖略。開始結(jié)點(diǎn) k1、k2,終端結(jié)點(diǎn)k6、k7。7 .設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖,給出它的邏輯結(jié) 構(gòu),并說出它是什么類型的邏輯結(jié)構(gòu)。答:數(shù)據(jù)邏輯結(jié)構(gòu)為:D=k1 , k2, k3,,k8 , R=<k1, k2>, <k1, k3>, <k3, k5>, <

12、;k3, k4>, <k4, k7>, <k4, k6>, <k5, k8>,其邏輯結(jié)構(gòu)類型為樹型結(jié)構(gòu)。8 .分析下列程序的時(shí)間復(fù)雜度(設(shè)n為正整數(shù))(1)int rec(int n)elseif(n=1)return(1) return(n*rec(n-1)(2)x=91; y=100;While (y>0) if(x>10) y-;(3)i=1; j=0 ;while(i+j<=n)if(i>j)j+; else i+;(4)x=n; y=0 ;while(x>=(y+1)*(y+1) y+;答: (1) O(n) (

13、2) O(1) (3) O(n) (4) O(n1/2)9設(shè)n 為正數(shù)。試確定下列各程序段中前面加記號(hào)的語句的頻度:(1)i=1; k=0 ;while(i<=n-1) k+=10*i;i+;)(2) k=0;for(i=1 ; i<=n ; i+)for(j=i; j<=n : j+) k+ ;答:(1)n-1 (2)n+(n-1)+1=n(n+1)/2第二節(jié) 線性表一、選擇題1線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)( ) 。*A 數(shù)據(jù)元素 B 數(shù)據(jù)項(xiàng) C 數(shù)據(jù) D 數(shù)據(jù)結(jié)構(gòu)2.線性表L=(a1 , a2,,ai ,,an),下列說法正確的是 ( ) 。A 每個(gè)元素都有一個(gè)直接前驅(qū)和

14、直接后繼 B 線性表中至少要有一個(gè)元素 C 表中諸元素的排列順序必須是由小到大或由大到小的 D * 除第一個(gè)元素和最后一個(gè)元素外其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼3順序表是線性表的 ( ) 。A 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) *B 順序存儲(chǔ)結(jié)構(gòu) C 索引存儲(chǔ)結(jié)構(gòu) D 散列存儲(chǔ)結(jié)構(gòu)4對于順序表,以下說法錯(cuò)誤的是( ) 。* A 順序表是用一維數(shù)組實(shí)現(xiàn)的線性表,數(shù)組的下標(biāo)可以看成是元素的絕對地址B 順序表的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列 C 順序表的特點(diǎn)是:邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰 D 順序表的特點(diǎn)是:邏輯上相鄰的元素,存儲(chǔ)在物理位置也相鄰的單元中5對順序表上

15、的插入、刪除算法的時(shí)間復(fù)雜度分析來說,通常以 ( ) 為標(biāo)準(zhǔn)操作。A 條件判斷*B 結(jié)點(diǎn)移動(dòng) C 算術(shù)表達(dá)式D.賦值語句6對于順序表的優(yōu)缺點(diǎn),以下說法錯(cuò)誤的是( ) 。A 無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間 B 可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)*C 插入和刪除操作較方便 D 由于順序表要求占用連續(xù)的空間,存儲(chǔ)分配只能預(yù)先進(jìn)行( 靜態(tài)分配 )7在含有 n 個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中,在任一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為 ( ) 。A n *B n/2 C (n-1)/2 D (n+1)/28在含有n 個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中,刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為 ( )

16、。A n B n/2 *C (n-1)/2 D (n+1)/29帶頭結(jié)點(diǎn)的單鏈表為空的條件是( ) 。A head=NULL *B head->next=NULLC head->next=head D head!=NULL10 非空單循環(huán)鏈表head 的尾結(jié)點(diǎn) *p 滿足 ( ) 。A p->next=NULLB p=NULL*C p->next=head D p=head11. 在雙循環(huán)鏈表的 *p 結(jié)點(diǎn)之后插入*s 結(jié)點(diǎn)的操作是A p->next=s ; s->next=p->next p->next->prior=s C s->

17、prior=p p->next->prior=s s->next=p->nexts->prior=p ; p->next->prior=s ;p->next=s ;s->prior=p : s->next=p->nexts->next=p->next*Dp->next->pror=s; p->next=s s->prior=p p->next=s ;12. 在一個(gè)單鏈表中,已知 *q 結(jié)點(diǎn)是 *p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在*q和*p之間插入結(jié)點(diǎn)*s ,s->next=p->nex

18、t( ) 。p->next=s ;B p->next=s->next ; s->next=p ; *C q->next=s;s->next=p ; D p->next=s; s->next=q ;13. 在一個(gè)單鏈表中,若 *p 結(jié)點(diǎn)不是最后結(jié)點(diǎn)。在*p之后插入結(jié)點(diǎn) *s ,則執(zhí)行 ( ) 。A s->next=p ; p->next=s; *B s->next=p->next ;p->next=s ;C s->next=p->next ; p=s ; D p->next=s ; s->nex

19、t=p;14. 若某線性表中最常用的操作是取第 i 個(gè)元素和找第 i 個(gè)元素的前驅(qū)元素,則采用 ( ) 存儲(chǔ)方式最節(jié)省時(shí)間。*A 順序表B. 單鏈表 C 雙鏈表D 單 循環(huán)鏈表15 設(shè)rear 是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針,則刪除表頭結(jié)點(diǎn)的操作可表示為,則刪除表頭結(jié)點(diǎn)的操作可表示為A B C *Dp=rear ; rear=rear->nextrear=rear->nextrear=rear->next->next ;Ofree(p)free(rear)free(rear)p=rear->next->nextrear->next->ne

20、xt=p->next ; free(p) ;16 在一個(gè)單鏈表中,若刪除*p 結(jié)點(diǎn)的后繼結(jié)點(diǎn),則 執(zhí)行 ( ) *A q=p->next ; p->next=q->next ; free(q) ; B p=p->next ; p->next=p->next->next ; free(p) ; C p->next=p->next ; free(p->next) ; D p=p->next->next ; free(p->next) ;17 設(shè)指針p 指向雙鏈表的某一結(jié)點(diǎn),則雙鏈表結(jié)構(gòu)的對稱性可用 ( ) 式來刻畫

21、。A p->prior->next->=p->next->nextBp->prior->prior=p->next->prior*Cp->prior->next->=p->next->priorD p->next->next=p->prior->prior18 在循環(huán)鏈表中,將頭指針改設(shè)為尾指針rear 后,其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是( ) 。A rear 和 rear->next->next *B rear->next 和 rear C rear->nex

22、t->next 和 rear D rear 和 rear->next19 循環(huán)鏈表的主要優(yōu)點(diǎn)是( ) 。A 不再需要頭指針了 B 已知某個(gè)結(jié)點(diǎn)的位置后,容易找到它的直接前驅(qū)C 在進(jìn)行插入、刪除操作時(shí),能更好地保證鏈表不斷開*D 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表20在線性表的下列存儲(chǔ)結(jié)構(gòu)中,讀取元素花費(fèi)時(shí)間最少的是 ( ) 。A 單鏈表 B 雙鏈表 C 循環(huán)鏈表*D 順序表 二、判斷題V1 .順序存儲(chǔ)的線性表可以隨機(jī)存取。X 2 .順序存儲(chǔ)的線性表的插入和刪除操作不需要付出很大的代價(jià),因?yàn)槠骄看尾僮髦挥薪话氲脑匦枰苿?dòng)。"3.線性表中的元素可以是各種各樣的,但同一

23、線性表中的數(shù)據(jù)元素具有相同的特性,因此是屬于同一數(shù)據(jù)對象。X4.在線性表的順序存儲(chǔ)結(jié)構(gòu)中,邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。,5.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,邏輯上相鄰的元素在物理位置上不一定相鄰。V6.在單鏈表中,可以從頭結(jié)點(diǎn)開始查找任何一個(gè)元素。X7.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。,8.在線性表的順序存儲(chǔ)結(jié)構(gòu)中,插入和刪除元素時(shí),移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。X9.在單鏈表中,要取得某個(gè)元素,只要知道該元素的指針即可,因此,單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。X10.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。三、填空題1 為了便于討論, 有時(shí)將含 n(n>0) 個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表

24、示成(a1 , a2,,an),其中每個(gè)ai代表一個(gè)結(jié)點(diǎn) _ 。 a1 稱為 _第一個(gè)_結(jié)點(diǎn),an 稱為 _最后一個(gè)_結(jié)點(diǎn),i 稱為 ai 在線性表中的_位置 _。 對任意一對相鄰結(jié)點(diǎn)ai、ai+1(1 < i<n) , ai 稱為 ai+1 的直接_前驅(qū)ai+1稱為 ai 的直接_后繼 _。2線性結(jié)構(gòu)的基本特征是:若至少含有一個(gè)結(jié)點(diǎn),則除起始結(jié)點(diǎn)沒有直接_前驅(qū) _外,其他結(jié)點(diǎn)有且僅有一個(gè)直接 _前驅(qū) _;除終端結(jié)點(diǎn)沒有直接_后繼_外,其他結(jié)點(diǎn)有且僅有一個(gè)直接_后繼 _。3所有結(jié)點(diǎn)按一對一的鄰接關(guān)系構(gòu)成的整體就是_線性_結(jié)構(gòu)。4線性表的邏輯結(jié)構(gòu)是_線性 _結(jié)構(gòu),其所含結(jié)點(diǎn)的個(gè)數(shù)稱為

25、線性表的_長度 _。5在單鏈表中,刪除p 所指結(jié)點(diǎn)的直接后繼的操作是_ q=p->next ; p->next=q->next ; free(q) ; 6非空的單循環(huán)鏈表head 的尾結(jié)點(diǎn) ( 由指針 p 所指 )滿足 _ p->next= head 。7 rear 是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針,則刪除起始結(jié)點(diǎn)的操作可表示為 _ p=rear->next ;q=p->next ; p->next=q->next ; free(q) ; 。8對于一個(gè)具有n 個(gè)結(jié)點(diǎn)的單鏈表,在p 所指結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為_O(1)_ , 在給定

26、值為x的結(jié)點(diǎn)后插入新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 _ O(n)_。9單鏈表表示法的基本思想是用 _指針 _表示結(jié)點(diǎn)間的邏輯關(guān)系。10 在順序表中插入或刪除一個(gè)元素,平均需要移動(dòng)_一半_元素,具體移動(dòng)的元素個(gè)數(shù)與_ 元素的位置_有關(guān)。11 .在一個(gè)長度為n的向量的第i(1 &i&n+1)個(gè)元素之前插入一個(gè)元素時(shí), 需向后移動(dòng)_ n-i+1_ 個(gè)元素。12 .在一個(gè)長度為n的向量中刪除第i(1&iwn)個(gè)元素時(shí),需向前移動(dòng)_ n-i _ 個(gè)元素。13 在雙鏈表中,每個(gè)結(jié)點(diǎn)有兩個(gè)指針域,一個(gè)指向_前驅(qū) _ ,另一個(gè)指向_后繼_。14 在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中, p 指向尾結(jié)點(diǎn)的直接

27、前驅(qū),則指向頭結(jié)點(diǎn)的指針 head 可用 p 表示為head=_ p->next->next; _ 。15 設(shè) head 指向單鏈表的表頭, p 指向單鏈表的表尾結(jié)點(diǎn),則執(zhí)行p->next=head 后,該單鏈表構(gòu)成_單循環(huán)鏈表 _ 。16 在單鏈表中, 若 p 和 s 是兩個(gè)指針, 且滿足 p->next 與 s 相同, 則語句 p->next=s->next 的作用是_刪除 _s指向的結(jié)點(diǎn)。17 設(shè) r 指向單循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn),要在最后一個(gè)結(jié)點(diǎn)之后插入s 所指的結(jié)點(diǎn),需執(zhí)行的三條語句是_s->next= r->next _; r->

28、;next=s ; r=s ;18 在單鏈表中,指針p 所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是_ p->next=NULL_ 。19 在雙循環(huán)鏈表中,若要在指p 所指結(jié)點(diǎn)前插入s所指 的 結(jié)點(diǎn) , 則 需 執(zhí) 行下 列 語句 : s->next=p ; s->prior=p->prior ; _ p->prior->next_=s ;p->prior=s ;20 在單鏈表中,若要在p 所指結(jié)點(diǎn)之前插入s 所指的結(jié)點(diǎn),可進(jìn)行下列操作:s->next=_p->next _ ; p->next=s ;temp=p->data ;p->d

29、ata=_ s->data _;s->data=_ temp_四、應(yīng)用題1描述以下三個(gè)概念的區(qū)別:頭指針,頭結(jié)點(diǎn),首元結(jié)點(diǎn) ( 第一個(gè)元素結(jié)點(diǎn) )答:首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)的線性表中的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便,通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn),稱為頭結(jié)點(diǎn)。頭指針是指向鏈表中的第一個(gè)結(jié)點(diǎn)的指針。2何時(shí)選用順序表,何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?答:從空間上來看,當(dāng)線性表的長度變化較大、難以估計(jì)其規(guī)模時(shí),選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié)構(gòu)比較合適,但鏈表除了需要設(shè)置數(shù)據(jù)域外,還要額外設(shè)置指針域,因此當(dāng)線性表長度變化不大、易于事先確定規(guī)模時(shí),為了節(jié)約存儲(chǔ)空間,宜采用順序存儲(chǔ)結(jié)

30、構(gòu)。從時(shí)間上來看,若線性表的操作主要是查找,很少進(jìn)行插入和刪除操作時(shí),應(yīng)選用順序表。對于頻繁進(jìn)行插入和刪除操作的線性表,宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?答:平均移動(dòng)表中大約一半的結(jié)點(diǎn),插入操作平均移動(dòng) n/2 個(gè)結(jié)點(diǎn),刪除操作平均移動(dòng)( n-1 ) /2 個(gè)結(jié)點(diǎn)。具體移動(dòng)的次數(shù)取決于表長和插入、刪除的結(jié)點(diǎn)的位曾置。4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?答:單循環(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個(gè)結(jié)點(diǎn),但設(shè)置尾指針時(shí),若在表尾進(jìn)行插入或刪除操作可在 O(1) 時(shí)間內(nèi)完成,同樣在表頭進(jìn)行插入或刪

31、除操作也可在 O(1) 時(shí)間內(nèi)完成。但若設(shè) 置的是頭指針,表尾進(jìn)行插入或刪除操作,需要遍歷整個(gè)鏈表,時(shí)間復(fù)雜度為 O(n) 。5雙鏈表和單循環(huán)鏈表中,若僅知道指針 p 指向某個(gè)結(jié)點(diǎn),不知道頭指針,能否將結(jié)點(diǎn) *p 從相應(yīng)的鏈表中刪除?若可以,其時(shí)間復(fù)雜度各為多少?答:能刪除。雙鏈表上刪除 p 所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1) ,單循環(huán)鏈表上刪除p 所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n) 。6下列算法的功能是什么?LinkList *testl(LinkList *L)/L 是無頭結(jié)點(diǎn)的單鏈表LinkList *q , *p ;if(L&&L->next) q=L ; L

32、=L->next ; p=L;while(p->next) p=p->next;p->next=q; q->next=NULL ; return L ; 答: 如果長度大于 1, 則將首元結(jié)點(diǎn)刪除并插入到表尾。7如果有 n 個(gè)線性表同時(shí)共存,并且在處理過程中各表的長度會(huì)發(fā)生動(dòng)態(tài)變化,線性表的總長度也會(huì)自動(dòng)地改變。在此情況下,應(yīng)選擇哪一種存儲(chǔ)結(jié)構(gòu)?為什么? 答:應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲(chǔ)結(jié)構(gòu),只能預(yù)先分配,不能隨著線性表長度的改變而變 化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)地申請空間,因此適用于動(dòng)態(tài)變化表長的線性表。8若線性表的總數(shù)基本穩(wěn)定,且很少進(jìn)行插入、刪除操

33、作,但要求以最快的方式存取線性表的元素,應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)?為什么?答:應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為 O(1) 。五、算法設(shè)計(jì)題假設(shè)算法中用到的順序表和鏈表結(jié)構(gòu)如下:#define maxsize 100;Typedef struct node1 datatype datamaxsize;int length SeqList;Typedef struct node2 datatype data; struct node2 *next LinkedList ;1試用順序表作為存儲(chǔ)結(jié)構(gòu),實(shí)現(xiàn)將線性表(a0 , a1,a2, an-l)就地逆置的操作,所謂“就地”是

34、指輔助空間為 O(1) 。答: (1) 順序表的就地逆置分析:分別用兩個(gè)整型變量指向順序表的兩端,同時(shí)向中間移動(dòng),移動(dòng)的同時(shí)互換兩個(gè)下標(biāo)指示的元素的值。void Seqreverse(SeqList *L) 順序表的就地逆置for(i=0 ; j=L->length-1 ; i<j ; i+ , j-) t=L->datai;L->datai=L.dataj;L->dataj=t; (2) 鏈表的就地逆置分析:本算法的思想是逐個(gè)地把L 的當(dāng)前元素r插入到新的鏈表頭部。void Linkedreverse(LinkedList *L) 鏈表的就地逆置p=L->

35、next ; L->next=NULL ;while(p!=NULL)r=p , p=p->next ; r 指向當(dāng)前待逆置的結(jié)點(diǎn), p 記下下個(gè)結(jié)點(diǎn)r->next=L >next ; L->next=r ;放到表頭 2設(shè)順序表L 是一個(gè)遞增 ( 允許有相同的值) 有序表,試寫一算法將x 插入 L 中,并使 L 仍為一個(gè)有序表。答:分析:先找到 x 的正確插入位置,然后將大于 xx 插入到其位int x) xvoid SeqListinsert(SeqList *L插入到遞增有序的順序表L 中i=0;while(i<=L->length-1)&

36、&(x>=L->datai)i+ ; 找正確的插入位置for(k=L->length-1;k>=i ; k-)元素從后往前依次后移L->datak+1=L->datakL->datai=x ; x 插入到正確位置L->length+ ;)3. 設(shè)單鏈表 L 是一個(gè)遞減有序表,試寫一個(gè)算法將x插入其中后仍保持L 的有序性。答:分析:此問題的關(guān)鍵是在鏈表中找到 x 的插入位置,因此需要兩個(gè)指針一前一后地依次向后移動(dòng)。void LinkListinsert(LinkedList *L, int x)x 插入有序鏈表L 中q=L ; p=q &g

37、t;next ;while(p!=NULL&&p >data>x) 找到插入的位置q=p ; p=p >next ; s=(LinkedList*)malloc(sizeof(LinkedList);生成新結(jié)點(diǎn)S >data=x ; S >next=p ; q >next=s ; 4. 試寫出在不帶頭結(jié)點(diǎn)的單鏈表的第 i 個(gè)元素之前插入一個(gè)元素的算法。答:分析:對不帶頭結(jié)點(diǎn)的鏈表操作時(shí),要注意對第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)操作的不同。i 個(gè)元素之前插入一int x ,void LinkedListlnsert(LinkedList *L int i)

38、 不帶頭結(jié)點(diǎn)的單鏈表的第個(gè)元素p=L : j=1;while(p!=NULL&&j<i-1) 找到第 i-1 個(gè)元素p=p >next ; j+ ; if(i<=0|p=NULL) printf( " 插入位置不正確力n” );elseq=(LinkedList*)malloc(sizeof(LinkedList); q >data=x ;if(i=1) q >next=L ; L=q; 在第一個(gè)元素之前插入elseq >next=p >next ; p >next=q ; 在其他位置插入 5設(shè)A、 B 是兩個(gè)線性表,其

39、表中元素遞增有序,長度分別為m和n。試寫一算法分別以順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)將 A 和 B 歸并成一個(gè)仍按元素值遞增有序的線性表A、B 表中較小的元素寫入最后將沒結(jié)束的表的剩余答: (1) 分析:用三個(gè)變量i 、 j 、 k 分別指示A、 B、 C三個(gè)順序表的當(dāng)前位置,將C 中, 直到有一個(gè)表先結(jié)束。元素寫入C表中。SeqList *Seqmerge(SeqList A , SeqList B , SeqList*C) /有序順序表 A和B歸并成有序順序表 Ci=0 ; j=0 ; k=0 ; i , i , k 分別為順序表A, B,C 的下標(biāo)while(i<m&&j<

40、n) A 中當(dāng)前元i+ ; ; Bif(A.datai<B.dataj)素較小C->datak=A.datailelse C->datak=B.dataj;j+中當(dāng)前元素較小k+ ; if (i=m) for(t=j ; t<n ;t+)C->datak=B.datat;k+ ; /B 表長度大于 A 表else for(t=i; t<m; t+) C->datak=A.datat ;k+; /A表長度大于B表C->length=m+n ; return C;(2)VOid Linkmerge(LinkedList *A , LinkedList

41、 *B , LinkedList *C)/有序鏈表A和B歸并成有序鏈表Cpa=A >next ; pb=B >next ; C=A; pc=C;while(pa&&pb)/A和B都不為空時(shí)if(pa >data<pb >data) A 當(dāng)前結(jié)點(diǎn)值較小qa=pa->next ;pC->next=pa ;pc=pc->next ; pa=qa ; else qb=pb->next ; pc->next=pb : pc=pc->next ;pb=qb; B 當(dāng)前結(jié)點(diǎn)值較小if(pa)pc >next=pa ;/A

42、沒有結(jié)束,將 A表剩余元素鏈接到C表if(pb)pc >next=pb;/B 沒有結(jié)束,將 B 表剩余元素鏈接到C表free(B) ;/釋放B表的頭結(jié)點(diǎn)本算法需要遍歷兩個(gè)線性表,因此時(shí)間復(fù)雜度為O(m+n)。6設(shè)指針 la 和 lb 分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表的首結(jié)點(diǎn),設(shè)計(jì)從表la 中刪除第 i 個(gè)元素起共len 個(gè)元素,并將這些元素插入到 lb 中第 j 個(gè)結(jié)點(diǎn)之前的算法。答:分析:先在 la 中找到第 i 個(gè)結(jié)點(diǎn),分別用兩個(gè)指針 pre 和 p 指向第 i-1 和第 i 個(gè)結(jié)點(diǎn),然后用指針 q從第 i 個(gè)結(jié)點(diǎn)起向后走 len 個(gè)元素,使q 指向此位置。然后在 lb 中找到第 j

43、個(gè)結(jié)點(diǎn),將p 所指向的 la 表中的第 i 個(gè)及 q 所指向的最后一個(gè)共len 個(gè)結(jié)點(diǎn)插入到lb 中。void Deletelnsert(LinkedList *la , LinkedList*lb , int i , int j, int len) 刪除不帶頭結(jié)點(diǎn)的單鏈表la 中第 i 個(gè)元素起共len 個(gè)元素 , 并將這峰元素插入到單鏈表lb 中第 j 個(gè)結(jié)點(diǎn)之前if(i<0|j<0|len<0) exit(0)p=la ; k=1; pre=NULL;while(p&&k<i) 在 la 表中查找第 i 個(gè)結(jié)點(diǎn)pre=p ; p=p->nex

44、t; k+; if(!p) exit(0) ;q=p ; k=l ; p 指向 la 表中第 i 個(gè)結(jié)點(diǎn)while(q&&k<len) q=q >next ; k+ ; 查找 la 表中第 i+len-1 個(gè)結(jié)點(diǎn)if(!q) exit(0) ;if(pre=la) la=q >next ;i=1 的情況else pre >next=q >next ;完成刪除將從 la 中刪除的結(jié)點(diǎn)插入到 lb 中if(j=1) q->next=lb ; lb=p ; j=1時(shí)else r=lb; k=1; j>1 時(shí)while(r&&k

45、<j-1) r=r >next ; k+ ; 查找 Lb 表中第 i 1 個(gè)元素if(!r) exit(0);q >next=r >next ; r >next=p ;完成插入 7單鏈表L 是一個(gè)遞減有序表,試寫一高效算法,刪除表中值大于 min 且小于max 的結(jié)點(diǎn)( 若表中有這樣的結(jié)點(diǎn)),同時(shí)釋放被刪結(jié)點(diǎn)空間,這里 min和max是兩個(gè)給定的參數(shù)。int min答: LinkedList delete(LinkedList *L int max) 刪除遞減有序單鏈表max的結(jié)點(diǎn)L 中值大于 min 且小于q=L ;if(min>max) printf(

46、" min>max' n " );exit(0) ; else p=L >next ; q 始終指向 p 的前驅(qū)while(p >data>=max) 當(dāng)前元素大于或等于max,則p、q依次向后移動(dòng)q=p ; p=p >next ; while(p!=NULL)&&(p 一 >data>min) /當(dāng)前元素的值比 min大同時(shí)比max小,刪除p 指向的結(jié)點(diǎn)q >next=p >next , free(p) ; p=q >next ;return L ;8編寫一個(gè)算法將一個(gè)頭結(jié)點(diǎn)指針為pa 的

47、單鏈表 A分解成兩個(gè)單鏈表A和B,其頭結(jié)點(diǎn)指針分別為pa和pb,使得A鏈表中含有原鏈表 A中序號(hào)為奇數(shù)的元素, 而 B 鏈表中含有原鏈表A 中序號(hào)為偶數(shù)的元素,且保持原來的相對順序。答:分析:用兩個(gè)工作指針p 和 q 分別指示序號(hào)為奇數(shù)和序號(hào)為偶數(shù)的結(jié)點(diǎn),將q 所指向的結(jié)點(diǎn)從A 表刪除,并鏈接到 B 表。void decompose(LinkedList *A , LinkedList *B) 單鏈表A 分解成元素序號(hào)為奇數(shù)的單鏈表A 和元素序號(hào)為偶數(shù)的單鏈表Bp=A->next;B=(LinkedList*)malloc(sizeof(LinkedList);r=B ;while(p!

48、=NULL&&p->next!=NULL)q=p >next ; q 指向偶數(shù)序號(hào)的結(jié)點(diǎn)p >next=q >next ;將 q 從 A 表中刪除r >next=q ;/將q結(jié)點(diǎn)鏈接到B鏈表的末尾r=q ;/r總是指向B鏈表的最后一個(gè)結(jié)點(diǎn)p=p >next ; p 指向原鏈表A 中的奇數(shù)序號(hào)的結(jié)點(diǎn)r >next=NULL;/將生成B鏈表中的最后一個(gè)結(jié)點(diǎn)的 next 域置為空9假設(shè)以兩個(gè)元素值遞增有序排列的線性表A、B 分別表示兩個(gè)集合, 要求另辟空間構(gòu)造一個(gè)線性表C, 其元素為兩集合的交集,且表C 中的元素值也遞增有序排列。用順序表實(shí)現(xiàn)

49、并寫出 C 的算法。答:分析:用三個(gè)變量 i 、 j 、 k 分別指示A、B、C 三個(gè)順序表的當(dāng)前位置,若A、 B 表中當(dāng)前元素值相同,則寫入C中,并使i、j、k值增1;若A表元素值較小,則使 i 增 1;若 B 表元素值較小,則使j 增 1,直到有一個(gè)表先結(jié)束。SeqLiSt *intersection(SeqList A , SeqList B ,SeqList *C) 求元素依值遞增有序排列的順序表A、 B 的交集Ci=0 ; j=0 ; k=0 ;while(i<=A.length-1)&&(j<=B.length-1)if(A.datai=B.dataj)

50、的元素C->datak=A.datai入 C 表中k+; i+ ; j+ ;elseif(A.datai<B.dataj) i+前元素不等,值較小的下標(biāo)增else j+;找到值相同相同元素寫; A、B 表當(dāng)C->length=k ; return C 11 假設(shè)在長度大于 1 的單循環(huán)鏈表中,既無頭結(jié)點(diǎn) 也無頭指針。 s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指針, 試編寫算法刪除結(jié)點(diǎn) *s 的直接前驅(qū)結(jié)點(diǎn)。答:分析:因?yàn)榧炔恢来藛窝h(huán)鏈表的頭指針,也不知道其尾指針,所以找 s 的前驅(qū)就只能從s 開始,順次向后尋找。void DeletePre(Linkedlist *s) 刪除單循環(huán)鏈表

51、中結(jié)點(diǎn) s 的直接前驅(qū)p=s ;while(p >next >next!=s) p=p >next ;找到 s 的前驅(qū)的前驅(qū)pq=p >next ; q 是 p 的后繼, 即 s 的前驅(qū)p >next=s ; 將 q 刪除free(q) ;12 計(jì)算帶頭結(jié)點(diǎn)的循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)。答: int number(Linkedlist *head) 計(jì)算單循環(huán)鏈表中結(jié)點(diǎn)的個(gè)數(shù)p=head >next ; i=0 ;while(p!=head) i+; p=p->next ; return i ;13 已知由單鏈表表示的線性表中,含有三類字符的數(shù)據(jù)元素 ( 如:

52、字母字符、數(shù)字字符和其他字符 ) ,試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表,使得每個(gè)表中只含有同一類的字符,且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間,頭結(jié)點(diǎn)可另辟空間。答:分析: p 指向待處理的單鏈表的首元結(jié)點(diǎn),構(gòu)造三個(gè)空的單循環(huán)鏈表,分別存儲(chǔ)三類字符,其中一個(gè)表可使用原來的單鏈表。 q 指向 p 的下一個(gè)結(jié)點(diǎn), 根據(jù) *p的數(shù)據(jù)域的值將其插入到不同的鏈表上。再把 q 的值給p,處理下一個(gè)結(jié)點(diǎn)。void change(LinkedList *L , LinkedList *pa , LinkedList *pb , LinkedList *pc) 分解含有三類字符的單鏈表為三個(gè)以循環(huán)鏈

53、表表示的線性表,使其分別含有三類字符p=L >next ; pa=L ;pa >next=pa ; 分別構(gòu)造三個(gè)單循環(huán)鏈表pb=(LinkedList*)malloc(sizeof(LinkedList);pc=(LinkedList*)malloc(sizeof(LinkedList);pb >next=pb ; pc >next=pc ;while(p!=L)q=p >next ; -/q記下L中下一個(gè)結(jié)點(diǎn)的位if(p >data<= z &&p >data>= a )鏈接到字母鏈表的頭部p >next=pa &g

54、t;next ; pa >next=p ; else if (p >data<= 9 &&(p >data>= 0 )鏈接到數(shù)字鏈表的頭部p >next=pb >next ; pb >next=p ; elsep->next=pc->next ; pc->next=p ; 鏈接到其他字母鏈表的頭部p=q ; 14、己知A、 B 和 C 為三個(gè)遞增有序的線性表,現(xiàn)要求對A表進(jìn)行如下操作:刪去那些既在B表中出現(xiàn)又在C 表中出現(xiàn)的元素。試對順序表編寫實(shí)現(xiàn)上述操作的算法( 注:題中未特別指明同一表中的元素值各不相同) 。

55、答:分析:先從B 和 C 中找出共有元素,記為same,再在A中從當(dāng)前位置開始,凡小于 same的元素均保留 ( 存到新的位置 ) ,等于 same 的就跳過,到大于 same時(shí)就再找下一個(gè)SameSeqList IntersectDelete(SeqList *A , SeqList B , SeqList C) 對順序表A 刪去那些既在B 表中出現(xiàn)又在C 表中出現(xiàn)的元素i=0 ; j=0 ; k=0 ; m=0; i 指示 A 中元素原來的位置,m為移動(dòng)后的位置while(i<A->length&&i<B.length&&k<C.length)if(B.dataj<C.datak) j+;e

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論