单项选择题
1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )
(A)栈
(B)队列
(C)树
(D)图
【正确答案】C
【试题解析】 在树中，除了根结点和叶子结点外，其余结点都仅有一个直接前驱而且有一个或多个直接后继。而根结点没有直接前驱但有一个或多个直接后继，叶子结点有一个直接前驱却没有直接后继。
2.下面程序段的时间复杂度为( ) for(i=0;i
(A)O(m2)
(B)O(n2)
(C)O(m*n)
(D)O(m+n)
【正确答案】C
【试题解析】 此程序的时间复杂度即为程序中循环次数的时间耗费。由程序为嵌套循环，外层循环的时间复杂度T(n1)=m，内层循环的时间复杂度T(n2)=n，则此程序的时间复杂度T(n)=m*n，即为0(m*n)。
3.在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是( )
(A)p—>next==head
(B)p—>next—>Next==head
(C)p—>next==NULL
(D)p==head
【正确答案】A
【试题解析】 在单链表中，将终端结点的指针域NULL改为指 ……此处隐藏12624个字…… os=Partition(&L,low,high);//调用快速排序的划分算法if(pivotposk) high=pivotpos-1; }while(pivotpos!=k); return L.data[pivotpos]; }
【正确答案】1. 20 2.利用快速排序的“划分”机制进行查找，以求取序列中排行第k小的元素。
算法设计题
34.二叉排序树的类型定义如下：typedef struet BSTNode{//二叉排序树的结点结构int data; //数据域struct BSTNode*lchild,*rchild;//左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【正确答案】(P71)参考答案之一：void count(BSTree T,int a,int*sum){ //以sum所指单元统计二叉排序树中元素值小于a的结点个数，其初值为0 if(T){ count(T—>lchild,a,sum); if(T—>data (*sum)++; count(T—>rchild,a,sum); } } }参考答案之二：int count(BSTree T,int a){ //统计二又排序树中元素值小于a的结点个数int sum; if(!T)return 0; else{ sum=count(T—>lchild,a); if(T—>datarchild,a); else return sum; } }
