數據結構形考作業(yè)1

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

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

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

4、。選擇一項：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)鏈表的尾結點滿足（ ）（設頭指針為head，指針p指向尾結點）。選擇一項：A. p=NULLB. p-next=NULLC. p-next=headD. p= head題目14鏈表不具有的特點是（ ）。選擇一項：A. 不必事先估計存儲空間B. 可隨機訪問任一元素C. 插入刪除不需要移動元素D. 所需空間與線性表長度成正比題目15帶頭結點的鏈表為空的判斷條件是（ ）（設頭指針為head）。選擇一項：

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

6、來的順序不變，平均要移動（ ）個元素。選擇一項：B. 63C. 7D. 8題目19一個順序表第一個元素的存儲地址是90，每個元素的長度為2，則第6個元素的地址是（ ）。選擇一項：A. 98B. 102C. 100D. 106題目20在雙向循環(huán)鏈表中，在p所指的結點之后插入指針f所指的新結點，其操作步驟是（ ）。選擇一項：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在一個長度為n的順序存儲結構的線性表中，向第i(1in+1)個元素之前插入新元素時，需向后移動n-i+1個數據元素。題目22從長度為n的采用順序存儲結構的線性表中刪除第i(1in+1)個元素，需向前移動n-i個元素。題目23數據結構按結點間的關系，可分為4種邏輯結構：_、_、_、_。集合、線性結構、樹形結構、圖狀結構題目24數據的邏輯結構在計算機中的表示稱為_或_。存儲結構 物理結構題目25除了第1個和最后一個結

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

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

10、通過每個結點指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致，而是一種鏈式存儲結構，又稱為鏈表。三、問答題（第1小題7分，第2小題8分）題目36簡述數據的邏輯結構和存儲結構的區(qū)別與聯系，它們如何影響算法的設計與實現？若用結點表示某個數據元素，則結點與結點之間的邏輯關系就稱為數據的邏輯結構。數據在計算機中的存儲表示稱為數據的存儲結構?？梢?，數據的邏輯結構是反映數據之間的固有關系，而數據的存儲結構是數據在計算機中的存儲表示。盡管因采用的存儲結構不同，邏輯上相鄰的結點，其物理地址未必相同，但可通過結點的內部信息，找到其相鄰的結點，從而保留了邏輯結構的特點。采用存儲結構不同，對數據的操作在靈活

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

12、，存儲空間利用率低。四、程序填空題（每空1分，共15分）題目38下列是用尾插法建立帶頭結點的且有n個結點的單向鏈表的算法，請在空格內填上適當的語句。 NODE *create1(n) /* 對線性表(1,2,.,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下列是用頭插法建立帶頭結點的且有n個結點的單向鏈表的算法，請在

13、空格內填上適當的語句。 NODE *create2(n) /*對線性表(n,n-1,.,1),建立帶頭結點的線性鏈表 */ 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下列是在具有頭結點單向鏈表中刪除第i個結點的算法，請在空格內填上適當的語句。 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下列是在具有頭結點單向列表中在第i個結點之前插入新結點的算法