2023年河北省資料總結大綱

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

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

2、給出折半查詢的遞迴演算法，並給出演算法時間複雜度性分析。

3、(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)top2) 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

4、設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹並給出構造過程。

5、(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)top2) 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

6、請設計乙個演算法，要求該演算法把二叉樹的葉子結點按從左到右的順序連成乙個單鏈表，表頭指標為head。二叉樹按二叉鍊錶方式儲存，鏈結時用葉子結點的右指標域來存放單鏈表指標。分析你的演算法的時、空複雜度。

7、設有兩個集合a和集合b，要求設計生成集合c=a∩b的演算法，其中集合a、b和c用鏈式儲存結構表示。

typedef struct node lklist;

void intersection(lklist *ha,lklist *hb,lklist *&hc)}}

8、後序遍歷最後訪問根結點，即在遞迴演算法中，根是壓在棧底的。採用後序非遞迴演算法，棧中存放二叉樹結點的指標，當訪問到某結點時，棧中所有元素均為該結點的祖先。本題要找p和q 的最近共同祖先結點r ,不失一般性，設p在q的左邊。

後序遍歷必然先遍歷到結點p，棧中元素均為p的祖先。將棧拷入另一輔助棧中。再繼續遍歷到結點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第乙個匹配（即相等）的元素就是結點p 和q的最近公共祖先。

typedef struct

stack;

stack s,s1;//棧，容量夠大

bitree ancestor(bitree root,p,q,r)//求二叉樹上結點p和q的最近的共同祖先結點r。

//沿左分枝向下

if(bt==p) //不失一般性，假定p在q的左側,遇結點p時，棧中元素均為p的祖先結點

//將棧s的元素轉入輔助棧s1 儲存

if(bt==q) //找到q 結點。

for(i=top;i>0;i--)//；將棧中元素的樹結點到s1去匹配

｝while(top!=0 && s[top].tag==1) top退棧

if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍歷

}//結束while(bt!=null ||top>0)

return(null);//ｑ、p無公共祖先

｝//結束ancestor