舊數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試卷三

個(gè)人采集整理僅供參照學(xué)習(xí)數(shù)據(jù)構(gòu)造導(dǎo)論試題三（課程代碼：2142）一、單項(xiàng)選擇題（本大題共15小題，每題2分，共30分）在每題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多項(xiàng)選擇或未選均無分。資料個(gè)人采集整理，勿做商業(yè)用途1．在儲(chǔ)蓄數(shù)據(jù)時(shí)，平時(shí)不單要儲(chǔ)蓄各數(shù)據(jù)元素的值，并且還要儲(chǔ)蓄【C】A.數(shù)據(jù)的辦理方法B．?dāng)?shù)據(jù)元素的種類C．?dāng)?shù)據(jù)元素之間的關(guān)系D．?dāng)?shù)據(jù)的儲(chǔ)蓄方法2．程序段for（i=0;i<n;i++）for(j=1;j<=n;j++)x++;此中n為正整數(shù)，則語句x++履行了次。【】A.n2B.n3C.3nD.2n3．單鏈表?yè)碛械奶厣恰続】A．可隨機(jī)接見任一元素B．插入、刪除不需要挪動(dòng)元素C．不用預(yù)先預(yù)計(jì)儲(chǔ)蓄空間D．所需空間與線性表長(zhǎng)度成正比4．在擁有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍舊有序的時(shí)間復(fù)雜度是【B】A．0(1)B．O(n)C．O(n2)D．O(nlog2n)5．若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的直接前趨，則最節(jié)儉時(shí)間的儲(chǔ)蓄形式為【A】資料個(gè)人采集整理，勿做商業(yè)用途A.序次表B.單鏈表C.雙鏈表D．循環(huán)鏈表6．設(shè)數(shù)組Data[0..m-1]作為循環(huán)行列的儲(chǔ)蓄空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語句為【】資料個(gè)人采集整理，勿做商業(yè)用途A．front=front+1B．front=(front+1)％mC．rear=(rear+1)%mD．front=(front+1)％(m-1)7．下邊不屬于特別矩陣的是【C】A．對(duì)角矩陣B．三角矩陣C．罕見矩陣D．對(duì)稱矩陣8．設(shè)棧S和行列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5，e6挨次經(jīng)過棧S，一個(gè)元素出棧后即進(jìn)入行列Q，若6個(gè)元素出列的序次是e2，e4，e3，e6，e5，e1，則棧S的容量最少應(yīng)當(dāng)是【】資料個(gè)人采集整理，勿做商業(yè)用途A．6B．4C．3D．29．對(duì)一個(gè)滿二叉樹，m個(gè)葉子結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，深度為h，則【】A．n=h+mB．h+m=2nC．m=h-1D．n=2h-110．一棵二叉樹擁有10個(gè)度為2的結(jié)點(diǎn)，則該二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)是【】C.12D.不確立11．設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為【】資料個(gè)人采集整理，勿做商業(yè)用途A．2hB．2h-1C．2h+lD．h+112．長(zhǎng)度為6的有序表采納序次儲(chǔ)蓄構(gòu)造，采納二分查找法，在等概率狀況下，查找成功時(shí)的平均查找長(zhǎng)度是【】資料個(gè)人采集整理，勿做商業(yè)用途A．7／3B．8／3C．7／6D．5／613．有一個(gè)按元素值排好序的序次表(長(zhǎng)度大于2)，分別用序次查找和二分查找兩種方法查找給定值相等的元素，比較次數(shù)分別是s和b，在查找成功的狀況下，s和b的關(guān)系是【】1/3個(gè)人采集整理僅供參照學(xué)習(xí)資料個(gè)人采集整理，勿做商業(yè)用途A．s＝bB．s>bC．s<bD．不必定14．下述排序方法中，比較次數(shù)與待排序記錄的初始狀態(tài)沒關(guān)的是【】A．直接插入排序B．迅速排序C．直接選擇排序D．冒泡排序15．排序的方法有好多種，從未排序序列中挨次拿出元素，與已排序序列中的元素作比較，將其放入已排序序列的正確地點(diǎn)上的排序方法是【】資料個(gè)人采集整理，勿做商業(yè)用途A．選擇排序B．迅速排序C．直接插入排序D．冒泡排序二、填空題（本大題共15小題，每題2分，共30分）請(qǐng)?jiān)诿款}的空格中填上正確答案。錯(cuò)填、不填均無分。1．是數(shù)據(jù)的不行切割的最小表記單位，可是它平時(shí)不擁有完好確立的實(shí)質(zhì)意義，或不被看作一個(gè)整體對(duì)待。2．一般地，運(yùn)算是指在任何邏輯構(gòu)造上施加的操作，依據(jù)操作的收效，可將運(yùn)算分紅加工型運(yùn)算和兩種基本種類。資料個(gè)人采集整理，勿做商業(yè)用途3．當(dāng)線性表的元素個(gè)數(shù)基本牢固，且極少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采納_______儲(chǔ)蓄構(gòu)造。資料個(gè)人采集整理，勿做商業(yè)用途4．有一長(zhǎng)度為n的序次表，假設(shè)刪除表中任一元素的概率同樣，則刪除一個(gè)元素平均需要挪動(dòng)元素的個(gè)數(shù)是________。資料個(gè)人采集整理，勿做商業(yè)用途5．關(guān)于非空的雙鏈表,在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)需改正的指針共______個(gè)。6．用push表示入棧操作，pop表示出棧操作。有一個(gè)空棧，現(xiàn)有輸入序列為1、2、3、4，為了獲得1、3、4、2的出棧序次，相應(yīng)的出棧和入棧操作序列為。資料個(gè)人采集整理，勿做商業(yè)用途7．一維數(shù)組Data[n]用來表示循環(huán)行列，隊(duì)頭指針front和隊(duì)尾指針rear定義為整型變量，隊(duì)空的條件是。資料個(gè)人采集整理，勿做商業(yè)用途8．有一個(gè)10階對(duì)稱矩陣A，現(xiàn)以行為主序儲(chǔ)蓄其下三角（包含對(duì)角線）中的元素，每個(gè)元素占1個(gè)儲(chǔ)蓄單元，A[0][0]的地點(diǎn)為1000，則A[8][5]的地點(diǎn)是。資料個(gè)人采集整理，勿做商業(yè)用途9．一棵樹中全部結(jié)點(diǎn)層數(shù)的最大值稱為該樹的。10．在擁有n（n>0）個(gè)結(jié)點(diǎn)的二叉鏈表中，共有個(gè)非空指針域。11．某二叉樹的先根遍歷序列和中根遍歷序列均為abcd,則它的后根遍歷序列為。12．長(zhǎng)度為6的有序表采納二分查找，共有個(gè)元素只需3次比較就能夠查找到。13．假如按重點(diǎn)字值遞加的序次挨次將n個(gè)結(jié)點(diǎn)插入到初始為空的二叉排序樹中，則對(duì)這樣的二叉排序樹查找時(shí)，平均比較次數(shù)為__________。資料個(gè)人采集整理，勿做商業(yè)用途14．對(duì)一組記錄（54，38，96，23，18，70，61，44，80）進(jìn)行直接插入排序，當(dāng)?shù)?個(gè)記錄61插入到有序表時(shí)，為找尋插入地點(diǎn)需比較次。資料個(gè)人采集整理，勿做商業(yè)用途15．對(duì)n個(gè)元素進(jìn)行直接插入排序，在全部元素有序的狀況下比較的次數(shù)最少，其比較次數(shù)為，而在全部元素逆序狀況下比較的次數(shù)最多。資料個(gè)人采集整理，勿做商業(yè)用途三、應(yīng)用題（本大題共5小題，每題5分，共25分）1．以下單鏈表分別獨(dú)自履行以下各程序段，此后畫出新的結(jié)果表示圖。(1)．R->data=P->data;2/3個(gè)人采集整理僅供參照學(xué)習(xí)(2)．R->data=P->next->data;(3)．T=P;while(T!=NULL){T->data=T->data*2;T=T->next;}資料個(gè)人采集整理，勿做商業(yè)用途2．有5個(gè)元素，其入棧序次為：A，B，C，D，E，在各樣可能的出棧序次中，以元素C，D最初出棧（即C第一個(gè)出棧且D第二個(gè)出棧）的序次有哪幾個(gè)？資料個(gè)人采集整理，勿做商業(yè)用途3．對(duì)以以下列圖所示的一棵樹，試畫出它相對(duì)應(yīng)的二叉樹。4．給定表（7，16，4，8，20，9，6，18，5），試按元素在表中的序次將它們挨次插入一棵初始為空的二叉排序樹，請(qǐng)畫出插入達(dá)成后的二叉排序樹并計(jì)算在等概率狀況下該二叉排序樹的平均查找長(zhǎng)度。資料個(gè)人采集整理，勿做商業(yè)用途5．以重點(diǎn)字序列{70,73,69,23,93,18,11,68}為例，手工履行迅速排序算法，寫出每一趟排序的結(jié)果。資料個(gè)人采集整理，勿做商業(yè)用途四、算法設(shè)計(jì)題（本大題共2小題，第1小題8分，第2小題7分，共15分）1．設(shè)序次表L中的數(shù)據(jù)元素遞加有序。試設(shè)計(jì)一個(gè)算法：將數(shù)據(jù)元素x插入到序次表的適當(dāng)?shù)攸c(diǎn)上，以保持該表的有序性。資料個(gè)人采集整理，勿做商