数据结构综合题(8)

41、写出在二叉排序树中插入一指定结点一个结点的算法。 42、完成计算二叉树叶子结点的算法。 Void midtravel(struct treenode *bt) {struct treenode *p,*a[n]; int top= - 1,true =1, j =0; while(true) { p=bt;

while(p != null) { top + +; a[top]=p;

p=________} if (top != -1) { p=a[top]; top -- ;

printf(“%c”,p->data);

if (p->left = = null )&&__________ ______________;

p=p->right;} Else true = 0; } Printf(“%d”,j)} 43、完成二叉树按层遍历的算法。

Void leveltravel ( struct treenode *bt) { struct treenode *p,*a[n]; int rear=front = -1; p=bt;

rear =__________; a[rear]=p;

while (rear != front) { front = ___________; p=a[front];

printf(“%c”,p->data);

If ( p->left !=null) { rear =(rear +1)% n a[rear]= _________; }

If (p->right!= null) {rear = (rear +1)%n ;

a[rear]=_________; } } }

44、给定一棵用链表表示的二叉树，其根指针为t，试写出从根开始，按层次遍历二叉树的算法，同层的节点按从左到有的次序访问。

45、写出在中序线索二叉树中结点*p的右子树中插入一个结点*s的算法。

36

46、试设计一个算法在中序线索化的树中，求指定结点P的前驱结点，要求用非递归算法。 47、完成下列程序,并说出该算法所完成的功能。 void weizhisort(struct node r[ n],int n) { int low,high,mid,j,i; for(i=2;i<=n;i++) { r[0]=r[i];

low=__________; high=_________; while(low<=high)

{ mid=(low+high)/2; if(r[0].key

for(j=i-1;j>=l;j--) r[j+1]=r[j]; r[low]=r[0]; }}

48、完成程序，并说出程序的功能 Bitreptr *bstsearch(t,k) Bitreptr *k; Keytype k; {if(t= =null) return null; else while(t !=null)

{if (t->key= =k)_________; if(t->key>k)______________; else____________________; } }

49、完成下列程序，并说出该算法的功能。 Void weizhitravel ( struct treenode *bt) { struct treenode *p,*a[n]; int true = 1,top =-1; while (true)

{ while (p!= null) //只要p不空全部压栈// { printf(“%c”,p->data); ______________;

37

a[top] =p ; _________;}

if ( top != - 1) {p=a[top]; p=p->right; top - -;} else

true =0; }

}

50、写出在二叉排序树中查找值为x的算法。

51、试写出以带头结点单链表为存储结构实现简单选择排序的算法。 52、阅读下列算法，并回答下列问题：

该算法完成什么功能？算法中R[n+1]的作用是什么？ Void sort (elemtype r[],int n) {int k,i;

for(k=n-1;k>=1;k- -) if(r[k]>r[k+1]) { r[n+1]=r[k];

for(i=k+1;r[i]

53、说出下列算法的运行结果: struct node { elemtype data;

struct node *next;}

void weizhi (struct node *head,struct node *q) {struct node *p, *r; p=head->next

while(p->next!=q)&&(p->next != null) p=p->next; if (p->next !=null) { r=p->next; q->next=r;

p->next=r->next;

38

r->next=p;}

}

算法完成的结果是: _______________________ 54、设编写一计算字符串长度的算法。

55、写一算法将一单链表逆置。要求操作在原链表上进行。

56、编写算法在一个非减有序线性表中，插入一个值x的元素，使插入的线性表仍为非减有序表。

39