軟件學(xué)生會學(xué)習(xí)部試卷-數(shù)據(jù)結(jié)構(gòu)期末習(xí)題選講

習(xí)題選講數(shù)據(jù)結(jié)構(gòu)與算法分析1一．單項選擇題1、下面程序段的時間復(fù)雜度為（）A.O(n)B.O(n^2)C.O(n(n-1)/2)D.O(logn)voidfun1(intn){x=0;for(i=0;i<n;i++)

for(j=i+1;j<n;j++)

x++;}b22、若某線性表最常用的操作是刪除最后一個結(jié)點，則采用存儲結(jié)構(gòu)算法的時間效率最高的是（）

a.單鏈表

b.給出表尾指針的單循環(huán)鏈表

c.雙向鏈表

d.給出表尾指針雙向循環(huán)鏈表d33、在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是（

）A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．s->next=p;p->next=s;b44、若一個棧以向量S[1..n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是（

）A．top+=1;S[top]=x;B．S[top]=x;top+=1;C．top-=1;S[top]=x;D．S[top]=x;top--;c55、下列說法正確的是（

）(1)稀疏矩陣壓縮存儲后，必會失去隨機存取功能。(2)若一個廣義表的表頭為空表，則此廣義表亦為空表。(3)廣義表的取表尾運算，其結(jié)果通常是個表，但有時也可是個單元素值。(4)從邏輯結(jié)構(gòu)上看，n維數(shù)組是由多個n-1維的數(shù)組構(gòu)成。A．僅(1)(2) B．僅(1)(4)C．僅(2)(3) D．僅(3)(4)b66、下列說法錯誤的是（）在圖G的最小生成樹G1中，可能會有某條邊的權(quán)值超過未選邊的權(quán)值。不同求最小生成樹的方法得到的生成樹是相同的.當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動后，必將產(chǎn)生不同的關(guān)鍵路徑網(wǎng)絡(luò)的最小生成樹是唯一的A12B23C234D14c77、有n個葉子的哈夫曼樹中分支節(jié)點總數(shù)為（

）。A．n-1B．2n+1C．n+1D．不確定n+n2=2n2+1n=n2+1n2=n-1a88、已知一算術(shù)表達式的中綴形式為：A+B*C-D/E，后綴形式為：ABC*+DE/-，則其前綴形式為（）A．-A+B*C/DE B．-A+B*CD/E C．-+*ABC/DE D．-+A*BC/DEd99、設(shè)森林F中有三棵樹，第1、第2和第3棵樹的結(jié)點個數(shù)分別為M1、M2和M3（M1，M2，M3皆大于0）。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（

）A．M1 B．M1+M2 C．M3 D．M2+M3d1010、已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，G的拓撲序列是（）A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7a1111、下面關(guān)于折半查找的敘述中，正確的是（）A．表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B．表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型C．表必須有序，而且只能從小到大排列D．表必須有序，且表只能以順序方式存儲d1212、設(shè)二叉排序樹中關(guān)鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點，下述關(guān)鍵字序列中不可能是在二叉排序樹中查到的序列（）1）51，250，501，382，320，340，390，3632）24，877，125，342，421，623，501，3633）345，829，765，542，412，395，341，3634）965，741，259，478，275，249，360，363A）僅1）2）B）僅1）2）3）C）僅1）4）D）僅2）a1313、對序列{15,9,7,8,20,-1,4}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15,-1,4,8,20,9,7}，則該次采用的增量是（

）A．1 B．2 C．3 D．4d1414、下列說法中，錯誤的是（

）(1)外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進行排序，因此排序所花的時間取決于內(nèi)部排序的時間(2)在外部排序時，利用敗者樹方法選擇當(dāng)前最小關(guān)鍵字過程的復(fù)雜度取決于歸并的路數(shù)。(3)影響外排序的時間因素主要是內(nèi)存與外設(shè)交換信息的總次數(shù)。A．僅(1) B．僅(1)(2) C．僅(2)(3) D．(1)(2)(3)a1515、有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（

）。A．不確定B．2nC．2n+1D．2n-1d16填空題1、用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為（

）。2、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（

）。S×SS×S××2和4173、廣義表A=(a,b,((c,d),(e,(f,g))))，則Head(Tail(Head(Tail(Tail(A)))))的值為（

）。4、在一棵高度為4的完全3叉樹中，結(jié)點總數(shù)在（

）之間。5、假設(shè)一個森林由4個節(jié)點構(gòu)成，則森林可能的形態(tài)有（

）種（假設(shè)森林中的樹不計順序，樹中的各個子樹也不計順序）。14--4081819森林無向圖6、無向圖G(V,E)，其中V(G)={1,2,3,4,5,6,7}，E(G)={(1,2)，(1,3)，(2,4)，(2,5)，(3,6)，(3,7)，(6,7)，(5,1)}，對該圖從頂點3開始進行遍歷，去掉遍歷中未走過的邊，得到生成樹G’(V,E)，V(G’)=V(G)，E(G’)={(1,3)，(3,6)，(7,3)，(1,2)，(1,5)，(2,4)}，則采用的遍歷方法是（

）。寬度優(yōu)先遍歷207、有向圖G=(V,E)，其中V(G)={0,1,2,3,4,5}，用三元組<a,b,d>表示弧<a,b>及弧上的權(quán)d。E(G)為{<0,5,100>,<0,2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2,3,50>,<4,3,20>}，則從源點0到頂點3的最短路徑長度是（

）。50218、散列表的地址區(qū)間為0～17，散列函數(shù)為H(K)=Kmod17。采用線性探測法處理沖突，并將關(guān)鍵字序列：26，25，72，38，8，18，59依次存儲到散列表中。元素59存放在散列表中的地址是（

）。9、向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動

（）個元素。10、設(shè)有關(guān)鍵碼序列（Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X），要按照關(guān)鍵碼值遞增的次序進行排序。若采用初始步長為7的Shell排序法，則一趟掃描的結(jié)果是（

）。11n-i+122三、問答題1、設(shè)有nn對稱矩陣A，aij=aji如圖所示。為了節(jié)約存儲，只存對角線及對角線以上的元素。將上三角矩陣中的元素按列存放到一個一維數(shù)組B中。問：(1)存放對稱矩陣A上三角部分的一維數(shù)組B要有多少個元素？(2)若在一維數(shù)組B中從0號位置開始存放，則矩陣A中的任一元素aij在只存上三角部分的情形下，應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。232、假設(shè)關(guān)鍵字集合為（30，15，10，40，35，43，25，28），所有關(guān)鍵字順序輸入。要求：構(gòu)造一棵平衡二叉樹排序樹T（給出每插入一個節(jié)點后平衡二叉樹的狀態(tài)）。243、設(shè)有12個初始歸并段，其長度分別為8,6,30,35,62,18,84,68,11,60,3,20；試畫出表示歸并過程的最佳4路歸并樹，并計算樹的WPL。254、已知一棵二叉樹的先序遍歷序列是B,A,C,D,G,F,E和整數(shù)序列3,2,0,1,3,0,0。其中整數(shù)序列中的第i個數(shù)表示先序序列第i個結(jié)點的狀態(tài)，含義如下：0——本結(jié)點為葉結(jié)點1——本結(jié)點只有左孩子2——本結(jié)點只有右孩子3——本結(jié)點有兩個孩子（1）請畫出該二叉樹；（2）請說明，這樣的方式能否唯一地表示一棵二叉樹。若“能”，請用數(shù)學(xué)歸納法給出證明；若“不能”，請找出反例。26歸納法（構(gòu)造性證明）假設(shè)樹的節(jié)點數(shù)為n（n>=0）當(dāng)n=0時，空樹當(dāng)n=1時，只有根節(jié)點的樹歸納假設(shè):當(dāng)結(jié)點數(shù)小于k（k>1）時，結(jié)論正確。有先序列可以確定樹的根。如果根只有一個兒子（其狀態(tài)是1或2，不可能是0）其余結(jié)點全在根左子樹（或右子樹）上。由歸納假設(shè)，剩余部分（結(jié)點數(shù)小于k）可以唯一確定根的左（或右）子樹。如果根由兩個兒子（狀態(tài)為3），那么在先序序列中，根的右側(cè)結(jié)點必為根的左孩子，并可根據(jù)左孩子的狀態(tài)畫出左子樹；類似，剩余結(jié)點就是根的右子樹。27四、算法題1、對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。typedefstructnode{ intdata; structnode*next;}linknode,*link;28voidInsertSort(linkL){linkp,q,r,u; p=L->next; L->next=NULL; while((1)) { r=L; q=L->next; while((2)&&q->data<=p->data) {r=q;q=q->next; } u=p->next;

(3);

(4); p=u; }}typedefstructnode{ intdata; structnode*next;}linknode,*link;(1)p!=NULL∥當(dāng)鏈表尚未到尾(2)q!=NULL∥查p結(jié)點在鏈表中的插入位置(3)p->next=r->next∥將p結(jié)點鏈入鏈表中(4)r->next=p∥r是q的前驅(qū)，u是下個待插入結(jié)點的指針。292、請寫出判斷一棵二叉樹是否為平衡二叉樹的算法（假設(shè)不要求該二叉樹是排序二叉樹）。已知二叉樹采用二叉鏈表表示，其數(shù)據(jù)定義如下：typedefstructBiTNode{intdata;//關(guān)鍵字//左右孩子指針structBiTNode*lchild,*rchild;}BiTNode,*BiTree;30intIsBalanced(BiTreeT)//檢查二叉樹T是否是平衡樹。{//如果不平衡則返回-1，否則返回樹的深度。 if(!T)return0; depthLeft=IsBalanced(T->lchild); if(depthLeft==-1)return-1;depthRight=IsBalanced(T->rchild);if(depthRight==-1)return-1; if(depthLeft–depthRight>1|| depthRight–depthLeft>1)return-1;return1+(depthLeft>depthRight? depthLeft:depthRight);}313、計數(shù)排序算法對一個待排序的表（用數(shù)組表示）進行排序，并將排序結(jié)果存放到另一個新的表中。假設(shè)，表中所有待排序的關(guān)鍵字互不相同，計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關(guān)鍵字比該記錄的關(guān)鍵字小，假設(shè)針對某一個記錄，統(tǒng)計出的計數(shù)值為c，那么，這個記錄在新的有序表中的合適的存放位置即為c。(1)給出適用于計數(shù)排序的數(shù)據(jù)表定義；(2)使用C語言編寫實現(xiàn)計數(shù)排序的算法；(3)對于有n個記錄的表，關(guān)鍵碼比較次數(shù)是多少？(4)該算法的空間復(fù)雜度是多少？32voidCountSort(RecTypea[],b[],intn)//計數(shù)排序算法，將a中記錄排序放入b中{for(i=0;i<n;i++)//對每一個元素a[i]

{ cnt=0; for(j=0;j<n;j++)//統(tǒng)計關(guān)鍵字比a[i]小的元素個數(shù) if(a[j].key<a[i].key)cnt++; b[cnt]=a[i];}}//Count_Sorttypedefstruct{ intkey; datatypeinfo}RecType33其它題目1、鏈表不具備的特點是()。A．插入和刪除不需要移動元素

B．可隨機訪問任一結(jié)點C．不必預(yù)分配空間

D．所需空間與其長度成正比B342、下面程序段的時間復(fù)雜度為（

）voidfun1(intn){i=1;while(i<=n) i=i*3;}35log3n3、下面程序段的時間復(fù)雜度為（）A.O(n)B.O(n^2)C.O(n(n-1)/2)D.O(√n)voidfun1(intn){s=0;i=0;while(s<n){

i++;

s=s+i;}}D364、不帶頭結(jié)點的單鏈表head為空的判定條件是()。A．head＝＝NULLB．Head->next＝＝NULLC．Head->next＝＝headD．head!＝NULL另：帶頭結(jié)點的單鏈表head為空的判定條件是()。AB375、帶頭結(jié)點的循環(huán)單鏈表head中，head為空的判定條件是()。A．head＝＝NULLB．head—>next＝＝NULLC．head—>next＝＝headD．head!＝NULLC386、在長度為n的()上，刪除第一個元素，其算法復(fù)雜度為O(n)。A．只有表頭指針的不帶頭結(jié)點的循環(huán)單鏈表B．只有表尾指針的不帶頭結(jié)點的循環(huán)單鏈表C．只有表尾指針的帶頭結(jié)點的循環(huán)單鏈表D．只有表尾指針的帶頭結(jié)點的循環(huán)雙鏈表A397、若線性表中有2n個元素，算法()在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。A．刪除所有值為x的元素

B．在最后一個元素的后面插入一個新元素C．順序輸出前k個元素

D．交換其中某兩個元素的值A(chǔ)409、文件局部有序或文件長度較小時，最佳排序方法是（）。A.直接插入排序B.冒泡排序C.簡單選擇排序D.歸并排序A411.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。（）2.算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，那么算法實際上就是程序。（）

3.棧和隊列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（?.帶頭結(jié)點的鏈隊出隊時不會改變頭指針的值，但可能改變尾指針。（）5.一顆樹中的葉子結(jié)點數(shù)一定等于其對應(yīng)的二叉樹的葉子數(shù)。（）FFTTF426.線性表用鏈表存儲時，結(jié)點間存儲空間可不連續(xù)的。（）7.哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。（）8.完全二叉樹中，若一個結(jié)點沒有左子樹，則必是葉子結(jié)點。（）9.當(dāng)待排記錄按關(guān)鍵字從大到小或從小到大基本有序時，快速排序的執(zhí)行時間最省。（）10.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（）TTTFF4311.在順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表的元素個數(shù)有關(guān)，而且與每一塊中的元素個數(shù)有關(guān)。（）12.內(nèi)部排序就是整個排序過程完全在內(nèi)存中進行的排序。（）13.存在這樣的二叉樹，對它采用任何次序的遍歷，結(jié)果相同。（）14.有一個小堆，堆中任意結(jié)點的關(guān)鍵字均小于它的左、右孩子關(guān)鍵字。則其中具有最大值的結(jié)點一定是一個葉子結(jié)點，并可能在堆的最后兩層中。（）15.散列表的查找效率主要取決于所選擇的散列函數(shù)與處理沖突的方法。（）TTTTT4416.順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。（）17.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。（）18.對查找進行時間分析時，只需要考慮查找成功的平均情況。（）19.堆是一顆完全二叉樹，反之亦然。（）

20.給定一棵樹，可以找到唯一的一顆二叉樹與之對應(yīng)。（）TFFFT