全國自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案4套

1、高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題、答案及評(píng)分參考第1頁全國全國2011年1月自學(xué)考試月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題數(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.在順序表中查找第i個(gè)元素，時(shí)間效率最高的算法的時(shí)間復(fù)雜度為()A.O(1)B.O()nC.O(log2n)D.O

2、(n)2.樹形結(jié)構(gòu)中，度為0的結(jié)點(diǎn)稱為()A.樹根B.葉子C.路徑D.二叉樹3.已知有向圖G=(VE)，其中V=V1V2V3V4V5V6V7，E=，，，，，，，，則圖G的拓?fù)湫蛄惺?)A.V1V3V4V6V2V5V7B.V1V3V2V6V4V5V7C.V1V3V4V5V2V6V7D.V1V2V5V3V4V6V74.有關(guān)圖中路徑的定義，表述正確的是()A.路徑是頂點(diǎn)和相鄰頂點(diǎn)偶對(duì)構(gòu)成的邊所形成的序列B.路徑是不同頂點(diǎn)所形成的序列C.路徑是

3、不同邊所形成的序列D.路徑是不同頂點(diǎn)和不同邊所形成的集合5.串的長度是指()A.串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)6.組成數(shù)據(jù)的基本單位是()A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量7.程序段i=n；x=0；dox=x5i；i；while（i0）；的時(shí)間復(fù)雜度為()A.O（1）B.O（n）C.O（n2）D.O(n3)8.與串的邏輯結(jié)構(gòu)不同的數(shù)據(jù)結(jié)構(gòu)是()A.線性表B.

4、棧高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題、答案及評(píng)分參考第3頁個(gè)存儲(chǔ)地址空間，則a85的地址為___________。22.設(shè)字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），則S的長度為___________。23.在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點(diǎn)是___________結(jié)點(diǎn)。24.一棵深度為n(n1)的滿二叉樹中共有___________個(gè)結(jié)點(diǎn)。25.在無向圖中，如果從頂點(diǎn)v到頂點(diǎn)v′有路徑，則稱v和v′是__

5、_________。26.無向完全圖G采用___________存儲(chǔ)結(jié)構(gòu)較省空間。27.在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個(gè)數(shù)沒有關(guān)系的查找方法是___________。28.快速排序最好情況下的時(shí)間復(fù)雜度為___________。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29.稀疏矩陣A如下，寫出矩陣A的三元組表及矩陣A的轉(zhuǎn)置矩陣的三元組表。????????????????0000030

6、4000000001500000010003030.一棵二叉樹的前根遍歷序列為ABCDEFG，中根遍歷序列為CBDAEGF，試構(gòu)造出該二叉樹。31.下述矩陣表示一個(gè)無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。?????????????????????????4210495281298110512132.給定表（80，90，50，70，75，60，40，100），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹，