1、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(15分)
(1)下面所示的序列中哪些是合法的?
A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D. IIIOOIOO
(2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。
2、假设K1,…,Kn是n个关键词,试解答:
试用二叉查找树的插入算法建立一棵二叉查找树,即当关键词的插入次序为K1,K2,…,Kn 时,用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。
3、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用递归算法。
int Similar(BiTree p,q) //判断二叉树p和q是否相似
{if(p==null && q==null) return (1);
else if(!p && q || p && !q) return (0);
else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar
4、假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)
有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类:未访问;已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。对应程序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。
{for(i=1;i<=n;i++)
if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i),且顶点i的状态为1。
{printf(“%d”,v);
if(i==start) printf(“\n”); else Print(i,start);break;}//if
void dfs(int v)
{visited[v]=1;
for(j=1;j<=n;j++ )
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。
{for (i=1;i<=n;i++) visited[i]=0;
for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);
}//find_cycle
5、设从键盘输入一整数的序列: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(0
6、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。
int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数
{if(bt==null || k<1) return(0);
BiTree p=bt,Q[]; //Q是队列,元素是二叉树结点指针,容量足够大
int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数
int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针,level 是二叉树的层数
while(front<=rear)
{p=Q[++front];
if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点
if(p->lchild) Q[++rear]=p->lchild; //左子女入队
if(p->rchild) Q[++rear]=p->rchild; //右子女入队
if(front==last) {level++; //二叉树同层最右结点已处理,层数增1
last=rear; } //last移到指向下层最右一元素
if(level>k) return (leaf); //层数大于k 后退出运行
}//while }//结束LeafKLevel
7、编程实现单链表的就地逆置。
23.在数组 A[1..n]中有n个数据,试建立一个带有头结点的循环链表,头指针为h,要求链中数据从小到大排列,重复的数据在链中只保存一个.
8、4、void LinkList_reverse(Linklist &L)
//链表的就地逆置;为简化算法,假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse