【正文】 數(shù)據(jù)結(jié)構(gòu)（本）形成性考核作業(yè)冊使用說明本作業(yè)冊是中央廣播電視大學(xué)計(jì)算機(jī)科與技術(shù)專業(yè)（本科）數(shù)據(jù)結(jié)構(gòu)（本）課程形成性考核的依據(jù)，與《數(shù)據(jù)結(jié)構(gòu)（本科）》教材（李偉生主編，中央電大出版社出版）配套使用。數(shù)據(jù)結(jié)構(gòu)（本）課程是中央廣播電視大學(xué)計(jì)算機(jī)科學(xué)技術(shù)專業(yè)的一門統(tǒng)設(shè)必修、學(xué)位課程，4學(xué)分，共72學(xué)時(shí)。其中實(shí)驗(yàn)24學(xué)時(shí)，開設(shè)一學(xué)期。本課程的特點(diǎn)是綜合性、實(shí)踐性強(qiáng)，內(nèi)容抽象，在專業(yè)中具有承上啟下的作用。因此，在學(xué)習(xí)本課程時(shí)，要注意理論聯(lián)系實(shí)際，結(jié)合教學(xué)內(nèi)容進(jìn)行上機(jī)實(shí)踐，認(rèn)真完成作業(yè)和實(shí)驗(yàn)內(nèi)容。本課程的總成績按百分制記分，其中形成性考核所占的比例為30%，終結(jié)性考試占70％（閉卷，答題時(shí)限為90分鐘）。課程總成績達(dá)到60分及以上者為合格，可以獲得該課程的學(xué)分。本課程的學(xué)位課程學(xué)分為70分，即課程總成績達(dá)到70分及以上者有資格申請專業(yè)學(xué)位。本課程共設(shè)計(jì)了4次形考作業(yè)，每次形考作業(yè)均包括實(shí)驗(yàn)內(nèi)容，由各地電大根據(jù)學(xué)生對作業(yè)中各種題型練習(xí)和實(shí)驗(yàn)的完成情況進(jìn)行考核。對于實(shí)驗(yàn)內(nèi)容要求按實(shí)驗(yàn)要求認(rèn)真完成，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)1（本部分作業(yè)覆蓋教材第12章的內(nèi)容）一、單項(xiàng)選擇題1．在數(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)和外部機(jī)構(gòu)2．下列說法中，不正確的是（ ）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位 B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識單位 C．?dāng)?shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成 D．?dāng)?shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成3．一個(gè)存儲結(jié)點(diǎn)存儲一個(gè)（ ）。A．?dāng)?shù)據(jù)項(xiàng) B．?dāng)?shù)據(jù)元素 C．?dāng)?shù)據(jù)結(jié)構(gòu) D．?dāng)?shù)據(jù)類型4．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ ）。A．存儲結(jié)構(gòu) B．物理結(jié)構(gòu)C．邏輯結(jié)構(gòu) D．物理和存儲結(jié)構(gòu)5．下列的敘述中，不屬于算法特性的是（ ）。A．有窮性 B．輸入性 C．可行性 D．可讀性6．算法分析的目的是（ ）。 A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系 C．分析算法的效率以求改進(jìn) D．分析算法的易懂性和文檔性7．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中（ ）對象及其關(guān)系的科學(xué)。A．?dāng)?shù)值運(yùn)算 B．非數(shù)值運(yùn)算C．集合 D．非集合 8．算法的時(shí)間復(fù)雜度與（ ）有關(guān)。 A．所使用的計(jì)算機(jī) B．與計(jì)算機(jī)的操作系統(tǒng) C．與算法本身 D．與數(shù)據(jù)結(jié)構(gòu)9．設(shè)有一個(gè)長度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（ ）。 A．ni+1 B．ni C．ni1 D．i10．設(shè)有一個(gè)長度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（ ）。 A．ni+1 B．ni C．ni1 D．i11．在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語句（ ）。 A．p=qnext B．pnext=q C．pnext=q224。next D．qnext=NULL12．在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）。 A．pnext= s。 s224。next= p224。next B．pnext=s224。next。 C．p=snext D．snext=pnext。 pnext=s。13．非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（ ）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。 A.．Pnext= =NULL B．P= =NULL C．Pnext= =head D．P= = head 14．鏈表不具有的特點(diǎn)是（ ）。 A．可隨機(jī)訪問任一元素 B．插入刪除不需要移動(dòng)元素 C．不必事先估計(jì)存儲空間 D．所需空間與線性表長度成正比15．帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）?！　　　．head = =NULL　　　　B．headnext= =NULL 　　　　C．headnext= =head　　D．head!=NULL　　16．在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語句（ ）?！　　　．p=qnext　　　　B．pnext=q　　　　C．pnext=qnext　　　　D．qnext=NULL17．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ）。 A．r=fnext。 B．r=rnext。 C．f=fnext。 D．f=rnext。18．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（ ）。 A．fnext=s。 f=s。 B．rnext=s。r=s。 C．snext=r。r=s。 D．snext=f。f=s。，每個(gè)元素的長度為2，則第6個(gè)元素的地址是（ ）。A．98 B．100 C．102 D．10620．有關(guān)線性表的正確說法是（ ）。A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B．線性表至少要求一個(gè)元素C．表中的元素必須按由小到大或由大到下排序 D．除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼二、填空題1．在一個(gè)長度為n的順序存儲結(jié)構(gòu)的線性表中，向第i(1163。i163。n+1)個(gè)元素之前插入新元素時(shí)，需向后移動(dòng) 個(gè)數(shù)據(jù)元素。2．從長度為n的采用順序存儲結(jié)構(gòu)的線性表中刪除第i(1163。i163。n+1)個(gè)元素 ，需向前移動(dòng) 個(gè)元素。3．?dāng)?shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4種邏輯結(jié)構(gòu)： 、 、 、 。4．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為 或 。5．除了第1個(gè)和最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為 ，每個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為 。6．算法的5個(gè)重要特性是 、 、 、 、 。7．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_____ ___結(jié)構(gòu)。8．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為___ _____結(jié)構(gòu)。9．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為______ __結(jié)構(gòu)。10．要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為___ _____和 ____ ____ 。11．在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行___ _____和pnext=s。的操作。12．設(shè)有一個(gè)頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結(jié)點(diǎn)，若pnext= =____ ____，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。13．在一個(gè)單向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。則可以用操作_ _______。14．設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有pnext= =NULL,通過操作_____ ___,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。15．每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的線性表叫 。16．線性表具有 和 兩種存儲結(jié)構(gòu)。17．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的關(guān)系 無關(guān)，是獨(dú)立于計(jì)算機(jī)的。18．在雙向循環(huán)鏈表的每個(gè)結(jié)點(diǎn)中包含 指針域，其中next指向它的 ，prior指向它的 ，而頭結(jié)點(diǎn)的prior指向 ，尾結(jié)點(diǎn)的next指向 。19．單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充，當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為 ；當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí)，則把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為指向 。20．線性鏈表的邏輯關(guān)系時(shí)通過每個(gè)結(jié)點(diǎn)指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致，而是一種 存儲結(jié)構(gòu)，又稱為 。 三、問答題1．簡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計(jì)與實(shí)現(xiàn)？2．解釋順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)，并比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。3．什么情況下用順序表比鏈表好？4．頭指針、頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)（或稱首元結(jié)點(diǎn)）的區(qū)別是什么？5．解釋帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別。四、程序填空題1．下列是用尾插法建立帶頭結(jié)點(diǎn)的且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。NODE *create1(n)/* 對線性表(1,2,.....,n),建立帶頭結(jié)點(diǎn)的單向鏈表 */{ NODE *head,*p,*q。 int i。 p=(NODE *)malloc(sizeof(NODE))。 head=p。 q=p。 pnext=NULL。 for(i=1。i=n。i++) { p=(NODE *)malloc(sizeof(NODE))。 （1） 。 （2） 。 （3） 。 （4） 。 } return(head)。}2．下列是用頭插法建立帶頭結(jié)點(diǎn)的且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。NODE *create2(n)/*對線性表(n,n1,.....,1),建立帶頭結(jié)點(diǎn)的線性鏈表 */{ NODE *head,*p,*q。 int i。 p=(NODE *)malloc(sizeof(NODE))。 （1） 。 pnext=NULL。 （2） 。 for(i=1。i=n。i++) { p=(NODE *)malloc(sizeof(NODE))。 pdata=i。 if(i==1) （3） 。 else（4） 。（5） 。} return(head)。}3．下列是在具有頭結(jié)點(diǎn)單向列表中刪除第i個(gè)結(jié)點(diǎn)，請?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。int delete(NODE *head,int i){NODE *p,*q。 int j。 q=head。j=0。 while((q!=NULL)amp。amp。(ji1)) /*找到要?jiǎng)h除結(jié)點(diǎn)的直接前驅(qū)，并使q指向它*/ {q=qnext。j++。} if(q==NULL) return(0)。（1） 。 （2） 。 free(p)。 return(1)。}五、完成：實(shí)驗(yàn)1――線性表根據(jù)實(shí)驗(yàn)要求（見教材P201202）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)2（本部分作業(yè)覆蓋教材第35章的內(nèi)容）一、單項(xiàng)選擇題1．若讓元素1，2，3依次進(jìn)棧，則出棧順序不可