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

1、高等教育自學考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導論試題、答案及評分參考第1頁全國全國2011年1月自學考試月自學考試數(shù)據(jù)結(jié)構(gòu)導論試題數(shù)據(jù)結(jié)構(gòu)導論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.在順序表中查找第i個元素，時間效率最高的算法的時間復雜度為()A.O(1)B.O()nC.O(log2n)D.O

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

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

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

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

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