数据结构试题及答案

{ 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的算法。

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) A

3. A 4. D 5. D 8. B 9. D 13 C 15. B 16. B

19. B 20． D 21． D 22．C 23． B 24．C 25．C 26． D 27． D

28 D 30．C 31．A 32． A 33. D 35. D 36. D 37. B 38 A 39． D 40．A 41． B 42. D 43. B 45. B 46. D 48. B 49. D 50. C 53. D 54. D 57. B 58. D 59．C 61 Ａ 62. D 63．Ａ 64. D 65． B 66. DA 67. DA 68.Ｃ 69. BA 70. CA 71. CB 72.Ｄ 73.Ｂ 75. C 76. A 78. D 80．B 81．A 82. D 83． D 84． D 85．B 87. B 88．A 89． B 90．C 91．A 92 B 93． B 94． D 95．A