40. 鏈表題：一個鏈表的結點結構

struct Node

{

int data ;

Node *next ;

};

typedef struct Node Node ;

(1)已知鏈表的頭結點head,寫一個函數把這個鏈表逆序 ( Intel)

Node * ReverseList(Node *head) //鏈表逆序

{

if ( head == NULL || head->next == NULL )

return head;

Node *p1 = head ;

Node *p2 = p1->next ;

Node *p3 = p2->next ;

p1->next = NULL ;

while ( p3 != NULL )

{

p2->next = p1 ;

p1 = p2 ;

p2 = p3 ;

p3 = p3->next ;

}

p2->next = p1 ;

head = p2 ;

return head ;

}

(2)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序。(保留所有結點，即便大小相同）

Node * Merge(Node *head1 , Node *head2)

{

if ( head1 == NULL)

return head2 ;

if ( head2 == NULL)

return head1 ;

Node *head = NULL ;

Node *p1 = NULL;

Node *p2 = NULL;

if ( head1->data < head2->data )

{

head = head1 ;

p1 = head1->next;

p2 = head2 ;

}

else

{

head = head2 ;

p2 = head2->next ;

p1 = head1 ;

}

Node *pcurrent = head ;

while ( p1 != NULL && p2 != NULL)

{

if ( p1->data <= p2->data )

{

pcurrent->next = p1 ;

pcurrent = p1 ;

p1 = p1->next ;

}

else

{

pcurrent->next = p2 ;

pcurrent = p2 ;

p2 = p2->next ;

}

}

if ( p1 != NULL )

pcurrent->next = p1 ;

if ( p2 != NULL )

pcurrent->next = p2 ;

return head ;

}

(3)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序，這次要求用遞歸方法進行。 (Autodesk)

答案：

Node * MergeRecursive(Node *head1 , Node *head2)

{

if ( head1 == NULL )

return head2 ;

if ( head2 == NULL)

return head1 ;

Node *head = NULL ;

if ( head1->data < head2->data )

{

head = head1 ;

head->next = MergeRecursive(head1->next,head2);

}

else

{

head = head2 ;

head->next = MergeRecursive(head1,head2->next);

}

return head ;

}

41. 分析一下這段程序的輸出 (Autodesk)

class B

{

public:

B()

{

cout<<"default constructor"<<endl;

}

~B()

{

cout<<"destructed"<<endl;

}

B(int i):data(i) //B(int) works as a converter ( int -> instance of B)

{

cout<<"constructed by parameter " << data <<endl;

}

private:

int data;

};

B Play( B b)

{

return b ;

}

(1) results:

int main(int argc, char* argv[]) constructed by parameter 5

{ destructed B(5)形參析構

B t1 = Play(5); B t2 = Play(t1); 　 destructed t1形參析構

return 0;　　　　　　　　　　　　　　 destructed t2　注意順序！

} destructed t1

(2) results:

int main(int argc, char* argv[]) constructed by parameter 5

{ destructed B(5)形參析構

B t1 = Play(5); B t2 = Play(10); 　 constructed by parameter 10

return 0;　　　　　　　　　　　　　　 destructed B(10)形參析構

} destructed t2　注意順序！

destructed t1

42. 寫一個函數找出一個整數數組中，第二大的數 （microsoft）

答案：

const int MINNUMBER = -32767 ;

int find_sec_max( int data[] , int count)

{

int maxnumber = data[0] ;

int sec_max = MINNUMBER ;

for ( int i = 1 ; i < count ; i++)

{

if ( data[i] > maxnumber )

{

sec_max = maxnumber ;

maxnumber = data[i] ;

}

else

{

if ( data[i] > sec_max )

sec_max = data[i] ;

}

}

return sec_max ;

}