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

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