试题1．在一个长度为n的顺序存储线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素，需要从后往前依次后移几个元素？删除第i个元素时，需要从前向后前移几个元素？
分析：考察线性表中顺序存储的特点。
答案：n-i+1，n-i
试题2．已知链表的头结点head，写一个函数把这个链表逆序。
分析：考察线性表中链式存储反转算法。
答案：
01． void List::reverse（）
02. {
03. list_node * p = head;
04. list_node * q = p->next;
05. list_node * r = NULL;
06. while(q){;
07. r = q->next;
08. q->next = p;
09. p = q;
10. q = r;
11. }
12. head->next = NULL;
13. head = p;
14. }
试题3．找出单向链表中的中间结点。
分析：两个指针，一个步长为1，另一个步长为2。步长为2的走到底后步长为1的正好到中间。
答案：
01. list_node * List::middleElement（）
02. {
03. list_node * p = head;
04. list_node * q = head->next;
05. while(q){;
06. p = p->next;
07. if(q)q=q->next;
08. if(q)q=q->next;
09. }
10. }
试题4．如何检查一个单向链表上是否有环。
分析：同样两个指针，一个步长为1，另一个步长为2，如果两个指针能相遇则有环。
答案：
01． list_node * List::getJoinPointer（）
02. {
03.
04. if(head == NULL || head->next == NULL)return NULL;
05. list_node * one = head;
06. list_node * two = head->next;
07. while(one != two){
08. one = one->next;
09. if(two)two=two->next;
10. else break;
11. if(two)two=two->next;
12. else break;
13. };
14. if(one == NULL || two == NULL)return NULL;
15. return one;
16. }
版权声明：51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
