单项选择题

　　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; } }