數(shù)據(jù)結(jié)構(gòu)形考作業(yè)1

1、-作者xxxx-日期xxxx數(shù)據(jù)結(jié)構(gòu)形考作業(yè)1【精品文檔】一、單項(xiàng)選擇題（每小題2分，共40分）題目1把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（ ）。選擇一項(xiàng)：A. 邏輯結(jié)構(gòu)B. 給相關(guān)變量分配存儲(chǔ)單元C. 物理結(jié)構(gòu)D. 算法的具體實(shí)現(xiàn)題目2下列說(shuō)法中，不正確的是（ ）。選擇一項(xiàng)：A. 數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成B. 數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成C. 數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位D. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位題目3一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（ ）。選擇一項(xiàng)：A. 數(shù)據(jù)類型B. 數(shù)據(jù)元素C. 數(shù)據(jù)結(jié)構(gòu)D. 數(shù)據(jù)項(xiàng)題目4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）。選擇一項(xiàng)

2、：A. 物理結(jié)構(gòu)B. 存儲(chǔ)結(jié)構(gòu)C. 邏輯結(jié)構(gòu)D. 物理和存儲(chǔ)結(jié)構(gòu)題目5下列的敘述中，不屬于算法特性的是（ ）。選擇一項(xiàng)：A. 輸入性B. 可行性C. 有窮性D. 可讀性題目6算法分析的目的是（ ）。選擇一項(xiàng)：A. 研究算法中的輸入和輸出的關(guān)系B. 分析算法的效率以求改進(jìn)C. 找出數(shù)據(jù)結(jié)構(gòu)的合理性D. 分析算法的易懂性和文檔性題目7算法指的是（ ）。選擇一項(xiàng)：A. 計(jì)算機(jī)程序B. 排序方法C. 解決問(wèn)題的計(jì)算方法D. 解決問(wèn)題的有限運(yùn)算序列題目8算法的時(shí)間復(fù)雜度與（ ）有關(guān)。選擇一項(xiàng)：A. 數(shù)據(jù)結(jié)構(gòu)B. 算法本身C. 計(jì)算機(jī)的操作系統(tǒng)D. 所使用的計(jì)算機(jī)題目9設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)

3、元素之前（也就是插入元素作為新表的第i個(gè)元素），插入一個(gè)元素，則移動(dòng)元素個(gè)數(shù)為（ ）。選擇一項(xiàng)：A. n-iB. iC. n-i-1D. n-i+1題目10設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（ ）。選擇一項(xiàng)：A. n-iB. n-i+1C. n-i-1D. i題目11在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語(yǔ)句（ ）。選擇一項(xiàng)：A. q-next=NULLB. p-next=q-nextC. p-next=qD. p=q-next題目12在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）

4、。選擇一項(xiàng)：A. s-next=p-next; p-next=s;B. p-next= s; s-next= p-nextC. p-next=s-next;D. p=s-next題目13非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（ ）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。選擇一項(xiàng)：A. p=NULLB. p-next=NULLC. p-next=headD. p= head題目14鏈表不具有的特點(diǎn)是（ ）。選擇一項(xiàng)：A. 不必事先估計(jì)存儲(chǔ)空間B. 可隨機(jī)訪問(wèn)任一元素C. 插入刪除不需要移動(dòng)元素D. 所需空間與線性表長(zhǎng)度成正比題目15帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）。選擇一項(xiàng)：

5、A. head-next=headB. head =NULLC. head-next=NULLD. head!=NULL題目16在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開(kāi)始從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（ ）。選擇一項(xiàng)：A. 25B. 19C. 20D. 21題目17有關(guān)線性表的正確說(shuō)法是（ ）。選擇一項(xiàng)：A. 線性表至少要求一個(gè)元素B. 表中的元素必須按由小到大或由大到下排序C. 除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼D. 每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼題目18向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原

6、來(lái)的順序不變，平均要移動(dòng)（ ）個(gè)元素。選擇一項(xiàng)：B. 63C. 7D. 8題目19一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為2，則第6個(gè)元素的地址是（ ）。選擇一項(xiàng)：A. 98B. 102C. 100D. 106題目20在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入指針f所指的新結(jié)點(diǎn)，其操作步驟是（ ）。選擇一項(xiàng)：A. f-prior=p; f-next=p-next; p-next=f;p-next-prior=f;B. p-next=f;f-prior=p;p-next-prior=f;f-next=p-next;C. p-next=f; p-next-prior=f;f-prior

7、=p;f-next=p-next;D. f-prior=p; f-next=p-next; p-next-prior=f; p-next=f;二、填空題（每小題2分，共30分）題目21在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，向第i(1in+1)個(gè)元素之前插入新元素時(shí)，需向后移動(dòng)n-i+1個(gè)數(shù)據(jù)元素。題目22從長(zhǎng)度為n的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第i(1in+1)個(gè)元素，需向前移動(dòng)n-i個(gè)元素。題目23數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4種邏輯結(jié)構(gòu)：_、_、_、_。集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)題目24數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為_(kāi)或_。存儲(chǔ)結(jié)構(gòu) 物理結(jié)構(gòu)題目25除了第1個(gè)和最后一個(gè)結(jié)

8、點(diǎn)外，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為非線性結(jié)構(gòu)。題目26數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為圖狀結(jié)構(gòu)結(jié)構(gòu)。題目27數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為樹(shù)形結(jié)構(gòu)結(jié)構(gòu)。題目28數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為線性結(jié)構(gòu)結(jié)構(gòu)。題目29要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為_(kāi)和_。n-1 0(n)題目30在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s-next=p-next;和p-next=s;的操作。題目31設(shè)有一個(gè)頭指針為head的單向

9、循環(huán)鏈表，p指向鏈表中的結(jié)點(diǎn)，若p-next=head，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。題目32在一個(gè)單向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。則可以用操作q-next=p-next;。題目33設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p-next= =NULL，通過(guò)操作p-next=head;，就可使該單向鏈表構(gòu)形成單向循環(huán)鏈表。題目34單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充，當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為頭結(jié)點(diǎn)的指針；當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí)，則把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為指向指向第一個(gè)結(jié)點(diǎn)的指針。題目35線性鏈表的邏輯關(guān)系是

10、通過(guò)每個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，又稱為鏈表。三、問(wèn)答題（第1小題7分，第2小題8分）題目36簡(jiǎn)述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計(jì)與實(shí)現(xiàn)？若用結(jié)點(diǎn)表示某個(gè)數(shù)據(jù)元素，則結(jié)點(diǎn)與結(jié)點(diǎn)之間的邏輯關(guān)系就稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)?？梢?jiàn)，數(shù)據(jù)的邏輯結(jié)構(gòu)是反映數(shù)據(jù)之間的固有關(guān)系，而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示。盡管因采用的存儲(chǔ)結(jié)構(gòu)不同，邏輯上相鄰的結(jié)點(diǎn)，其物理地址未必相同，但可通過(guò)結(jié)點(diǎn)的內(nèi)部信息，找到其相鄰的結(jié)點(diǎn)，從而保留了邏輯結(jié)構(gòu)的特點(diǎn)。采用存儲(chǔ)結(jié)構(gòu)不同，對(duì)數(shù)據(jù)的操作在靈活

11、性，算法復(fù)雜度等方面差別較大。題目37解釋順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，并比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。順序結(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：一般情況下，存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：（1）在做插入和刪除操作時(shí)，需移動(dòng)大量元素；（2）由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；（3）表的容量難以擴(kuò)充。鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。優(yōu)點(diǎn)：插入和 刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小

12、，存儲(chǔ)空間利用率低。四、程序填空題（每空1分，共15分）題目38下列是用尾插法建立帶頭結(jié)點(diǎn)的且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z(yǔ)句。 NODE *create1(n) /* 對(duì)線性表(1,2,.,n),建立帶頭結(jié)點(diǎn)的單向鏈表 */ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); head=p; q=p; p-next=NULL; for(i=1;idata=i; p-next=NULL; q-next=p; q=p; return(head); 題目39下列是用頭插法建立帶頭結(jié)點(diǎn)的且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)?/p>

13、空格內(nèi)填上適當(dāng)?shù)恼Z(yǔ)句。 NODE *create2(n) /*對(duì)線性表(n,n-1,.,1),建立帶頭結(jié)點(diǎn)的線性鏈表 */ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); head=p; p-next=NULL; q=p; for(i=1;idata=i; if(i=1) p-next=NULL; else p-next=q-next; q-next=p; return(head); 題目40下列是在具有頭結(jié)點(diǎn)單向鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z(yǔ)句。 int delete(NODE *head,int i) NODE *p,*q; int j; q=head; j=0; while(q!=NULL)&(jnext; j+; if(q=NULL) return(0); p=q-next q-next=p-next; free(p); return(1); 題目41下列是在具有頭結(jié)點(diǎn)單向列表中在第i個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)的算法