1、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）
（1）下面所示的序列中哪些是合法的？
a. ioiioioo b. iooioiio c. iiioioio d. iiiooioo
（2）通過對（1）的分析，寫出乙個演算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維陣列中）。
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)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
3、二部圖（bipartite graph） g=（v，e）是乙個能將其結點集v分為兩不相交子集v 1和v2=v-v1的無向圖，使得：v1中的任何兩個結點在圖g中均不相鄰，v2中的任何結點在圖g中也均不相鄰。
（1）．請各舉乙個結點個數為5的二部圖和非二部圖的例子。
（2）．請用c或pascal編寫乙個函式bipartite判斷乙個連通無向圖g是否是二部圖，並分析程式的時間複雜度。設g用二維陣列a來表示，大小為n*n（n為結點個數）。請在程式中加必要的注釋。
若有必要可直接利用堆疊或佇列操作。【
4、設t是一棵滿二叉樹，編寫乙個將t的先序遍歷序列轉換為後序遍歷序列的遞迴演算法。
5、設t是給定的一棵二叉樹，下面的遞迴程式count(t)用於求得:二叉樹t中具有非空的左,右兩個兒子的結點個數n2;只有非空左兒子的個數nl;只有非空右兒子的結點個數nr和葉子結點個數n0。n2、nl、nr、n0都是全域性量，且在呼叫count(t)之前都置為0.
typedef struct node
node;
int n2,nl,nr,n0;
void count(node *t)
26.樹的先序非遞迴演算法。
void example(b)
btree *b;
if (p->lchild!=null)
(3)___; (4)__;
}}}}
6、根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全域性指標變數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演算法結束
7、題目中要求矩陣兩行元素的平均值按遞增順序排序，由於每行元素個數相等，按平均值排列與按每行元素之和排列是乙個意思。所以應先求出各行元素之和，放入一維陣列中，然後選擇一種排序方法，對該陣列進行排序，注意在排序時若有元素移動，則與之相應的行中各元素也必須做相應變動。
void translation（float *matrix，int n）
//本演算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。
//for i
for(i=0; i
sum=p[i]; p[i]=p[k]; p[k]=sum; //交換一維陣列中元素之和.
}//if
}//for i
free(p); //釋放p陣列.
}// translation
[演算法分析] 演算法中使用選擇法排序,比較次數較多,但資料交換(移動)較少.若用其它排序方法,雖可減少比較次數,但資料移動會增多.演算法時間複雜度為o(n2).
2019遼寧省資料庫入門入門
1 陣列a和b的元素分別有序，欲將兩陣列合併到c陣列，使c仍有序，應將a和b拷貝到c，只要注意a和b陣列指標的使用，以及正確處理一陣列讀完資料後將另一陣列餘下元素複製到c中即可。void union int a,b,c,m,n 整型陣列a和b各有m和n個元素，前者遞增有序，後者遞減有序，本演算法將a...
2019遼寧省資料庫期末考試入門
1 證明由二叉樹的中序序列和後序序列，也可以唯一確定一棵二叉樹。當n 1時，只有乙個根結點，由中序序列和後序序列可以確定這棵二叉樹。設當n m 1時結論成立，現證明當n m時結論成立。設中序序列為s1，s2，sm,後序序列是p1,p2,pm。因後序序列最後乙個元素pm是根，則在中序序列中可找到與pm...
2019遼寧省土建造價員考試真題 含答案 考試題庫
1 下面關於絕對偏差說法正確的是 a.絕對偏差 投資實際值 投資計畫值 投資計畫值 b.絕對偏差可指導調整資金支出計畫和資金籌措計畫 c.從對投資控制角度看，絕對偏差比相對偏差更有意義 d.絕對偏差反映了投資偏差的嚴重程度 2 工程造價的職能除一般商品 職能外，還有自己特殊的職能 a 預計職能 b ...