數(shù)據(jù)結(jié)構(gòu)考試習(xí)題試卷B

南通大學(xué)2006—2007學(xué)年第二學(xué)期數(shù)據(jù)結(jié)構(gòu)(閉卷)試卷〔B〕第1頁(yè)共3頁(yè)試題一二三四五總分···················裝···················裝·····················訂·························線···················密封線內(nèi)答題無(wú)效學(xué)院：專業(yè)：班級(jí)：學(xué)號(hào)：。學(xué)生姓名〔簽名〕：—————————密————————————封——————————線————————得分評(píng)卷人一、單項(xiàng)選擇題〔每題1分，共20分〕以下各小題的候選答案中只有一個(gè)答案是正確的，請(qǐng)把正確答案的字母代號(hào)填寫在題后括號(hào)內(nèi)。1.下面程序段的時(shí)間復(fù)雜度為〔〕。1.下面程序段的時(shí)間復(fù)雜度為〔〕。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A．O(m2)B．O(n2)C．O(m*n)D．O(m+n)2.以下關(guān)于集合說(shuō)法正確的選項(xiàng)是〔〕。A．集合的元素必須有某種邏輯關(guān)系B．集合屬于圖狀結(jié)構(gòu)C．集合作為邏輯結(jié)構(gòu)，結(jié)點(diǎn)之間不存在邏輯關(guān)系D．集合屬于線性結(jié)構(gòu)3.設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，那么數(shù)據(jù)結(jié)構(gòu)A是〔〕。 A．線性結(jié)構(gòu) B．樹型結(jié)構(gòu)C．圖型結(jié)構(gòu) D．集合4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)()個(gè)元素。A．63.5B．8C．63D．645.帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是〔〕。A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL6.鏈棧比照順序棧主要優(yōu)點(diǎn)在于〔〕。A．通常不會(huì)出現(xiàn)棧滿的情況B．通常不會(huì)出現(xiàn)棧空的情況C．插入操作更加方便D．刪除操作更方便7.循環(huán)隊(duì)列SQ采用數(shù)組空間SQ．base[0．．n-1]存放其元素值，其頭尾指針?lè)謩e是front和rear，那么當(dāng)前隊(duì)列中的元素個(gè)數(shù)是()。A．(rear-front+n)%nB．(rear-front+1)%nC．(rear-front-1)%nD．(rear-front)%n8.8.二維數(shù)組A的每個(gè)元素是一個(gè)2字節(jié)的整數(shù)，行下標(biāo)i的范圍從0-8，列下標(biāo)j的范圍從0-9。存放A至少需要的字節(jié)數(shù)為〔〕A．90B．180C．72D．1449.下面關(guān)于串的的表達(dá)中，〔〕是不正確的。A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)10.樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的()。A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷11.用5個(gè)權(quán)值為5個(gè)葉結(jié)點(diǎn)的權(quán)值，構(gòu)造的哈夫曼樹共有〔〕個(gè)結(jié)點(diǎn)。A．14B．11C．10D．912.一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個(gè)數(shù)是〔〕。 A．250B．490C．254D．13.以下圖所示的鄰接矩陣代表一有向圖。在矩陣中，如果第i行第j列的值為1，那么代表第i個(gè)結(jié)點(diǎn)有一有向邊指向第j個(gè)結(jié)點(diǎn)。在此有向圖中，結(jié)點(diǎn)3的入度為：()。A．1B．2C14.己知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如以下圖所示。那么按深度優(yōu)先遍歷算法從頂點(diǎn)V1出發(fā),所得到的頂點(diǎn)序列為()。A．V1,V2,V3,V5,V4B．Vl,V2,V3,V4,V5C．V1,V3,V4,V5,V2D．V1,V使用班級(jí)計(jì)51,052,053,054,計(jì)師051,軟051,052出卷日期2007年6月21日通大學(xué)2006—2007學(xué)年第二學(xué)期數(shù)據(jù)結(jié)構(gòu)〔閉卷〕試卷〔B〕第2頁(yè)共3頁(yè)15.15.以下圖所示的拓?fù)渑判虻恼_結(jié)果序列為〔〕。A．516234B．125634C．123456D．52163416.請(qǐng)指出在順序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找關(guān)鍵碼12需做〔〕次關(guān)鍵碼比擬。A.2B.3C.417.對(duì)包含n個(gè)元素的散列表進(jìn)行檢索，平均查找長(zhǎng)度為〔〕。A．O(log2n〕B．O(n)C．O(nlog2n)D．不直接依賴于n18.以下不屬于散列函數(shù)構(gòu)造方法的是〔〕A．除余法B．平方取中法C．二分法D．隨機(jī)數(shù)法19.排序方法中，從末排序序列中挑選元素，并將其依次放入已排序序列(初始時(shí)為空)的一端的方法，稱為()。A．希爾排序B．歸并排序C．選擇排序D．插入排序20.對(duì)具有n個(gè)元素的任意序列采用選擇排序，排序趟數(shù)為()。A．n-1B．nC．n+1D．得分評(píng)卷人二、判斷題〔每題1分，共10分〕請(qǐng)判斷下各命題，如正確的，請(qǐng)?jiān)谇懊胬ㄌ?hào)內(nèi)填上√，否那么填上×。1．〔〕線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。2．〔〕在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。1．〔〕線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。2．〔〕在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。3．〔〕棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。4．〔〕對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。5．〔〕線性表的邏輯順序與存儲(chǔ)順序總是一致的6．〔〕棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。7．〔〕棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。8．〔〕兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出時(shí)機(jī)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。9．〔〕對(duì)任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問(wèn)圖的每個(gè)頂點(diǎn).。10．〔〕一個(gè)棧的輸入序列是12345，那么棧的輸出序列不可能是12345?！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぱb·····················訂·························線························學(xué)院：專業(yè)：班級(jí)：姓名：學(xué)號(hào)：—————————密————————————封——————————線————————得分評(píng)卷人三、填空題(每題1分，共10分)請(qǐng)將以下各題的正確答案填寫在空白處。得分評(píng)卷人四、應(yīng)用題〔每題10分，共40分〕請(qǐng)運(yùn)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)解答以下各題。1．設(shè)無(wú)向圖G〔所右以下圖所示〕，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列，1．設(shè)無(wú)向圖G〔所右以下圖所示〕，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列，并給出該圖的最小生成樹。1．1．?dāng)?shù)據(jù)結(jié)構(gòu)中元素間的邏輯關(guān)系稱為數(shù)據(jù)的結(jié)構(gòu)。2．最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)的鏈表稱為鏈表。3．一個(gè)棧的輸入序列為123…100，假設(shè)輸出序列的第一個(gè)元素是100，輸出的第80個(gè)元素是___________。4.是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表。5．散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=Kmod17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是________。6．一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有__________條邊。7．有n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)序號(hào)分別為1，2，…，n，對(duì)任意結(jié)點(diǎn)i如果存在左孩子，其左孩子結(jié)點(diǎn)是________。8．關(guān)鍵路徑是指AOE網(wǎng)中從源點(diǎn)到匯點(diǎn)最________的路徑。9．設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為。10．平衡二叉樹中各結(jié)點(diǎn)左右子樹深度之差的絕對(duì)值不超過(guò)_______。南通大學(xué)2006—2007學(xué)年第二學(xué)期數(shù)據(jù)結(jié)構(gòu)〔閉卷〕試卷〔B〕第3頁(yè)共3頁(yè)2．設(shè)一組初始記錄關(guān)鍵字序列為(2．設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，請(qǐng)分別給出前4趟簡(jiǎn)單項(xiàng)選擇擇排序和前4趟直接插入排序后的結(jié)果。(排序方式為按關(guān)鍵字升序)3．設(shè)散列函數(shù)為H(k)=k%7,一組關(guān)鍵字為23、14、6、30、12和18,散列表T的地址空間為0-7,用線性探測(cè)法解決沖突,試依次將這組關(guān)鍵字插入T中,寫出散列表的構(gòu)造過(guò)程,并計(jì)算在等概率條件下查找成功的平均查找長(zhǎng)度。4．假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用0～7的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比擬兩種方案的優(yōu)缺點(diǎn)?！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぱb·······················訂·························線························學(xué)院：專業(yè)：年級(jí)：班級(jí)：