【正文】 puts(Got a null pointer)。else puts(Got a valid pointer)。這是一個(gè)有趣的問題。最近在我的一個(gè)同事不經(jīng)意把0值傳給了函數(shù)malloc，得到了一個(gè)合法的指針之后，我才想到這個(gè)問題。這就是上面的代碼，該代碼的輸出是“Got a valid pointer”。我用這個(gè)來開始討論這樣的一問題，看看被面試者是否想到庫例程這樣做是正確。得到正確的答案固然重要，但解決問題的方法和你做決定的基本原理更重要些。第五大塊：鏈表33. 設(shè)計(jì)一個(gè)用鏈表表示的直接插入排序算法typedef struct node{int key。struct node *next。}NODE。sort(NODE *h){NODE *p,*h1,*t,*q。h1=hnextnext。hnextnext=null。while(h1!=null){t=h1。 h1=h1next。q=h。p=hnext。while(pnumtnumamp。amp。p!=null) {q=p。p=pnext。} tnext=p。qnext=t。}}34. 鏈表題：一個(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 。}(4)單鏈表刪除：假設(shè)表中有數(shù)據(jù)2 8 11 6 9 ，題目是：找到數(shù)據(jù)為11的節(jié)點(diǎn)并將之從鏈表中刪除；【題目誤區(qū)】這里要注意，只能用一次循環(huán)！如果用了兩次，那就被面試官判為錯(cuò)誤35. 如何判斷一個(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(head==NULL) return false。 node *low=head, *fast=headnext。 while(fast!=NULL amp。amp。 fastnext!=NULL) { low=lownext。 fast=fastnextnext。 if(low==fast) return true。 } return false。}36. 雙向鏈表的刪除結(jié)點(diǎn)第六大塊：算法寫在具體之前：我們一個(gè)學(xué)員去面試，面試官問：你的項(xiàng)目中用到算法了嗎？他想了想說，沒有。結(jié)果可想而知。后來我問他，你《XXX管理系統(tǒng)中》，沒有排序嗎？他說有啊，我說那里面沒有用到算法嗎？他說，冒泡是算法嗎？無語！??！【一句話擺平】所有排序、查找，必然用到算法37. 查找算法include include int MAX=100000。 /*二分查找*/ int bs(int data[],int dvalue){ int l,u,m。 int p。 l=0。u=MAX。 for(。){ if(lu) return 1。 m=(l+u)/2。 if (data[m]==dvalue){ return m。 }else if(data[m]dvalue){ u=m1。 }else{ l=m+1。 } } } /*順序查找*/ int ss(int data[],int dvalue){ int i。 // int l=len(data)。 for(i=0。iMAX。i++){ // printf(%d\n,data[i])。 if(data[i]==dvalue){ return i。 } } return 1。 } int main(){ //int MAX=1000。 int data[MAX]。 int i。 //給數(shù)組賦值 for(i=0。iMAX。i++){ data[i]=i*10。 } //要查找的值 int value=300。 //順序查找 int s=ss(data,value)。 printf(%d\n,s)。 //二分查找 int d=bs(data,value)。 printf(%d\n,d)。 return 0。 } 38. 快速排序39. 編寫算法判斷二叉樹是否是完全二叉樹（此題看情況）分析：完全二叉樹是指在一棵二叉樹中除最后一層外，其余層都是滿的，并且最后一層或者是滿的，或者在右邊缺少連續(xù)若干結(jié)點(diǎn)。要判定一棵二叉樹是否完全二叉樹，應(yīng)先建立一棵二叉樹，此例采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的先序算法建立一棵二叉樹。判定一棵二叉樹是否是完全二叉樹，可以使用隊(duì)列，在層次遍歷的過程中利用完全二叉樹“若某結(jié)點(diǎn)無左孩子，就一定沒有右孩子”的原則進(jìn)行判斷。答案：include typedef char ElementType。typedef struct node{ ElementType data。 struct node *LChild,*RChild。}BinNode, *BinTree。void CreateBinTree(BinTree *root){char ch。 ch=getchar()。 if (ch==’’) *root=NULL。 else { *root=(BinTree)malloc(sizeof(BinNode))。 (*root)data=ch。 CreateBinTree(amp。((*root)LChild))。 CreateBinTree(amp。((*root)RChild))。 }}int JudgeComplete(BinTree bt) /* 判斷二叉樹是否是完全二叉樹，是返回1，不是返回0 */{ int tag=0,front,rear。 BinTree p=bt,Q[50]。 /* Q是隊(duì)列，元素是二叉樹結(jié)點(diǎn)指針，容量足夠大 */ if(p==NULL) return 1。 front=rear=0。 Q[++rear]=p。 /* 初始化隊(duì)伍，根結(jié)點(diǎn)指針入隊(duì) */ while(front!=rear) {p=Q[++front]。 if(pLChildamp。amp。!tag) Q[++rear]=pLChild。 /* 左孩子入隊(duì) */ else if(pLChild) return 0。 /* 前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空 */ else tag=1。 /* 首次出現(xiàn)結(jié)構(gòu)為空 */ if(pRChildamp。amp。!tag) Q[++rear]=pRChild。 /* 右孩子入隊(duì) */ else if(pRChild) return 0。 else tag=1。 }return 1。}main(){int y。BinTree bt。printf(請(qǐng)輸入結(jié)點(diǎn)數(shù)據(jù)：)。 CreateBinTree(amp。bt)。y=JudgeComplete(bt)。if(y==1) printf(該二叉樹是完全二叉樹\n)。 else printf(該二叉樹不是完全二叉樹\n)。}40. 已知數(shù)據(jù)序列為（12，5，9，20，6，31，24），對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫出插入排序和冒泡排序41. unsigned int intvert(unsigned int x,int p,int n)實(shí)現(xiàn)對(duì)x的進(jìn)行轉(zhuǎn)換,p為起始轉(zhuǎn)化位,n為需要轉(zhuǎn)換的長度,=0b0001 0001,p=4,n=3轉(zhuǎn)換后x=0b0110 0001unsigned int intvert(unsigned int x,int p,int n){ 　　unsigned int _t = 0。 　　unsigned int _a = 1。 　　for(int i = 0。 i n。 ++i){ 　　_t |= _a。 　　_a = _a 1。 　　} 　　_t = _t p。 　　x ^= _t。 　　return x。}42. 單詞反轉(zhuǎn) 如：this is a pig 反轉(zhuǎn)后：pig a is this 寫一個(gè)函數(shù)實(shí)現(xiàn)該反轉(zhuǎn)?！军c(diǎn)評(píng)】要求不能增加復(fù)雜度43. 寫一個(gè)程序，判斷運(yùn)行程序的系統(tǒng)的是大字節(jié)序還是小字節(jié)序？寫函數(shù)實(shí)現(xiàn)大小字節(jié)序轉(zhuǎn)換。void checkSystem(){ union check { int i。 char ch。 }c。 = 1。 if ((char)1 == ) printf(系統(tǒng)是小字節(jié)序\n)。 else printf(系統(tǒng)是大字節(jié)序\n)。}int main(){ checkSystem()。}44. 用C語言完成以下這個(gè)子程序，要求：1，定義一個(gè)一維數(shù)組，數(shù)組大小為24。2，產(chǎn)生023的隨機(jī)數(shù)。3，將產(chǎn)生的隨