一.概论
1.通常要求同一逻辑结构中的所以数据元素具有相同的特性，这意味着（ ）。
A)数据元素具有同一特点
B)不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C)每个数据元素都一样
D)数据元素所包含的数据项的个数要相等
[分析]同一逻辑结构中的所有数据元素必须具有相同的数据域，而且对应数据项的类型要一致。因为一方面只有同一类型的数据元素才能归类到同一结构中；另一方面，在计算机存储器中表示数据元素时，还必须为它们定义相同的数据类型。故B)答案是正确的。
[答案]B)
2.下列程序段的时间复杂度是多少？
…
for(i=1;i<=n;i++)
…
k++;
for(j=1,j<=n;j++) l+=k;
…
…
[分析]确切地计算一个算法的时间消耗没有任何实际意义。因为在具体问题中，问题规模n的大小是变化的，而且每台计算机的主频也不相同，所有我们关注的是算法中每条语句的执行次数(频度)。对上述程序段，语句执行的总次数为：
n+1+n+n(n+1)+n2=2n2+3n+1 注：n后的2为上标
令T(n)=2n2+3n+1
T(n)就能反映出程序段的时间消耗。当n较大时，T(n)的大小主要取决于n的数量级。借助数学上极限的概念，如果 lim T(n)
n→∞ f(n) =常数，表示当n→∞时，T(n)和f(n)具有相同的数量级，称T(n)与f(n)同阶。
在本例中，假设f(n)＝n2，则有
即T(n)与n2同阶。采用O记法，有T(n)=O(f(n))=O(n2)
其中：T(n)就是算法的渐近时间复杂度，简称时间复杂度。而f(n)恰为算法中执行频度最大的那句语句的频度。由此得到求解时间复杂度的方法：找出所有语句中执行频度最大的那条语句的频度，然后取其数量级放入O中即可。
[答案]O[n2]
二.线性表
1.带头结点的单链表head为空的判断条件是()。
A)head=NULL B)head->next=NULL
C)head->next=head D)head!=NULL
[分析]带头结点的空单链表如图1所示：
所以其判断条件可表示为head->next=NULL。如果单链表不带头结点，则其判空条件是head=NULL。
[答案]B)
2.单链表中，增加头结点的目的是为了( )。
A)方便运算的实现
B)用于标识单链表
C)使单链表中至少有一个结点
D)用于标识起始结点的位置
[分析]对单链表来讲，我们是用头指针来对其进行标识的。头指针可以指向头结点，也可以指向起始结点，所以没有必要用头结点来标识起始结点。而一个单链表允许是空的，不一定非要保证单链表中至少有一个结点，因此B),C),D)答案都是错误的。至所以要引入头结点，目的就是为了方便单链表上运算的实现。
[答案]A)
3.在 一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p,q之间插入s结点，这执行（ ）操作。
A)s->next=p->next;p->next=s;
B)q->next=s;s->next=p;
C)p->next=s->next;s->next=p;
D)p->next=s;s->next=q;
[分析]按题意画草图如图2所示。在本题中，因为相关的三个结点分别被三个指针所指向，所以图中的操作步骤可以对调。
[答案]B)。
4.在单链表中，删除p所指结点的直接后继的操作是( )。
A)p->next=p->next->next;
B)p=p->next;p->next=p->next->next;
C)p->next=p->next;
D)p=p->next->next;
[分析]删除p的直接后继后，p的直接后继的直接后继成为p的新的直接后继，所以应将新的直接后继的地址存入p的指针域中。
5.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。
A)n B)n/2 C)(n-1)/2 D)(n+1)/2
[分析]最好情况下只需比较1次，最坏情况下需比较n次，所以平均次数为(1+2+3+...+n)/n=(n+1)/2
[答案]D)
6.非空的循环单链表head的尾结点(由指针p所指)满足( )。
A)p->next=NULL B)p=NULL
C)p->next=head D)p=head
[分析]不管循环单链表是否带有头结点，其尾结点的指针域一定指向头结点head的目标，所以有p->next=head。
[答案]C)
7.在循环双链表的p所指结点之后插入s所指结点的操作是( )。
A)p->next=s;
s->prior=p;
p->next->prior=s;
s->next=p->next;
B)p->next=s;
p->next->prior=s;
s->prior=p;
s->next=p->next;
C)s->prior=p;
s->next=p->next;
p->next=s;
p->next->prior=s;
D)s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
[分析]循环双链表上的插入，关键是指针操作的先后顺序不能出错，否则会失去某些结点的地址。建议大家在做这类练习时画一个草图，标出指针的先后操作顺序，如图3所示。
8.在单链表中的p所指结点之前插入一个s所指结点时，可按下述步骤进行：
s->next=_________;
p->next=s;
temp=p->data;
p->data=_________;
s->data=_________;
[分析]通常，在某结点ai前插入一个结点x,需知道其直接前趋ai-1的地址，此时只有从单链表的头部向后查找以得到ai-1的地址。而本例则是一种更简便的方法，它的思想是，将新结点插入到p所指结点之后，然后再将p,s所指结点的值对换，如图4所示。对照图示，就可以进行填空了。
[答案]p->next,s->data,temp。
9.下列算法用于判断带头结点的循环双链表A是否对称相等，请在算法中的_______处填上正确的语句。
int dlink_symmetry (dlklist s)
{j=true;yiq
p=s->next;
q=s->prior;
while(p!=q)&(_____)
if(p->data=q->data)
{_______;
_______;
}
else
j=false;
return(j);
}
[分析]这里循环双链表的对称是指以指针s所指的结点为中心，左、右两边对应位置处结点的值相等。由于是循环双链表，故设置两个指针p,q，分别按前域指针和后域指针查找左、右两边对称位置处的结点，然后比较它们的值是否相等，如果相等，改变p,q指针，以便继续往下查找，否则使标志j=false，表示循环双链表不对称。算法中第一个空应该填入一个判断条件，以决定何时终止while循环，当p->prior!=q，或者q->next!=p时，表示沿前域指针或后域指针还未循环一圈，还可继续往下查找。第2,3空填入的应是p,q所指结点的值相等时，分别使它们指向其直接前趋合直接后继，以便进行下一轮比较。
[答案]p->prior!q||q->next!=p,p=p->next,q=q->prior。
10.已知一个顺序表中的元素按值非递增有序排列，试编写一个函数，删除顺序表中多余的值相同的元素。
[分析]由于顺序表中的元素按值非递增有序排序，值相同的元素一定排列在一起，因此可以依次比较相邻的元素，若值相等着删除其中一个，并使其后面的元素依次向前移一位；若值不相等，这继续向后查找。
| 
