数据结构与算法离线作业【2014春】(3)

scanf(\,&a,&b); delete_L(L,a,b); out_L(L); printf(\); }

【8，3，2】给定一个顺序存储的线性表L = (a1, a2, ?, an)，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

#include #include using namespace std;

#define MAXN 1003 int A[MAXN]; int dp[MAXN];

int main() {

int n, i, j, k; cin >> n;

for (i=1; i<=n; i++) cin >> A[i]; dp[1] = 1;

for (i=2; i<=n; i++) {

dp[i] = 1;

for (j=i-1; j>=0; j--) {

if (A[i]>A[j])

dp[i] = max(dp[i], dp[j]+1); } }

int maximum = dp[1]; for (i=2; i<=n; i++)

maximum = max(maximum, dp[i]); cout << maximum;

11

}

【9，3，3】 如果有1、2、3、4、5按顺序入栈，不同的堆栈操作（pop, push）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？

1、2、3、4、5已经在栈中，那最后输出的是由尾到头：5、4、3、2、1。后进先出。

【10，3，2】请编写程序将中缀表达式转换为后缀表达式。

#include #include #include using namespace std; int prior(char op) {

if(op=='+'||op=='-') return 1;

if(op=='*'||op=='/') return 2; return 0; }

string middletolast(string middle) {

stack op; string ans;

for(int i=0;i

char c=middle[i]; if(c>='0'&&c<='9') {

ans.append(1,c); } else {

if(c=='(') op.push('('); else {

if(c==')')

12

{

while(op.top()!='(') {

ans.append(1,op.top()); op.pop(); }

op.pop(); } else {

if(op.empty()) {

op.push(c); } else {

if(prior(c)>prior(op.top())) op.push(c); else {

while(!op.empty()&&prior(c)<=prior(op.top())) {

ans.append(1,op.top()); op.pop(); }

op.push(c); } } } } } }

while(!op.empty()) {

ans.append(1,op.top()); op.pop(); }

return ans; }

int main()

13

{

string mdata,res; cin>>mdata;

res=middletolast(mdata); for(int i=0;i

if(i==0)

cout<

cout<<' '<

cout<

【11，4，3】设二叉树的存储结构如下：

Lchild data Rchild 1 0 J 0 2 0 H 0 3 2 F 0 4 3 D 9 5 7 B 4 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 其中根结点的指针值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为数据域。

（1） 画出二叉树的逻辑结构。

14

（2） 写出该树的前序、中序和后序遍历的序列。 前序：ABCEDFHGIJ 中序：ECBHFDJIGA 后序：ECHFJIGDBA

【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意4个。

【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答： （1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）； （2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）；

17 4 5 15 4 7 1316 11215 22