【正文】 ( !tag )break 。}}void main( void ){vectorintdata。ifstream in(c:\\)。if ( !in){coutfile error!。exit(1)。}int temp。while (!()){intemp。(temp)。}()。 //關(guān)閉輸入文件流order(data)。ofstream out(c:\\)。if ( !out){coutfile error!。exit(1)。}for ( i = 0 。 i () 。 i++)outdata 。()。 //關(guān)閉輸出文件流}40. 鏈表題：一個(gè)鏈表的結(jié)點(diǎn)結(jié)構(gòu)struct node{int data 。node *next 。}。typedef struct node node 。(1)已知鏈表的頭結(jié)點(diǎn)head,寫一個(gè)函數(shù)把這個(gè)鏈表逆序 ( intel)node * reverselist(node *head) //鏈表逆序{if ( head null || headnext null )return head。node *p1 = head 。node *p2 = p1next 。node *p3 = p2next 。p1next = null 。while ( p3 != null ){p2next = p1 。p1 = p2 。p2 = p3 。p3 = p3next 。}p2next = p1 。head = p2 。return head 。}(2)已知兩個(gè)鏈表head1 和head2 各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序。(保留所有結(jié)點(diǎn)，即便大小相同）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 ( head1data head2data ){head = head1 。p1 = head1next。p2 = head2 。}else{head = head2 。p2 = head2next 。p1 = head1 。}node *pcurrent = head 。while ( p1 != null amp。amp。 p2 != null){if ( p1data = p2data ){pcurrentnext = p1 。pcurrent = p1 。p1 = p1next 。}else{pcurrentnext = p2 。pcurrent = p2 。p2 = p2next 。}}if ( p1 != null )pcurrentnext = p1 。if ( p2 != null )pcurrentnext = p2 。return head 。}(3)已知兩個(gè)鏈表head1 和head2 各自有序，請(qǐng)把它們合并成一個(gè)鏈表依然有序，這次要求用遞歸方法進(jìn)行。 (autodesk)答案：node * mergerecursive(node *head1 , node *head2){if ( head1 null )return head2 。if ( head2 null)return head1 。node *head = null 。if ( head1data head2data ){head = head1 。headnext = mergerecursive(head1next,head2)。}else{head = head2 。headnext = mergerecursive(head1,head2next)。}return head 。}41. 分析一下這段程序的輸出 (autodesk)class b{public:b(){coutdefault constructorendl。}~b(){coutdestructedendl。}b(int i):data(i) //b(int) works as a converter ( int instance of b){coutconstructed 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)形參析構(gòu)b t1 = play(5)。 b t2 = play(t1)。 　 destructed t1形參析構(gòu)return 0?！　　　　　　　　　　　　　?destructed t2　注意順序！} destructed t1(2) results:int main(int argc, char* argv[]) constructed by parameter 5{ destructed b(5)形參析構(gòu)b t1 = play(5)。 b t2 = play(10)。 　 constructed by parameter 10return 0?！　　　　　　　　　　　　　?destructed b(10)形參析構(gòu)} destructed t2　注意順序！destructed t142. 寫一個(gè)函數(shù)找出一個(gè)整數(shù)數(shù)組中，第二大的數(shù) （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 maxnumber ){sec_max = maxnumber 。maxnumber = data 。}else{if ( data sec_max )sec_max = data 。}}return sec_max 。}43. 寫一個(gè)在一個(gè)字符串(n)中尋找一個(gè)子串(m)第一個(gè)位置的函數(shù)。kmp算法效率最好，時(shí)間復(fù)雜度是ｏ(n+m)。44. 多重繼承的內(nèi)存分配問題：比如有class a : public class b, public class c {}那么a的內(nèi)存結(jié)構(gòu)大致是怎么樣的？這個(gè)是pilerdependent的, 不同的實(shí)現(xiàn)其細(xì)節(jié)可能不同。如果不考慮有虛函數(shù)、虛繼承的話就相當(dāng)簡單；否則的話，相當(dāng)復(fù)雜?？梢詤⒖肌渡钊胩剿鱟++對(duì)象模型》，或者：45. 如何判斷一個(gè)單鏈表是有環(huán)的？（注意不能用標(biāo)志位，最多只能用兩個(gè)額外指針）struct node { char val。 node* next。}bool check(const node* head){} //return false : 無環(huán)；true: 有環(huán)一種o（n）的辦法就是（搞兩個(gè)指針，一個(gè)每次遞增一步，一個(gè)每次遞增兩步，如果有環(huán)的話兩者必然重合，反之亦然）：bool check(const node* head){if(headnull) return false。node *low=head, *fast=headnext。while(fast!=null amp。amp。 fastnext!=null){low=lownext。fast=fastnextnext。if(lowfast) return true。}return false。}26 / 26