单选题 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 (53) 。

单选题 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 (53) 。
A．O(1) B．O(n)
C．O(nlogn) D．O(n2)
【正确答案】 B
【答案解析】[解析] 本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。
插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；……；在第，n个结点之后插入需查找次。如果在每一个位罩上作插入的概率相等，即则在有序单链表上查找插入位置的平均比较次数为：
单选题 队和栈的主要区别是 (54) 。
A．逻辑结构不同
B．存储结构不同
C．所包含的运算个数不同
D．限定插入和删除的位置不同
【正确答案】 D
【答案解析】[解析] 本题主要考核队列和栈的概念。从逻辑上讲，它们都是属于线性结构。栈是将插入和删除限定在同一端进行的线性表；队列是将插入限定在表的一端，而将删除限定在表的另一端进行的线性表。它们都既可以顺序存储，也可以链接存储。
单选题 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若P→* next→*next=head，则 (55) 。
A．p指向头结点
B．p指向尾结点
C．*p的直接后继是头结点
D．*p的直接后继是尾结点
【正确答案】 D
【答案解析】[解析] 因为循环链表的尾结点的指针域中存放的是头指针，而尾结点由其直接前驱结点的指针域所指向，因此，当指针p指向尾结点的直接前驱结点时，满足关系式p-＞next-＞next=head。
单选题 判定“带头结点的链队列为空”的条件是 (56) 。
A．Q.front==NULL B．Q.rear==NULL
C．Q.front==Q.rear D．Q.front!=Q.rear
【正确答案】 C
【答案解析】[解析] 当带头结点的链队为空时，只有一个头结点，头、尾指针均指向头结点，因此有Q.front==Q.rear。