1、對二叉樹的某層上的結點進行運算,採用佇列結構按層次遍歷最適宜。
int leafklevel(bitree bt, int k) //求二叉樹bt 的第k(k>1) 層上葉子結點個數
//last移到指向下層最右一元素
if(level>k) return (leaf層數大於k 後退出執行
}//while }//結束leafklevel
2、陣列a和b的元素分別有序,欲將兩陣列合併到c陣列,使c仍有序,應將a和b拷貝到c,只要注意a和b陣列指標的使用,以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。
void union(int a,b,c,m,n)
//整型陣列a和b各有m和n個元素,前者遞增有序,後者遞減有序,本演算法將a和b歸併為遞增有序的陣列c。
演算法結束
4、要求二叉樹按二叉鍊錶形式儲存。15分
(1)寫乙個建立二叉樹的演算法。(2)寫乙個判別給定的二叉樹是否是完全二叉樹的演算法。
bitree creat建立二叉樹的二叉鍊錶形式的儲存結構
else error(「輸入錯誤」);
return(bt);
}//結束 bitree
int judgecomplete(bitree bt) //判斷二叉樹是否是完全二叉樹,如是,返回1,否則,返回0
//while
return 1; } //judgecomplete
3、請設計乙個演算法,要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表,表頭指標為head。 二叉樹按二叉鍊錶方式儲存,鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時、空複雜度。
4、設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)
//last移到指向下層最右一元素
if(level>k) return (leaf層數大於k 後退出執行
}//while }//結束leafklevel
6、 連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊,最小生成樹是邊上權值之和最小的生成樹。故可按權值從大到小對邊進行排序,然後從大到小將邊刪除。每刪除一條當前權值最大的邊後,就去測試圖是否仍連通,若不再連通,則將該邊恢復。
若仍連通,繼續向下刪;直到剩n-1條邊為止。
void spntree (adjlist g)
//用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。
node; //設頂點資訊就是頂點編號,權是整型數
node edge;
scanf( "%d%d",&e,&n) ; //輸入邊數和頂點數。
for (i=1;i<=e;i輸入e條邊:頂點,權值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge
ge[i].w);
for (i=2;i<=e;i++) //按邊上的權值大小,對邊進行逆序排序。
//測試下一條邊edge[k],權值置0表示該邊被刪除
k++; //下條邊
}//while
}//演算法結束。
connect()是測試圖是否連通的函式,可用圖的遍歷實現,
7、設指標變數p指向雙向鍊錶中結點a,指標變數q指向被插入結點b,要求給出在結點a的後面插入結點b的操作序列(設雙向鍊錶中結點的兩個指標域分別為llink和rlink)。
8、氣泡排序演算法是把大的元素向上移(氣泡的上浮),也可以把小的元素向下移(氣泡的下沉)請給出上浮和下沉過程交替的氣泡排序演算法。
48.有n個記錄儲存在帶頭結點的雙向鍊錶中,現用雙向起泡排序法對其按上公升序進行排序,請寫出這種排序的演算法。(注:雙向起泡排序即相鄰兩趟排序向相反方向起泡)
9、設一棵二叉樹的結點結構為 (llink,info,rlink),root為指向該二叉樹根結點的指標,p和q分別為指向該二叉樹中任意兩個結點的指標,試編寫一演算法ancestor(root,p,q,r),該演算法找到p和q的最近共同祖先結點r。
10、設有一組初始記錄關鍵字序列(k1,k2,…,kn),要求設計乙個演算法能夠在o(n)的時間複雜度內將線性表劃分成兩部分,其中左半部分的每個關鍵字均小於ki,右半部分的每個關鍵字均大於等於ki。
void quickpass(int r, int s, int t)
node;
int n2,nl,nr,n0;
void count(node *t)
lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
//沿左分枝向下
if(tag[top]==1) //當前結點的右分枝已遍歷
//保留當前最長路徑到l棧,記住最高棧頂指標,退棧
}else if(top>0) //沿右子分枝向下
}//while(p!=null||top>0)
}//結束longestpath
2023年湖南省資料總結要領
1 二路插入排序是將待排關鍵字序列r 1.n 中關鍵字分二路分別按序插入到輔助向量d 1.n 前半部和後半部 注 向量d可視為迴圈表 其原則為,先將r l 賦給d 1 再從r 2 記錄開始分二路插入。編寫實現二路插入排序演算法。2 設t是一棵滿二叉樹,編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞...
2023年湖南省資料總結高階
free p k1 pre next新的報數起點 printf 4d k1 data 輸出最後乙個結點 free k1 main r next head 生成迴圈鍊錶 jose head,s,m 呼叫函式 3 因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指...
2023年湖南省資料總結綱要
1 有一種簡單的排序演算法,叫做計數排序 count sorting 這種排序演算法對乙個待排序的表 用陣列表示 進行排序,並將排序結果存放到另乙個新的表中。必須注意的是,表中所有待排序的關鍵碼互不相同,計數排序演算法針對表中的每個記錄,掃瞄待排序的表一趟,統計表中有多少個記錄的關鍵碼比該記錄的關鍵...