1、二路插入排序是將待排關鍵字序列r[1..n]中關鍵字分二路分別按序插入到輔助向量d[1..n]前半部和後半部(注:
向量d可視為迴圈表),其原則為,先將r[l]賦給d[1],再從r[2] 記錄開始分二路插入。編寫實現二路插入排序演算法。
2、設t是給定的一棵二叉樹,下面的遞迴程式count(t)用於求得:二叉樹t中具有非空的左,右兩個兒子的結點個數n2;只有非空左兒子的個數nl;只有非空右兒子的結點個數nr和葉子結點個數n0。n2、nl、nr、n0都是全域性量,且在呼叫count(t)之前都置為0.
typedef struct node
node;
int n2,nl,nr,n0;
void count(node *t)
26.樹的先序非遞迴演算法。
void example(b)
btree *b;
if (p->lchild!=null)
(3)___; (4)__;
}}}}
3、我們用l代表最長平台的長度,用k指示最長平台在陣列b中的起始位置(下標)。用j記住區域性平台的起始位置,用i指示掃瞄b陣列的下標,i從0開始,依次和後續元素比較,若區域性平台長度(i-j)大於l時,則修改最長平台的長度k(l=i-j)和其在b中的起始位置(k=j),直到b陣列結束,l即為所求。
void platform (int b[ ], int n)
//求具有n個元素的整型陣列b中最長平台的長度。
//區域性最長平台
i++; j=i新平台起點
printf(「最長平台長度%d,在b陣列中起始下標為%d」,l,k);
}// platform
4、 將頂點放在兩個集合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); }//是二部圖
[演算法討論] 題目給的是連通無向圖,若非連通,則演算法要修改。
5、證明由二叉樹的中序序列和後序序列,也可以唯一確定一棵二叉樹。
29. ① 試找出滿足下列條件的二叉樹
1)先序序列與後序序列相同 2)中序序列與後序序列相同
3)先序序列與中序序列相同 4)中序序列與層次遍歷序列相同
6、若第n件物品能放入揹包,則問題變為能否再從n-1件物品中選出若干件放入揹包(這時揹包可放入物品的重量變為s-w[n])。若第n件物品不能放入揹包,則考慮從n-1件物品選若干件放入揹包(這時揹包可放入物品仍為s)。若最終s=0,則有一解;否則,若s<0或雖然s>0但物品數n<1,則無解。
(1)s-w[n],n-1 //knap(s-w[n],n-1)=true
(2)s,n-1knap←knap(s,n-1)
7、有一種簡單的排序演算法,叫做計數排序(count sorting)。這種排序演算法對乙個待排序的表(用陣列表示)進行排序,並將排序結果存放到另乙個新的表中。必須注意的是,表中所有待排序的關鍵碼互不相同,計數排序演算法針對表中的每個記錄,掃瞄待排序的表一趟,統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小,假設針對某乙個記錄,統計出的計數值為c,那麼,這個記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用於計數排序的資料表定義;
(2) (7分)使用pascal或c語言編寫實現計數排序的演算法;
(3) (4分)對於有n個記錄的表,關鍵碼比較次數是多少?
(4) (3分)與簡單選擇排序相比較,這種方法是否更好?為什麼?
8、4、 void linklist_reverse(linklist &l)
//鍊錶的就地逆置;為簡化演算法,假設表長大於2
q->next=p;s->next=q;l->next=s;
}//linklist_reverse
2023年廣東省資料總結章程
1 因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退 棧時,棧頂指標高於儲存最高棧頂指標的值時,則將該棧倒入輔助棧中,輔助棧始終儲存最 長路徑長度上的結點,直至後序遍歷完畢,則輔助棧中內容即為所求。void longestpath bitree bt 求二叉樹中的第一條...
2019遼寧省資料庫入門入門
1 陣列a和b的元素分別有序,欲將兩陣列合併到c陣列,使c仍有序,應將a和b拷貝到c,只要注意a和b陣列指標的使用,以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。void union int a,b,c,m,n 整型陣列a和b各有m和n個元素,前者遞增有序,後者遞減有序,本演算法將a...
2023年廣東省資料高階
1 設一棵樹t中邊的集合為,要求用孩子兄弟表示法 二叉鍊錶 表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。2 假設以鄰接矩陣作為圖的儲存結構,編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路,若存在,則以頂點序列的方式輸出該迴路 找到一條即可 注 圖中不存在頂點到自己的弧 有向圖判斷迴路要比...