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

1、形考作業(yè)一題目1把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（   ）。選擇一項：A. 邏輯結(jié)構(gòu)B. 給相關(guān)變量分配存儲單元C. 算法的具體實現(xiàn)D. 物理結(jié)構(gòu) 題目2下列說法中，不正確的是（   ）。選擇一項：A. 數(shù)據(jù)可有若干個數(shù)據(jù)元素構(gòu)成B. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位C. 數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位D. 數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成 題目3一個存儲結(jié)點存儲一個（   ）。選擇一項：A. 數(shù)據(jù)結(jié)構(gòu)B. 數(shù)據(jù)類型C. 數(shù)據(jù)項D. 數(shù)據(jù)元素 題目4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是

2、數(shù)據(jù)的（   ）。選擇一項：A. 物理結(jié)構(gòu)B. 邏輯結(jié)構(gòu) C. 物理和存儲結(jié)構(gòu)D. 存儲結(jié)構(gòu)題目5下列的敘述中，不屬于算法特性的是（   ）。選擇一項：A. 有窮性B. 可行性C. 可讀性 D. 輸入性題目6正確獲得2.00分中的2.00分A. 研究算法中的輸入和輸出的關(guān)系B. 分析算法的易懂性和文檔性C. 分析算法的效率以求改進 D. 找出數(shù)據(jù)結(jié)構(gòu)的合理性題目7算法指的是（   ）。選擇一項：A. 排序方法B. 解決問題的計算方法C. 計算機程序D. 解決問題的有限運算序列 題目8算法的時間復(fù)

3、雜度與（   ）有關(guān)。選擇一項：A. 所使用的計算機B. 數(shù)據(jù)結(jié)構(gòu)C. 算法本身 D. 計算機的操作系統(tǒng)題目9設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（   ）。選擇一項：A. n-i+1 B. n-i-1C. n-iD. i題目10設(shè)有一個長度為n的順序表，要刪除第i個元素移動元素的個數(shù)為（   ）。選擇一項：A. n-i B. n-i-1C. n-i+1D. i題目11在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)

4、點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（   ）。選擇一項：A. p->next=q->next B. p=q->nextC. q->next=NULLD. p->next=q題目12在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行（   ）。選擇一項：A. p=s->nextB. p->next= s; s->next= p->nextC. p->next=s->next;D. s->next=p->next; p->next=s;&

5、#160;題目13非空的單向循環(huán)鏈表的尾結(jié)點滿足（   ）（設(shè)頭指針為head，指針p指向尾結(jié)點）。選擇一項：A. p= headB. p=NULLC. p->next=head D. p->next=NULL題目14鏈表不具有的特點是（   ）。選擇一項：A. 可隨機訪問任一元素 B. 插入刪除不需要移動元素C. 不必事先估計存儲空間D. 所需空間與線性表長度成正比題目15帶頭結(jié)點的鏈表為空的判斷條件是（   ）（設(shè)頭指針為head）。選擇一項：A. head->next=NULL B

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

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

8、xt->prior=f;B. p->next=f;f->prior=p;p->next->prior=f;f->next=p->next;C. f->prior=p; f->next=p->next; p->next->prior=f; p->next=f; D. p->next=f; p->next->prior=f;f->prior=p;f->next=p->next;二、填空題（每小題2分，共30分）題目21在一個長度為n的順序存儲結(jié)構(gòu)的線性表中，向第i(1

9、3;i£n+1)個元素之前插入新元素時，需向后移動回答個數(shù)據(jù)元素。題目22從長度為n的采用順序存儲結(jié)構(gòu)的線性表中刪除第i(1£i£n+1)個元素，需向前移動回答個元素。題目23數(shù)據(jù)結(jié)構(gòu)按結(jié)點間的關(guān)系，可分為4種邏輯結(jié)構(gòu)：_集合_、_線性結(jié)構(gòu)、_、_樹形結(jié)構(gòu)_、_圖狀結(jié)構(gòu)_。題目24數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示稱為_存儲結(jié)構(gòu)_或_物理結(jié)構(gòu)_。題目25除了第1個和最后一個結(jié)點外，其余結(jié)點有且只有一個前驅(qū)結(jié)點和后繼結(jié)點的數(shù)據(jù)結(jié)構(gòu)為回答，每個結(jié)點可有任意多個前驅(qū)和后繼結(jié)點數(shù)的結(jié)構(gòu)為回答。答案：線性結(jié)構(gòu)，非線性結(jié)構(gòu)題目26數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為回答結(jié)構(gòu)。

10、題目27數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為回答結(jié)構(gòu)。題目28數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為回答結(jié)構(gòu)。題目29要求在n個數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時間復(fù)雜度分別為_ n-1_和_ O(n)_。題目30在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時，應(yīng)執(zhí)行回答和p->next=s;的操作。題目31設(shè)有一個頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結(jié)點，若p->next=回答，則p所指結(jié)點為尾結(jié)點。題目32在一個單向鏈表中，要刪除p所指結(jié)點，已知q指向p所指結(jié)點的前驅(qū)結(jié)點。則可以用操作回答。正確答案是：q->n

11、ext=p->next;題目33設(shè)有一個頭指針為head的單向鏈表，p指向表中某一個結(jié)點，且有p->next= =NULL，通過操作回答，就可使該單向鏈表構(gòu)形成單向循環(huán)鏈表。正確答案是：p->next=head;題目34單向循環(huán)鏈表是單向鏈表的一種擴充，當單向鏈表帶有頭結(jié)點時，把單向鏈表中尾結(jié)點的指針域由空指針改為回答；當單向鏈表不帶頭結(jié)點時，則把單向鏈表中尾結(jié)點的指針域由空指針改為指向回答。答案：頭結(jié)點的指針、指向第一個結(jié)點的指針題目35線性鏈表的邏輯關(guān)系是通過每個結(jié)點指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致，而是一種回答存儲結(jié)構(gòu)，又稱為回答。答案：鏈式、鏈

12、表三、問答題（第1小題7分，第2小題8分）題目36簡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計與實現(xiàn)？答：若用結(jié)點表示某個數(shù)據(jù)元素，則結(jié)點與結(jié)點之間的邏輯關(guān)系就稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)?？梢姡瑪?shù)據(jù)的邏輯結(jié)構(gòu)是反映數(shù)據(jù)之間的固有關(guān)系，而數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計算機中的存儲表示。盡管因采用的存儲結(jié)構(gòu)不同，邏輯上相鄰的結(jié)點，其物理地址未必相同，但可通過結(jié)點的內(nèi)部信息，找到其相鄰的結(jié)點，從而保留了邏輯結(jié)構(gòu)的特點。采用的存儲結(jié)構(gòu)不同，對數(shù)據(jù)的操作在靈活性，算法復(fù)雜度等方面差別較大。題目37解釋順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的特點，并比較順序存儲結(jié)構(gòu)和

13、鏈式存儲結(jié)構(gòu)的優(yōu)缺點。答：順序結(jié)構(gòu)存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。優(yōu)點：一般情況下，存儲密度大，存儲空間利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結(jié)構(gòu)存儲時，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。優(yōu)點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。四、程序填空題（每空1分，共15分）題目38下列是用尾插法建立帶頭結(jié)點的且

14、有n個結(jié)點的單向鏈表的算法，請在空格內(nèi)填上適當?shù)恼Z句。  NODE *create1(n)  /* 對線性表(1,2,.,n),建立帶頭結(jié)點的單向鏈表 */      NODE *head,*p,*q;    int i;    p=(NODE *)malloc(sizeof(NODE);    head=p; q=p; p->next=NULL;    for(i=1;i<=n;i+)         

15、 p=(NODE *)malloc(sizeof(NODE);      回答;   回答;      回答;      回答;         return(head);  題目39下列是用頭插法建立帶頭結(jié)點的且有n個結(jié)點的單向鏈表的算法，請在空格內(nèi)填上適當?shù)恼Z句。  NODE *create2(n)  /*對線性表(n,n-1,.,1),建立帶頭結(jié)點的線性鏈表 */

16、0;     NODE *head,*p,*q;    int i;    p=(NODE *)malloc(sizeof(NODE);    回答;    p->next=NULL;    回答;    for(i=1;i<=n;i+)          p=(NODE *)malloc(sizeof(NODE);      p->dat

17、a=i;      if(i=1)          回答;      else        回答;      回答;        return(head);  題目40下列是在具有頭結(jié)點單向鏈表中刪除第i個結(jié)點的算法，請在空格內(nèi)填上適當?shù)恼Z句。  int delete(NODE *head,int i) 

18、;     NODE *p,*q;    int j;    q=head;    j=0;    while(q!=NULL)&&(j<i-1)        /*找到要刪除結(jié)點的直接前驅(qū)，并使q指向它*/          回答;      j+;        if(q=

19、NULL)      return(0);    回答    回答;    free(p);    return(1);  題目41下列是在具有頭結(jié)點單向列表中在第i個結(jié)點之前插入新結(jié)點的算法，請在空格內(nèi)填上適當?shù)恼Z句。  int insert(NODE *head,int x,int i)      NODE *q,*p;    int j;    q=head; 

20、   j=0;    while(q!=NULL)&&(j<i-1)     q=q->next;j+;      if(q=NULL) return(0);                          p=回答;    p->data=x;    回答正確正確答案是：p->next

21、=q->next獲得1.00分中的1.00分;    回答;    return(1);                                  形考任務(wù)2題目1若讓元素1，2，3依次進棧，則出棧順序不可

22、能為（   ）。選擇一項：A. 2，1，3B. 3，1，2 C. 3，2，1題目2一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（   ）。選擇一項：A. 3，2，4，1B. 1，2，3，4 C. 4，3，2，1D. 1，4，3，2題目3向順序棧中壓入新元素時，應(yīng)當（   ）。選擇一項：A. 先存入元素，再移動棧頂指針B. 先移動棧頂指針，再存入元素 C. 先后次序無關(guān)緊要D. 同時進行題目4在一個棧頂指針為top的鏈棧中，將一個p指針所指的結(jié)點入棧，應(yīng)執(zhí)行（   ）。選擇一項

23、：A. p->next=top;top=p; B. top->next=p;C. p->next=top->next;top=top->next;D. p->next=top->next;top->next=p;題目5在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用 x保存被刪結(jié)點的值，則執(zhí)行（   ）。選擇一項：A. x=top->data;top=top->next;B. x=top->data; C. top=top->next;x=top->data;D. x=top;

24、top=top->next;題目6判斷一個順序隊列（最多元素為m）為空的條件是（   ）。選擇一項：A. rear=m-1B. front=rear+1C. front=rear 題目7判斷一個循環(huán)隊列Q（最多元素為m）為滿的條件是（   ）。選擇一項：A. Q->rear!= (Q->front+1)%m B. Q->front=Q->rearC. Q->front=(Q->rear+1)%mD. Q->front=Q->rear +1題目8判斷棧滿（元素個數(shù)最多n個）的條件是（

25、   ）。選擇一項：A. top=0B. top!=0C. top=-1D. top=n-1 題目9設(shè)有一個20階的對稱矩陣A（第一個元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始）， 則矩陣元素a6,2在一維數(shù)組B中的下標是（   ）。選擇一項：A. 17 B. 23C. 21D. 28題目10在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（  

26、）結(jié)構(gòu)。選擇一項：A. 隊列 B. 先性表C. 數(shù)組D. 堆棧題目11一個遞歸算法必須包括（   ）。選擇一項：A. 遞歸部分B. 迭代部分C. 終止條件和迭代部分D. 終止條件和遞歸部分 題目12在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為（   ）。選擇一項：A. f=r->next;B. r=r->next;C. r=f->next;D. f=f->next; 題目13在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的運算為（   ）。選

27、擇一項：A. s->next=r;r=s;B. r->next=s;r=s; C. s->next=f;f=s;D. f->next=s;f=s;題目14數(shù)組a經(jīng)初始化char a =“English”;a7中存放的是（   ）。選擇一項：A. "h"B. 字符串的結(jié)束符 C. 變量hD. 字符h題目15設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（   ）。選擇一項：A. BCdB. Bcd C. AbcD. ABC題目16字符串 a1="A

28、EIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（   ）。選擇一項：A. a3B. a1 C. a4D. a2題目17兩個字符串相等的條件是（   ）。選擇一項：A. 兩串的長度相等，并且對應(yīng)位置上的字符相同 B. 兩串的長度相等C. 兩串的長度相等，并且兩串包含的字符相同D. 兩串包含的字符相同題目18一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用6個字節(jié)，第6個元素的存儲地址為100，則該數(shù)組的首地址是（  

29、 ）。選擇一項：A. 64B. 90C. 28D. 70 題目19一個非空廣義表的表頭（   ）。選擇一項：A. 可以是子表或原子B. 只能是原子 C. 不可能是原子D. 只能是子表題目20對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個元素，矩陣A共有（   ）個零元素。選擇一項：A. 8B. 10C. 72D. 74 題目21對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A共有73個零元素，A的右下角元素為6，其相應(yīng)的三元組表中的第7個元素是（ 

30、  ）。選擇一項：A. （10，8，7）B. （10，8，6） C. （7，10，8）D. （7，8，10）題目22對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結(jié)點，并給該     結(jié)點賦值a，則執(zhí)行: p=(struct node *)malloc(sizeof(struct node);p->data=a;和（   ）。選擇一項：A. p->next=top;p=top;B. top->next=p;p=top;C. p->nex=top;top=p; D.

31、 top=top->next;pe=top;題目23頭指針為head的帶頭結(jié)點的單向鏈表為空的判定條件是（   ）為真。選擇一項：A. head=NULLB. head->next=NULLC. head->next!=NULL D. head->next!=NULL題目24設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），B數(shù)組共有55個元素,則該矩陣是（   ）階的對稱矩陣。選擇一項：A. 20B. 15C. 10 D. 5題目25數(shù)組a經(jīng)初始化cha

32、r a =“English”;a1中存放的是（   ）。選擇一項：A. "n"B. 字符n C. "E"D. 字符E二、填空題（每小題2分，共30分）題目26循環(huán)隊列隊頭指針在隊尾指針回答位置，隊列是“滿”狀態(tài)。題目27循環(huán)隊列的引入，目的是為了克服回答。題目28判斷一個循環(huán)隊列LU（最多元素為m）為空的條件是回答。題目29題干向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時，可執(zhí)行回答s->next=h;和h=s;操作。（結(jié)點的指針域為next）題目30從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，可

33、執(zhí)行x=h-題目31在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的操作為回答和r=s; r->next=s;（結(jié)點的指針域為next）題目32在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的操作為回答f=f->next;。 （結(jié)點的指針域為next）題目33串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是回答。題目34空串的長度是回答；空格串的長度是回答。題目35設(shè)廣義表L=(),()，則表頭是_，表尾是_，L的長度是_。則表頭是（），表尾是（），L的長度是2題目36廣義表A（a，b，c），（d，e，f）的表尾為回答(d,e,f)。題目37設(shè)有n

34、階對稱矩陣A，用數(shù)組s進行壓縮存儲，當ij時，A的數(shù)組元素aij相應(yīng)于數(shù)組s的數(shù)組元素的下標為回答。（數(shù)組元素的下標從1開始）題目38對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的_、_和_三項信息。答案：行下標、列下標和非零元素值題目39循環(huán)隊列用a0，a7的一維數(shù)組存放隊列元素，（采用少用一個元素的模式)，設(shè)front和rear分別為隊頭和隊尾指針，且front和rear 的值分別為2和7，當前隊列中的元素個數(shù)是回答5。題目40循環(huán)隊列的引入，目的是為了克服回答。三、問答題（每小題5分，共20分）題目41完成滿分5.00題干棧、隊列和線性表的區(qū)別是什么？答：棧是一種先進

35、后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。隊列是一種先進先出的線性表，隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。題目42設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該是多少？出隊序列是e2,e4,e3,e6,e5,e1的過程：（1）e1入棧（棧底到棧頂元素是e1）（2）e2入棧（棧底到棧頂元素是e1，e2）（3）e2出棧（棧底到棧

36、頂元素是e1）（4）e3入棧（棧底到棧頂元素是e1，e3）（5）e4入棧（棧底到棧頂元素是e1，e3，e4）（6）e4出棧（棧底到棧頂元素是e1，e3）（7）e3出棧（棧底到棧頂元素是e1）（8）e5入棧（棧底到棧頂元素是e1，e5）（9）e6入棧（棧底到棧頂元素是e1，e5，e6）（10）e6出棧（棧底到棧頂元素是e1，e5）（11）e5出棧（棧底到棧頂元素是e1）（12）e1出棧（棧底到棧頂元素是空）棧中最多時有3個元素，所以棧S的容量至少是3。題目43有5個元素，其入棧次序為：A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個？從題中可知，要使C第一個且D第二個出

37、棧，應(yīng)是A入棧，B入棧，C入棧，C出棧，D入棧。之后可以有以下幾種情況：（1）B出棧，A出棧，E入棧，E出棧，輸出序列為：CDBAE。（2）B出棧，E入棧，E出棧，A 出棧，輸出序列為CDBEA。（3）E入棧，E出棧，B出棧，A出棧，輸出序列為CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA題目44簡述廣義表和線性表的區(qū)別和聯(lián)系。廣義表是線性表的的推廣，它也是n（n>0）個元素a1，a2，ai，an的有限序列，其中ai或者是原子或者是一個廣義表。所以，廣義表是一種遞歸數(shù)據(jù)結(jié)構(gòu)，而線性表沒有這種特性，線性表可以看成廣義表的特殊情況，當ai都是原子時，廣義表退化成線性表。形考任

38、務(wù)三一、單項選擇題（每小題2分，共32分）題目1假定一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（   ）。選擇一項：A. 17B. 16 C. 15D. 47題目2二叉樹第k層上最多有（   ）個結(jié)點。選擇一項：A. 2k-1 B. 2k-1C. 2k-1D. 2k題目3設(shè)某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（   ）。選擇一項：A. abedcB. abdecC. debacD. debca 題目4將含有150個結(jié)點的完全二叉樹從根這

39、一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為69的結(jié)點的雙親結(jié)點的編號為（   ）。選擇一項：A. 35B. 33C. 34 D. 36題目5如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（   ）。選擇一項：A. 平衡二叉樹B. 完全二叉樹C. 二叉樹D. 哈夫曼樹 題目6在一棵度為3的樹中，度為3的結(jié)點個數(shù)為2，度為2的結(jié)點個數(shù)為1，則度為0的結(jié)點個數(shù)為（   ）。選擇一項：A. 5B. 4C. 7D. 6 題目7在一棵度具有5層的滿二叉樹中

40、結(jié)點總數(shù)為（   ）。選擇一項：A. 31 B. 32C. 16D. 33題目8利用n個值作為葉結(jié)點的權(quán)生成的哈夫曼樹中共包含有（   ）個結(jié)點。選擇一項：A. n+1B. 2*nC. nD. 2*n-1 題目9利用3、6、8、12這四個值作為葉子結(jié)點的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子結(jié)點中的最長帶權(quán)路徑長度為（   ）。選擇一項：A. 16B. 30C. 12D. 18 題目10在一棵樹中，（   ）沒有前驅(qū)結(jié)點。選擇一項：A. 葉結(jié)點B. 空結(jié)點C. 樹根結(jié)點 D.

41、分支結(jié)點題目11設(shè)一棵有n個葉結(jié)點的二叉樹，除葉結(jié)點外每個結(jié)點度數(shù)都為2，則該樹共有（   ）個結(jié)點。選擇一項：A. 2n-1 B. 2n+2C. 2n+1D. 2n題目12在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（   ）倍。選擇一項：A. 1B. 1/2C. 2 D. 4題目13鄰接表是圖的一種（   ）。選擇一項：A. 索引存儲結(jié)構(gòu)B. 順序存儲結(jié)構(gòu)C. 散列存儲結(jié)構(gòu)D. 鏈式存儲結(jié)構(gòu) 題目14如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是（ 

42、60; ）。選擇一項：A. 一棵樹B. 有回路C. 完全圖D. 連通圖 題目15圖的深度優(yōu)先遍歷算法類似于二叉樹的（   ）遍歷。選擇一項：A. 先序 B. 層次C. 中序D. 后序題目16已知下圖所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（   ）。選擇一項：A. V1V2V4V5V8V3V6V7 B. V1V2V4V8V5V3V6V7 C. V1V2V4V8V3V5V6V7D. V1V3V6V7V2V4V5V8二、填空題 （每小題1分，共20分）題目17結(jié)點的度是指結(jié)點

43、所擁有的回答。正確答案是：子樹樹木或后繼結(jié)點數(shù)題目18樹的度是指回答。正確答案是：樹中所有結(jié)點的度的最大值題目19度大于0的結(jié)點稱作_或_。分支結(jié)點、非終端結(jié)點題目20度等于0的結(jié)點稱作_或_。葉子結(jié)點、終端結(jié)點題目21在一棵樹中，每個結(jié)點的_或者說每個結(jié)點的_稱為該結(jié)點的_，簡稱為孩子。子樹的根、后繼結(jié)點、孩子結(jié)點題目22從根結(jié)點到該結(jié)點所經(jīng)分支上的所有結(jié)點稱為該結(jié)點的回答。正確答案是：祖先題目23樹的深度或高度是指回答。正確答案是：樹中結(jié)點的最大層數(shù)題目24具有n個結(jié)點的完全二叉樹的深度是_。題目25先序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，訪問二叉樹的回答

44、；先序遍歷二叉樹的回答，先序遍歷二叉樹的回答。根結(jié)點、左子樹、右子樹題目26中序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，中序遍歷二叉樹的回答；訪問而叉樹的回答，中序遍歷二叉樹的回答。左子樹、根結(jié)點、右子樹題目27后序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，后序遍歷二叉樹的回答；后序遍歷二叉樹的回答，訪問而叉樹的回答。左子樹、右子樹、根結(jié)點題目28將樹中結(jié)點賦上一個有著某種意義的實數(shù)，稱此實數(shù)為該結(jié)點的回答。正確答案是：權(quán)題目29樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的回答。正確答案是：帶權(quán)路徑長度之和題目30哈夫曼樹又稱為回答，它是n個帶

45、權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL回答。答案：最優(yōu)二叉樹，最小的二叉樹題目31若以4，5，6，7，8作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是回答。正確答案是：69題目32具有m個葉子結(jié)點的哈夫曼樹共有回答結(jié)點。正確答案是：2m-1題目33圖的遍歷是從圖的某一頂點出發(fā)，按照一定的搜索方法對圖中回答各做回答訪問的過程。答案：所有頂點; 一次題目34圖的深度優(yōu)先搜索遍歷類似于樹的回答遍歷。正確答案是：先序題目35圖的廣度優(yōu)先搜索類似于樹的回答遍歷。正確答案是：按層次題目36圖常用的兩種存儲結(jié)構(gòu)是_和_。鄰接矩陣、鄰接表三、綜合題（每小題8分，共40分）題目37寫出如下圖所示的二

46、叉樹的先序、中序和后序遍歷序列。答：二叉樹的定義是遞歸的，所以，一棵二叉樹可看作由根結(jié)點，左子樹和右子樹這三個基本部分組成，即依次遍歷整個二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續(xù)分為根結(jié)點、左子樹和右子樹三個部分，這樣劃分一直進行到樹葉結(jié)點。（1）先序為“根左右”，先序序列為：fdbacegihl（2）中序為“左根右”，中序序列為：abcdefghij（3）后序為“左右根”，后序序列為：acbedhjigf題目38已知某二叉樹的先序遍歷結(jié)果是：A，B，D，G，C，E，H，L，I，K，M，F(xiàn)和J，它的中序遍歷結(jié)果是：G，D，B，A，L，H，E，K，I，M，C，F(xiàn)和J，請畫出這棵二叉樹，

47、并寫出該二叉樹后續(xù)遍歷的結(jié)果。（1）二叉樹圖形表示如下：           （2）該二叉樹后序遍歷的結(jié)果是：G、D、B、L、H、K、M、I、E、J、F、C和A。題目39假設(shè)通信用的報文由9個字母A、B、C、D、E、F、G、H和I組成，它們出現(xiàn)的頻率分別是：10、20、5、15、8、2、3、7和30。請請用這9個字母出現(xiàn)的頻率作為權(quán)值求：（1）設(shè)計一棵哈夫曼樹；（2）計算其帶權(quán)路徑長度WPL；（3）寫出每個字符的哈夫曼編碼。1）哈夫曼樹如圖B-4所示。 圖B-4（2）其帶權(quán)路徑長度WP

48、L值為270。（3）每個字符的哈夫曼編碼為：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01題目40請根據(jù)以下帶權(quán)有向圖G（1）給出從結(jié)點v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié)點序列；（2）給出G的一個拓撲序列；（3）給出從結(jié)點v1到結(jié)點v8的最短路徑。（1）深度優(yōu)先遍歷：v1，v2，v3，v8，v5，v7，v4，v6廣度優(yōu)先遍歷：v1，v2，v4，v6，v3，v5，v7，v8（2）G的拓撲序列為：v1，v2，v4，v6，v5，v5，v3，v5，v7，v8（3）最短路徑為：v1，v2，v5

49、，v7，v8題目41已知無向圖G描述如下：G=（V，E）V=V1，V2，V3，V4，V5E=（V1，V2），（V1，V4），（V2，V4），（V3，V4），（V2，V5），（V3，V4），（V3，V5）（1）畫出G的圖示；（2）然后給出G的鄰接矩陣和鄰接表；（3）寫出每個頂點的度。g1的圖示和圖g1的鄰接表如下圖所示。                       &#

50、160;            圖G                              圖G的鄰接矩陣如下圖所示：     

51、0;       圖G的鄰接矩陣                     圖G的鄰接表 V1、V2、V3、V4、V5的度分別為：2，3，2，3，2   四、程序填空題（每空2分，共8分）題目42部分正確獲得4.00分中的2.00分題干以下是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中

52、左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。void Inorder (struct BTreeNode *BT)  if(BT!=NULL)    回答;    回答;    Inorder(BT->right); 答案：（1）Inorder(BT->left)（2）printf("%c",BT->data)題目43以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和rig

53、ht，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。void Inorder (struct BTreeNode *BT)  if(BT!=NULL)    回答;    Inorder(BT->right);    回答;（1）Inorder(BT->left)（2）printf("%c",BT->data)形考任務(wù)四一、單項選擇題（每小題2分，共42分）題目1對線性表進行二分查找時，要求線性表必須（   ）。選擇一項：A. 以順序存儲方式B. 以順

54、序存儲方式，且數(shù)據(jù)元素有序 C. 以鏈接存儲方式，且數(shù)據(jù)元素有序D. 以鏈接存儲方式題目2采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（   ）。選擇一項：A. (n-1)/2B. (n+1)/2 C. nD. n/2題目3有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（   ）。選擇一項：A. 29/9B. 26/10C. 31/10D. 29/10 題目4已知一個有序表為11,22,33,44,55,66,77,88,99，則順序查找元素55需要比較（

55、60;  ）次。選擇一項：A. 5 B. 6C. 4D. 3題目5有數(shù)據(jù)53,30,37,12,45,24,96，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是（   ）。選擇一項：A. 12,24,30,37,45,53,96B. 30,24,12,37,45,96,53C. 37,24,12,30,53,45,96 D. 45,24,53,12,37,96,30題目6 對于順序存儲的有序表5,12,20,26,37,42,46,50,64，若采用折半查找，則查找元素26的比較次數(shù)是（ 

56、60; ）。選擇一項：A. 6B. 4 C. 5D. 3題目7在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無關(guān)的是（   ）。選擇一項：A. 冒泡排序B. 直接插入排序C. 希爾排序D. 直接選擇排序 題目8從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（   ）。選擇一項：A. 插入排序 B. 歸并排序C. 選擇排序D. 交換排序題目9依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（   ）。選擇一項：A. 選擇排序B. 插入排

57、序C. 歸并排序 D. 交換排序題目10當兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（   ）。選擇一項：A. 選擇排序B. 歸并排序C. 插入排序D. 交換排序 題目11每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準記錄的關(guān)鍵字，這種排序稱為（   ）。選擇一項：A. 堆排序B. 插入排序C. 快速排序 D. 歸并排序題目12在待排序元素基本有序的情況下，效率最高的排序方法是（   ）。選擇一項：A. 歸

58、并排序B. 快速排序C. 插入排序 D. 堆排序題目13對數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進行排序，前三趟排序結(jié)果時的結(jié)果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。該排序采用的方法是（   ）。選擇一項：A. 選擇排序法B. 冒泡排序法C. 插入排序法 D. 堆積排序法題目14對具有n個元素的任意序列采用插入排序法進行排序，排序趟數(shù)為（   ）。選擇一項：A. n-1

59、0;B. log2nC. nD. n+1題目15對序列（49，38，65，97，76，13，47，50）采用直接插入排序法進行排序，要把第七個元素47插入到已排序中，為尋找插入的合適位置需要進行（   ）次元素間的比較。選擇一項：A. 4B. 6C. 5 D. 3反題目16排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（   ）排序。選擇一項：A. 插入B. 快速C. 選擇 D. 歸并題目17一組記錄的關(guān)鍵字序列為（40，80，65，100，14，30，55，50），利用堆排序的方法建立的初

60、始小根堆為（   ）。選擇一項：A. 40，14，30，50，80，65，55，100B. 40，80，65，50，14，30，55，100C. 14，40，30，50，80，65，55，100 D. 40，80，30，50，14，65，55，100題目18一組記錄的關(guān)鍵字序列為（25，48，16，35，79，82，23，40，36，72），其中，含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結(jié)果為（   ）。選擇一項：A. 16，25，35，48，79，82，23，36，40，72B. 16，25，35，48，79，23，

61、36，40，82，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，23，40，79，82，36，72 題目19已知10個數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（   ）。選擇一項：A. 16，28，34，54，73，62，60，26，43，95B. 28，16，34，54，62，60，73，26，43，95C. 28，16，34，54，62，73，60，26，43，95 D. 16，28，34，54，62，60，73，26

62、，43，95題目20一組記錄的關(guān)鍵字序列為（56，30，89，66，48，50，94，87，100），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（   ）。選擇一項：A. 48，30，50，56，66，89，94，87，100B. 30，50，48，56，66，89，94，100，87C. 50，30，48，66，56，89，94，87，100D. 50，30，48，56，66，89，94，87，100 題目21如果要求一個線性表既能較快地查找，又能動態(tài)適應(yīng)變化要求，可以采用（   ）查找方法。選擇一項：A. 散列B. 折半C. 分塊 D. 順序二、填空題（每小題1分，共16分）題目22在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是回答。正確答案是：哈希表查找法題目23關(guān)鍵字是記錄某個回答，用它可以識別、確定一個回答。答案：數(shù)據(jù)項的值、記錄題目24在一個查找表中，能夠唯一地確定一個記錄的關(guān)鍵字稱為回答。正確答案是：主關(guān)鍵字題目25平均查找長度是指為確定記錄在