電大數(shù)據(jù)結(jié)構(gòu)本形成性考核冊作業(yè)1-4原題帶答案

1、1數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)作業(yè)1（本部分作業(yè)覆蓋教材第（本部分作業(yè)覆蓋教材第12章的內(nèi)容）章的內(nèi)容）一、單項(xiàng)選擇題一、單項(xiàng)選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）。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下列說法中，不正確的是（D）。A數(shù)據(jù)元素是數(shù)據(jù)的基本單位B數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位C數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成D數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)

2、成3一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（B）。A數(shù)據(jù)項(xiàng)B數(shù)據(jù)元素C數(shù)據(jù)結(jié)構(gòu)D數(shù)據(jù)類型4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（C）。A存儲(chǔ)結(jié)構(gòu)B物理結(jié)構(gòu)C邏輯結(jié)構(gòu)D物理和存儲(chǔ)結(jié)構(gòu)5下列的敘述中，不屬于算法特性的是（D）。A有窮性B輸入性C可行性D可讀性6算法分析的目的是（C）。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)D分析算法的易懂性和文檔性7數(shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中（B）對(duì)象及其關(guān)系的科學(xué)。A數(shù)值運(yùn)算B非數(shù)

3、值運(yùn)算C集合D非集合8算法的時(shí)間復(fù)雜度與（C）有關(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）。Ani1BniCni1Di10設(shè)有一個(gè)長度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（B）。Ani1BniCni1Di11在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h

4、除q所指結(jié)點(diǎn)，可用語句（C）。Ap=qnextBpnext=qCpnext=q?nextDqnext=NULL12在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（D）。Apnext=ss?next=p?nextBpnext=s?nextCp=snextDsnext=pnextpnext=s13非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（C）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。A.Pnext==NULLBP==NULLCPnext=

5、=headDP==head14鏈表不具有的特點(diǎn)是（A）。A可隨機(jī)訪問任一元素B插入刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性表長度成正比15帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（B）（設(shè)頭指針為head）。Ahead==NULLBheadnext==NULLCheadnext==headDhead!=NULL16在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語句（C

6、）。Ap=qnextBpnext=qCpnext=qnextDqnext=NULL17在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（C）。Ar=fnextBr=rnextCf=fnextDf=rnext18在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（B）。Afnext=sf=sBrnext=sr=sCsnext=rr=sDsnext=ff=s19.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，

7、每個(gè)元素的長度為2，則第6個(gè)元素的地址是（B）。A98B100C102D10620有關(guān)線性表的正確說法是（D）。A每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B線性表至少要求一個(gè)元素C表中的元素必須按由小到大或由大到下排序D除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼二、填空題二、填空題1在一個(gè)長度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，向第i(1?i?n1)個(gè)元素之前插入新元素時(shí)，需向后移動(dòng)ni1個(gè)數(shù)據(jù)元素。2從長度為n

8、的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第i(1?i?n1)個(gè)元素，需向前移動(dòng)ni個(gè)元素。3數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4種邏輯結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)。4數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為物理結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)。5除了第1個(gè)和最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的3內(nèi)填上適當(dāng)?shù)恼Z句。NODEcreate2(n)對(duì)線性表(nn1.....1)建立帶頭結(jié)點(diǎn)的線性鏈表NODEheadpqintip=(NODE)mal

9、loc(sizeof(NODE))（1）head=ppnext=NULL（2）q=pf(i=1idata=iif(i==1)（3）pnext=NULLelse（4）pnext=qnext（5）qnext=preturn(head)3下列是在具有頭結(jié)點(diǎn)單向列表中刪除第i個(gè)結(jié)點(diǎn)，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z句。int(NODEheadinti)NODEpqintjq=headj=0while((q!=NULL)jif(q==NULL)return

10、(0)（1）p=qnext（2）qnext=pnextfree(p)return(1)五、完成：實(shí)驗(yàn)五、完成：實(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è)數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)2（本部分作業(yè)覆蓋教材第（本部分作業(yè)覆蓋教材第35章的內(nèi)容）章的內(nèi)容）一、單項(xiàng)選擇題一、單項(xiàng)選擇題1若讓元素1，2，3依次進(jìn)棧，則出棧順序不可能為（C）。A3，2，1B2，1，3C3，1，2D

11、1，3，22一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（B）。A4，3，2，1B1，2，3，4C1，4，3，2D3，2，4，13向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（A）。A先移動(dòng)棧頂指針，再存入元素B先存入元素，再移動(dòng)棧頂指針C先后次序無關(guān)緊要D同時(shí)進(jìn)行4在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（C）。Atopnext=pBpnext=topnexttopnext=pCpnext=toptop=pDpne

12、xt=topnexttop=topnext5在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（B）。Ax=toptop=topnextBx=topdataCtop=topnextx=topdataDx=topdatatop=topnext6一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（A）。A棧B隊(duì)列C堆?；蜿?duì)列D數(shù)組7表達(dá)式a(bc)d的后綴表達(dá)式是（B）。AabcdBabcdCabcdDabcd8判

13、斷一個(gè)順序隊(duì)列sq（最多元素為m0）為空的條件是（C）。Asqrearsqfront==m0Bsqrearsqfront1==m0Csqfront==sqrearDsqfront==sqrear19判斷一個(gè)循環(huán)隊(duì)列Q（最多元素為m0）為空的條件是（A）。AQfront==QrearBQfront!=QrearCQfront==(Qrear1)%m0DQfront!=(Qrear1)%m010判斷棧S滿（元素個(gè)數(shù)最多n個(gè)）的條件是（C）。

14、Astop==0Bstop!=0Cstop==n1Dstop!=n111一個(gè)隊(duì)列的入隊(duì)順序是abcd，則離隊(duì)的順序是（B）。AadcbBabcdCdcbaDcbda12如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（C）。A必須判斷棧是否滿B判斷棧元素類型C必須判斷棧是否空D對(duì)棧不作任何判斷13在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)