2012數(shù)據(jù)結(jié)構(gòu)-習(xí)題及程序設(shè)計(jì)整理

實(shí)用文檔實(shí)用文檔第二章1、首尾順序逆置2、找出順序表中最大值和最小值及位置3、頭插法算法4、尾插法：5、帶頭結(jié)點(diǎn)的單鏈表，向表頭插入一個(gè)結(jié)點(diǎn)：6、單鏈表中查找第i個(gè)結(jié)點(diǎn)：7、在單鏈表中查找值為K的結(jié)點(diǎn)8、單鏈表刪除操作：9、重要習(xí)題，頭結(jié)點(diǎn)與尾結(jié)點(diǎn)互換：10、重要習(xí)題，一個(gè)單鏈表拆為兩個(gè)奇偶單鏈表：試寫一個(gè)算法，將一個(gè)頭結(jié)點(diǎn)為a的帶頭結(jié)點(diǎn)的單鏈表A分解成兩個(gè)單鏈表A和B，其中頭結(jié)點(diǎn)指針分別為a和b，使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素，而B鏈表中含有原鏈表中序號為偶數(shù)的元素，并保持原來的相對順序。11、循環(huán)鏈表插入結(jié)點(diǎn)后仍然保持有序：12、重要習(xí)題(刪除表中所有數(shù)值相同的多余元素)：13、雙向鏈表的刪除操作：14、雙向鏈表的插入操作：在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針數(shù)量是4個(gè)。包括新插入的新結(jié)點(diǎn)的指針，還有插入結(jié)點(diǎn)的前面結(jié)點(diǎn)的next域，和后面結(jié)點(diǎn)的prior域。第二章課后習(xí)題14、設(shè)計(jì)兩個(gè)順序表A和B，且都遞增有序，試寫一算法，從A中刪除與B中相同的元素（也就是計(jì)算A-B）。15、已知head是指向一個(gè)帶頭結(jié)點(diǎn)的單鏈表的頭指針，P指向該鏈表的任一結(jié)點(diǎn)，試寫一算法，將P指向結(jié)點(diǎn)與其后繼結(jié)點(diǎn)位置交換。（q為p的后繼結(jié)點(diǎn)，s是首結(jié)點(diǎn)（頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，r為首結(jié)點(diǎn)以后的結(jié)點(diǎn)）16、已知兩個(gè)單鏈表A和B分別表示兩個(gè)集合，其元素值遞增有序，試寫一算法，求A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲(chǔ)。r=head;查找p的前趨結(jié)點(diǎn)17、設(shè)有一個(gè)頭結(jié)點(diǎn)的雙向循環(huán)鏈表，head為鏈表的頭指針，試寫一算法，實(shí)現(xiàn)在值為x的結(jié)點(diǎn)之前插入一個(gè)值為y的結(jié)點(diǎn)。第三章一、隊(duì)列算法f31的功能是清空帶頭結(jié)點(diǎn)的鏈隊(duì)列Q，請?zhí)羁?。Typestructnode{DataTypedata;Structnode*next;}QueueNode;{QueueNode*front;//隊(duì)頭指針二、填空題15、如果編號為1，2，3的3輛列車進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，那么可能得到的3輛車出站序列有哪些？不可能出現(xiàn)的序列是什么？16、簡述下列程序算法的功能（假設(shè)元素為整數(shù)類型）（1）voidex31(SeqStack*S){intA[80],i,n;n=0;while(!empty(S)){A[n]=pop[S];n++;}for(i=0;i<n;i++)push(S,A[i]);}答案：此算法功能是通過一個(gè)數(shù)組將一個(gè)棧中的所有元素逆置存放。例如原來?xiàng)中存放5個(gè)元素abcde，經(jīng)過算法執(zhí)行后，變?yōu)閑dcba。(2)voidex32(SeqStack*s,intc){SeqStackT;intd;while(!StackEmpty(S)){d=pop(S);if(d!=c)push(T,d);}while(!StackEmpty(T)){d=pop(T);if(d!=c)push(S,d);}}答案：通過一個(gè)中間棧T，達(dá)到刪除棧S中所有與變量c相同的元素。17、寫出下列程序的輸出結(jié)果（棧結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽址蚦har）SeqStackS;Charx,y;X=`c`,y=`k`;Push(S,x);push(S,`a`);Push(S,y);x=pop(S);Push(S,`t`);push(S,x);X=pop(S);push(S,`s`);While(!StackEmpty(S)){Y=pop(S);Putchar(y);}Putchar(x);該程序段執(zhí)行過程中，變量x,y和棧S中的順序變化情況：x=`c`,y=`k`,S=”&”;x=`c`,y=`k`,S=”cak”;x=`k`,y=`k`,S=”cat”；x=`k`,y=`k`,S=”catk”;x=`k`,y=`k`,S=”cats”;最后輸出結(jié)果為stack19、在循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)下，分別寫出入隊(duì)（插入元素），出隊(duì)（刪除元素），時(shí)修改尾、隊(duì)頭指針的操作語句以及求隊(duì)列長度的公式。入隊(duì)操作指針移動(dòng)語句為cq.rear=(cq.rear+1)%QueueSize;出隊(duì)操作指針移動(dòng)語句為cq.front=(cq.front+1)%QueueSize;隊(duì)列長度(cq.rear+QueueSize-cq.front)%QueueSize;20、利用兩個(gè)棧S1和S2模擬一個(gè)隊(duì)列，如何用棧的運(yùn)算來實(shí)現(xiàn)隊(duì)列的插入和刪除運(yùn)算？試寫出算法。21、試設(shè)計(jì)一個(gè)算法，實(shí)現(xiàn)輸入一個(gè)字符串并檢查字符串中是否含有圓括號，當(dāng)圓括號匹配時(shí)輸出括號內(nèi)的字符串，否則給出出錯(cuò)信息（提示：利用棧記錄在左括號出現(xiàn)后的字符）22、試?yán)醚h(huán)隊(duì)列（長度為K）存儲(chǔ)，編寫求斐波那契序列的前N（N>K）項(xiàng)（f0,f1,…fn-1）的算法，其函數(shù)定義如下：第四章22、1、2、3、4、6、已知A和B是兩個(gè)NxN的對稱矩陣，因?yàn)槭菍ΨQ矩陣，所以僅需要輸入下三角元素存入一維數(shù)組。試寫一算法，求對稱矩陣A與B的乘積。7、三角矩陣與對對性的三角矩陣很相似。三角矩陣：對稱矩陣:第五章1、求葉結(jié)點(diǎn)公式：2、3、4、5、若二叉樹從0開始排序，則：若二叉樹從1開始排序，則：第六章課后習(xí)題：22、對于圖，試給出：（1）圖的鄰接矩陣；（2）鄰接表和逆鄰接表；(3)強(qiáng)連通分量。23、第七章23、對于給定的一組關(guān)鍵字（46，32，55，81，65，11，25，43），進(jìn)行直接插入排序，寫出其排序的每一趟結(jié)果。24、寫出給定的一組關(guān)鍵字（26，18，60，14，7，45，13，32），寫出直接選擇排序，寫出其排序的每一趟結(jié)果。25、對于給定的關(guān)鍵字（41，62，13，84，35，96，57，39，79，61，15，83）,分別寫出執(zhí)行以下排序算法的每一趟排序結(jié)果。（1）希爾排序（5，2，1）（2）快速排序(3)基數(shù)排序26、對于給定的關(guān)鍵字（26，18，60，14，7，45，13，32），寫出執(zhí)行堆排序算法的每一趟結(jié)果。27、對待排序記錄關(guān)鍵字序列，在以下幾種情況下，進(jìn)行直接插入排序時(shí)（按升序）至多需要進(jìn)行多少次關(guān)鍵字的比較？(1)關(guān)鍵字從小到大順序有序（正序）（2）關(guān)鍵字從大到小順序有序（反序）（3）前一半關(guān)鍵字序列從小到大順序在序，后一半關(guān)鍵字序列是從大到小順序有序28、判斷下列序列是否為堆（小根堆或大根堆），如果不是，則將其調(diào)整為堆。（1）（17，18，60，70，7，32，73，65）（2）（96，83，72，45，28，54，60，23，38，15）（3）（25，48，16，35，79，82，23，40，36，72）（4）（12，24，18，65，33，56，33，92，86，70）29、算法設(shè)計(jì)已知一個(gè)按結(jié)點(diǎn)數(shù)值遞增有序的單鏈表，試寫一算法，插入一個(gè)新記錄，使得鏈表仍然按關(guān)鍵字從小到大的次序排列。已知兩個(gè)有序列A[0…n-1]和B[0…m-1]，試寫一算法，將它們合并為一個(gè)有序表C【0…m+n-1】1、直接插入排序2、希爾排序3、冒泡排序（從后往前兩兩交換）第八章21、分別畫出線性表（5，10，15，20，25，30，35，40）中用二分查找方法查找關(guān)鍵字等于10、30及39的查找過程。22、畫出對長度為13的有序表進(jìn)行二分查找的判定樹，并求其等概率情況下查找成功的平均查找長度。23、已知關(guān)鍵字序列（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）,按元素的先后順序依次插入到一棵初始為空的二叉排序樹中，畫出插入完成后的二叉排序樹，并求等概率情況下查找成功的平均查找長度。24、已長如圖的3階B樹，分別畫出插入26后的B樹和接著刪除48后的B樹。25、設(shè)散列函數(shù)f(k)=kmod13，散列表地址空間為0~12,對給定的關(guān)鍵字序列（19，14，23，01，68，20，84，27，55，11，10，79），分別以拉鏈法和線性探測法解決沖突構(gòu)造散列表，畫出所造的散列表，并指出這兩個(gè)散列表中查找每一個(gè)關(guān)鍵字時(shí)進(jìn)行比較的次數(shù)。26、用二分查找法對一個(gè)長度為12