2023年廣東省理論資料高階

1、(1)p->rchild(2)p->lchild(3)p->lchild(4)addq(q,p->lchild)(5)addq(q,p->rchild)

25.(1)t->rchild!=null(2)t->rchild!=null(3)n0++(4)count(t->lchild)(5)count(t->rchild)

26..(1)top++(2)stack[top]=p->rchild(3)top++(4)stack[top]=p->lchild

27. (1)*ppos //根結點（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

2、(1)p->rchild(2)p->lchild(3)p->lchild(4)addq(q,p->lchild)(5)addq(q,p->rchild)

25.(1)t->rchild!=null(2)t->rchild!=null(3)n0++(4)count(t->lchild)(5)count(t->rchild)

26..(1)top++(2)stack[top]=p->rchild(3)top++(4)stack[top]=p->lchild

27. (1)*ppos //根結點（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1

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

int bpgraph (adjmatrix g)

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

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

q[1]=1; r=1; s[1]=1;//頂點1放入集合s1while(f //鄰接點入佇列else if (s[j]==s[v]) return(0);} //非二部圖}//if (!visited[v])}//while

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

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

4、對一般二叉樹，僅根據乙個先序、中序、後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。

void pretopost(elemtype pre ,post,int l1,h1,l2,h2)

//將滿二叉樹的先序序列轉為後序序列，l1,h1,l2,h2是序列初始和最後結點的下標。

}//pretopost32..葉子結點只有在遍歷中才能知道，這裡使用中序遞迴遍歷。設定前驅結點指標pre，初始為空。

第乙個葉子結點由指標head指向，遍歷到葉子結點時，就將它前驅的rchild指標指向它，最後葉子結點的rchild為空。linkedlist head,pre=null; //全域性變數linkedlist inorder(bitree bt)

//中序遍歷二叉樹bt，將葉子結點從左到右鏈成乙個單鏈表，表頭指標為head //處理第乙個葉子結點else //將葉子結點鏈入鍊錶inorder(bt->rchild中序遍歷左子樹pre->rchild=null設定鍊錶尾}

return(head); } //inorder

時間複雜度為o(n),輔助變數使用head和pre,棧空間複雜度o(n)

5、#define maxsize棧空間容量

void inouts(int s[maxsize])

//s是元素為整數的棧，本演算法進行入棧和退棧操作。

else s[++top]=x; //x入棧。else //讀入的整數等於-1時退棧。

else printf(「出棧元素是%d\n」,s[top--])；}}

}//演算法結