數(shù)據(jù)結(jié)構(gòu)試題及答案(免費(fèi))

數(shù)據(jù)結(jié)構(gòu)試卷（十一）一、選擇題(30分)1．設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結(jié)點。(A)2n(B)n(C)n/2(D)n(n-1)2．設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。(A)n(B)n-1(C)2n(D)2n-13．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，804．（）二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（）。(A)2i+1(B)2i(C)i/2(D)2i-16．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(n3/2)7．設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=08．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（）。(A)20(B)256(C)512(D)10249．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。(A)1(B)2(C)3(D)410.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;二、判斷題(20分)1．不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（）2．當(dāng)向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（）3．設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復(fù)雜度為O(log2n)。（）4．完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。（）5．哈夫曼樹中沒有度數(shù)為1的結(jié)點。（）6．對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（）7．先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（）8．由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（）9．線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（）10.帶權(quán)無向圖的最小生成樹是唯一的。（）三、填空題(30分)1.1.設(shè)指針變量p指向雙向鏈表中的結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為_________=p；s->right=p->right；__________=s；p->right->left=s；（設(shè)結(jié)點中的兩個指針域分別為left和right）。2.2.設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。3.3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進(jìn)行篩選。4.4.解決散列表沖突的兩種方法是________________和__________________。5.5.設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有______個。6.6.7.7.高度為h的完全二叉樹中最少有________個結(jié)點，最多有________個結(jié)點。設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。8.8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。9.9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。10.10.下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i){intj=t;structrecordx=r[s];i=s;while(i<j){while(i<j&&r[j].key>x.key)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(____________________)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}_________________;}四、算法設(shè)計題(