數(shù)據(jù)結(jié)構(gòu)作業(yè)題

4/4數(shù)據(jù)結(jié)構(gòu)作業(yè)題答案出錯(cuò)，本寶寶概不負(fù)責(zé)，應(yīng)該沒錯(cuò)

作業(yè)題

一、填空題：

(1)一個(gè)有向圖G中若有弧、和,則在圖G的拓?fù)湫蛄兄?，頂點(diǎn)vi,vj和vk的相對(duì)位置為_____i,j,k_____。

(2)隊(duì)列是一種_線性的結(jié)構(gòu)。

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

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

(5)棧是一種_線性的結(jié)構(gòu)。

(6)由____樹____轉(zhuǎn)換成二叉樹時(shí)，其根結(jié)點(diǎn)的右子樹總是空的。

(7)直接選擇排序是不穩(wěn)定的，其時(shí)間復(fù)雜性為__n2______。

(8)對(duì)無向圖，其鄰接矩陣是一個(gè)關(guān)于__對(duì)角線______對(duì)稱的矩陣。

(9)由________轉(zhuǎn)換成二叉樹時(shí)，其根結(jié)點(diǎn)的右子樹總是空的。

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

(11)已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹中有___12_______個(gè)葉子的結(jié)點(diǎn)。

二、單項(xiàng)選擇題：

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

A.G’為G的子圖；

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

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

D.G’為G的一個(gè)無環(huán)子圖。

(2)單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含（D）。

A.數(shù)據(jù)域或指針域；

B.指針域或鏈域；

C.指針域和鏈域；

D.數(shù)據(jù)域和鏈域。

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

A.鍵值有序的鏈接表；

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

C.鍵值有序的順序表；

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

(4)設(shè)指針P指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱性可用（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）存儲(chǔ)結(jié)構(gòu)的查找表。

A.壓縮；

B.散列；

C.索引；

D.順序或鏈?zhǔn)健?/p>

(6)在循環(huán)鏈表中，將頭指針改設(shè)為尾指針（rear）后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是（B）。

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

B.rear->next和rear；

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

D.rear和rear->next。

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

A.ki≤k2i≤k2i+1；

B.kinext!=NULL)

{_____p=p->next___________;@

j++;

}

return(j);/*回傳表長(zhǎng)*/

2.以下為單鏈表按序號(hào)查找的運(yùn)算，分析算法，請(qǐng)?jiān)赺___處填上正確的語句。

pointerfind_lklist(lklisthead,inti)

{p=head;j=0;

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

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

elsereturn(NULL);

}

}

3.以下為單鏈表的插入運(yùn)算，分析算法，請(qǐng)?jiān)赺___處填上正確的語句。

voidinsert_lklist(lklisthead,datatypex,inti)

/*在表head的第i個(gè)位置上插入一個(gè)以x為值的新結(jié)點(diǎn)*/

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

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

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

s->next=p->next；@

p->next=s;

}

}

4.程序段的功能是利用tmp棧將一個(gè)非空棧s1的所有元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去，請(qǐng)完成程序。

SeqStackS1,S2,tmp;

DataTypex;

...//假設(shè)棧tmp和S2已做過初始化

while(!StackEmpty(

Push(@

}

while(!StackEmpty(

Push(

Push(

}

5.以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請(qǐng)?jiān)跈M線處填充適當(dāng)?shù)恼Z句。

Voidcountleaf(bitreptrt,int*count)/*根指針為t，假定葉子數(shù)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.以下是直接選擇排序的算法。請(qǐng)分析算法，并在橫線上填充適當(dāng)?shù)恼Z句。

voidselect(listr,intn)

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

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

}

8.以下為冒泡排序的算法。請(qǐng)分析算法，并在________上填充適當(dāng)?shù)恼Z句。

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

{for(i=1;i

4.設(shè)某密碼電文由8個(gè)字母組成，每個(gè)字母在電文中的出現(xiàn)頻率分別是22，15，2，5，17，11，9，19，試為這8個(gè)字母設(shè)計(jì)相應(yīng)的哈夫曼編碼。

19=00

22=01

2=11000

15=101

11=100

5=11001

9=1101

17=111

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