數(shù)據(jù)結構(本)形考作業(yè)答案

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

2、述中，不屬于算法特性的是（ ）。 選擇一項：a. 有窮性b. 可行性c. 可讀性d. 輸入性題目6正確獲得 2.00 分中的 2.00 分a. 研究算法中的輸入和輸出的關系 b. 分析算法的易懂性和文檔性c. 分析算法的效率以求改進d. 找出數(shù)據(jù)結構的合理性題目7算法指的是（ ）。 選擇一項：a. 排序方法b. 解決問題的計算方法c. 計算機程序d. 解決問題的有限運算序列題目8算法的時間復雜度與（ ）有關。 選擇一項：a. 所使用的計算機b. 數(shù)據(jù)結構c. 算法本身d. 計算機的操作系統(tǒng)題目9設有一個長度為 n 的順序表，要在第 i 個元素之前（也就是插入元素作為新表的第 i 個元 素），插

3、入一個元素，則移動元素個數(shù)為（ ）。選擇一項：a. n-i+1b. n-i-1c. n-id. i題目10設有一個長度為 n 的順序表，要刪除第 i 個元素移動元素的個數(shù)為（ ）。 選擇一項：a. n-ib. n-i-1c. n-i+1d. i題目11在一個單鏈表中，p、q 分別指向表中兩個相鄰的結點，且 q 所指結點是 p 所指結點的直接 后繼，現(xiàn)要刪除 q 所指結點，可用語句（ ）。選擇一項：a. p-next=q-nextb. p=q-nextc. q-next=nulld. p-next=q題目12在一個單鏈表中 p 所指結點之后插入一個 s 所指的結點時，可執(zhí)行（ ）。 選擇一項：a

4、. p=s-nextb. p-next= s; s-next= p-nextc. p-next=s-next;d. s-next=p-next; p-next=s;題目13非空的單向循環(huán)鏈表的尾結點滿足（ ）（設頭指針為 head，指針 p 指向尾結點）。 選擇一項：a. p= headb. p=nullc. p-next=headd. p-next=null題目14鏈表不具有的特點是（ ）。 選擇一項：a. 可隨機訪問任一元素b. 插入刪除不需要移動元素c. 不必事先估計存儲空間d. 所需空間與線性表長度成正比題目15帶頭結點的鏈表為空的判斷條件是（ ）（設頭指針為 head）。 選擇一項：

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

6、入一個新元素，并保持原來的順序不變，平均要移動 （ ）個元素。選擇一項：a. 8b. 7c. 63d. 63.5題目19一個順序表第一個元素的存儲地址是 90，每個元素的長度為 2，則第 6 個元素的地址是 （ ）。選擇一項：a. 102b. 98c. 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. f-p

7、rior=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(1in+1)個元素之前插入新元素時，需向后移動回答 22題目n-i+1個數(shù)據(jù)元素。從長度為 n 的采用順序存儲結構的線性表中刪除第 i(1in+1)個元素，需向前移動回答n-i個元素。題目23數(shù)據(jù)結構按結點間的關系，可分為 4 種邏輯結構：_集合_、_線性結構、 _、_樹形結構_、_圖狀結構_。

8、題目24數(shù)據(jù)的邏輯結構在計算機中的表示稱為_存儲結構_或_物理結構_ 。題目25除了第 1 個和最后一個結點外，其余結點有且只有一個前驅(qū)結點和后繼結點的數(shù)據(jù)結構為回答線性結構，每個結點可有任意多個前驅(qū)和后繼結點數(shù)的結構為回答非線性結。答案：線性結構，非線性結構26題目數(shù)據(jù)結構中的數(shù)據(jù)元素存在多對多的關系稱為回答 27題目數(shù)據(jù)結構中的數(shù)據(jù)元素存在一對多的關系稱為回答 28題目圖狀結構樹形結構結構。結構。數(shù)據(jù)結構中的數(shù)據(jù)元素存在一對一的關系稱為回答 29題目線性結構結構。要求在 n 個數(shù)據(jù)元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數(shù) 和算法的時間復雜度分別為_ n-1_ 和_

9、o(n)_。題目30在一個單鏈表中 p 所指結點之后插入一個 s 所指結點時，應執(zhí)行回答s-next=p-next;和 p-next=s;的操作。題目31設有一個頭指針為 head 的單向循環(huán)鏈表，p 指向鏈表中的結點，若 p-next=回答head，則 p 所指結點為尾結點。題目32在一個單向鏈表中，要刪除 p 所指結點，已知 q 指向 p 所指結點的前驅(qū)結點。則可以用操作回答。正確答案是：q-next=p-next;題目33設有一個頭指針為 head 的單向鏈表，p 指向表中某一個結點，且有 p-next= =null，通過操作回答正確答案是：p-next=head;，就可使該單向鏈表構形

10、成單向循環(huán)鏈表。題目34單向循環(huán)鏈表是單向鏈表的一種擴充，當單向鏈表帶有頭結點時，把單向鏈表中尾結點的指針域由空指針改為回答指針域由空指針改為指向回答；當單向鏈表不帶頭結點時，則把單向鏈表中尾結點的 。答案：頭結點的指針、指向第一個結點的指針題目35線性鏈表的邏輯關系是通過每個結點指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致，而是一種回答存儲結構，又稱為回答 。答案：鏈式、鏈表三、問答題（第 1 小題 7 分，第 2 小題 8 分）題目36簡述數(shù)據(jù)的邏輯結構和存儲結構的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O計與實現(xiàn)？ 答：若用結點表示某個數(shù)據(jù)元素，則結點與結點之間的邏輯關系就稱為數(shù)據(jù)的邏

11、輯結構。 數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結構?？梢姡瑪?shù)據(jù)的邏輯結構是反映數(shù)據(jù)之間 的固有關系，而數(shù)據(jù)的存儲結構是數(shù)據(jù)在計算機中的存儲表示。盡管因采用的存儲結構不 同，邏輯上相鄰的結點，其物理地址未必相同，但可通過結點的內(nèi)部信息，找到其相鄰的 結點，從而保留了邏輯結構的特點。采用的存儲結構不同，對數(shù)據(jù)的操作在靈活性，算法 復雜度等方面差別較大。題目37解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和鏈式存儲結構的優(yōu)缺 點。答：順序結構存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結構和存儲結構是統(tǒng)一的，要 求內(nèi)存中存儲單元的地址必須是連續(xù)的。優(yōu)點：一般情況下，存儲密度大，存儲空間

12、利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預先分 配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結構存儲時，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結點值， 另一部分存放表示結點間關系的指針。優(yōu)點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。四、程序填空題（每空 1 分，共 15 分）題目38下列是用尾插法建立帶頭結點的且有 n 個結點的單向鏈表的算法，請在空格內(nèi)填上適當?shù)?語句。node *create1(n)/* 對線性表(1,2,.,n),建立帶頭結點的單向鏈表 */node *

13、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 個結點的單向鏈表的算法，請在空格內(nèi)填上適當?shù)?語句。node *create2(n)/*對線性表(n,n-1,.,1), 建立帶頭結點的線性鏈表 */node *head,*p,*q;int i;p=(node *)malloc(sizeof(node);回答head=p;p-next=n

14、ull;回答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 個結點的算法，請在空格內(nèi)填上適當?shù)恼Z句。 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下列是在具有頭結點單向列表中在

15、第 i 個結點之前插入新結點的算法，請在空格內(nèi)填上適 當?shù)恼Z句。int insert(node *head,int x,int i)node *q,*p;int j;q=head;j=0;while(q!=null)&(jnext;j+; if(q=null) return(0);p=回答(node *)malloc(sizeof(node);p-data=x;回答p-next=q-next正確正確答案是：p-next=q-next 獲得 1.00 分中的 1.00 分 ;回答q-next=p;return(1);形考任務 2題目1若讓元素 1，2，3 依次進棧，則出棧順序不可能為（ ）。 選

16、擇一項：a. 2，1，3b. 3，1，2c. 3，2，1題目2一個隊列的入隊序列是 1，2，3，4。則隊列的輸出序列是（ ）。 選擇一項：a. 3，2，4，1b. 1，2，3，4c. 4，3，2，1d. 1，4，3，2題目3向順序棧中壓入新元素時，應當（ ）。 選擇一項：a. 先存入元素，再移動棧頂指針b. 先移動棧頂指針，再存入元素c. 先后次序無關緊要d. 同時進行題目4在一個棧頂指針為 top 的鏈棧中，將一個 p 指針所指的結點入棧，應執(zhí)行（ ）。 選擇一項：a. p-next=top;top=p;b. top-next=p;c. p-next=top-next;top=top-nex

17、t;d. p-next=top-next;top-next=p;題目5在一個棧頂指針為 top 的鏈棧中刪除一個結點時，用 x 保存被刪結點的值，則執(zhí)行 （ ）。選擇一項：a. x=top-data;top=top-next;b. x=top-data;c. top=top-next;x=top-data;d. x=top;top=top-next;題目6判斷一個順序隊列（最多元素為 m）為空的條件是（ ）。 選擇一項：a. rear=m-1b. front=rear+1c. front=rear題目7判斷一個循環(huán)隊列 q（最多元素為 m）為滿的條件是（ ）。 選擇一項：a. q-rear!=

18、 (q-front+1)%mb. q-front=q-rearc. q-front=(q-rear+1)%md. q-front=q-rear +1題目8判斷棧滿（元素個數(shù)最多 n 個）的條件是（ ）。 選擇一項：a. top=0b. top!=0c. top=-1d. top=n-1題目9設有一個 20 階的對稱矩陣 a（第一個元素為 a ），采用壓縮存儲的方式，將其下三角部1,1分以行序為主序存儲到一維數(shù)組 b 中（數(shù)組下標從 1 開始）， 則矩陣元素 a 在一維數(shù)組6,2b 中的下標是（ ）。選擇一項：a. 17b. 23c. 21d. 28題目10在解決計算機主機與打印機之間速度不匹配

19、問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將 要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應該是 一個（ ）結構。選擇一項：a. 隊列b. 先性表c. 數(shù)組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 所指結點的運

20、算為 （ ）。選擇一項：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. hb. 字符串的結束符c. 變量 hd. 字符 h題目15設主串為“abccdabcdefabc”，以下模式串能與主串成功匹配的是（ ）。 選擇一項：a. bcdb. bcdc. abcd. abc題目16字符串 a1=aeijing，a2=aei，a3=aefang，a4=aefi中最大的是（ ）。 選擇一項：a. a3b. a1c. a4

21、d. a2題目17兩個字符串相等的條件是（ ）。選擇一項：a. 兩串的長度相等，并且對應位置上的字符相同b. 兩串的長度相等c. 兩串的長度相等，并且兩串包含的字符相同 d. 兩串包含的字符相同題目18一維數(shù)組 a 采用順序存儲結構，每個元素占用 6 個字節(jié)，第 6 個元素的存儲地址為 100， 則該數(shù)組的首地址是（ ）。選擇一項：a. 64b. 90c. 28d. 70題目19一個非空廣義表的表頭（ ）。 選擇一項：a. 可以是子表或原子b. 只能是原子c. 不可能是原子d. 只能是子表題目20對稀疏矩陣進行壓縮存儲,可采用三元組表，一個 10 行 8 列的稀疏矩陣 a，其相應的三元 組表共

22、有 6 個元素，矩陣 a 共有（ ）個零元素。選擇一項：a. 8b. 10c. 72d. 74題目21對稀疏矩陣進行壓縮存儲,可采用三元組表，一個 10 行 8 列的稀疏矩陣 a 共有 73 個零元 素，a 的右下角元素為 6，其相應的三元組表中的第 7 個元素是（ ）。選擇一項：a. （10，8，7）b. （10，8，6）c. （7，10，8）d. （7，8，10）題目22對一個棧頂指針為 top 的鏈棧進行入棧操作，通過指針變量 p 生成入棧結點，并給 該 結點賦值 a，則執(zhí)行: p=(struct node *)malloc(sizeof(struct node);p-data=a;和

23、（ ）。選擇一項：a. p-next=top;p=top;b. top-next=p;p=top;c. p-nex=top;top=p;d. top=top-next;pe=top;題目23頭指針為 head 的帶頭結點的單向鏈表為空的判定條件是（ ）為真。 選擇一項：a. head=nullb. head-next=nullc. head-next!=nulld. head-next!=null題目24設有一個對稱矩陣 a，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù) 組 b 中（數(shù)組下標從 1 開始），b 數(shù)組共有 55 個元素,則該矩陣是（ ）階的對稱矩 陣。選擇一項：a.

24、 20b. 15c. 10d. 5題目25數(shù)組 a 經(jīng)初始化 char a =“english”;a1中存放的是（ ）。 選擇一項：a. nb. 字符 nc. ed. 字符 e二、填空題（每小題 2 分，共 30 分）26題目循環(huán)隊列隊頭指針在隊尾指針回答下一個位置，隊列是“滿”狀態(tài)。ij27題目循環(huán)隊列的引入，目的是為了克服回答 28題目假上溢。判斷一個循環(huán)隊列 lu（最多元素為 m）為空的條件是回答 29題目lu-front=lu-rear。題干向一個棧頂指針為 h 的鏈棧中插入一個 s 所指結點時，可執(zhí)行回答 s-next=h;和 h=s;操 作。（結點的指針域為 next）題目30從一

25、個棧頂指針為 h 的鏈棧中刪除一個結點時，用 x 保存被刪結點的值，可執(zhí)行 x=h-題目 31在一個鏈隊中，設 f 和 r 分別為隊頭和隊尾指針，則插入 s 所指結點的操作為回答和 r=s; r- next=s;（結點的指針域為 next）題目32在一個鏈隊中，設 f 和 r 分別為隊頭和隊尾指針，則刪除一個結點的操作為回答 f=f- next;。 （結點的指針域為 next）題目33串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是回答字符。題目34空串的長度是回答0；空格串的長度是回答空格字符的。題目35設廣義表 l=(),()，則表頭是_，表尾是_ ，l 的長度是 _ 。則表頭是（

26、），表尾是（），l 的長度是 2題目36廣義表 a（a，b，c），（d，e，f）的表尾為回答(d,e,f)。題目37設有 n 階對稱矩陣 a，用數(shù)組 s 進行壓縮存儲，當 ij 時，a 的數(shù)組元素 a 相應于數(shù)組 s的數(shù)組元素的下標為回答i(i-1)/2+j。（數(shù)組元素的下標從 1 開始）題目38對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的_、 _和_三項信息。答案：行下標、列下標和非零元素值題目39循環(huán)隊列用 a0，a7的一維數(shù)組存放隊列元素，（采用少用一個元素的模式)，設 front 和 rear 分別為隊頭和隊尾指針，且 front 和 rear 的值分別為 2 和

27、 7，當前隊列中的元素個數(shù)是回答 5。40題目循環(huán)隊列的引入，目的是為了克服回答 三、問答題（每小題 5 分，共 20 分）41題目假上溢。完成滿分 5.00題干棧、隊列和線性表的區(qū)別是什么？答：棧是一種先進后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性 表可以在線性表的任何位置進行插入和刪除操作。隊列是一種先進先出的線性表，隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進 行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。題目42設棧 s 和隊列 q 的初始狀態(tài)為空，元素 e1，e2，e3，e4，e5 和 e6 依次通過 s，一個元素 出棧后即進隊列 q，若 6 個

28、元素出隊的序列是 e2，e4，e3，e6，e5，e1，則棧 s 的容量至 少應該是多少？出隊序列是 e2,e4,e3,e6,e5,e1 的過程：（1） e1 入棧（棧底到棧頂元素是 e1）（2） e2 入棧（棧底到棧頂元素是 e1，e2）（3） e2 出棧（棧底到棧頂元素是 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） e

29、6 出棧（棧底到棧頂元素是 e1，e5）（11） e5 出棧（棧底到棧頂元素是 e1）（12） e1 出棧（棧底到棧頂元素是空）棧中最多時有 3 個元素，所以棧 s 的容量至少是 3。k-1-1k題目43有 5 個元素，其入棧次序為：a、b、c、d、e，在各種可能的出棧次序中，以元素 c、d 最先的次序有哪幾個？從題中可知，要使 c 第一個且 d 第二個出棧，應是 a 入棧，b 入棧，c 入棧，c 出棧，d 入棧。之后可以有以下幾種情況：（1） b 出棧，a 出棧，e 入棧，e 出棧，輸出序列為：cdbae。（2） b 出棧，e 入棧，e 出棧，a 出棧，輸出序列為 cdbea。（3） e 入

30、棧，e 出棧，b 出棧，a 出棧，輸出序列為 cdeba所以可能的次序有：cdbae，cdbea，cdeba題目44簡述廣義表和線性表的區(qū)別和聯(lián)系。廣義表是線性表的的推廣，它也是 n（n0）個元素 a ，a ， ，a ， ，a 的有限序列，其1 2 i n中 a 或者是原子或者是一個廣義表。所以，廣義表是一種遞歸數(shù)據(jù)結構，而線性表沒有這 i種特性，線性表可以看成廣義表的特殊情況，當 a 都是原子時，廣義表退化成線性表。i形考任務三一、單項選擇題（每小題 2 分，共 32 分）題目1假定一棵二叉樹中，雙分支結點數(shù)為 15，單分支結點數(shù)為 30，則葉子結點數(shù)為 （ ）。選擇一項：a. 17b. 1

31、6c. 15d. 47題目2二叉樹第 k 層上最多有（ ）個結點。 選擇一項：a. 2b. 2kc. 2 -1d. 2k題目3設某一二叉樹先序遍歷為 abdec，中序遍歷為 dbeac，則該二叉樹后序遍歷的順序是 （ ）。選擇一項：a. abedcb. abdecc. debacd. debca題目4將含有 150 個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號， 根結點的編號為 1，則編號為 69 的結點的雙親結點的編號為（ ）。選擇一項：a. 35b. 33c. 34d. 36題目5如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱 為（ ）

32、。選擇一項：a. 平衡二叉樹b. 完全二叉樹c. 二叉樹d. 哈夫曼樹題目6在一棵度為 3 的樹中，度為 3 的結點個數(shù)為 2，度為 2 的結點個數(shù)為 1，則度為 0 的結點 個數(shù)為（ ）。選擇一項：a. 5b. 4c. 7d. 6題目7在一棵度具有 5 層的滿二叉樹中結點總數(shù)為（ ）。 選擇一項：a. 31b. 32c. 16d. 33題目8利用 n 個值作為葉結點的權生成的哈夫曼樹中共包含有（ ）個結點。 選擇一項：a. n+1b. 2*nc. nd. 2*n-1題目9利用 3、6、8、12 這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子結點 中的最長帶權路徑長度為（ ）。選擇

33、一項：a. 16b. 30c. 12d. 18題目10在一棵樹中，（ ）沒有前驅(qū)結點。 選擇一項：a. 葉結點b. 空結點c. 樹根結點d. 分支結點題目11設一棵有 n 個葉結點的二叉樹，除葉結點外每個結點度數(shù)都為 2，則該樹共有（ ）個 結點。選擇一項：a. 2n-1b. 2n+2c. 2n+1d. 2n題目12在一個圖 g 中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。 選擇一項：a. 1b. 1/21c. 2d. 4題目13鄰接表是圖的一種（ ）。 選擇一項：a. 索引存儲結構b. 順序存儲結構c. 散列存儲結構d. 鏈式存儲結構題目14如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜

34、索即可訪問所有頂點，則該圖一定是 （ ）。選擇一項：a. 一棵樹b. 有回路c. 完全圖d. 連通圖題目15圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。 選擇一項：a. 先序b. 層次c. 中序d. 后序題目16已知下圖所示的一個圖，若從頂點 v 出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一 種頂點序列為（ ）。選擇一項：a. v v v v v v v v1 2 4 5 8 3 6 7b. v v v v v v v v1 2 4 8 5 3 6 7c. v v v v v v v v1 2 4 8 3 5 6 7d. v v v v v v v v1 3 6 7 2 4 5 8二、填空

35、題 （每小題 1 分，共 20 分）17題目結點的度是指結點所擁有的回答子樹樹木或后繼結點。正確答案是：子樹樹木或后繼結點數(shù)18題目樹的度是指回答樹中所有結點的度的最大值。正確答案是：樹中所有結點的度的最大值題目19度大于 0 的結點稱作_ 或_。 分支結點、非終端結點題目20度等于 0 的結點稱作_ 或_。 葉子結點、終端結點題目21在一棵樹中，每個結點的_ 或者說每個結點的_ 稱為該結點的 _ ，簡稱為孩子。子樹的根、后繼結點、孩子結點22題目從根結點到該結點所經(jīng)分支上的所有結點稱為該結點的回答 正確答案是：祖先祖先。23題目樹的深度或高度是指回答樹中結點的最大層數(shù)。正確答案是：樹中結點的

36、最大層數(shù)題目24具有 n 個結點的完全二叉樹的深度是_ 。題目25先序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，訪問二叉樹的回答根結點；先序遍歷二叉樹的回答左子樹，先序遍歷二叉樹的回答右子樹。根結點、左子樹、右子樹題目26中序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，中序遍歷二叉樹的回答左子樹；訪問而叉樹的回答根結點，中序遍歷二叉樹的回答右子樹。左子樹、根結點、右子樹題目27后序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，后序遍歷二叉樹的回答左子樹；后序遍歷二叉樹的回答右子樹，訪問而叉樹的回答根結點。左子樹、右子

37、樹、根結點題目28將樹中結點賦上一個有著某種意義的實數(shù)，稱此實數(shù)為該結點的回答權。正確答案是：權29題目樹的帶權路徑長度為樹中所有葉子結點的回答 正確答案是：帶權路徑長度之和30題目最優(yōu)二叉哈夫曼樹又稱為回答帶權路徑長度之和。，它是 n 個帶權葉子結點構成的所有二叉樹中帶權路徑長度 wpl 回答最小的二叉。答案：最優(yōu)二叉樹，最小的二叉樹題目31若以 4，5，6，7，8 作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是回答69。正確答案是：6932題目具有 m 個葉子結點的哈夫曼樹共有回答 正確答案是：2m-133題目2m-1結點。圖的遍歷是從圖的某一頂點出發(fā)，按照一定的搜索方法對圖中回答所有

38、頂點各做回答一次訪問的過程。答案：所有頂點; 一次34題目圖的深度優(yōu)先搜索遍歷類似于樹的回答 正確答案是：先序35題目先序遍歷。圖的廣度優(yōu)先搜索類似于樹的回答 正確答案是：按層次36題目按層次遍歷。圖常用的兩種存儲結構是_和_。 鄰接矩陣、鄰接表三、綜合題（每小題 8 分，共 40 分）題目37寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。答：二叉樹的定義是遞歸的，所以，一棵二叉樹可看作由根結點，左子樹和右子樹這三個 基本部分組成，即依次遍歷整個二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續(xù) 分為根結點、左子樹和右子樹三個部分，這樣劃分一直進行到樹葉結點。（1） 先序為“根左右”，先序

39、序列為：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，請畫出這棵二叉樹，并寫 出該二叉樹后續(xù)遍歷的結果。（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 組成，它們出現(xiàn)的頻率分別 是：10、20

40、、5、15、8、2、3、7 和 30。請請用這 9 個字母出現(xiàn)的頻率作為權值求：（1） 設計一棵哈夫曼樹；（2） 計算其帶權路徑長度 wpl；（3） 寫出每個字符的哈夫曼編碼。1）哈夫曼樹如圖 b-4 所示。圖 b-4（2） 其帶權路徑長度 wpl 值為 270。（3） 每個字符的哈夫曼編碼為：a:100, b:11, c:1010, d:000, e:0010, f:10110, g:10111, h:0011, i:01題目40請根據(jù)以下帶權有向圖 g（1）給出從結點 v 出發(fā)分別按深度優(yōu)先搜索遍歷 g 和廣度優(yōu)先搜索遍歷 g 所得的結點序1列；（2） 給出 g 的一個拓撲序列；（3） 給

41、出從結點 v 到結點 v 的最短路徑。1 8（1）深度優(yōu)先遍歷：v ，v ，v ，v ，v ，v ，v ，v1 2 3 8 5 7 4 6廣度優(yōu)先遍歷：v ，v ，v ，v ，v ，v ，v ，v1 2 4 6 3 5 7 8（2）g 的拓撲序列為：v ，v ，v ，v ，v ，v ，v ，v ，v ，v1 2 4 6 5 5 3 5 7 8（3）最短路徑為：v ，v ，v ，v ，v1 2 5 7 8題目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

42、）（1） 畫出 g 的圖示；（2） 然后給出 g 的鄰接矩陣和鄰接表；（3） 寫出每個頂點的度。 g1 的圖示和圖 g1 的鄰接表如下圖所示。圖g 圖 g 的鄰接矩陣如下圖所示：圖 g 的鄰接矩陣圖 g 的鄰接表 v1、v2、v3、v4、v5 的度分別為：2，3，2，3，2 四、程序填空題（每空 2 分，共 8 分）題目42部分正確獲得 4.00 分中的 2.00 分題干以下是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域 分別為 left 和 right，數(shù)據(jù)域 data 為字符型，bt 指向根結點）。void inorder (struct btreenode *

43、bt)if(bt!=null)回答;回答;inorder(bt-right);答案：（1） inorder(bt-left)（2） printf(%c,bt-data)題目43以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指 針域分別為 left 和 right，數(shù)據(jù)域 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. 以順序存儲方式，且數(shù)據(jù)元素有序c. 以鏈接存儲方式，且數(shù)據(jù)元素有序d. 以鏈接存儲方式題目2采用順序查找方法查找長度為 n 的線性表時，每個元素的平均查找長度為（ ）。 選擇一項：a. (n-1)/2b. (n+1)/2c. nd. n/2題目3有一個長度為 10 的有序表，按折半查