单项选择题

1.若将数据结构形式定义为二元组(K,R)，其中K是数据元素的有限集合，则R是K上( )

（A）操作的有限集合

（B）映象的有限集合

（C）类型的有限集合

（D）关系的有限集合

【正确答案】D

2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为 ( )

（A）n-i+1

（B）i

（C）i+1

（D）n-i

【正确答案】D

3.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是 ( )

（A）head==NULL

（B）head—＞next==NULL

（C）head!=NULL

（D）head—＞next==head

【正确答案】A

4.引起循环队列队头位置发生变化的操作是 ( )

（A）出队

（B）入队

（C）取队头元素

（D）取队尾元素

【正确答案】A

5.若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )

（A）2,4,3,1,5,6

（B）3,2,4,1,6,5

（C）4,3,2,1,5,6

（D）2,3,5,1,6,4

【正确答案】D

6.字符串通 ……此处隐藏8310个字…… pedef struct node{ DataType data; struct node*lchild,*rchild; //左右孩子指针 struct node*parent; //指向双亲的指针 }BinTNode; typedef BinTNode*BinTree; 若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

【正确答案】

34.1. 就后继的不同情况，简要叙述实现求后继操作的方法；

【正确答案】分两种情况讨论 ①当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结点为止，则该结点为*pX在中序序列中的后继； ②当*px的右子树为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点为*px在中序序列中的后继。

35.2. 编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。

【正确答案】BinTree f34(BinTree px) { BinTree q=px—＞rchild; if(q!=NULL){ //沿左孩子往下查找 px=q; while(px—＞lchild!=NULL) px=px—＞lchild; } else{ //沿双亲指针链向上查找 while(px!=NULL&&px—＞rchild==q){ q=px; px=px—＞parent; } } retun px； //返回所找到的中序序列后继结点的指针 //或者无后继结点时返回空指针 }