河北東方學(xué)院2021 -2022 學(xué)年第一學(xué)期期末《數(shù)據(jù)結(jié)構(gòu)》補(bǔ)考試卷

河北東方學(xué)院2021—2022學(xué)年第一學(xué)期期末《數(shù)據(jù)結(jié)構(gòu)》補(bǔ)考試卷一、選擇題（共15小題，每小題2分，共30分）O(n^2)，表明該算法的（）[單選題]*n^2n^2n^2成正比(正確答案)n^2成正比p結(jié)點(diǎn)（非尾結(jié)點(diǎn)）之后的一個結(jié)點(diǎn)的操作是（）[選題]*A.p->next=pA.p->next=pB.p->next->next=p->nextC.p->next->next=pD.p->next=p->next->next(正確答案)計(jì)的（）[]*A.A.正確性B.可讀性C.可使用性D.健壯性(正確答案)在下列排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是（）。[單選題]*A.A.希爾排序B.冒泡排序C.直接插入排序D.簡單選擇排序(正確答案)33210的結(jié)點(diǎn)數(shù)為（）[]*A.4A.4B.5C.6(正確答案D.7A．6B.15C.16(正確答案D.21G(V,E)17G的邊數(shù)最少是（A．6B.15C.16(正確答案D.21在以下排序方法中，（）[單選題]*簡單選擇排序簡單選擇排序折半插入排序(正確答案C.希爾排序快速排序1001個結(jié)點(diǎn)，其葉子結(jié)點(diǎn)的個數(shù)是（）[]*A.250A.250B.501(正確答案C.254D.505StackEmpty(s)的值為（）。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)[單選題]*A.aA.aB.bC.1(正確答案D.03B-2047個關(guān)鍵字，則樹的最大高度是（）[單選題]*A.11A.11B.12(正確答案C.13D.1411R[1…13]={1,3,9,12,32,41,45,62,75,77,82,510折半查找法查找值為82的結(jié)點(diǎn)時，經(jīng)過（）次比較后查找成功。[單選題]*A.1A.1B.2C.4(正確答案D.813個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（）[選題]*A.13B.12C.26A.13B.12C.26D.25(正確答案)操作正確的是（）[單選題]*

儲，初始棧頂指針top為n，則以下元素x進(jìn)棧的A.top++;data[top]=x;B.data[top]=x;top++;C.top--;data[top]=x;A.top++;data[top]=x;B.data[top]=x;top++;C.top--;data[top]=x;D.data[top]=x;top--;(正確答案)L中，至少有一個結(jié)點(diǎn)的條件是（）[單選題]*A.L->next!=NULLA.L->next!=NULLB.L->next!=L(正確答案)C.p==NULLD.p->next==L算法的空間復(fù)雜度是指（）[單選題]*A.A.算法中輸入數(shù)據(jù)所占用的存儲空間的大小B.算法本身所占用的存儲空間的大小C.算法中所占用的所有存儲空間的大小D.算法中需要的輔助變量所占用存儲空間的大小(正確答案)二、填空題（共10小題，每小題1分，共10分）數(shù)據(jù)的基本單位 ，最小單位 。[填空題]*空1答案：數(shù)據(jù)元素空2答案：數(shù)據(jù)項(xiàng)邏輯結(jié)構(gòu)的類型有集合、 、樹形結(jié)構(gòu)、 。[填空題]*對二叉排序樹進(jìn)行 遍歷，可以得到關(guān)鍵字從小到大排列的結(jié)點(diǎn)序列。[填空題]* (答案：中序)4.對一組數(shù)據(jù)（4,48,96,23,12,60,45,73）采用直接插入排序算法進(jìn)行遞增排序，當(dāng)把60插入到有序表中時，為尋找插入位置需比較 次。[填空題]* (答案：2)用一個大小為8的數(shù)組來實(shí)現(xiàn)環(huán)形隊(duì)列，隊(duì)頭指針front指向隊(duì)頭元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素位置。當(dāng)前front和rear的值分別是0和5，在進(jìn)隊(duì)3個元素，又出隊(duì)3個元素，front和rear的值分別是 、 [填空題*空1答案：3空2答案：0對于n個頂點(diǎn)的連通圖來說，它的生成樹一定有 條邊。[填空]* (答案：n-1)對矩陣的壓縮存儲是為了 。[填空題]* (答案：節(jié)省存儲空間)用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中 有關(guān)，而與邊數(shù)關(guān)。[填空題]* (答案：結(jié)點(diǎn)個數(shù))通過對堆棧S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)輸出的序列為： 。[填空題]* (答案：231)10.廣義表（（(a,b,(）,c）,d),e,((f),g))的長度是 ，深度是4。[填空題]* (答案：3)三、簡答題（共6小題，每小題5分，共30分）voidfun(intn){inti,x=0;for(i=1;i<n;i++){for(j=i+1,j<=n;j++)x++;}}[填空題]*對于如圖所示的二叉樹轉(zhuǎn)換成樹。[填空題]*已知先序序列為ABCEGDFH，中序序列為CBGEAFHD。構(gòu)造 對應(yīng)的二樹。[填空題]*G，試回答以下問題。給 從頂點(diǎn)V0 發(fā)的一個深度優(yōu)先遍歷序列和一個廣度優(yōu)先遍歷序列。G的一個拓?fù)湫蛄小填空題]*G0始，畫出其構(gòu)成過程。[填空題]*6.已知數(shù)據(jù)元素序列（35，66，2，15，6，81，6*，9）進(jìn)行調(diào)整為大根堆。[填空題]*四、編程題（共2小題，每小題15分，共30分）nLO(n)O(1)x[填空題]*答案解析：1．voiddelnode1(SqList*&L，ElemTypex){intk=0，i;（1分）for(i=0;i<L->length;i++)（4分）if(L->data[i]!=x){L->data[k]=L->data[i];k++;（13分）}L->length=k;（15分）}[填空題]*答案解析：2．voidconversion(intn,intd){SqStackS;（1