2019台灣省資料簡介基礎

2022-06-15 16:54:02 字數 3034 閱讀 6909

1、根據二叉排序樹中序遍歷所得結點值為增序的性質,在遍歷中將當前遍歷結點與其前驅結點值比較,即可得出結論,為此設全域性指標變數pre(初值為null)和全域性變數flag,初值為true。若非二叉排序樹,則置flag為false。

#define true 1

#define false 0

typedef struct node

*btree;

void judgebst(btree t,int flag)

// 判斷二叉樹是否是二叉排序樹,本演算法結束後,在呼叫程式中由flag得出結論。

//不是完全二叉樹

judgebst (t->rlink,flag);// 中序遍歷右子樹

}//judgebst演算法結束

2、對二叉樹的某層上的結點進行運算,採用佇列結構按層次遍歷最適宜。

int leafklevel(bitree bt, int k) //求二叉樹bt 的第k(k>1) 層上葉子結點個數

//last移到指向下層最右一元素

if(level>k) return (leaf層數大於k 後退出執行

}//while }//結束leafklevel

3、設從鍵盤輸入一整數的序列:a1, a2, a3,…,an,試編寫演算法實現:用棧結構儲存輸入的整數,當ai≠-1時,將ai進棧;當ai=-1時,輸出棧頂整數並出棧。

演算法應對異常情況(入棧滿等)給出相應的資訊。

設有乙個揹包可以放入的物品重量為s,現有n件物品,重量分別為w1,w2,...,wn。問能否從這n件物品中選擇若干件放入揹包,使得放入的重量之和正好是s。

設布林函式knap(s,n)表示揹包問題的解,wi(i=1,2,...,n)均為正整數,並已順序儲存地在陣列w中。請在下列演算法的下劃線處填空,使其正確求解揹包問題。

knap(s,n)

若s=0

則knap←true

否則若(s<0)或(s>0且n<1)

則knap←false

否則若knap(1) , _=true

則print(w[n]);knap ←true

否則 knap←knap(2

設有乙個順序棧s,元素s1, s2, s3, s4, s5, s6依次進棧,如果6個元素的出棧順序為s2, s3, s4, s6, s5, s1,則順序棧的容量至少應為多少?畫出具體進棧、出棧過程。

假定採用帶頭結點的單鏈表儲存單詞,當兩個單詞有相同的字尾時,則可共享相同的字尾儲存空間。例如:

設str1和str2是分別指向兩個單詞的頭結點,請設計乙個盡可能的高效演算法,找出兩個單詞共同字尾的起始位置,分析演算法時間複雜度。

將n(n>1)個整數存放到一維陣列r中。設計乙個盡可能高效(時間、空間)的算

法,將r中儲存的序列迴圈左移p(04、矩陣中元素按行和按列都已排序,要求查詢時間複雜度為o(m+n),因此不能採用常規的二層迴圈的查詢。可以先從右上角(i=a,j=d)元素與x比較,只有三種情況:一是a[i,j]>x, 這情況下向j 小的方向繼續查詢;二是a[i,j]void search(datatype a[ ][ ], int a,b,c,d, datatype x)

//n*m矩陣a,行下標從a到b,列下標從c到d,本演算法查詢x是否在矩陣a中.

else if (a[i][j]>x) j--; else i++;

if(flag) printf(「a[%d][%d]=%d」,i,j,x假定x為整型.

else printf(「矩陣a中無%d 元素」,x);

}演算法search結束。

[演算法討論]演算法中查詢x的路線從右上角開始,向下(當x>a[i,j])或向左(當x5、假設以鄰接矩陣作為圖的儲存結構,編寫演算法判別在給定的有向圖中是否存在乙個簡單有向迴路,若存在,則以頂點序列的方式輸出該迴路(找到一條即可)。(注:圖中不存在頂點到自己的弧)

有向圖判斷迴路要比無向圖複雜。利用深度優先遍歷,將頂點分成三類:未訪問;已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。

下面用0,1,2表示這三種狀態。前面已提到,若dfs(v)結束前出現頂點u到v的回邊,則圖中必有包含頂點v和u的迴路。對應程式中v的狀態為1,而u是正訪問的頂點,若我們找出u的下一鄰接點的狀態為1,就可以輸出迴路了。

void print(int v,int start ) //輸出從頂點start開始的迴路。

//if

}//print

void dfs(int v)

//if

else

visited[v]=2;

}//dfs

void find_cycle() //判斷是否有迴路,有則輸出鄰接矩陣。visited陣列為全域性變數。

//find_cycle

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

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

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

8、本題應使用深度優先遍歷,從主調函式進入dfs(v)時 ,開始記數,若退出dfs()前,已訪問完有向圖的全部頂點(設為n個),則有向圖有根,v為根結點。將n個頂點從1到n編號,各呼叫一次dfs()過程,就可以求出全部的根結點。題中有向圖的鄰接表儲存結構、記頂點個數的變數、以及訪問標記陣列等均設計為全域性變數。

建立有向圖g的鄰接表儲存結構參見上面第2題,這裡只給出判斷有向圖是否有根的演算法。

int num=0, visited=0 //num記訪問頂點個數,訪問陣列visited初始化。

const n=使用者定義的頂點數;

adjlist g用鄰接表作儲存結構的有向圖g。

void dfs(v)

//if

p=g[v].firstarc;

while (p)

//while

visited[v]=0; num--; //恢復頂點v

}//dfs

void judgeroot()

//判斷有向圖是否有根,有根則輸出之。

{static int i ;

2019台灣省資料結構考試基礎

1 約瑟夫環問題 josephus問題 是指編號為1 2 n的n n 0 個人按順時針方向圍坐成一圈,現從第s個人開始按順時針方向報數,數到第m個人出列,然後從出列的下乙個人重新開始報數,數到第m的人又出列,如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法,模擬此過程。2 給出...

2023年台灣省資料總結深入

1 請編寫乙個判別給定二叉樹是否為二叉排序樹的演算法,設二叉樹用llink rlink法儲存。2 define maxsize 棧空間容量 void inouts int s maxsize s是元素為整數的棧,本演算法進行入棧和退棧操作。else s top x x入棧 else 讀入的整數等於 ...

2019台灣省預防醫學考

1 氯乙烯引起的職業性腫瘤是 a a.肝血管肉瘤 b.膀胱癌 c.肺癌 d.癌2 慢性汞中毒的特有症狀為 a a.震顫 b.易興奮症 c.汞線 d.腎臟損害3 驅汞 的藥物是 a a.二巰丙磺鈉 b.依地酸二鈉鈣 c.阿托品 d.青黴胺4 維持正常生理功能所需要營養素的量稱為 c a.營養素供給量 ...