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)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

2、給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連線，邊上的wij表示這條道路的長度，現在要從這n個村莊中選擇乙個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計乙個解答上述問題的演算法，並應用該演算法解答如圖所示的例項。（20分）

3、因為後序遍歷棧中保留當前結點的祖先的資訊，用一變數儲存棧的最高棧頂指標，每當退棧時，棧頂指標高於儲存最高棧頂指標的值時，則將該棧倒入輔助棧中，輔助棧始終儲存最長路徑長度上的結點，直至後序遍歷完畢，則輔助棧中內容即為所求。

void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度

//沿左分枝向下

if(tag[top]==1) //當前結點的右分枝已遍歷

//保留當前最長路徑到l棧，記住最高棧頂指標，退棧

} else if(top>0) //沿右子分枝向下

}//while(p!=null||top>0)

}//結束longestpath

4、設指標變數p指向雙向鍊錶中結點a，指標變數q指向被插入結點b，要求給出在結點a的後面插入結點b的操作序列（設雙向鍊錶中結點的兩個指標域分別為llink和rlink）。

5、我們用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

6、設一棵樹t中邊的集合為，要求用孩子兄弟表示法（二叉鍊錶）表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。