1、設有兩個集合a和集合b,要求設計生成集合c=a∩b的演算法,其中集合a、b和c用鏈式儲存結構表示。
typedef struct node lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)}}
2、約瑟夫環問題(josephus問題)是指編號為1、2、…,n的n(n>0)個人按順時針方向圍坐成一圈,現從第s個人開始按順時針方向報數,數到第m個人出列,然後從出列的下乙個人重新開始報數,數到第m的人又出列,…,如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法,模擬此過程。
#include<>
typedef int datatype;
typedef struct node
listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
while(k1->next!=k1) /*當迴圈鍊錶中的結點個數大於1時*/
pre->next=p->next; /*輸出該結點,並刪除該結點*/
printf("%4d",p->data);
free(p);
k1=pre->next新的報數起點*/
} printf("%4d",k1->data); /*輸出最後乙個結點*/
free(k1);
}main()
r->next=head; /*生成迴圈鍊錶*/
jose(head,s,m); /*呼叫函式*/
}}3、 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上,層次遍歷序列中的每個結點都是「區域性根」。確定根後,到二叉樹的中序序列中,查到該結點,該結點將二叉樹分為「左根右」三部分。
若左、右子樹均有,則層次序列根結點的後面應是左右子樹的根;若中序序列中只有左子樹或只有右子樹,則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣,定義乙個全域性變數指標r,指向層次序列待處理元素。演算法中先處理根結點,將根結點和左右子女的資訊入佇列。
然後,在佇列不空的條件下,迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下:
typedef struct
qnode;
bitree creat(datatype in,level,int n)
//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數
qnode s,qq是元素為qnode型別的佇列,容量足夠大
init(q); int r=0; //r是層次序列指標,指向當前待處理的結點
bitree p=(bitree)malloc(sizeof(binode生成根結點
p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料
for (i=0; i if (in[i]==level[0]) break;
if (i==0) //根結點無左子樹,遍歷序列的1—n-1是右子樹
else if (i==n-1) //根結點無右子樹,遍歷序列的1—n-1是左子樹
else //根結點有左子樹和右子樹
while (!empty(q)) //當佇列不空,進行迴圈,構造二叉樹的左右子樹
else if (i==
else
}//結束while (!empty(q))
return(p);
}//演算法結束
4、因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指標高於儲存最高棧頂指標的值時,則將該棧倒入輔助棧中,輔助棧始終儲存最長路徑長度上的結點,直至後序遍歷完畢,則輔助棧中內容即為所求。
void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度
//沿左分枝向下
if(tag[top]==1) //當前結點的右分枝已遍歷
//保留當前最長路徑到l棧,記住最高棧頂指標,退棧
} else if(top>0) //沿右子分枝向下
}//while(p!=null||top>0)
}//結束longestpath
5、兩棵空二叉樹或僅有根結點的二叉樹相似;對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
{if(p==null && q==null) return (1);
else if(!p && q || p && !q) return (0);
2023年陝西省資料總結高階
1 兩棵空二叉樹或僅有根結點的二叉樹相似 對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。int similar bitree p,q 判斷二叉樹p和q是否相似 結束similar 2 請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法,設二叉樹用llink rlink法儲存。3 給定n個村莊之間...
2023年陝西省資料總結加強
1 設t是一棵滿二叉樹,編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。2 兩棵空二叉樹或僅有根結點的二叉樹相似 對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。int similar bitree p,q 判斷二叉樹p和q是否相似 結束similar 3 因為後序遍歷棧中保留當前結點...
2023年陝西省資料總結大綱
1 本題應使用深度優先遍歷,從主調函式進入dfs v 時 開始記數,若退出dfs 前,已訪問完有向圖的全部頂點 設為n個 則有向圖有根,v為根結點。將n個頂點從1到n編號,各呼叫一次dfs 過程,就可以求出全部的根結點。題中有向圖的鄰接表儲存結構 記頂點個數的變數 以及訪問標記陣列等均設計為全域性變...