2023年河北省資料總結入門

1、將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。

int bpgraph (adjmatrix g)

判斷以鄰接矩陣表示的圖g是否是二部圖。

//初始化，各頂點未確定屬於那個集合

q[1]=1; r=1; s[1]=1;//頂點1放入集合s1

while(f //鄰接點入佇列

else if (s[j]==s[v]) return(0);} //非二部圖

}//if (!visited[v])

}//while

return(1); }//是二部圖

[演算法討論] 題目給的是連通無向圖，若非連通，則演算法要修改。

2、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是「區域性根」。確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為「左根右」三部分。

若左、右子樹均有，則層次序列根結點的後面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣，定義乙個全域性變數指標r，指向層次序列待處理元素。演算法中先處理根結點，將根結點和左右子女的資訊入佇列。

然後，在佇列不空的條件下，迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下：

typedef struct

qnode;

bitree creat(datatype in,level,int n)

//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數

qnode s,qq是元素為qnode型別的佇列，容量足夠大

init(q); int r=0; //r是層次序列指標，指向當前待處理的結點

bitree p=(bitree)malloc(sizeof(binode生成根結點

p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料

for (i=0; i if (in[i]==level[0]) break;

if (i==0) //根結點無左子樹，遍歷序列的1—n-1是右子樹

else if (i==n-1) //根結點無右子樹，遍歷序列的1—n-1是左子樹

else //根結點有左子樹和右子樹

while (!empty(q)) //當佇列不空，進行迴圈，構造二叉樹的左右子樹

else if (i==

else

}//結束while (!empty(q))

return(p);

}//演算法結束

3、氣泡排序演算法是把大的元素向上移（氣泡的上浮），也可以把小的元素向下移（氣泡的下沉）請給出上浮和下沉過程交替的氣泡排序演算法。

48.有n個記錄儲存在帶頭結點的雙向鍊錶中，現用雙向起泡排序法對其按上公升序進行排序，請寫出這種排序的演算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）

4、有一種簡單的排序演算法，叫做計數排序（count sorting）。這種排序演算法對乙個待排序的表(用陣列表示)進行排序，並將排序結果存放到另乙個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數排序演算法針對表中的每個記錄，掃瞄待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小，假設針對某乙個記錄，統計出的計數值為c，那麼，這個記錄在新的有序表中的合適的存放位置即為c。

(1) (3分)給出適用於計數排序的資料表定義;

(2) (7分)使用pascal或c語言編寫實現計數排序的演算法；

(3) (4分)對於有n個記錄的表，關鍵碼比較次數是多少?

(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什麼?

2023年河北省資料總結入門

2023年河北省資料總結入門

2023年河北省資料總結入門

2023年河北省資料總結入門

相關推薦