1、形考作業一題目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正確獲得2.00分中的2.00分A. 研究算法中的輸入和輸出的關系B. 分析算法的易懂性和文檔性C. 分析算法的效率以求改進 D. 找出數據結構的合理性題目7算法指的是（   ）。選擇一項：A. 排序方法B. 解決問題的計算方法C. 計算機程序D. 解決問題的有限運算序列 題目8算法的時間復

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

4、點是p所指結點的直接后繼，現要刪除q所指結點，可用語句（   ）。選擇一項：A. p->next=q->next B. p=q->nextC. q->next=NULLD. p->next=q題目12在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執行（   ）。選擇一項：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非空的單向循環鏈表的尾結點滿足（   ）（設頭指針為head，指針p指向尾結點）。選擇一項：A. p= headB. p=NULLC. p->next=head D. p->next=NULL題目14鏈表不具有的特點是（   ）。選擇一項：A. 可隨機訪問任一元素 B. 插入刪除不需要移動元素C. 不必事先估計存儲空間D. 所需空間與線性表長度成正比題目15帶頭結點的鏈表為空的判斷條件是（   ）（設頭指針為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有關線性表的正確說法是（   ）。選擇一項：A. 表中的元素必須按由小到大或由大到下排序B. 除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅和一個直接后繼 C. 線性表至少要求一個元素D. 每個元素都有一個直接前驅和一個直接后繼題目18向一個有1

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

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

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

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

12、表三、問答題（第1小題7分，第2小題8分）題目36簡述數據的邏輯結構和存儲結構的區別與聯系，它們如何影響算法的設計與實現？答：若用結點表示某個數據元素，則結點與結點之間的邏輯關系就稱為數據的邏輯結構。數據在計算機中的存儲表示稱為數據的存儲結構。可見，數據的邏輯結構是反映數據之間的固有關系，而數據的存儲結構是數據在計算機中的存儲表示。盡管因采用的存儲結構不同，邏輯上相鄰的結點，其物理地址未必相同，但可通過結點的內部信息，找到其相鄰的結點，從而保留了邏輯結構的特點。采用的存儲結構不同，對數據的操作在靈活性，算法復雜度等方面差別較大。題目37解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和

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

14、有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;i<=n;i+)         

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

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下列是在具有頭結點單向鏈表中刪除第i個結點的算法，請在空格內填上適當的語句。  int delete(NODE *head,int i) 

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

19、NULL)      return(0);    回答    回答;    free(p);    return(1);  題目41下列是在具有頭結點單向列表中在第i個結點之前插入新結點的算法，請在空格內填上適當的語句。  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);                                  形考任務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向順序棧中壓入新元素時，應當（   ）。選擇一項：A. 先存入元素，再移動棧頂指針B. 先移動棧頂指針，再存入元素 C. 先后次序無關緊要D. 同時進行題目4在一個棧頂指針為top的鏈棧中，將一個p指針所指的結點入棧，應執行（   ）。選擇一項

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的鏈棧中刪除一個結點時，用 x保存被刪結點的值，則執行（   ）。選擇一項：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判斷一個循環隊列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判斷棧滿（元素個數最多n個）的條件是（

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

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

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數組a經初始化char a =“English”;a7中存放的是（   ）。選擇一項：A. "h"B. 字符串的結束符 C. 變量hD. 字符h題目15設主串為“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. 兩串的長度相等，并且對應位置上的字符相同 B. 兩串的長度相等C. 兩串的長度相等，并且兩串包含的字符相同D. 兩串包含的字符相同題目18一維數組A采用順序存儲結構，每個元素占用6個字節，第6個元素的存儲地址為100，則該數組的首地址是（  

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

30、  ）。選擇一項：A. （10，8，7）B. （10，8，6） C. （7，10，8）D. （7，8，10）題目22對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結點，并給該     結點賦值a，則執行: 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的帶頭結點的單向鏈表為空的判定條件是（   ）為真。選擇一項：A. head=NULLB. head->next=NULLC. head->next!=NULL D. head->next!=NULL題目24設有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始），B數組共有55個元素,則該矩陣是（   ）階的對稱矩陣。選擇一項：A. 20B. 15C. 10 D. 5題目25數組a經初始化cha

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

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

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

35、后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。隊列是一種先進先出的線性表，隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。題目42設棧S和隊列Q的初始狀態為空，元素e1，e2，e3，e4，e5和e6依次通過S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應該是多少？出隊序列是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、棧，應是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簡述廣義表和線性表的區別和聯系。廣義表是線性表的的推廣，它也是n（n>0）個元素a1，a2，ai，an的有限序列，其中ai或者是原子或者是一個廣義表。所以，廣義表是一種遞歸數據結構，而線性表沒有這種特性，線性表可以看成廣義表的特殊情況，當ai都是原子時，廣義表退化成線性表。形考任

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

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

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

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

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

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

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

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

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

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

48、L值為270。（3）每個字符的哈夫曼編碼為：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01題目40請根據以下帶權有向圖G（1）給出從結點v1出發分別按深度優先搜索遍歷G和廣度優先搜索遍歷G所得的結點序列；（2）給出G的一個拓撲序列；（3）給出從結點v1到結點v8的最短路徑。（1）深度優先遍歷：v1，v2，v3，v8，v5，v7，v4，v6廣度優先遍歷：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分題干以下是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中

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

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

54、序存儲方式，且數據元素有序 C. 以鏈接存儲方式，且數據元素有序D. 以鏈接存儲方式題目2采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（   ）。選擇一項：A. (n-1)/2B. (n+1)/2 C. nD. n/2題目3有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數為（   ）。選擇一項：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有數據53,30,37,12,45,24,96，從空二叉樹開始逐個插入數據來形成二叉排序樹，若希望高度最小，應該選擇的序列是（   ）。選擇一項：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的比較次數是（ 

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

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

58、并排序B. 快速排序C. 插入排序 D. 堆排序題目13對數據元素序列（49，72，68，13，38，50，97，27）進行排序，前三趟排序結果時的結果依次為第一趟：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個元素的任意序列采用插入排序法進行排序，排序趟數為（   ）。選擇一項：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一組記錄的關鍵字序列為（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一組記錄的關鍵字序列為（25，48，16，35，79，82，23，40，36，72），其中，含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為（   ）。選擇一項：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個數據元素為（54，28，16，34，73，62，95，60，26，43），對該數列從小到大排序，經過一趟冒泡排序后的序列為（   ）。選擇一項：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一組記錄的關鍵字序列為（56，30，89，66，48，50，94，87，100），利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為（   ）。選擇一項：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如果要求一個線性表既能較快地查找，又能動態適應變化要求，可以采用（   ）查找方法。選擇一項：A. 散列B. 折半C. 分塊 D. 順序二、填空題（每小題1分，共16分）題目22在各種查找方法中，平均查找長度與結點個數n無關的查找方法是回答。正確答案是：哈希表查找法題目23關鍵字是記錄某個回答，用它可以識別、確定一個回答。答案：數據項的值、記錄題目24在一個查找表中，能夠唯一地確定一個記錄的關鍵字稱為回答。正確答案是：主關鍵字題目25平均查找長度是指為確定記錄在