02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2005年01月試卷

浙02142#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第4頁(yè)（共4頁(yè)）全國(guó)2005年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1.數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)是指()A.數(shù)組、鏈表、樹、圖形結(jié)構(gòu)B.線性表、鏈表、棧隊(duì)列、數(shù)組廣義表C.線性結(jié)構(gòu)、鏈表、樹、圖形結(jié)構(gòu)D.集合、線性結(jié)構(gòu)、樹、圖形結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)中，通常采用兩種方法衡量算法的時(shí)間復(fù)雜性，即()A.最大時(shí)間復(fù)雜性和最小時(shí)間復(fù)雜性B.最好時(shí)間復(fù)雜性和最壞時(shí)間復(fù)雜性C.部分時(shí)間復(fù)雜性和總體時(shí)間復(fù)雜性D.平均時(shí)間復(fù)雜性和最壞時(shí)間復(fù)雜性3.下列關(guān)于線性表的敘述中，不正確的是()A.線性表是n個(gè)結(jié)點(diǎn)的有窮序列B.線性表可以為空表C.線性表的每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前趨和一個(gè)后繼D.線性表結(jié)點(diǎn)間的邏輯關(guān)系是1:1的聯(lián)系4.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的正確操作是()A.p=p->nextB.p->next=p->nextC.p->next=p->next->nextD.p->next=p5.棧和隊(duì)列()A.共同之處在于二者都是先進(jìn)先出的特殊的線性表B.共同之處在于二者都是先進(jìn)后出的特殊的線性表C.共同之處在于二者都只允許在頂端執(zhí)行刪除操作D.沒有共同之處6.二維數(shù)組A［5］［6］采用按列為主序的存儲(chǔ)方式，每個(gè)元素占3個(gè)存儲(chǔ)單元，若A［0］［0］的存儲(chǔ)地址是100，則A［4］［3］的存儲(chǔ)地址是()A.127B.142C.150D.1577.深度為k的二叉樹至多有()A.2k個(gè)結(jié)點(diǎn)B.2k-1個(gè)結(jié)點(diǎn)C.2k-1個(gè)結(jié)點(diǎn)D.2k-1-1個(gè)結(jié)點(diǎn)8.對(duì)于如圖所示二叉樹采用中根遍歷，正確的遍歷序列應(yīng)為()A.ABCDEFB.ABECDFC.CDFBEAD.CBDAEF9.下面關(guān)于生成樹的描述中，不正確的是()A.生成樹是樹的一種表現(xiàn)形式B.生成樹一定是連通的C.生成樹一定不含有環(huán)D.若生成樹頂點(diǎn)個(gè)數(shù)為n，則其邊數(shù)一定為n-110.圖的鄰接表如下所示，從頂點(diǎn)V1出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點(diǎn)序列

是()A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V211.下列查找方法中，不屬于動(dòng)態(tài)的查找方法是()A.二叉排序樹法B.平衡樹法C.散列法D.斐波那契查找法12.要解決散列引起的沖突問題，常采用的方法有()A.數(shù)字分析法、平方取中法B.數(shù)字分析法、線性探測(cè)法C.二次探測(cè)法、平方取中法D.二次探測(cè)法、鏈地址法13.用于外存儲(chǔ)器的數(shù)據(jù)組織結(jié)構(gòu)散列文件，主要適用于()A.順序存取B.隨機(jī)存取C.索引存取D.以上三種都可以14.堆排序?qū)儆谝环N選擇排序，其時(shí)間復(fù)雜性為()A.O(1)B.O(nlog2n)C.O(n)D.O(n2)15.下列排序方法中，屬于不穩(wěn)定的排序方法是()A.直接插入排序法B.冒泡排序法C.基數(shù)排序法D.歸并排序法二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16.根據(jù)不同的描述方式，對(duì)數(shù)據(jù)的操作運(yùn)算通?？煞譃榧庸ば瓦\(yùn)算和__________兩種基本

類型。17.數(shù)據(jù)結(jié)構(gòu)中的算法，通常采用最壞時(shí)間復(fù)雜度和____________兩種方法衡量其效率。18.判斷帶頭結(jié)點(diǎn)head的單鏈表為空的條件是___________。19.若順序表每個(gè)元素長(zhǎng)度均為5，其中第一個(gè)元素的存儲(chǔ)地址為30，則第6個(gè)元素的存儲(chǔ)地址為___________。20.若front和rear分別表示循環(huán)隊(duì)列Q的頭指針和尾指針，m0表示該隊(duì)列的最大容量，則判斷循環(huán)隊(duì)列為滿的條件是___________。21.對(duì)于順序存儲(chǔ)結(jié)構(gòu)的二維數(shù)組，通常采用___________兩種存放方式存儲(chǔ)數(shù)據(jù)元素。22.若某二叉樹的先根遍歷序列為CEDBA，中根遍歷序列為DEBAC，則其后根遍歷序列為___________。23.具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為___________。24.圖主要采用___________兩種存儲(chǔ)結(jié)構(gòu)存放。25.索引順序查找通常分兩個(gè)階段進(jìn)行，首先采用順序查找法或二分法確定所要查找的塊，然后再用___________法在塊中找到具體的元素值。26.二叉排序樹是一種特殊的有序表，若要保證輸出序列其鍵值完全按遞增排列，則應(yīng)對(duì)二叉排序樹采用___________法遍歷。27.文件常見的存儲(chǔ)結(jié)構(gòu)有順序文件、鏈接文件、索引文件和___________四種。28.在各種內(nèi)部排序中，占用存儲(chǔ)空間較大的排序通常是___________排序。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.已知某二叉樹的順序存儲(chǔ)結(jié)構(gòu)如圖所示，試畫出該二叉樹。ABCDEFG30.試用Prim算法構(gòu)造下圖的最小生成樹，要求分步給出構(gòu)造過程31.已知散列函數(shù)為H(key)=key%7，散列表長(zhǎng)度為7(散列地址空間為0..6)，待散列序列為：(25，48，32，50，68)。要求：(1)根據(jù)以上條件構(gòu)造一散列表，并用線性探測(cè)法解決有關(guān)地址沖突；(2)若要用該散列表查找元素68，給出所需的比較次數(shù)。32.已知一組鍵值序列為(38，64，73，52，40，37，56，43)，試采用快速排序法對(duì)該組序列

作升序排序，并給出每一趟的排序結(jié)果。33.已知一組鍵值序列(26，21，32，56，78，89，90)，試采用二路歸并排序法