4/4數據結構作業題答案出錯，本寶寶概不負責，應該沒錯

作業題

一、填空題：

(1)一個有向圖G中若有弧、和,則在圖G的拓撲序列中，頂點vi,vj和vk的相對位置為_____i,j,k_____。

(2)隊列是一種_線性的結構。

(3)在單鏈表中，指針p所指結點為最后一個結點的條件是p->next==NULL。

(4)二路歸并排序的時間復雜度是__nlogn______。

(5)棧是一種_線性的結構。

(6)由____樹____轉換成二叉樹時，其根結點的右子樹總是空的。

(7)直接選擇排序是不穩定的，其時間復雜性為__n2______。

(8)對無向圖，其鄰接矩陣是一個關于__對角線______對稱的矩陣。

(9)由________轉換成二叉樹時，其根結點的右子樹總是空的。

(10)歸并排序要求待排序列由若干個____有序_______的子序列組成。

(11)已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有___12_______個葉子的結點。

二、單項選擇題：

(1)設有一個無向圖G=（V，E）和G’=（V’，E’）如果G’為G的生成樹，則下面不正確的說法是（B）。

A.G’為G的子圖；

B.G’為G的邊通分量；

C.G’為G的極小連通子圖且V’=V；

D.G’為G的一個無環子圖。

(2)單鏈表的一個存儲結點包含（D）。

A.數據域或指針域；

B.指針域或鏈域；

C.指針域和鏈域；

D.數據域和鏈域。

(3)二分查找要求被查找的表是（C）。

A.鍵值有序的鏈接表；

B.鏈接表但鍵值不一定有序；

C.鍵值有序的順序表；

D.順序表但鍵值不一定有序。

(4)設指針P指向雙鏈表的某一結點，則雙鏈表結構的對稱性可用（C）式來刻畫。

A.p->prior->next->==p->next->next；

B.p->prior->prior->==p->next->prior；

C.p->prior->next->==p->next->prior；

D.p->next->next==p->prior->prior。

(5)順序查找法適合于（D）存儲結構的查找表。

A.壓縮；

B.散列；

C.索引；

D.順序或鏈式。

(6)在循環鏈表中，將頭指針改設為尾指針（rear）后，其頭結點和尾結點的存儲位置分別是（B）。

A.real和rear->next->next；

B.rear->next和rear；

C.rear->next->next和rear；

D.rear和rear->next。

（7）堆是一個鍵值序列{k1,k2,…,kn},對i=1,2,…,|_n/2_|,滿足(C)。

A.ki≤k2i≤k2i+1；

B.kinext!=NULL)

{_____p=p->next___________;@

j++;

}

return(j);/*回傳表長*/

2.以下為單鏈表按序號查找的運算，分析算法，請在____處填上正確的語句。

pointerfind_lklist(lklisthead,inti)

{p=head;j=0;

while(p->next!=null&&jnext;j++;}

if(i==j)return(p);

elsereturn(NULL);

}

}

3.以下為單鏈表的插入運算，分析算法，請在____處填上正確的語句。

voidinsert_lklist(lklisthead,datatypex,inti)

/*在表head的第i個位置上插入一個以x為值的新結點*/

{p=find_lklist(head,i-1);

if(p==NULL)error(“不存在第i個位置”)；

else{s=mailloc(size);s->data=x;

s->next=p->next；@

p->next=s;

}

}

4.程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復制到一個棧s2當中去，請完成程序。

SeqStackS1,S2,tmp;

DataTypex;

...//假設棧tmp和S2已做過初始化

while(!StackEmpty(

Push(@

}

while(!StackEmpty(

Push(

Push(

}

5.以下程序段采用先根遍歷方法求二叉樹的葉子數，請在橫線處填充適當的語句。

Voidcountleaf(bitreptrt,int*count)/*根指針為t，假定葉子數count的初值為0*/

{if(t!=NULL)

{if((t->lchild==NULL)

countleaf(t->lchild,

countleaf(t->rchild,inti;

InitStack(

while(!StackEmpty(S))

if(i=Pop(@

while(!StackEmpty(Push(S,i);

}

}

7.以下是直接選擇排序的算法。請分析算法，并在橫線上填充適當的語句。

voidselect(listr,intn)

{for(i=1;ir[j])k=j;

if(_k!=I)swap(r[k],r[i]）;/*函數swap(r[k],r[i]）交換r[k]和r[i]的位置*/

}

8.以下為冒泡排序的算法。請分析算法，并在________上填充適當的語句。

voidbulbblesort(intn,listr)/*flag為特征位，定義為布爾型*/

{for(i=1;i

4.設某密碼電文由8個字母組成，每個字母在電文中的出現頻率分別是22，15，2，5，17，11，9，19，試為這8個字母設計相應的哈夫曼編碼。

19=00

22=01

2=11000

15=101

11=100

5=11001

9=1101

17=111

5.請用類C語言編寫從單鏈表中刪除表頭元素的算