全國(guó)2021年10月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

202110月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題全國(guó)2008年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題02142一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合標(biāo)題問題要求的號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.挨次結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.關(guān)于算法的描述，不正確的是（ ）算法最終必需由計(jì)算機(jī)程序?qū)崿F(xiàn)C.健壯的算法不會(huì)因不法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)D.算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指該結(jié)點(diǎn)的（ ）B.直接后繼C.開始結(jié)點(diǎn)D.將兩個(gè)各有n個(gè)元素的有序表合并成一個(gè)有序表，其最少的比力次數(shù)為（）A.nB.2n-1C.2nD.n2棧和隊(duì)列共同具有的特點(diǎn)是（ ）B.都是先進(jìn)先出C.只允許在端點(diǎn)進(jìn)行操作運(yùn)算D.若用一個(gè)有6個(gè)單元的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列和front的初值別離為0和3。則從隊(duì)中刪除一個(gè)元素，再添加兩個(gè)元素后和front的值別離為（ ）5B.24C.42D.51數(shù)組A[0..5][0..5]的每個(gè)元素占5個(gè)字節(jié)，將其以列為主序存儲(chǔ)在起始地址為1000的內(nèi)單元中，則元素［5［］的地址是（ ）A.1175B.1180C.1205D.1210含有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，空指針域的個(gè)數(shù)為（ ）A.n-1B.nC.n+1D.n+2在一棵深度為H的完全二叉樹中，所含結(jié)點(diǎn)的個(gè)數(shù)不少于（ ）A.2H-1-1B.2H-1C.2H-1D.2H一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量數(shù)為（ ）A.0B.1C.nD.不確定下列說法中不正確的是（ ）無(wú)向圖的極大連通子圖稱為連通分量C.連通圖的深度優(yōu)先搜索中一般要采用棧來暫存剛拜候過的頂點(diǎn)D.有向圖的遍歷不成采用廣度優(yōu)先搜索算法對(duì)一棵二叉排序樹采用中根遍歷進(jìn)行輸出的數(shù)據(jù)必然是（ ）A.B.遞減序列C.無(wú)序序列D.13.一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，查找成功時(shí)的比力次數(shù)為（ ）A.1B.2C.4D.8一組記錄的關(guān)鍵字為{45，80，55，40，42，85}，則利用堆排序的方法建立的初始堆為（ ）A.80，45，55，40，42，85B.85，80，55，40，42，45C.85，80，55，45，42，40D.85，55，80，42，45，40關(guān)于VSAM文件存取操作的說法，正確的是（）A.不能挨次存取，只能按關(guān)鍵字隨機(jī)存取B.不能挨次存取，不能按關(guān)鍵字隨機(jī)存取C.只能挨次存取，不能按關(guān)鍵字隨機(jī)存取D.既能挨次存取，也能按關(guān)鍵字隨機(jī)存取二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。在任何問題中，數(shù)據(jù)元素都不是孤立的，它們之間總存在某種關(guān)系，通常稱這種關(guān)系為 。存儲(chǔ)結(jié)點(diǎn)之間通常有四種基本存儲(chǔ)方式，即挨次存儲(chǔ)方式、索引存儲(chǔ)方式、 散列存儲(chǔ)方式。在一個(gè)長(zhǎng)度為n的挨次表中第i個(gè)元1≤i≤之前插入一個(gè)元素時(shí)需向后移 個(gè)元素。對(duì)一棵深度為10的滿二叉樹按層編號(hào)，則編號(hào)為51的結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)編號(hào)為 。用S表示入棧操作表示出棧操作若元素入棧挨次為為了得到1342的出棧次，相應(yīng)的S和X操作串。具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)。一棵具有n個(gè)結(jié)點(diǎn)的樹所有非終端結(jié)點(diǎn)的度均為則該樹中葉子結(jié)點(diǎn)個(gè)數(shù) 。在無(wú)向圖G的鄰接矩陣A中，若A[i][j]等于0，則A[j][i]等于 。兩個(gè)串是相等的，當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度相等的字符都相同。某二叉樹的后根遍歷序列為中根遍歷序列為則它的先根遍歷序列。先在所有的記錄中選出鍵值最小的記錄，將它與第一個(gè)記錄交換；然后在其余的記錄中再選出最小的記錄與第二個(gè)記錄交換依此類推直至所有記錄排序完成這種排序方法為 。對(duì)含有n個(gè)結(jié)點(diǎn)eprim算法生成最小生成樹的時(shí)間復(fù)雜度為 。對(duì)n個(gè)元素進(jìn)行冒泡排序時(shí)，最少的比力次數(shù)。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)設(shè)有編碼為A，B，C，D4列火車，依次進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，試寫出這4車開出站臺(tái)的所有可能的挨次。30圖所示的二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)。題30圖31圖，試給出：鄰接矩陣；鄰接表。題31圖32給定表（3，14，22，8，6，2，88，29，6，13，10們依次插入一棵初始時(shí)為空的二叉排序樹，畫出插入完成后的二叉排序樹。33.用插入排序算法對(duì)數(shù)據(jù)序列（47，33，61，82，72，11，25，57）進(jìn)行排序，寫出整個(gè)插入排序的每一趟過程。四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)設(shè)兩個(gè)數(shù)據(jù)元素均為整型數(shù)據(jù)的線性表和。若n=mai=bi（i=1，2,…，n）則認(rèn)為A=Bai=bi（i=1，2,…，j）且aj+1B比力AB的算法，當(dāng)AB。要求線性表的存儲(chǔ)結(jié)構(gòu)使用鏈接存儲(chǔ)。typed