【文章內(nèi)容簡(jiǎn)介】 while (pamp。amp。 pinfo!=x) p=pnext。 return p。C．node *p=headnext。while (pamp。amp。pinfo!=x) p=pnext。 return p。D．node *p=head。 while (pinfo!=x) p=pnext 。 return p。（4）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ D ）。A．必須是連續(xù)的C．一定是不連續(xù)的B．部分地址必須是連續(xù)的D．連續(xù)不連續(xù)都可以（5）在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是（ B）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)（6）用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（ D ）。A．僅修改隊(duì)頭指針C．隊(duì)頭、隊(duì)尾指針都要修改B．僅修改隊(duì)尾指針D．隊(duì)頭,隊(duì)尾指針都可能要修改（7）若從鍵盤輸入 n 個(gè)元素，則建立一個(gè)有序單向鏈表的時(shí)間復(fù)雜度為（ B ）。A．O(n)B．O(n2)C．O(n3)D．O(nlog2n)（8）下面哪個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)（ D ）。A．順序表B．鏈表C．散列表D．隊(duì)列（9）在一個(gè)單鏈表中，若刪除 p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（ A ）。A．pnext=pnextnext。C．pnext=pnext。B．p=pnext。 pnext=pnextnext。D．p =pnextnext。（10）在一個(gè)單鏈表中，若 p 所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在 p 之后插入 s 所指結(jié)點(diǎn)，則執(zhí)行（ B ）。A．snext=p。pnext=s。C．snext=pnext。p=s。B．snext=pnext。pnext=s。D．pnext=s。snext=p。 設(shè)計(jì)一個(gè)算法，求一個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)?！敬稹浚?jiǎn)捂湵泶鎯?chǔ)結(jié)構(gòu)定義如下（相關(guān)文件：）include 14十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材include typedef struct node{ int data。struct node *next。}linknode。typedef linknode *linklist。/*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表*/linklist creatlinklist(){ linklist head,r,s。int x。head=r=(linklist)malloc(sizeof(linknode))。printf(\n 請(qǐng)輸入一組以 0 結(jié)束的整數(shù)序列：\n)。scanf(%d,amp。x)。while (x){ s=(linklist)malloc(sizeof(linknode))。sdata=x。rnext=s。r=s。scanf(%d,amp。x)。}rnext=NULL。return head。}/*輸出帶頭結(jié)點(diǎn)的單鏈表*/void print(linklist head){ linklist p。p=headnext。printf(List is:\n)。while(p){ printf(%5d,pdata)。p=pnext。}printf(\n)。}基于上述結(jié)構(gòu)定義，求單鏈表中的結(jié)點(diǎn)個(gè)數(shù)的算法程序如下：int count(linklist head)高等學(xué)校精品資源共享課程{int c=0。linklist p=head。while (p)15十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程{c++。p=pnext。}return c。} 設(shè)計(jì)一個(gè)算法，求一個(gè)帶頭結(jié)點(diǎn)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)?！敬稹浚簬ь^結(jié)點(diǎn)的單鏈表的存儲(chǔ)結(jié)構(gòu)定義同題 ，實(shí)現(xiàn)本題功能的算法程序如下（）include int count(linklist head){ int c=0。linklist p=headnext。while (p){c++。p=pnext。}return c。}main()/*測(cè)試函數(shù)*/{linklist head。head=creatlinklist()。print(head)。printf(\nLength of head is:%d,count(head))。getch()。}當(dāng)輸入 5 個(gè)數(shù)據(jù)時(shí)，產(chǎn)生的輸出結(jié)果如下圖所示： 設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表中值為 y 的結(jié)點(diǎn)前面插入一個(gè)值為 x 的結(jié)點(diǎn)。即使值為 x 的新結(jié)點(diǎn)成為值為 y 的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚篿nclude void insert(linklist head,int y,int x){/*在值為 y 的結(jié)點(diǎn)前插入一個(gè)值為 x 的結(jié)點(diǎn)*/linklist pre,p,s。pre=head。16}十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材p=headnext。while (p amp。amp。 pdata!=y){ pre=p。p=pnext。}if (p)/*找到了值為 y 的結(jié)點(diǎn)*/{ s=(linklist)malloc(sizeof(linknode))。sdata=x。snext=p。prenext=s。}高等學(xué)校精品資源共享課程void main(){linklist head。int y,x。head=creatlinklist()。print(head)。/*測(cè)試程序*//*創(chuàng)建單鏈表*//*輸出單鏈表*/printf(\n 請(qǐng)輸入 y 與 x 的值:\n)。scanf(%d %d,amp。y,amp。x)。insert(head,y,x)。print(head)。}程序的一種運(yùn)行結(jié)果如下圖所示： 設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表中各個(gè)結(jié)點(diǎn)值是否有序?！敬稹浚篿nclude int issorted(linklist head,char c)/*當(dāng)參數(shù) c=’a’時(shí)判斷鏈表是否為升序，當(dāng)參數(shù) c=’d’是判斷鏈表是否為降序*/{ int flag=1。linklist p=headnext。switch (c)17}十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材{case 39。a39。:/*判斷帶頭結(jié)點(diǎn)的單鏈表 head 是否為升序*/while (p amp。amp。pnext amp。amp。 flag){if (pdata=pnextdata) p=pnext。else flag=0。}break。case 39。d39。:/*判斷帶頭結(jié)點(diǎn)的單鏈表 head 是否為降序*/while (p amp。amp。pnext amp。amp。 flag){if (pdata=pnextdata) p=pnext。else flag=0。}break。}return flag。高等學(xué)校精品資源共享課程int main()/*測(cè)試程序*/{ linklist head。head=creatlinklist()。print(head)。if (issorted(head,39。a39。)) printf(單鏈表 head 是升序排列的！\n)。elseif (issorted(head,39。d39。)) printf(單鏈表 head 是降序排列的！\n)。else printf(單鏈表 head 是無序的！\n)。}程序運(yùn)行時(shí)的三種輸出結(jié)果如下圖所示： 設(shè)計(jì)一個(gè)算法，利用單鏈表原來的結(jié)點(diǎn)空間將一個(gè)單鏈表就地轉(zhuǎn)置。【答】：include void verge(linklist head)18十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材{/*本函數(shù)的功能是就地倒置帶頭結(jié)點(diǎn)的單鏈表*/linklist p,q。p=headnext。headnext=NULL。高等學(xué)校精品資源共享課程while (p)/*每次從原表取一個(gè)結(jié)點(diǎn)插入到新表的最前面*/{q=p。p=pnext。qnext=headnext。headnext=q。}}int main(){linklist head。head=creatlinklist()。print(head)。verge(head)。print(head)。/*測(cè)試函數(shù)*//*創(chuàng)建單鏈表*//*輸出原單鏈表*//*就地倒置單鏈表*//*輸出倒置后的單鏈表*/} 設(shè)計(jì)一個(gè)算法，將一個(gè)結(jié)點(diǎn)值自然數(shù)的單鏈表拆分為兩個(gè)單鏈表，原表中保留值為偶數(shù)的結(jié)點(diǎn)，而值為奇數(shù)的結(jié)點(diǎn)按它們?cè)谠碇械南鄬?duì)次序組成一個(gè)新的單鏈表。【答】：include linklist sprit(linklist head){/*將帶頭結(jié)點(diǎn)的單鏈表 head 中的奇數(shù)值結(jié)點(diǎn)刪除生成新的單鏈表并返回*/linklist L,pre,p,r。L=r=(linklist)malloc(sizeof(linknode))。rnext=NULL。pre=head。p=headnext。while (p){if (pdata%2==1){prenext=pnext。rnext=p。r=p。p=prenext。}/*刪除奇數(shù)值結(jié)點(diǎn)*/else{pre=p。p=pnext。/*保留偶數(shù)值結(jié)點(diǎn)*/19}十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材}高等學(xué)校精品資源共享課程rnext=NULL。return L。}int main(){linklist head,L。head=creatlinklist()。print(head)。L=sprit(head)。/*置鏈表結(jié)束標(biāo)記*//*測(cè)試函數(shù)*//*創(chuàng)建單鏈表*//*輸出原單鏈表*//*分裂單鏈表 head*/printf(\n 原單鏈表為:\n)。print(head)。/*輸出倒置后的單鏈表*/printf(\n 分裂所得奇數(shù)單鏈表為:\n)。print(L)。}本程序的一組測(cè)試情況如下圖所示。 設(shè)計(jì)一個(gè)算法，對(duì)一個(gè)有序的單鏈表，刪除所有值大于 x 而不大于 y 的結(jié)點(diǎn)?！敬稹浚篿nclude void deletedata(linklist head,datatype x,datatype y){/*刪除帶頭結(jié)點(diǎn)單鏈表中所有結(jié)點(diǎn)值大于 x 而不大于 y 的結(jié)點(diǎn)*/linklist pre=head,p,q。p=headnext。/*初始化*/while (p amp。amp。 pdata=x)/*找第 1 處大于 x 的結(jié)點(diǎn)位置*/{pre=p。p=pnext。}while (p amp。amp。 pdata=y)p=pnext。q=prenext。/*找第 1 處小于 y 的位置*//*刪除大于 x 而小于 y 的結(jié)點(diǎn)*/prenext=p。20十二五普通高等教育國(guó)家級(jí)本科規(guī)劃教材pre=qnext。高等學(xué)校精品資源共享課程while (pre!=p){free(q)。q=pre。pre=prenext。}}void main()/*釋放被刪除結(jié)點(diǎn)所占用的空間*//*測(cè)試函數(shù)*/{linklist head,L。datatype x,y。head=creatlinklist()。print(head)。/*創(chuàng)建單鏈表*//*輸出原單鏈表*/printf(\n 請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)區(qū)間:\n)。scanf(%d%d,amp。x,amp。y)。deletedata(head,x,y)。print(