面试题 程序部分.doc

面试题_程序部分.doc〃个人搜集资料总结：李金霖
1、 题目：求 l+2+...+n,
要求不能使用乘除法、for、while> if、else、switch> case等关键字以及条件判断语句(A?B:C)。
#include <iostream>
using namespace std;
template<int N>
struct CalCIs
(
enum {sum = CalCls<N-l>::sum + N);
)；
templateo
struct CalCls<0>
(
enum {sum = 0};
)；
int main()
(
cout«"l+2+3+...+100 = "«CalCls<100>::sum«endl;
return 0;
)
2、 反转链表：
方法一：递归版本：
template<typename T>
ListNode<T>* reverse_slist_recursive(ListNode<T>* head)
(
if (!head| | !(head->next)) return head;
ListNode<T>* rtn = reverse_list(head->next);
head->next->next = head;
head->next = NULL;
return rtn;
方法二：利用循环
template<typename T>
ListNode<T>* reverse_slist_common(ListNode<T>* head) (
if (!head| | !(head->next)) return head;
ListNode<T> * prev=O;
while (head)
(
ListNode<T> * temp = head;
head = head->next;
temp->next = prev;
prev = temp;
}
return prev;
)
方法三：利用辅助栈
template<typename T>
ListNode<T>* reverse_slist_usingstack(ListNode<T>* head) (
if (!head| | !(head->next)) return head;
ListNode<T> *prev=O, *pcur=O;
stack<ListNode<T>*> si;
while (head)
(
(head);
head = head->next;
}
head = pcur = ();
while (!())
prev = ();
pcur->next = prev;
pcur = prev;
)
pcur->next = 0;
return head;
)
把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/\
6 14
/\/\
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16o
首先我们定义的二元查找树节点的数据结构如下：
struct BSTreeNode
(
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
｝；
*/
#include <>
#include <iostream>
using namespace std;
struct BSTreeNode
(
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
｝；
typedef BSTreeNode DoubleList;
DoubleList * pHead;
DoubleList * pListlndex;
void convertToDoubleList(BSTreeNode * pCurrent);
//创建二元查找树
void addBSTreeNode(BSTreeNode * & pCurrent, int value)
(
if (NULL == pCurren