单项选择题

　　1.按值可否分解，数据类型通常可分为两类，它们是 ( )

　　(A)静态类型和动态类型

　　(B)原子类型和表类型

　　(C)原子类型和结构类型

　　(D)数组类型和指针类型

　　【正确答案】C

　　【试题解析】 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解;结构类型，其值可分解为若干个成分。

　　2.对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )

　　(A)f(n)是O(g(n))

　　(B)g(n)是O(f(n))

　　(C)h(n)是O(nlogn)

　　(D)h(n)是O(n2)

　　【正确答案】C

　　【试题解析】 当n充分大时，由题意可得：f(n)与n3是同阶的，g(n)与n3是同阶的，h(n)与n2是同阶的。所以f(n)=O(g(n))，g(n)=O(f(n))，h(n)=O(n2)。

　　3.指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是 ( )

　　(A)p—>next=r; q—>next=r—>next; r—>next=q;

　　(B)p—>next=r; r— ……此处隐藏8550个字…… / }BSTNode,*BSTree; 阅读算法f33，并回答问题：

　　【正确答案】1. 10 2. T是空树或T中所有结点的关键字均不大于给定值X时，返回空指针。 3. 如果二叉排序树T中存在含有关键字大于给定值X的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。

　　算法设计题

　　34.假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct{ int data[ListSize]; int length; }SeqList,*Table; 编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。

　　【正确答案】参考答案一： void f34(Table L) { int i,j,t; i=0; j=L—>length-1; while(idata[i]%2) i++; while(idata[j]%2==0) j--; if(idata[i]; L—>data[i]=L—>data[j]; L—>data[j]=t; i++; j--; } } } 参考答案二： void f34(SeqList*L) { int i,j=0.t; for(i=0;ilength;i++) if(L—>data[i]%2)/*奇数*/ { if(i!=j) { t=L—>data[i]; L—>data[i]=L—>data[j]; L—>data[j]=t; } j++; } }