数据结构试题库(10)

do {

while (q!=NULL) {

top++; s[top]=q; [6] ; }

if (top= =0) [7] ; else {

[8] ; top--;

if (q->data

[9] ; }

else if (q->datarch; } } while (bool);

printf(―%d,%d‖,x1,x2); } [6] q=q->lch [7] bool=0 [8] q=s[top] [9] x1=q->data [10] x2=q->data

12. 已知单链表结点的存储结构如下：

struct node { int data;

struct node *next; };

这里，单链表的头指针为head, 数据域为data，指针域为next。试在下列A~J中选择一个正确答案，填入相应的空格处，分别实现下列四小题的算法功能，注意各个小题之间没有联系。

1）将单链表中值相同的多余结点删除。 void test1(struct node *head) { struct node *p,*q,*r; p=head;

while (p!=NULL) {

第 46 页 共 100 页

r=p;

(1) E while (q!=NULL) {

if (q->data==p->data) (2) I else r=q; q=q->next; }

(3) G } }

2）将值为y的结点插入到值为x的结点之后，如果值为x的结点不存在，则将其插入到单链表的表尾。

void test2(struct node *head,int x,int y) { struct node *p,*q,*r;

r=(struct node *)malloc(sizeof(struct node)); r->data=y; int sgn=0; p=head;

while (p!=NULL)&&(sgn==0) { if (p->data==x) sgn=1; (4) C p=p->next; }

if (sgn==1) (5) H else (6) J q->next=r; } }

3）假设在上述单链表结点的存储结构中增加另一个指针域prior，将该单链表改造成双向循环链表(假设该单链表中至少有一个结点)。 void test3(struct node *head) { struct node *p,*q; p=head;

while (p!=NULL) { q=p->next;

if (q!=NULL) (7) D else {

第 47 页 共 100 页

(8) F head->prior=p; break; }

p=p->next; } }

4）若采用单链表结构去存储一个堆栈，分别实现在堆栈中入栈和出栈一个元素的算法。

void test4(struct node *head,int x) { struct node *p;

p=(struct node *)malloc(sizeof(struct node)); p->data=x; p->next=head; (9) B }

int test5(struct node *head) { struct node *p; if (head!=NULL) { p=head;

(10) A x=p->data; return(x); } else exit(1); }

本题选项：

(A)head=head->next; (B)head=p; (C)q=p; (D)q->prior=p; (E)q=p->next; (F)p->next=head; (G)p=p->next; (H)r->next=p; (I)r->next=q->next; (J)r->next=NULL;

13. 已知二叉树结点的链表存储结构如下：

struct node { char data;

struct node *lch,*rch; };

第 48 页 共 100 页

这里，树结点的数据域为data，左孩子指针域为lch，右孩子指针域为rch，根结点所在链结点的指针由BT给出。试在下列A~J中选择一个正确答案，填入相应的空格处，分别实现下列两个小题的算法功能，注意各个小题之间没有联系。 1）利用中序遍历算法，查找二叉树BT中值为x的这个结点的双亲、左孩子及右孩子。

void test6(struct node *BT,char x) {

struct node *p,*q,*s[100]; struct node *x1,*x2,*x3; int top=0;

x1=x2=x3=NULL; p=BT;

while ((top!=0)||(p!=NULL)) { if (p!=NULL) while(p!=NULL) { top++; s[top]=p;

p= (11) F } else {

p=s[top];

(12) J if (p->data==x) {

(13) B =p->lch; (14) C =p->rch; } q=p;

p=p->rch;

if (p!=NULL)&&(p->data==x) (15) A =q; } } if(x1!=NULL) printf(\结点x的双亲是:%c\\n\else printf(\结点x是树根\\n\

if(x2!=NULL) printf(\结点x的左孩子是:%c\\n\else printf(\结点x无左孩子\\n\

if(x3!=NULL) printf(\结点x的右孩子是%c\\n\else printf(\结点x无右孩子\\n\

第 49 页 共 100 页

}

2）假设上述二叉树BT为一个二叉排序树，实现在该二叉排序树中插入一个结点s的算法。

void test7(struct node *BT,struct node *s) {

struct node *p,*q;

if (BT==NULL) BT=s; else {

(16) G while (p!=NULL) { q=p;

if (s->datadata) (17) D else (18) E }

if(s->datadata) (19) H else (20) I } }

本题选项：

(A)x1 (B)x2 (C)x3 (D)p=p->lch; (E)p=p->rch; (F)p->lch; (G)p=BT; (H)q->lch=s; (I)q->rch=s; (J)top--;

14. 下列程序用来统计一个非空链队列Q中结点值为素数的元素个数，请在空格处

填入正确合理的内容。 struct Nodetype {

int data;

struct Nodetype *next; };

struct LinkQueue {

struct Nodetype *front,*rear; };

int countqueue(struct LinkQueue *Q) {

struct Nodetype *p; int i,k,num=0;

p=(5) ;

第 50 页 共 100 页