1、數據結構（本）形成性考核作業冊使用說明本作業冊是中央廣播電視大學計算機科與技術專業（本科）數據結構（本）課程形成性考核的依據，與數據結構（本科） 教材（李偉生主編，中央電大出版社出版）配套使用。數據結構 （本） 課程是中央廣播電視大學計算機科學技術專業的一門統設必修、 學位課程， 4學分，共 72 學時。其中實驗24 學時，開設一學期。本課程的特點是綜合性、實踐性強，內容抽象，在專業中具有承上啟下的作用。因此，在學習本課程時，要注意理論聯系實際，結合教學內容進行上機實踐，認真完成作業和實驗內容。本課程的總成績按百分制記分， 其中形成性考核所占的比例為30%， 終結性考試占 70 （閉卷，答題時

2、限為 90 分鐘） 。課程總成績達到 60 分及以上者為合格，可以獲得該課程的學分。 本課程的學位課程學分為 70 分， 即課程總成績達到 70 分及以上者有資格申請專業學位。本課程共設計了 4 次形考作業， 每次形考作業均包括實驗內容， 由各地電大根據學生對 作業中各種題型練習和實驗的完成情況進行考核。對于實驗內容要求按實驗要求認真完成，并提交實驗報告。數據結構（本）課程作業作業 1（本部分作業覆蓋教材第 1-2 章的內容）一、單項選擇題1在數據結構中，從邏輯上可以把數據結構分為（ ） 。A.動態結構和靜態結構B .緊湊結構和非緊湊結構C.線性結構和非線性結構D.內部結構和外部機構2下列說法

3、中，不正確的是（） 。A.數據元素是數據的基本單位B.數據項是數據中不可分割的最小可標識單位C.數據可有若干個數據元素構成D.數據項可由若干個數據元素構成3一個存儲結點存儲一個（） 。A.數據項B .數據元素C.數據結構D .數據類型4數據結構中，與所使用的計算機無關的是數據的（） 。A.存儲結構B .物理結構C.邏輯結構D.物理和存儲結構5下列的敘述中，不屬于算法特性的是（） 。A.有窮性B ,輸入性C.可行性D.可讀性6 算法分析的目的是（） 。A 找出數據結構的合理性B 研究算法中的輸入和輸出的關系C.分析算法的效率以求改進 D .分析算法的易懂性和文檔性7數據結構是一門研究計算機中（

4、）對象及其關系的科學。A.數值運算B .非數值運算C.集合D .非集合8算法的時間復雜度與（）有關。A 所使用的計算機B 與計算機的操作系統C.與算法本身D .與數據結構9設有一個長度為n 的順序表，要在第i 個元素之前（也就是插入元素作為新表的第i 個元素） ，則移動元素個數為（ ） 。An-i+1Bn-iCn-i-1Di10設有一個長度為 n 的順序表，要刪除第i 個元素移動元素的個數為（ ） 。An-i+1Bn-iCn-i-1Di11 .在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現要刪除q所指結點，可用語句（）。A . p=q->next

5、 B . p->next=q C . p->next=q next D . q->next=NULL12 .在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執行（）。A . p->next= s; s next= p next C. p=s->nextD13.非空的單向循環鏈表的尾結點滿足（ 結點）。A. . P->next= =NULLBC . P->next= =headD14 .鏈表不具有的特點是（）。A .可隨機訪問任一元素BC .不必事先估計存儲空間 D15 .帶頭結點的鏈表為空的判斷條件是（ A head = =NULLB. head

6、->next= =NULLC. head->next= =headD. head!=NULLB . p->next=s next;.s->next=p->next; p->next=s;）（設頭指針為head,指針p指向尾P= =NULL.P= = head.插入刪除不需要移動元素.所需空間與線性表長度成正比）（設頭指針為head）。16 .在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且 q所指結點是p所指結 點的直接后繼，現要刪除q所指結點，可用語句（）。A p=q->next B. p->next=q C. p->next=q-&

7、gt;next D. q->next=NULL17 .在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（）。A . r=f->next;B. r=r->next;C. f=f->next;D. f=r->next;18 .在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算為（）。A . f->next=s; f=s; B . r->next=s;r=s;C. s->next=r;r=s; D . s->next=f;f=s;19 .一個順序表第一個元素的存儲地址是90,每個元素的長度為 2,則第6個元素

8、的地址是（）。A. 98 B . 100 C . 102 D . 10620 .有關線性表的正確說法是（）。A.每個元素都有一個直接前驅和一個直接后繼B.線性表至少要求一個元素C.表中的元素必須按由小到大或由大到下排序D.除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅和一個直接 后繼二、填空題i（1 i n+1）個元素之前插入新1.在一個長度為n的順序存儲結構的線性表中，向第 元素時，需向后移動 個數據元素。2.從長度為n的采用順序存儲結構的線性表中刪除第i(1 in+1）個元素，需向前移動 個元素。3 .數據結構按結點間的關系，可分為4種邏輯結構： 、O4 .數據的邏輯結構在計

9、算機中的表示稱為 或。5 .除了第1個和最后一個結點外，其余結點有且只有一個前驅結點和后繼結點的數據結構為,每個結點可有任意多個前驅和后繼結點數的結構 為。6 .算法的5個重要特性是 、7 .數據結構中的數據元素存在多對多的關系稱為 結構。8 .數據結構中的數據元素存在一對多的關系稱為 結構。9 .數據結構中的數據元素存在一對一的關系稱為 結構。10 .要求在n個數據元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數和算法的時間復雜度分別為 和 。11 .在一個單鏈表中p所指結點之后插入一個s所指結點時，應執行和p->next=s;的操作。12 .設有一個頭指針為 head

10、的單向循環鏈表，p指向鏈表中的結點，若 p->next= =,則p所指結點為尾結點。13 .在一個單向鏈表中，要刪除p所指結點，已知q指向p所指結點的前驅結點。則可以用操作 。14 .設有一個頭指針為 head的單向鏈表，p指向表中某一個結點，且有p->next= =NULL, 通過操作 , 就可使該單向鏈表構造成單向循環鏈表。15 .每個結點只包含一個指針域的線性表叫 。16 .線性表具有 和 兩種存儲結構。17 .數據的邏輯結構是從邏輯關系上描述數據，它與數據的關系 無關，是獨 立于計算機的。18 .在雙向循環鏈表的每個結點中包含 指針域，其中next指向它的 , prior

11、指向它的 ,而頭結點的 prior 指向,尾結點的 next 指 向。19 .單向循環鏈表是單向鏈表的一種擴充，當單向鏈表帶有頭結點時，把單向鏈表中尾 結點的指針域由空指針改為 ;當單向鏈表不帶頭結點時，則把單向鏈表中尾結點的指針域由空指針改為指向 。20 .線性鏈表的邏輯關系時通過每個結點指針域中的指針來表示的。其邏輯順序和物理 存儲順序不再一致，而是一種 存儲結構，又稱為 。三、問答題1.簡述數據的邏輯結構和存儲結構的區別與聯系，它們如何影響算法的設計與實現?2解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和鏈式存儲結構的 優缺點。3什么情況下用順序表比鏈表好4頭指針、頭結點、第

12、一個結點（或稱首元結點）的區別是什么5解釋帶頭結點的單鏈表和不帶頭結點的單鏈表的區別。四、程序填空題1 .下列是用尾插法建立帶頭結點的且有n個結點的單向鏈表的算法，請在空格內填上適當的語句。NODE *create1(n)/*對線卜t表(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+) p=(NODE *)malloc(sizeof(NODE);(1) ;(2) ;(3) ;(4) ; return

13、(head);2 .下列是用頭插法建立帶頭結點的且有n個結點的單向鏈表的算法，請在空格內填上適當的語句。NODE *create2(n)/*對線ft表(n,n-1,.,1),建立帶頭結點的線性鏈表*/NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);(1) ;p->next=NULL;(2) ;for(i=1;i<=n;i+) p=(NODE *)malloc(sizeof(NODE);p->data=i;if(i=1)(3) ;else(4) ;(5) ;return(head);3.下列是在具有頭結點單向列表中刪除第

14、i個結點，請在空格內填上適當的語句。int delete(NODE *head,int i) NODE *p,*q;int j；q=head;j=0;while(q!=NULL)&&(j<i-1)/*找到要刪除結點的直接前驅，并使 q指向它*/ q=q->next; j+; if(q=NULL) return(0); (1);(2);free(p); return(1); 五、完成：實驗1線性表根據實驗要求(見教材P201-202)認真完成本實驗，并提交實驗報告。數據結構（本）課程作業23-5 章的內容）一、單項選擇題1若讓元素1， 2， 3 依次進棧，則出棧順序不

15、可能為（ ） 。A 3 ， 2 ， 1 B 2， 1 ， 3C 3， 1 ， 2D 1， 3， 22一個隊列的入隊序列是1 ， 2， 3， 4 。則隊列的輸出序列是（）。1 ， 2， 3 ， 43 ， 2， 4 ， 1A 4 ， 3 ， 2 ， 1BC 1 ， 4 ， 3 ， 2D）。B 先存入元素，再移動棧頂指針同時進行3向順序棧中壓入新元素時，應當（A.先移動棧頂指針，再存入元素C.先后次序無關緊要D4在一個棧頂指針為 top 的鏈棧中，將一個p 指針所指的結點入棧，應執行（ ） 。A top->next=p;B p->next=top->next; top->ne

16、xt=p;C p->next=top; top=p;D p->next=top->next; top=top->next;5在一個棧頂指針為top 的鏈棧中刪除一個結點時，用 x 保存被刪結點的值，則執行）。A x=top;top=top->next;B x=top->data;C top=top ->next; x=top->data;D x=top->data; top=top->next;6一般情況下，將遞歸算法轉換成等價的非遞歸算法應該設置（） 。A.棧B.隊列C.堆棧或隊列D.數組7表達式a*（b+c）-d 的后綴表達式是（

17、 ） 。A abcd*+- B abc+*d- C abc*+d- D -+*abcd8判斷一個順序隊列sq （最多元素為 m>）為空的條件是（）。A sq->rear-sq->front= m 0C sq->front=sq->rearD9.判斷一個循環隊列Q （最多元素為A Q->front=Q->rearBC Q->front=（Q->rear+1）% m 0B sq->rear-sq->front-1= = m 0 sq->front=sq->rear+1mo）為空的條件是（）。 Q->front!=Q

18、->rearD Q->front!= （Q->rear+1）%m010 .判斷一個循環隊列Q (最多元素為A Q->front=Q->rearBC Q->front=(Q->rear+1)% m 0mO為空的條件是()。 Q->front!=Q->rearD Q->front!= (Q->rear+1)% m11 .判斷棧S滿（元素個數最多n個）的條件是（）。s->top!=0s->top!=n-1A s->top=0BC s->top=n-1D12一個隊列的入隊順序是a,b,c,d ，則離隊的順序是（

19、） 。A a,d,cb B a,b,c,d C d,c,b,a D c,b,d,a13如果以鏈表作為棧的存儲結構，則退棧操作時（ ） 。A 必須判斷棧是否滿B 判斷棧元素類型C.必須判斷棧是否空 D .對棧不作任何判斷14 在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入緩沖區中， 而打印機則從緩沖區中取出數據打印， 該緩沖區應該是一個（ ）結構。A.堆棧 B .隊列 C .數組 D .先性表15一個遞歸算法必須包括（ ） 。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D .終止條件和迭代部分16 從一個棧頂指針為 top 的鏈棧中刪除一個結

20、點時， 用變量 x 保存被刪結點的值， 則執行（ ） 。A x=top->data; top=top->next; B x=top->data;C top=top->next; x=top->data; D top=top->next; x=data;17 在一個鏈隊中， 假設 f 和 r 分別為隊頭和隊尾指針， 則刪除一個結點的運算為 （） 。A r=f->next; B r=r->next; C f=f->next; D f=r->next;18 在一個鏈隊中，假設 f 和 r 分別為隊頭和隊尾指針，則插入 s 所指結點的運算為

21、（） 。r->next=s;r=s;s->next=f;f=s;）。B 串的長度必須大于零D 空串就是空白串A f->next=s; f=s;BC s->next=r;r=s;D19. 以下陳述中正確的是（A.串是一種特殊的線性表C.串中元素只能是字母20 設有兩個串 p 和 q， 其中 q 是 p 的子串， q 在 p 中首次出現的位置的算法稱為 （） 。A.求子串B.連接C 匹配D 求串長21串是（ ）。A 不少于一個字母的序列C 不少于一個字符的序列22 串的長度是指（ ） 。A.串中所含不同字母的個數C.串中所含不同字符的個數B任意個字母的序列D有限個字符的序列

22、B 串中所含字符的個數D 串中所含非空格字符的個數23. 若串 S=“English ” ，其子串的個數是（ ）。A 9 B 16 C 36 D 2824 下面關于串的敘述中，不正確的是（ ） 。A.串是字符的有限序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串即可以采用順序存儲，也可以采用鏈式存儲25串與普通的線性表相比較，它的特殊性體現在（ ） 。A.順序的存儲結構BC.數據元素是一個字符D26空串與空格串（ ） 。A.相同 B .不相同 C.鏈接的存儲結構.數據元素可以任意D 無法確定27兩個字符串相等的條件是（） 。A 兩串的長度相等B.兩串包含的字符相同C 兩串的長度

23、相等，并且兩串包含的字符相同D 兩串的長度相等，并且對應位置上的字符相同28在實際應用中，要輸入多個字符串，且長度無法預定。則應該采用（）存儲比較合適（ ） 。 A.鏈式 B .順序C.堆結構 D .無法確定29.一維數組A采用順序存儲結構，每個元素占用6個字節，第6個元素的存儲地址為100，則該數組的首地址是（ ）。A 64B 28C 70D 9030 稀疏矩陣采用壓縮存儲的目的主要是（） 。A.表達變得簡單B.對矩陣元素的存取變得簡單C 去掉矩陣中的多余元素 D 減少不必要的存儲空間的開銷）。.只能是子表.可以是子表或原子）。.索引與、和修改.查找與索引31 . 一個非空廣義表的表頭（A

24、.不可能是原子BC.只能是原子D32 .常對數組進行的兩種基本操作是（A.建立與刪除BC.查找和修改D33 .設二維數組A56按行優先順序存儲在內存中，已知 A00起始地址為1000,每個數組元素占用5個存儲單元，則元素 A44的地址為（）。A . 1140 B . 1145 C . 1120 D , 112534 .設有一個20階的對稱矩陣 A,采用壓縮存儲的方式，將其下三角部分以行序為主 序存儲到一維數組B中（數組下標從1開始），則矩陣中元素 a0在一維數組B中的下標是（ ）。A. 41 B . 32 C . 18 D . 3835 . 一個非空廣義表的表頭（）。A.不可能是子表B .只能

25、是子表C.只能是原子D .可以是子表或原子二、填空題1 .棧是限定在表的一端進行插入和刪除操作的線性表，又稱為 。2 .隊列的特性是。3 .往棧中插入元素的操作方式是：先 ,后4 .刪除棧中元素的操作方式是：先 ,后。5 .循環隊列隊頭指針在隊尾指針 位置，隊列是“滿”狀態6 .在隊列的順序存儲結構中，當插入一個新的隊列元素時，尾指針 ，: 刪除一個元素隊列時，頭指針 。7 .循環隊列的引入，目的是為了克服 。8 .向順序棧插入新元素分為三步：第一步進行判斷，判斷條件是;第二步是修改 ;第三步是把新元素賦給 。 同樣從順序棧刪除元素分為三步： 第一步進行 判斷，判斷條件是 。 第二步是把 ;第

26、三步 。9 .假設以S和X分別表示入棧和出棧操作，則對輸入序列 a,b,c,d,e 一系列棧操作 SSXSXSSXXX后，得至ij的輸出序歹“為 。10 . 一個遞歸算法必須包括 和。11 .判斷一個循環隊列 LU （最多元素為ma）為空的條件是 。12 .在將中綴表達式轉換成后綴表達式和計算后綴表達式的算法中，都需要使用棧，對于前者，進入棧中的元素為表達式中的 ,而對于后者，進入棧的元素為 _ ，中綴表達式（a+b）心（f-d/c）所對應的后綴表達式是 。16 .向一個棧頂指針為 h的鏈棧中插入一個 s所指結點時，可執行 和h=s;操 作。(結點的指針域為next)17 .從一個棧頂指針為h

27、的鏈棧中刪除一個結點時，用x保存被刪結點的值，可執行x=h->data;和。(結點的指針域為 next)18 .在一個鏈隊中，設 f和r分別為隊頭和隊尾指針，則插入 s所指結點的操作為 和r=s;(結點的指針域為 next)19 .在一個鏈隊中，設f和r分別為隊頭和隊尾指針，則刪除一個結點的操作為 . (結點的指針域為next)20 .串是一種特殊的線性表，其特殊性表現在組成串的數據元素都是 。21 .串的兩種最基本的存儲方式是 和。22 .空串的長度是 ;空格串的長度是 。23 .需要壓縮存儲的矩陣可分為 矩陣和 矩陣兩種。24 .設廣義表 L=(), (),則表頭是 ,表尾是, L的

28、長度25 .廣義表 A(a,b,c ) ,(d,e,f)的表尾為 。26 .兩個串相等的充分必要條件是 。27 .設有n階對稱矩陣A,用數組s進行壓縮存儲，當i j時，A的數組元素a.相應 于數組s的數組元素的下標為 。(數組元素的下標從 1開始)28 .對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的、和 三項信息。三、問答題1 .簡述棧和一般線性表的區別。2 .簡述隊列和一般線性表的區另I。3 .鏈棧中為何不設頭結點?4 .利用一個棧，則:( 1) 如果輸入序列由A， B， C 組成，試給出全部可能的輸出序列和不可能的輸出序列。(2)如果輸入序列由A, B, C, D組成

29、，試給出全部可能的輸出序列和不可能的輸出序列。5 .用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234,為了得到1342出棧 順序，相應的S 和 X 操作串是什么？6 .有5個元素，其入棧次序為：A、B C、D E,在各種可能的出棧次序中，以元素 CD 最先的次序有哪幾個？7寫出以下運算式的后綴算術運算式 3x2+x-1/x+5 (A+B)*C-D/(E+F)+G8在什么情況下可以用遞歸解決問題？在寫遞歸程序時應注意什么？9.簡述廣義表和線性表的區別和聯系。四、程序填空題1 .在下面空格處填寫適當的語句，以使下面的循環隊列的入隊和出隊算法完整。define TRUE 1;define

30、FALSE 0;define MAXSIZE 100;typedef charelemtype;typedef structElemtype queue MAXSIZE;int front,rear;sequeuetype;Sequeuetype Q;int encqueue(sequeuetype*Q,elemtype x)if (");Printf( '' The cicular queue is full!n return(FALSE);elsereturn(TRUE); /*encqueue*/ elemtype del_cqueue(sequeuetype

31、*Q)if (Printf(The queue is empty !n")return(NULL);elseReturn(Q-queueQ- >front);/*del_cqueue*/2 .在下面空格處填寫適當的語句，以使下面的鏈式隊列取出元素的算法完整。int write(LinkQueue *q)QueueNode *p;if (q->front=q->rear)/* 隊空 */printf( "underflow ");exit(0);while (q->front->next != NULL) p=q->front-&

32、gt;next;printf("%4d ,p ->data);(2) (3) ;/*隊空時，頭尾指針指向頭結點*/五、綜合題1 .設棧S和隊列Q的初始狀態為空，元素 e1,e2,e3,e4,e5 和e6依次通過S, 一個元 素出棧后即進隊列 Q若6個元素出隊的序列是 e2,e4,e3,e6,e5,e1 ,則棧S的容量至少應 該是多少？2 .假設用循環單鏈表實現循環隊列，該隊列只使用一個尾指針rear ,其相應的存儲結構和基本算法如下；(1)初始化隊列initqueue(Q):建立一個新的空隊列Q。(2)入隊列enqueue(Q,x):將元素x插入到隊列Q中。(3)出隊列delq

33、ueue(Q):從隊列Q中退出一個元素。(4)取隊首元素gethead(Q):返回當前隊首元素。(5)判斷隊列是否為空：emptyqueue(Q)。(6)顯示隊列中元素：dispqueue(Q)。六、完成：實驗2棧、隊列、遞歸程序設計根據實驗要求（見教材 P203）認真完成本實驗，并提交實驗報告。數據結構（本）課程作業作業 3（本部分作業覆蓋教材第 6-7 章的內容）一、單項選擇題1. 假定一棵二叉樹中，雙分支結點數為 15 ，單分支結點數為30 ，則葉子結點數為（）。A 15 B 16 C 17 D 472二叉樹第k 層上最多有（ ）個結點。A 2kB 2k-1C 2k-1D 2k-13 二

34、叉樹的深度為k, 則二叉樹最多有（ ）個結點。A 2kB 2k-1C 2k-1D 2k-14 . 設某一二叉樹先序遍歷為abdec ，中序遍歷為dbeac ，則該二叉樹后序遍歷的順序是（）。A abdec B debac C debca D abedc5 樹最適合于用來表示（） 。A.線性結構的數據B.順序結構的數據C.元素之間無前驅和后繼關系的數據D.元素之間有包含和層次關系的數據6.設a,b為一棵二叉樹的兩個結點，在后續遍歷中， a在b前的條件是（）。A a 在 b 上方B a 在 b 下方C. a在b左方D. a在b右方7權值為1 ， 2， 6， 8 的四個結點構成的哈夫曼樹的帶權路徑長

35、度是（ ）。A 18 B 28 C 19 D 298將含有150 個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為 1 ，則編號為 69 的結點的雙親結點的編號為（ ）。A 33 B 34 C 35 D 369如果將給定的一組數據作為葉子數值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（ ）。A.哈夫曼樹B.平衡二叉樹C 二叉樹D 完全二叉樹10下列有關二叉樹的說法正確的是（ ）。A.二叉樹中度為0的結點的個數等于度為2的結點的個數加1B.二叉樹中結點個數必大于0C.完全二叉樹中，任何一個結點的度，或者為 0或者為2D.二叉樹的度是 211在一棵度為 3

36、的樹中，度為 3 的結點個數為2，度為2 的結點個數為1，則度為0的結點個數為（ ）。A 4 B 5 C 6 D 712 .在一棵度具有5層的滿二叉樹中結點總數為（）。A. 31 B .32 C .33 D . 1613 .利用n個值作為葉結點的權生成的哈夫曼樹中共包含有（）個結點。A. nB. n+1C. 2*nD. 2*n-114. 利用n個值作為葉結點的權生成的哈夫曼樹中共包含有（）個雙支結點。A. nB. n-1C. n+1D. 2*n-115. 利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉 子的最長帶權路徑長度為（）。1 . 18 B. 16 C. 1

37、2 D. 3016 .在一棵樹中，（）沒有前驅結點。A.分支結點 B .葉結點 C .樹根結點D .空結點17 .在一棵二叉樹中，若編號為 i的結點存在右孩子，則右孩子的順序編號為（）。A . 2iB. 2i-1 D . 2i+1 C . 2i+218 .設一棵哈夫曼樹共有 n個葉結點，則該樹有（）個非葉結點。A . nB. n-1 C , n+1 D . 2n19 .設一棵有n個葉結點的二叉樹，除葉結點外每個結點度數都為2,則該樹共有（）個結點。A 2nB. 2n-1 C . 2n+1 D . 2n+220 . 一棵完全二叉樹共有 5層，且第5層上有六個結點，該樹共有（）個結點。A . 20

38、B. 21 C . 23 D . 3021 .在一個圖G中，所有頂點的度數之和等于所有邊數之和的（）倍。A . 1/2 B . 1 C . 2 D . 422 .在一個有像圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A .鄰接矩陣表示法B .鄰接表表示法C.逆鄰接表表示法D .鄰接表和逆鄰接表23 .在圖的存儲結構表示中，表示形式唯一的是（）。A . n B . n 1 C . n 1 D . n/224 . 一個具有n個頂點的無向完全圖包含（）條邊。A . n （n1）B. n （n1）C.n （n1）/2 D. n （n1） /225 . 一個具有n個頂點的有向完全圖包含（）條

39、邊。A . n （n1）B. n （n1）C.n （n1）/2 D. n （n1） /226 .對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A . n B . n2 C , n 1 D .（n1）227 .對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大 小為（）。A . n B . e C . 2n D . 2e28 .對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接 表中的結點總數為（）。A . n B . e C . 2n D . 2e29 .在有向圖的鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。A .入邊B. 出邊

40、C.入邊和出邊D不是入邊也不是出邊30 .在有向圖的逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。C.入邊和出邊31.鄰接表是圖的一種（A .順序存儲結構C.索引存儲結構D）。BD.出邊.不是入邊也不是出邊.鏈式存儲結構.散列存儲結構32 .如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點，則該圖A .完全圖 B .連通圖 C .有回路 D . 一棵樹33.下列有關圖遍歷的說法不正確的是（）。A.連通圖的深度優先搜索是一個遞歸過程B.圖的廣度優先搜索中鄰接點的尋找具有“先進先出”的特征C.非連通圖不能用深度優先搜索法D.圖的遍歷要求每一頂點僅被訪問一次34 .無向圖的鄰接

41、矩陣是一個（）。A.對稱矩陣B .零矩陣 C .上三角矩陣D .對角矩陣35 .圖的深度優先遍歷算法類似于二叉樹的（）遍歷。A先序 B .中序 C .后序 D .層次36 .已知下圖所示的一個圖，若從頂點V1出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為（）。A . VMV4V3V3V5V6V7BC. MW4V3V5V3V6V7DV1V2V4V5V8V3V6V7V1V3V6V7V2V4V5V8二、填空題1 .結點的度是指結點所擁有的 。2 .樹的度是指。3 .度大于 0的結點稱作 或。4 .度等于 0的結點稱作 或。5 .在一棵樹中，每個結點的 或者說每個結點的 稱為該 結點的,簡

42、稱為孩子。6 . 一個結點稱為其后繼結點的 。7 .具有 的結點互稱為兄弟結點，簡稱為兄弟。8 .每個結點的所有子樹中的結點被稱為該結點的9 .從根結點到該結點所經分支上的所有結點稱為該結點的 。10 .樹的深度或高度是指 。11 . m(m 0)棵互不相交的樹的集合稱為 。12度為k的樹中的第i層上最多有 結點。13 .深度為k的二叉樹最多有 結點。14 .在一棵二叉樹中，如果樹中的每一層都是滿的，則稱此樹為 ; 但如果出最后一層外， 其余層都是滿的，并且最后一層是滿的， 或者是在缺少若干連續個結 點，則稱此二叉樹為 。15 .具有n個結點的完全二叉樹的深度是 。16 .先序遍歷二叉樹的的操

43、作定義為；若二叉樹為空，則為空操作，否則進行如下操作，訪問二叉樹的 ;先序遍歷二叉樹的 ,先序遍歷二叉樹的 1 7.中序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，中序遍歷二叉樹的 ;訪問而叉樹的 ,中序遍歷二叉樹的18 .后序遍歷二叉樹的的操作定義為；若二叉樹為空，則為空操作，否則進行如下操作，后序遍歷二叉樹的 ;后序遍歷二叉樹的 ,訪問而叉樹的 19 .將樹中結點賦上一個有著某種意義的實數，稱此實數為該結點的 。20 .樹的帶權路徑長度為樹中所有葉子結點的 。21 .哈夫曼樹又稱為 ,它是n個帶權葉子結點構成的所有二叉樹中帶 權路徑長度WPL。22 .若以4, 5

44、, 6, 7, 8作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度23 .具有m個葉子結點的哈夫曼樹共有 結點。24 .在圖中，任何兩個數據元素之間都可能存在關系，因此圖的數據元素之間是一種_的關系。25 .圖的鄰接矩陣表示法是用一個 來表示圖中頂點之間的相鄰關系。26 .鄰接表是圖中的每個頂點建立一個鄰接關系的 。27 .圖的遍歷是從圖的某一頂點出發，按照一定的搜索方法對圖中 各做. 訪問的過程。28 .圖的深度優先搜索遍歷類似于樹的 遍歷。29 .圖的廣度優先搜索類似于樹的 遍歷。30 .具有n個頂點的有向圖的鄰接矩陣，其元素個數為 。31 .具有n個頂點的無向圖至少有 條邊，才能確保其為

45、一個連通圖。32 .圖常用的兩種存儲結構是 和。33 . 一個AOVxJ (頂點活動圖)應該是一個 。即不應該帶有回路，否則回 路上的所有活動都。34 .用鄰接矩陣存儲有向圖G其第i行的所有元素之和等于頂點i的。35 .在有n個頂點的有向圖中，每個頂點的度最大可達 。36 .在一個帶權圖中，兩頂點之間的最段路徑最多經過 條邊。37 .為了實現圖的深度優先搜索遍歷，其非遞歸的算法中需要使用的一個輔助數據結構為。三、綜合題1.寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列O2.已知某二叉樹的先序遍歷結果是：A,B,D,GC,E,H,L, I ,K,M F和J,它的中序遍歷結果是： G, D, B

46、, A, L, H, E, K, I , M G F和J,請畫出這棵二叉樹，并寫 出該二叉樹后續遍歷的結果。3 .已知一棵完全二叉樹共有892個結點，求樹的高度葉子結點數單支結點數(4)最后一個非終端結點的序號4 .給出滿足下列條件的所有二叉樹。1）先序和中序相同2）中序和后序相同3）先序和后序相同5 .假設通信用的報文由9個字母A B C D、E、F、G H和I組成，它們出現的頻率分別是：10、 20、 5、 15、 8、 2、 3、 7和 30。請請用這9個字母出現的頻率作為權值求：（ 1）設計一棵哈夫曼樹；（ 2）計算其帶權路徑長度WPL；（ 3）寫出每個字符的哈夫曼編碼。6請根據以下帶

47、權有向圖G（1）給出從結點v1出發分別按深度優先搜索遍歷G和廣度優先搜索遍歷G所得的結點序列；（ 2）給出G 的一個拓撲序列；（ 3）給出從結點v1 到結點 v8 的最短路徑。7 .已知無向圖G描述如下：G=（ V， E）V=V1， V2， V3， V4， V5V2， V5） ， （ V3， V4） ， （ V3， V5） E= （ V1， V2） ， （ V1， V4） ， （ V2， V4） ， （ V3， V4） ，(1)畫出G的圖示；(2)然后給出G的鄰接矩陣和鄰接表;(3)寫出每個頂點的度。8 .回答下列問題：對于存儲結構采用鄰接矩陣的無向圖，如何判斷下列有關問題?圖中有多少條邊？任

48、意兩頂點間是否有邊相連？任意一個頂點的度是多少？對于存儲結構采用鄰接表的有向圖，如何判斷下列有關問題？圖中有多少條邊？圖中是否存在從 V到V的邊？如何求頂點 V的入度和出度？四、程序填空題1 .下面函數的功能是返回二叉樹BT中值為X的結點所在的層號，請在劃有橫線的地方填寫合適內容。int NodeLevel(struct BinTreeNode* BT, char X)if(BT=NULL) return 0;/*空樹的層號為 0*/else if(BT->data=X) return 1; /*根結點的層號為 1*/* 向子樹中查找X結點*/ else int c1=NodeLevel

49、(BT->left,X);if(c1>=1);int c2=(2) if (3)；/若樹中不存在X結點則返回0else return 0;2 .下面函數的功能是按照圖的深度優先搜索遍歷的方法，輸出得到該圖的生成樹中的 各條邊，請在劃有橫線的地方填寫合適內容。void dfstree(adjmatrix GA, int i, int n)int j；visitedi=1;(1) if(GAij!=0 && GAij!=MaxValue && !visitedj)printf("(%d,%d)%d,",i,j,GAij);(2) 五、

50、算法設計題1 .寫一個將一棵二叉樹復制給另一棵二叉樹的算法。2 .根據下面函數聲明編寫出求一棵二叉樹中葉子結點總數的算法，該總數值由函數返 回。假定參數BT初始指向二叉樹的根結點。int BTreeLeafCount(struct BTreeNode* BT);3 .已知有n個頂點的有向圖鄰接表，設計算法分別實現下列功能:(1)求出圖G中每個頂點的出度、入度。(2)計算圖中度為0的頂點數。六、完成：實驗3棧、隊列、遞歸程序設計實驗4圖的存儲方式和應用根據實驗要求（見教材 P203）認真完成本實驗，并提交實驗報告。數據結構（本）課程作業（ 4）8-9 章的內容）的線性表。 索引存儲 順序存儲或鏈

51、接存儲一、單項選擇題1. 順序查找方法適合于存儲結構為（A.散列存儲BC.散列存儲或索引存儲D2對線性表進行二分查找時，要求線性表必須（）。A 以順序存儲方式B.以鏈接存儲方式C 以順序存儲方式 ，且數據元素有序D.以鏈接存儲方式，且數據元素有序3 如果要求一個線性表既能較快地查找，又能動態適應變化要求，可以采用（）查找方法。A.順序B.分塊C.折半D.散列4 . 對于一個線性表，若要求既能進行較快地插入和刪除，又要求存儲結構能夠反映數據元素之間的邏輯關系，則應該（ ） 。A 以順序存儲方式B以鏈接存儲方式C.以索引存儲方式D.以散列存儲方式5 采用順序查找方法查找長度為n 的線性表時，每個元

52、素的平均查找長度為（ ） 。A nB n/2C （n+1）/2 D （n-1）/26 采用折半查找方法查找長度為 n 的線性表時，每個元素的平均查找長度為（ ） 。A O（n*n）B O（nlog 2n）C O（n）D s（log 2n）7 哈希函數有一個共同的性質，即函數值應當以（）取其值域的每個值。A.最大概率B .最小概率C .平均概率D .同等概率8 有一個長度為 10 的有序表， 按折半查找對該表進行查找， 在等概率情況下查找成功）。A 29/10 B 31/10 C 26/10 D 29/99已知一個有序表為11,22,33,44,55,66,77,88,99 ，則順序查找元素55

53、 需要比較）次。A 3 B 4 C 5 D 69 0順序查找法與二分查找法對存儲結構的要求是（）。A.順序查找與二分查找均只是適用于順序表B.順序查找與二分查找均既適用于順序表，也適用于鏈表C.順序查找只是適用于順序表D.二分查找適用于順序表從空二叉樹開始逐個插入數據來形成二叉排序樹，）。 37,24,12,30,53,45,96 30,24,12,37,45,96,5311有數據 53,30,37,12,45,24,96 若希望高度最小，應該選擇的序列是（A 45,24,53,12,37,96,30BC 12,24,30,37,45,53,96D12對有 18 個元素的有序表作二分（折半）查找，則查找 為（ ）。A3 的比較序列的下標可能A 1 、 2、 3BC 9 、 5、 3D13. 對于順序存儲的有序表則查找元素26 的比較次數是（ 9 、 5、 2、 3 9 、 4、 2、 35 ， 12， 20