六、算法分析题
1、简述以下关于二叉树某操作的算法的功能和主要思想。 typedef struct BiTNode {
char data ; // 结点信息是字符
struct BiTNode *lchild,*rchild; // 左右孩子指针 } *BiTree;
Status xxxx (BiTree T, Status(*Visit)(char e)) { TStack S; BiTree p; InitStack(S); if(T) Push(S,T); while (!StackEmpty(S)){ Pop(S,p); Visit(p->data); if(p->lchild) Push(S,p->lchild); if(p->rchild) Push(S,p->rchild); } return OK; }
答案：线序遍历二叉树
2、一线性表存储在带头结点的双向循环链表中，L为头指针，算法如下。 说明该算法的功能。 void unknown (BNODETP *L)
第 页 16 共 23 页
{ ?
p=L->next; q=p->next; r=q->next； while (q!=L)
{ while (p!=L) && (p->data>q->data) p=p->prior； q->prior->next=r；r->prior=q->prior； q->next=p->next；q->prior=p；
p->next->prior=q；p->next=q; q=r；p=q->prior； r=r->next;或r=q->next;
答案：将该链表从小到大排序
3、分析下列算法，并简述其功能。 void conversion( )
{ InitStack(s); scanf(“%d”,&x);
while(x!=0) { push(s, x% 8); x=x/8; }
while(! StackEmpty(s) ) //输出存放在栈中 { x=pop(s);
printf(“%d”,x); } }
答案：把十进制数转换成八进制数 4、写出以下递归算法功能 。 typedef struct BiTNode {
char data ; // 结点信息是字符
struct BiTNode *lchild,*rchild; // 左右孩子指针 } *BiTree;
Status exchangelr(BiTree &T) // 算法用函数名 exchangelr 表示 {BiTree p; // 临时工作指针叉树某操作的算法的功能和主要思想。 ...... // 待完成的若干语句； }
Status exchangelr(BiTree &T) // 算法用函数名 exchangelr 表示 {BiTree p; // 临时工作指针
if(!T) return OK; // 待完成的若干语句； else{ p = T->lchild;
第 页 17 共 23 页
T->lchild = T->rchild; T->rchild = p; exchangelr(T->lchild); exchangelr(T->rchild); } }
答案：将所以节点的左右孩子交换
5、简述以下两个算法的功能并指出这两个算法在算法思想上的主要区别是什么。 typedef struct { ElemType *elem; int length; int listsize; }SqList;
(1) Status DK1(SqList &a, int i, int k) {int j, count;
if (i<1 || k<0 || i+k > a.length) return INFEASIBLE; //参数不合法 else {
for (count = 0; count < k; count++){
for (j = i; j < a.length; j++) a.elem[j-1] = a.elem[j]; a.length--; } }
return OK; } // DK1
(2) Status DK2(SqList &a, int i, int k) { int count;
if (i<1 || k<0 || i+k > a.length) return INFEASIBLE; // 参数不合法 else {
for (count = 0; count < a.length-(i+1); count++){ a.elem[i-1+count] = a.elem[i+k-1+count]; }
a.length -= k; }
return OK; } // DK2
答案：把第i-1个元素之后的k个元素删除
6、简述以下算法的功能
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
pa=La->next; pb=Lb->next;
Lc=pc=La; //用La的头结点作为Lc的头结点 while (pa && pb){
第 页 18 共 23 页
if (pa->data<=pb->data){
pc->next=pa; pc=pa; pa=pa->next; }
else {pc->next=pb; pc=pb; pb=pb->next;} }
pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放Lb的头结点 }//MergeList_L
答案：把La和Lb中的元素按递增的顺序合并到Lc中
7求下列算法段的语句频度及时间复杂度 for(i=1; i<=n; i++)
for(j =1; j <=i ; j++) x=x+1;
（7,8题的答案在下面）
8、分析下列算法段的时间频度及时间复杂度
for （i=1;i<=n;i++） for (j=1;j<=i;j++) for ( k=1;k<=j;k++) x=i+j-k;
七、算法设计题(每题5分 )
1、若由键盘输入若干个整数，请写出按输入数据逆序建立一个带头结点的单链表的算法。
第 页 19 共 23 页
void CreateList_L1(LinkList &L,int n){
//逆位序输入n个元素的值，建立带表头结点的单链线性表L L=(LinkList) malloc (sizeof (Lnode));
L->next=NULL; //先建立一个带头结点的单链表(空表) for (i=n; i>0; --i);{
p=(LinkList) malloc (sizeof (LNode)); //生成新结点 scanf(&p->data); //输入元素值
p->next=L->next; L->next=p; //插入到表头 }
}//CreateList-L1
2、已知一个顺序存储的线性表的元素非递减有序排列，设计一个算法删除表中多余的值相同的元素
的算法。
void Delete_Equal(LinkList *L)
{
p=(*L)->next;q=p->next; /*p和q指向相邻的两个元素*/ while(p->next) {
if(p->data!=q->data) /*若相邻两元素不相等时，p和q都向后推一步*/ { p=p->next; q=p->next; } else {
while(q->data==p->data) /*当相邻元素相等时删除多余元素*/ { r=q; q=q->next; free(r); }
p->next=q;p=q;q=p->next; }/*else*/
第 页 20 共 23 页