電大數(shù)據(jù)結(jié)構(gòu)(本)形成性考核冊(cè)(作業(yè)4)

使用說明本作業(yè)冊(cè)是中央廣播電視大學(xué)計(jì)算機(jī)科與技術(shù)專業(yè)（本科）數(shù)據(jù)結(jié)構(gòu)（本）課程形成用。際，結(jié)合教學(xué)內(nèi)容進(jìn)行上機(jī)實(shí)踐，認(rèn)真完成作業(yè)和實(shí)驗(yàn)內(nèi)容。位。作業(yè)中各種題型練習(xí)和實(shí)驗(yàn)的完成情況進(jìn)行考核。對(duì)于實(shí)驗(yàn)內(nèi)容要求按實(shí)驗(yàn)要求認(rèn)真完成，并提交實(shí)驗(yàn)報(bào)告。作業(yè)1（）（）A.．P->next==NULLB．P==NULL17．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為()。18．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為()。址是。素時(shí)，需向后移動(dòng)個(gè)數(shù)據(jù)元素。個(gè)元素。 。以用操作_。14．設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p->next==NULL,通過操作,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。立于計(jì)算機(jī)的。尾結(jié)點(diǎn)的指針域由空指針改為指向。存儲(chǔ)順序不再一致，而是一種存儲(chǔ)結(jié)構(gòu)，又稱為。優(yōu)缺點(diǎn)。適當(dāng)?shù)恼Z句。{inti;head=p;q=p;p->next=NU{ }}適當(dāng)?shù)恼Z句。{inti; p->next=NULL; {p->data=i; }}intdelete(NODE*head,inti){intj;j=0;while((q!=NULL)&&(j<i-1))/*找到要?jiǎng)h除結(jié)點(diǎn)的直接前驅(qū)，{j++;} free(p);}1--線性表()。執(zhí)行。17．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為()。18．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為()。20．設(shè)有兩個(gè)串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為()。（）較合適。29.一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)33.設(shè)二維數(shù)組A[5][6]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，已知A[0][序存儲(chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是()。刪除一個(gè)元素隊(duì)列時(shí)，頭指針。第三步。9．假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)輸入序列a,b,c,d,e一系列棧操作12．在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中，都需要使用棧， ,中綴表達(dá)式(a+b)/c-(f-d/c)所對(duì)應(yīng)的后綴表達(dá)式是。18．在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為 23．需要壓縮存儲(chǔ)的矩陣可分為矩陣和度是。 和三項(xiàng)信息。（1）如果輸入序列由A，B，C組成，試給出全部可能列。序列?！?x2+x-1/x+5□(A+B)*C-D/(E+F)+G9．簡述廣義表和線性表的區(qū)別和聯(lián)系。typedefcharelemtype;typedefstruct{intfront,rear;intencqueue(sequeuetype*Q,elem□□Printf(〝Thecicularqueueisfull!□□□elemtypedel_cqu□□□① ①2.在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的鏈?zhǔn)疥?duì)列取出元素的算法完整。 } }構(gòu)和基本算法如下；2--棧、隊(duì)列、遞歸程序設(shè)計(jì)1.假定一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為()。()。（）13.利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有(A.n14.利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有(A.nB.n-1C.n+1子的最長帶權(quán)路徑長度為()。（）個(gè)結(jié)點(diǎn)。（）（）（）（）（）（）得到的一種頂點(diǎn)序列為。V15．在一棵樹中，每個(gè)結(jié)點(diǎn)的點(diǎn)，則稱此二叉樹為。 。 。 。 的關(guān)系。 訪問的過程?；芈飞系乃谢顒?dòng)都。f//dbbeecachj并寫出該二叉樹后續(xù)遍歷的結(jié)果。（1）設(shè)計(jì)一棵哈夫曼樹；（3）寫出每個(gè)字符的哈夫曼編碼。（1）給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍點(diǎn)序列；（2）給出G的一個(gè)拓?fù)湫蛄校唬?）給出從結(jié)點(diǎn)v1到結(jié)點(diǎn)v8的最短路徑。E={（V1，V2V1，V4V2，V4V3，V4V2，V5V3，V4V3，V5）}（1）畫出G的圖示；（2）然后給出G的鄰接矩陣和鄰接表；（3）寫出每個(gè)頂點(diǎn)的度。1.下面函數(shù)的功能是返回二叉樹BT中值為X的結(jié)點(diǎn)所在的層號(hào)，請(qǐng)?jiān)趧澯袡M線的地方填寫合適內(nèi)容。{if(3);}2.下面函數(shù)的功能是按照?qǐng)D的深度優(yōu)先搜索遍歷的方法，輸出得到該圖的生成樹中的各條邊，請(qǐng)?jiān)趧澯袡M線的地方填寫合適內(nèi)容。voiddfstree(adjmatrixGA,inti,intn){intj; if(GA[i][j]!=0&&GA[i][{printf("(%d,%d)%d,",i,j,GA[i][j]); }}2．根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中intBTreeLeafCount(structBTreeNod（2）計(jì)算圖中度為0的頂點(diǎn)數(shù)。3--棧、隊(duì)列、遞歸程序設(shè)計(jì)（）（）3．如果要求一個(gè)線性表既能較快地查找，又能動(dòng)態(tài)適應(yīng)變化要求，可以采用()查找方法。4.對(duì)于一個(gè)線性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該。9．已知一個(gè)有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較次。（）C.刪除一個(gè)元素后，不管用哪種方法處理沖突，都只需簡單地把D.因?yàn)闆_突是不可避免的，所以裝填因子A.冒泡排序B.希爾排序C.直接選擇排序16.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為()20.每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為。A.插入排序B.快速排序C.堆排21.在正常情況下，直接插入排序的時(shí)間復(fù)雜A.O(log2n)22.在正常情況下，冒泡排序的時(shí)間復(fù)雜A.O(log2n)A.O(log2n)24.在待排序元素基本有序的情況下，效率最高的排序方A.插入排序B.快速排序C.堆排25.下面幾種排序方法中，要求內(nèi)存量最大26.在下列排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列秩序無關(guān)（）A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)（）A.插入排序B.選擇排序C.快速排序D.歸并排序()。用的方法是。A.插入排序法B.選擇排序法C.冒泡排序法D.堆積排序法第七個(gè)元素47插入到已排序中，為尋找插入的合適位置需要進(jìn)行次元素間的比較。A.3B.4C.5D.6A.插入排序法B.選擇排序法C.快速排序法D.希爾排序法初始堆為。含有5個(gè)長度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為 ()。小到到大排序，經(jīng)過一趟冒泡排序后的序列為。元素序列的變化情況如下：A.希爾排序B.歸并排序C.快速排序D.直數(shù)據(jù)元素的各種屬性兩種類型的基本操作，而不進(jìn)行插入和刪除操作數(shù)據(jù)元素的查找表稱為。查找表中刪除已存在的某個(gè)數(shù)據(jù)元素，則稱此類查找表為。個(gè)數(shù)的。應(yīng)的關(guān)鍵字值必須按。之間的查找方法。（1）若左子數(shù)不空，則左子樹所有結(jié)點(diǎn)的值。（2）若右子數(shù)不空，則右子樹所有結(jié)點(diǎn)的值。