(13電子本)數(shù)據(jù)結(jié)構(gòu)-選擇填空

第一章概論一、填空題計(jì)算機(jī)專業(yè)人員必須完成的兩項(xiàng)基本任務(wù)是：數(shù)據(jù)表示和數(shù)據(jù)處理。數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存在形式稱為機(jī)內(nèi)表示。3?概括地說，數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容包括：數(shù)據(jù)的邏輯結(jié)構(gòu)、定義在邏輯結(jié)構(gòu)上的基本運(yùn)算、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和運(yùn)算的實(shí)現(xiàn)。此外，該課程還要考慮各種結(jié)構(gòu)和實(shí)現(xiàn)方法的評(píng)價(jià)和選擇。由一種邏輯性_結(jié)構(gòu)和一組—基本運(yùn)算構(gòu)成的整體是實(shí)際問題的一種數(shù)學(xué)模型，這種數(shù)學(xué)模型的建立、選擇和實(shí)現(xiàn)是數(shù)據(jù)結(jié)構(gòu)的核心問題。存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的存儲(chǔ)實(shí)現(xiàn)。數(shù)據(jù)表示任務(wù)是逐步完成的，即數(shù)據(jù)表示形式的變化過程是機(jī)外表示-〉邏輯結(jié)構(gòu)->存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)處理任務(wù)也是逐步完成的，即轉(zhuǎn)化過程是處理要求->基本運(yùn)算和運(yùn)算->算法。&從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)看，通常所說的〃數(shù)據(jù)〃應(yīng)分成三個(gè)不同的層次，即—數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)。9?根據(jù)需要，數(shù)據(jù)元素又被稱為元素、結(jié)點(diǎn)、頂點(diǎn)或記錄。在有些場(chǎng)合下，數(shù)據(jù)項(xiàng)又稱為字段或域，它是數(shù)據(jù)的不可分割的最小標(biāo)識(shí)單位。從某種意義上說，數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)實(shí)際反映了數(shù)據(jù)組織的三個(gè)層次，數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)四類基本邏輯結(jié)構(gòu)，它們反映了四類基本的數(shù)據(jù)組織形式。根據(jù)操作的效果，可將運(yùn)算分成以下兩種基本類型：加工型運(yùn)算，其操作改變了原邏輯結(jié)構(gòu)的“值”,如結(jié)點(diǎn)個(gè)數(shù)、某些結(jié)點(diǎn)的內(nèi)容等；引用型運(yùn)算，其操作不改變?cè)壿嫿Y(jié)構(gòu)，只從中提取某些信息作為運(yùn)算的結(jié)果。將以某種邏輯結(jié)構(gòu)S為操作對(duì)象的運(yùn)算稱為“定義在S上的運(yùn)算”,簡(jiǎn)稱“_S上運(yùn)算”。一般地，可能存在同一邏輯結(jié)構(gòu)S上的兩個(gè)運(yùn)算A和B，A的實(shí)現(xiàn)需要或可以利用B，而B的實(shí)現(xiàn)不需要利用A。在這種情況下，稱A可以“歸納”為B。存儲(chǔ)實(shí)現(xiàn)的基本目標(biāo)是建立數(shù)據(jù)的機(jī)內(nèi)表示。—般地，一個(gè)存儲(chǔ)結(jié)構(gòu)包括存儲(chǔ)結(jié)點(diǎn)、數(shù)據(jù)兀素之間關(guān)聯(lián)方式的表示7.附加設(shè)施三個(gè)主要部分。通常，存儲(chǔ)結(jié)點(diǎn)之間可以有順序存儲(chǔ)方式、鏈?zhǔn)酱鎯?chǔ)方式、索引存儲(chǔ)方式、散列存儲(chǔ)方式四種關(guān)聯(lián)方式，稱為四種基本存儲(chǔ)方式?？捎萌魏我环N存儲(chǔ)方式所規(guī)定的存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)方式來間接表達(dá)給定邏輯結(jié)構(gòu)S中數(shù)據(jù)元素之間的邏輯關(guān)系。由此得到的存儲(chǔ)結(jié)構(gòu)，稱為給定邏輯結(jié)構(gòu)S的存儲(chǔ)實(shí)現(xiàn)—或—存儲(chǔ)映象?！獋€(gè)運(yùn)算的實(shí)現(xiàn)是指一個(gè)完成該運(yùn)算功能的墮序。運(yùn)算實(shí)現(xiàn)的核心是處理步驟的規(guī)定，即算法設(shè)計(jì)。21?任何算法都必須用某種語(yǔ)言加以描述。根據(jù)描述算法的語(yǔ)言的不同，可將算法分為：運(yùn)行終止的程序可執(zhí)行部分、偽語(yǔ)言算法、非形式算法三類。數(shù)據(jù)結(jié)構(gòu)課程著重評(píng)論算法的時(shí)空性能，又稱為“算法分析”。通常從正確性能、易讀性、健壯性、高效性等幾方面評(píng)價(jià)算法的（包括程序）的質(zhì)量。一個(gè)算法的時(shí)空性能是指該算法的時(shí)間性能和空間性能，前者是算法包含的計(jì)算量后者是算法需要的存儲(chǔ)量。通常采用下述辦法來估算求解某類問題的各個(gè)算法在給定輸入下的計(jì)算量：根據(jù)該類問題的特點(diǎn)合理地選擇一種或幾種操作作為“標(biāo)準(zhǔn)操作”;確定每個(gè)算法在給定輸入下共執(zhí)行了多少次—標(biāo)準(zhǔn)操作，并將此次數(shù)規(guī)定為該算法在給定輸入下的計(jì)算量。通常，一個(gè)算法在不同輸入下的計(jì)算量是不同的。則可用以下兩種方式來確定一個(gè)算法的計(jì)算量：以算法在所有輸入下的計(jì)算量的最大值作為算法的計(jì)算量，這種計(jì)算量稱為算法的最壞情況時(shí)間復(fù)雜性或—最壞情況時(shí)間復(fù)雜度。以算法在所有輸入下的計(jì)算量的加權(quán)平均值作為算法的計(jì)算量，這種計(jì)算量稱為算法的—平均時(shí)間復(fù)雜性或平均時(shí)間復(fù)雜度。最壞情況時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性統(tǒng)稱為時(shí)間復(fù)雜性或時(shí)間復(fù)雜度。在一般情況下，一個(gè)算法的時(shí)間復(fù)雜性是算法輸入規(guī)模的函數(shù)。一個(gè)算法的輸入規(guī)模或問題的規(guī)模是指—作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)。常見時(shí)間復(fù)雜性的量級(jí)有：常數(shù)階0(1)、對(duì)數(shù)階0(log2n)、線性階0(_n_)、平方階o(_n_)、和指數(shù)階0(2n)o通常認(rèn)為，具有指數(shù)階量級(jí)的算法是實(shí)際不可計(jì)算,而量級(jí)低于平方階的算法是高效的。數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的—設(shè)計(jì)_和_實(shí)現(xiàn)_。數(shù)據(jù)結(jié)構(gòu)的課程的主要內(nèi)容可以概括為：數(shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的評(píng)價(jià)和選擇-。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。程序段“for(i=l;i〈二n;i++){k++;for(j=1;j〈二n;j++)l+=k;}”的時(shí)間復(fù)雜度T(n)=0(n2)。程序段“i=1;while(i〈二n)i=i*2;”的時(shí)間復(fù)雜度T(n)=o(lo%n)。二、單項(xiàng)選擇題以下說法錯(cuò)誤的是2_用數(shù)字式計(jì)算機(jī)解決問題的實(shí)質(zhì)是對(duì)數(shù)據(jù)的加工處理程序設(shè)計(jì)的實(shí)質(zhì)是數(shù)據(jù)處理數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的組織形式，基本運(yùn)算規(guī)定了數(shù)據(jù)的基本操作方式運(yùn)算實(shí)現(xiàn)是完成運(yùn)算功能的算法，或這些算法的設(shè)計(jì)數(shù)據(jù)處理方式總是與數(shù)據(jù)某種相應(yīng)的表示形式相聯(lián)系，反之亦然根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式。以下解釋錯(cuò)誤的是(1)集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條〃鎖鏈〃樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接3?關(guān)于邏輯結(jié)構(gòu)，以下說法錯(cuò)誤的是(2)邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形成、內(nèi)容無關(guān)邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置有關(guān)邏輯結(jié)構(gòu)與所含結(jié)點(diǎn)個(gè)數(shù)無關(guān)一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種〃本質(zhì)性〃的東西根據(jù)操作的效果，可將運(yùn)算分成加工型運(yùn)算、引用型運(yùn)算兩種基本類型。對(duì)于表格處理中的五種功能以下解釋錯(cuò)誤的是(3)查找引用型運(yùn)算，功能是找出滿足某種條件的結(jié)點(diǎn)在S(線形結(jié)構(gòu))中的位置讀取引用型運(yùn)算功能是讀出S(線形結(jié)構(gòu))中某指定位置結(jié)點(diǎn)的內(nèi)容插入引用型運(yùn)算，功能是在S(線形結(jié)構(gòu))的某指定位置上增加一個(gè)新結(jié)點(diǎn)刪除加工型運(yùn)算，功能是撤消S(線形結(jié)構(gòu))某指定位置上的結(jié)點(diǎn)更新加工型運(yùn)算，功能是修改S(線形結(jié)構(gòu))中某指定結(jié)點(diǎn)的內(nèi)容一般地，一個(gè)存儲(chǔ)結(jié)構(gòu)包括以下三個(gè)主要部分。以下說法錯(cuò)誤的是(1)存儲(chǔ)結(jié)點(diǎn)每個(gè)存儲(chǔ)結(jié)點(diǎn)可以存放一個(gè)或一個(gè)以上的數(shù)據(jù)元素?cái)?shù)據(jù)元素之間關(guān)聯(lián)方式的表示也就是邏輯結(jié)構(gòu)的機(jī)內(nèi)表示附加設(shè)施，如為便于運(yùn)算實(shí)現(xiàn)而設(shè)置的“啞結(jié)點(diǎn)”等等一般地，一個(gè)存儲(chǔ)結(jié)構(gòu)包括以下三個(gè)主要部分。以下說法錯(cuò)誤的是每個(gè)存儲(chǔ)結(jié)點(diǎn)只能存放一個(gè)數(shù)據(jù)元素(2)數(shù)據(jù)元素之間的關(guān)聯(lián)方式可由存儲(chǔ)結(jié)點(diǎn)之間的關(guān)聯(lián)方式直接表達(dá)一種存儲(chǔ)結(jié)構(gòu)可以在兩個(gè)級(jí)別上討論。其一是機(jī)器級(jí)，其二是語(yǔ)言級(jí)語(yǔ)言級(jí)描述可經(jīng)編譯自動(dòng)轉(zhuǎn)換成機(jī)器級(jí)因此也可以看成是一種機(jī)內(nèi)表示通常從正確性、易讀性、健壯性、高效性等四個(gè)方面評(píng)價(jià)算法(包括程序)的質(zhì)量。以下解釋錯(cuò)誤的是(4)正確性算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能(即處理要求)易讀性算法應(yīng)易于閱讀和理解以便于調(diào)試修改和擴(kuò)充健壯性當(dāng)環(huán)境發(fā)生變化時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不需要的運(yùn)行結(jié)果高效性即達(dá)到所需要的時(shí)間性能對(duì)于數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容，以下解釋正確的是(3)數(shù)據(jù)結(jié)構(gòu)的定義，包括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算集數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，包括存儲(chǔ)實(shí)現(xiàn)、運(yùn)算實(shí)現(xiàn)和基本運(yùn)算集數(shù)據(jù)結(jié)構(gòu)的評(píng)價(jià)和選擇，包括邏輯結(jié)構(gòu)的選擇、基本運(yùn)算集的選擇和存儲(chǔ)選擇9，與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的(3)存儲(chǔ)結(jié)構(gòu)②存儲(chǔ)實(shí)現(xiàn)③邏輯結(jié)構(gòu)④運(yùn)算實(shí)現(xiàn)10順序存儲(chǔ)結(jié)構(gòu)(3)僅適合于靜態(tài)查找表的存儲(chǔ)僅適合于動(dòng)態(tài)查找表的存儲(chǔ)既適合靜態(tài)又適合動(dòng)態(tài)查找表的存儲(chǔ)既不適合靜態(tài)又不適合動(dòng)態(tài)查找表的存儲(chǔ)算法的時(shí)間復(fù)雜度，都要以通過算法中執(zhí)行頻度最高的語(yǔ)句的執(zhí)行次數(shù)來確定這種觀點(diǎn)(2)正確②錯(cuò)誤以下說法正確的是(2)所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)順序文件只適合于存放在磁帶上，索引文件只能存放在磁盤上基于某種邏輯結(jié)構(gòu)之上的運(yùn)算，其實(shí)現(xiàn)是惟一的以下說法正確的是(4)①數(shù)據(jù)元素是數(shù)據(jù)的最小單位數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合以下說法錯(cuò)誤的是（4）①所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系的整體數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要而建立的數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映象分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（2）數(shù)據(jù)元素具有同一特點(diǎn)不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致每個(gè)數(shù)據(jù)元素都一樣數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等第二章線性表習(xí)題一、單項(xiàng)選擇題TOC\o"1-5"\h\z線性表是__A?！獋€(gè)有限序列，可以為空B.—個(gè)有限序列，不可以為空C.一個(gè)無限序列，可以為空D.—個(gè)無限序列，不可以為空在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（O〈=i〈=n）時(shí)，需向前移動(dòng)A個(gè)元素。n-iB.n-i+lC.n-i-1D.i線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址___D。A.必須是連續(xù)的B.一定是不連續(xù)的C.部分地址必須是連續(xù)的D.連續(xù)與否均可以從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較___C個(gè)元素結(jié)點(diǎn)。A.n/2B.nC.（n+1）/2D.（n-1）/2在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是_D—。p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;設(shè)單鏈表中指針p指向結(jié)點(diǎn)m,若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為___A。A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p;在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素（0〈i〈n+l）之前插入一個(gè)新元素時(shí)，需向后移動(dòng)__B個(gè)元素。A．n-iB．n-i+lC．n-i-1D．i在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行BA．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q以下關(guān)于線性表的說法不正確的是__C。A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。線性表的順序存儲(chǔ)結(jié)構(gòu)是一種__A的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B順序存取C.索引存取D.散列存取在順序表中，只要知道___D，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A.基地址B結(jié)點(diǎn)大小C.向量大小D.基地址和結(jié)點(diǎn)大小在等概率情況下，順序表的插入操作要移動(dòng)__B結(jié)點(diǎn)。A.全部B一半C.三分之一D.四分之一在___C___運(yùn)算中，使用順序表比鏈表好。A.插入B刪除C.根據(jù)序號(hào)查找D.根據(jù)元素值查找在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是TOC\o"1-5"\h\z__B。A．O(1)B．O(n)C．O(n2)D．O(logn)設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列C。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端(即0單元)作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為__C。A．top不變B．top=0C．top--D．top++向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行__B。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為___D。A．rear％n==frontB．(front+l)％n==rearC．rear％n-1==frontD．(rear+l)％n==front在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為___C。A．rear％n==frontB．front+l=rearC．rear==frontD．(rear+l)％n=front在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為___A。A．front=front->nextB．rear=rear->nextC．rear=front->nextD．front=rear->next二、填空題線性表是一種典型的線性結(jié)構(gòu)。在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移n-i+1個(gè)元素。順序表中邏輯上相鄰的元素的物理位置相鄰。要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需一前移-一個(gè)位置,移動(dòng)過程是從一前-向一后-依次移動(dòng)每一個(gè)元素。在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過物理存儲(chǔ)位置決定的：在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向一前趨-結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)。當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用一順序-存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí),則采用鏈接一存儲(chǔ)結(jié)構(gòu)為宜。&順序表中邏輯上相鄰的元素，物理位置-一定相鄰,單鏈表中邏輯上相鄰的元素，物理位置一不一定相鄰。線性表、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在線性表的任何位置插入和刪除元素；對(duì)于棧只能在棧頂一位置插入和刪除元素：對(duì)于隊(duì)列只能在隊(duì)尾位置插入元素和在一隊(duì)頭-位置刪除元素。根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為單鏈表和雙鏈表：而根據(jù)指針的聯(lián)接方式，鏈表又可分為非循環(huán)鏈表和循環(huán)鏈表。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是。對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為一0(1)一，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)__。對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為棧滿，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為?？眨?dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明棧的可用最大容量為m。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的棧底分別設(shè)在這片內(nèi)存空間的兩端,這樣只有當(dāng)兩個(gè)棧的棧頂在?？臻g的某一位置相遇時(shí)才產(chǎn)牛上溢。設(shè)有一空棧，現(xiàn)有輸入序列1,2，3，4，5,經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是2、3。無論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為。習(xí)題三棧和隊(duì)列一單項(xiàng)選擇題在作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否(①)，在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否(②)。當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為(③)。(BAB)①,②:A.空B.滿C.上溢D.下溢:A.n-1B.nC.n+1D.n/2若已知一個(gè)棧的進(jìn)棧序列是1,2,3,…，n，其輸出序列為pl,p2,p3,...,pn,若pl=3,則p2為(A)。A可能是2B一定是2C可能是1D一定是1有六個(gè)元素6,5,4,3,2,1的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？(C)543612B.453126C.346521D.234156設(shè)有一順序棧S,元素s,s,s,s,s,s依次進(jìn)棧，如果6個(gè)元素出棧的順序是s,s,s,s,1234562346s,s,則棧的容量至少應(yīng)該是(B)51A.2B.3C.5D.6若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1..m],top[i]代表第i個(gè)棧(i=1,2)棧頂，棧1的底在v[1],棧2的底在V[m],則棧滿的條件是(B)。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]執(zhí)行完下列語(yǔ)句段后，i值為：(B)intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.無限遞歸表達(dá)式3*2'(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為(D),其中’為乘冪。A.3,2,4,1,1；(*(+*-B.3,2,8；(*—C.3,2,4,2,2；(*"(-D.3,2,8；(*"(-&用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)(D)。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為(C)的數(shù)據(jù)結(jié)構(gòu)。A.隊(duì)列B.多維數(shù)組C.棧D.線性表設(shè)C語(yǔ)言數(shù)組Data[m+1]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針,則執(zhí)行出隊(duì)操作的語(yǔ)句為(D)A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%(m+1)D.front=(front+1)%(m+1)循環(huán)隊(duì)列的隊(duì)滿條件為(C)(sq.rear+1)%maxsize==(sq.front+1)%maxsize;(sq.front+1)%maxsize==sq.rear(sq.rear+1)%maxsize==sq.frontsq.rear==sq.front棧和隊(duì)列的共同點(diǎn)是(C)。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)二、填空題棧是_操作受限(或限定僅在表尾進(jìn)行插入和刪除操作)的線性表，其運(yùn)算遵循—后進(jìn)先出的原則。一個(gè)棧的輸入序列是：1,2,3則不可能的棧輸出序列是312。用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為SXSSXSXX_。循環(huán)隊(duì)列的引入，目的是為了克服假溢出時(shí)大量移動(dòng)數(shù)據(jù)元素。隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是先進(jìn)先出。已知鏈隊(duì)列的頭尾指針分別是f和r，則將值x入隊(duì)的操作序列是s=(LinkedList)malloc(sizeof(LNode))；s—〉data二x;s—〉next=r—〉next；r—〉next=s；r=s；7.表達(dá)式求值是應(yīng)用的一個(gè)典型例子。循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear，貝V當(dāng)前隊(duì)列的元素個(gè)數(shù)是__(rear-front+m)%m_。以下運(yùn)算實(shí)現(xiàn)在鏈棧上的初始化，請(qǐng)?jiān)谔幱谜?qǐng)適當(dāng)句子予以填充。VoidInitStacl(LstackTp*ls){一ls二NULL;}'以下運(yùn)算實(shí)現(xiàn)在鏈棧上的進(jìn)棧，請(qǐng)?jiān)谔幱谜?qǐng)適當(dāng)句子予以填充。VoidPush(LStackTp*ls,DataTypex){LstackTp*p;p=malloc(sizeof(LstackTp));p—〉data=x;p—〉next=ls;ls=p;}以下運(yùn)算實(shí)現(xiàn)在鏈棧上的退棧，請(qǐng)?jiān)谔幱谜?qǐng)適當(dāng)句子予以填充。IntPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x=;ls=ls—〉next;一free(p);return(1)；}elsereturn(0);}以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的入隊(duì)列，請(qǐng)?jiān)谔幱眠m當(dāng)句子予以填充。VoidEnQueue(QueptrTp*lq,DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));p—〉data=x;p—〉next=NULL;(lq-〉rear)-〉next二_p_;.lq—〉rear二p;習(xí)題四串一、單項(xiàng)選擇題1．下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（B）A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)2．串是一種特殊的線性表，其特殊性體現(xiàn)在（B）。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符3．串的長(zhǎng)度是指（B）A.串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)設(shè)有兩個(gè)串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（C）A.求子串B.聯(lián)接C.匹配D.求串長(zhǎng)若串S=“software”，其子串的個(gè)數(shù)是（C）。A.8B.37C.36D.9二、填空題1?含零個(gè)字符的串稱為空-串。任何串中所含字符-的個(gè)數(shù)稱為該串的長(zhǎng)度?？崭翊侵竉由空格字符（ASCII值32）所組成的字符串,其長(zhǎng)度等干空格個(gè)數(shù)。當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度____相等并且各個(gè)對(duì)應(yīng)位置上的字符都相等時(shí),這兩個(gè)串相等。一個(gè)串中任意個(gè)連續(xù)字符組成的序列稱為該串的一子____串，該串稱為它所有子串的一主一串。TOC\o"1-5"\h\zINDEX（'DATASTRUCTURE','STR'）=_5。模式串P='abaabcac'的next函數(shù)值序列為_01122312,。下列程序判斷字符串s是否對(duì)稱，對(duì)稱則返回1,否則返回0；如f（〃abba〃）返回1,f（〃abab〃）返回0；intf（）{inti=0,j=0；while（s[j]）（2）j++;for（j—;i<j&&s[i]==s[j];i++,j—）;return（（3）i〉=j）}下列算法實(shí)現(xiàn)求采用順序結(jié)構(gòu)存儲(chǔ)的串s和串t的一個(gè)最長(zhǎng)公共子串。voidmaxcomstr(orderstring*s,*t;intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while(i<=s.len){j=1;while(j<=t.len){if(s[i]==t[j]){k=1;length1=1;con=1;while(con)if(l)i+k〈二s.len&&j+k〈二t.len&&s「i+k]二=t[j+k]{length1=length1+1;k=k+1;}else(2)con=0:if(length1>length){index=i;length=length1;}(3)i+=k:}else(4)i++:}(5)i++}}習(xí)題五數(shù)組和廣義表一、單項(xiàng)選擇題1．常對(duì)數(shù)組進(jìn)行的兩種基本操作是(C)A.建立與刪除B.索引與修改C.查找與修改D.查找與索引對(duì)于C語(yǔ)言的二維數(shù)組DataTypeA[m][n],每個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組中任意元素a[i,j]的存儲(chǔ)位置可由(C)式確定.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kLoc[i,j]=loc[0,0]+[(m+n)*i+j]*kLoc[i,j]=loc[0,0]+[(n+1)*i+j]*kLoc[i,j]=[(n+1)*i+j]*k稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)(A)A.非零元素B.三元祖(i,j,aij)C.aijD.i,j數(shù)組A[0..5,0..6]的每個(gè)元素占五個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是(A)。A.1175B.1180C.1205D.1210A[N，N]是對(duì)稱矩陣，將下面三角(包括對(duì)角線)以行序存儲(chǔ)到一維數(shù)組T[N(N+1)/2]中，則對(duì)任一上三角元素a[i][j]對(duì)應(yīng)T[k]的下標(biāo)k是(B)。A.i(i-1)/2+jB.j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+1用數(shù)組r存儲(chǔ)靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中結(jié)點(diǎn)，使j沿鏈移動(dòng)的操作為(A)。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是(C)。A.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間D.降低運(yùn)算的時(shí)間復(fù)雜度&已知廣義表LS=((a,b,c),(d,e,f)),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是(C)。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS)))D.head(tail(tail(head(LS))))廣義表((a,b,c,d))的表頭是()，表尾是(C)。A.aB.()C.(a,b,c,d)D.(b,c,d)設(shè)廣義表L=((a,b,c)),則L的長(zhǎng)度和深度分別為(C)。

A.1A.1和1B.1和3下面說法不正確的是(A)。A.廣義表的表頭總是一個(gè)廣義表C.廣義表難以用順序存儲(chǔ)結(jié)構(gòu)二、填空題C.1和2D.2和3B.廣義表的表尾總是一個(gè)廣義表D.廣義表可以是一個(gè)多層次的結(jié)構(gòu)通常采用_順序-存儲(chǔ)結(jié)構(gòu)來存放數(shù)組。對(duì)二維數(shù)組可有兩種存儲(chǔ)方法：一種是以列序?yàn)橹餍虻拇鎯?chǔ)方式，另一種是以為主序的存儲(chǔ)方式。用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素A[i,j](1WiWn,i-2WjWi+2),B中的第8個(gè)元素是A中的第第1行，第第3列的元素。設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組B[1..n*(n+1)/2]中，若按行為主序存儲(chǔ)，則A[i,j]對(duì)應(yīng)的B中存儲(chǔ)位置為i(i-1)/2+j(1〈=i,j〈=n)。所謂稀疏矩陣指的是非零元很少(t〈〈m*n)且分布沒有規(guī)律。廣義表簡(jiǎn)稱表，是由零個(gè)或多個(gè)原子或子表組成的