笔试面试题—软件测试工程师 试题 1.在一个长度为 n 的.顺序存储线性表中，向第 i 个元素(1in+1)之前插入一个新元素，需要从后往前依次后移几个元素?删除第 i 个元素时，需要从前向后前移几个元素? 分析：考察线性表中顺序存储的特点，笔试面试题—软件测试工程师。 答案：ni+1，ni 试题 2.已知链表的头结点 head，写一个函数把这个链表逆序。 分析：考察线性表中链式存储反转算法。 答案： 01. void List::reverse() 02. { 03. list_node * p = head; 04. list_node * q = pnext; 05. list_node * r = NULL; 06. while(q){; 07. r= qnext; 08. qnext = p; 09. p= q; 10. q= r; 11. } 12. headnext = 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 =headnext; 05. while(q){; 06. p= pnext; 07. if(q)q=qnext; 08. if(q)q=qnext; 09. } 10. } 试题 4.如何检查一个单向链表上是否有环，资料共享平台《笔试面试题—软件测试工程师》(https://)。 分析：同样两个指针，一个步长为 1，另一个步长为 2，假如两个指针能相遇则有环。 答案： 01. list_node * List::getJoinPointer() 02. { 03. 04. if(head == NULL ||headnext == NULL)return NULL; 05. list_node * one = head; 06. list_node * two =headnext; 07. while(one != two){ 08. one =onenext; 09. if(two)two=twonext; 10. elsebreak; 11. if(two)two=twonext; 12. elsebreak; 13. }; 14. if(one == NULL || two ==NULL)return NULL; 15. return one; 16. }
