数据结构期中考试试题答案

一、　　　　　  单选题（每小题2分，共8分） 

1.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为　  C　  。 

A.n  　　　　　　　　B.n/2　　　  　　　 C.(n+1)/2 　　　　　　 D.(n-1)/2 

2.在一个带附加表头的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 

　  D　 。 

A.HL=p;p->next=HL;　　 　　　　　　　　　 B.p->next=HL;HL=p;

C.p->next=HL;p=HL;　　　　  　　　　　　　D.p->next=HL->next;HL->next=p;

3．若让元素A，B，C，D依次入栈，则出栈次序不可能出现　　 D　  种情况。 

A.D,C,B,A  　　　　　 B.A,D,C,B　　　　　 C.B,A,D,C　　　　　　 D.D,A,B,C 

4．从一个顺序队列删除元素时，首先需要　  B　  。 

A.前移一位队首指针　  　　　　　　　　　　　B.后移一位队首指针 

C.取出队首指针所指位置上的元素 　　　　　　 D.取出队尾指针所指位置上的元素 

二、　　　　　  填空题（每空1分，共32分） 

1．数据的逻辑结构分为  集合  、  线性　、  树型　、　 图形　四种。 

2.函数重载要求  参数个数 、  参数类型 或  参数次序 有所不同。 

3．在带附加表头的循环双向链表中， 表头附加结点 的 左 指针域指向最后一个结点，最后一个结点的 右 指针域指向 表头附加  结点。 

4．在以HL为表头指针的带附加结点的单链表和循环单链表中，链表为空的条件分别为 

HL->next==NULL 和 HL==HL->next 。 

5．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a[i].next=a[1].next 、 a[1].next=i 。 

6．在由数组a中元素结点构成的单链表中，删除下标为i的结点的后继结点并将被删除结点的下标赋给i时，所进行的操作（需要用一个临时变量p）描述为 p=a[i].next　  

和 a[i].next=a[p].next;i=p  。 

7．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向  列号  相同的下一个结点，right指针域指向  行号　相同的下一个结点。 

8．一个广义表中的元素分为  单  元素和  表　元素两类。 

9．广义表A=((a,(b,(),c),((d),e)))的长度为  1  ，深度为  4　 。 

10．向一个顺序栈插入一个元素时，首先应 top++ ，然后再将待插入元素 放入栈顶位置 。 

11．对于队列，应在  队尾  进行插入，在  队首　进行删除。 

12．中缀表达式2+7/(4-1)所对应的后缀表达式为 2 7 4 1 - / + @　 。 

13．后缀表达式“10 3 5 4 - * - 1 + 3 2 + -”的值为　 3  。 

14.一棵二叉树的广义表表示为a(b(c,d),e(f(,g))),则e结点的双亲结点为 　 a　 ，孩子结点为　 f　　 ，树的深度为　  4　　。 

三、运算题（每小题8分，共24分） 

1．假定线性表L=（33,69,78,22,44,88）,i=3,x=34,y=22,则对L进行下列一组操作` 

　 ListEmpty(L);　　　　　　  　 false　　　　　　　　　　　　　　　 

　 GetElem(L,i);　　　　　　  　 78　　　　　　　　　　　　　　　　  

　 InsertFront(L,x);　　　　  　 (34 33 69 78 22 44 88)　　　　　　  

　 InsertRear(L,x);　　　　　 　 (34 33 69 78 22 44 88 34)　　　　　 

　 DeleteFront(L);　　　　　  　 (33 69 78 22 44 88 34)　　　　　　  

　 Delete(L,y);　　　　　　　 　 (33 69 78 44 88 34)　　　　　　　　 

　 Sort(L);　　　　　　　　　 　 (33 34 44 69 78 88)　　　　　　　　 

　 Insert(L,66);　　　　　 　 　 (33 34 44 66 69 78 88)　　　　　　  

　 请写出每步操作后的结果。 

2．假定线性表L=（33,85,21,56,30,63,42,91,76）,调用顺序表的排序算法 

void Sort(List& L)对此表进行排序，请写出排序过程。（将每一步结果写出） 

　 （1）[ 33 85 ] 21 56 30 63 42 91 76 

　 （2）[ 21 33 85 ] 56 30 63 42 91 76 

　 （3）[ 21 33 56 85 ] 30 63 42 91 76 

　 （4）[ 21 30 33 56 85 ] 63 42 91 76 

　 （5）[ 21 30 33 56 63 85 ] 42 91 76 

　 （6）[ 21 30 33 42 56 63 85 ] 91 76 

　 （7）[ 21 30 33 42 56 63 85 91 ] 76 

　 （8）[ 21 30 33 42 56 63 76 85 91 ] 

3．已知一个中缀表达式为：10-3*(2+1)+(3-1)/2@，请画出其转换为后缀表达式过程中S2及R栈的变化。 

S　3　2  1　　　　　  

R @ - * ( +  

S  1 0　3　2　1  + 

R@ - * 

S  1 0　3　2　1  + * - 3　1 

R@ + ( - 

S  1 0　3　2　1  + * - 3　1　- 2  

R@ + / 

S  1 0　3　2　1  + * - 3　1　- 2　/ + 

R 

S  1 0　3　2　1  + * - 3　1　- 2　/ + @ \\0 

R 

四、　　　　　  阅读算法，回答问题（每小题8分，共16分） 

1.Void MADE(Lnode * & H1)　　　　　　　　  2.Void AE(Stack& S) 

  {　　　　　　　　　　　　　　　　　　　　  { 

Lnode *p;  　　　　　　　　　　　　　　　 InitStack(S); 

p=H1;　　　　　 　　　　　　　　　　　　　 Push(S,30); 

H1=NULL;　　 　　　　　　　　　　　　　　 Push(S,40); 

while(p!=NULL)　　　　　　　　　　　　　　  Push(S,50); 

{　　　　　　　　　　　　　　　　　　　　　 int x=Pop(S)+2*Pop(S); 

  lnode *q=p; 　　　　　　　　　　　　　　　　Push(S,x); 

p=p->next;　　　 　　　　　　　　　　　　　int i,a[4]={5,8,12,15}; 

q->next=h1;　　　　　　　　　　　　　　　 for(i=0;i<4;i++)

  H1=q;　　　　　　　　　　　　　　　　　　 Push(S,a[i]); 

}　　　　　　　　　　　　　　　　　 　　　　while(!StackEmpty(S)) 

  }　　　　　　　　　　　　　　　　　　　　  　　　 cout<}  

该算法的功能为：　　　　　　　　　　　　　　 该算法被调用后得到的输出结果为： 

将原链表逆序　　　　　　　　　　　　　　　　 15　12　8　5　130　30 

五、　　　　　  算法填空，在画有横线的地方填写合适的内容（10分）。 

删除带附加表头的单链表上第pos个元素的算法。 

Void Del(LNode * & HL,int pos) 

{ 

　 if(pos<1){

cerr<<”pos is out range!”<exit(1); 

} 

int i=0; 

Lnode *p, *q; 

q=HL　　 ; 

p=HL->next　　　　　　 ; 

int  i=1　　　　　　　  ; 

while( p!=NULL ){ 

　　　　　　　  if (i= =pos)  break; 

　　　　　　　  else{ 

 　　　　　　 ; 

　　　　　　　　　　 　　　　; 

　　　　　　　　　　 　　  　　　　　; 

　　　　　　　 } 

i　　　　　 ; 

delete p　　  ; 

　　　　　 } 

else{ 

　　 cerr<<”pos is out range!”<　　 exit(1); 

} 

} 

六、　　　　　  编写算法（10分）。 

写出向二叉排序树中插入一个元素的非递归算法。 

Void insert(BtreeNode * BST, const ElemType & item) 

{ 

　　　 BtreeNode *t=BST, *parent=NULL; 

　　　 While(t!=NULL){ 

　　　 　　　 Parent=t; 

　　　 　　　 If(itemdata) t=t->left;

　　　 　　　 Else t=t->right;

　　　 } 

　　　 BtreeNode *p=newBtreeNode; 

　　　 p->data=item;

　　　 p->left=p->right=NULL;

　　　 if(parent= =NULL) BST=p; 

　　　 else if(itemdata)　　　 parent->left=p;

　　　 else　parent->right=p;

}