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

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

2、(n)2.樹形結構中，度為0的結點稱為()A.樹根B.葉子C.路徑D.二叉樹3.已知有向圖G=(VE)，其中V=V1V2V3V4V5V6V7，E=，，，，，，，，則圖G的拓撲序列是()A.V1V3V4V6V2V5V7B.V1V3V2V6V4V5V7C.V1V3V4V5V2V6V7D.V1V2V5V3V4V6V74.有關圖中路徑的定義，表述正確的是()A.路徑是頂點和相鄰頂點偶對構成的邊所形成的序列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.與串的邏輯結構不同的數(shù)據(jù)結構是()A.線性表B.

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

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

6、3030.一棵二叉樹的前根遍歷序列為ABCDEFG，中根遍歷序列為CBDAEGF，試構造出該二叉樹。31.下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。?????????????????????????4210495281298110512132.給定表（80，90，50，70，75，60，40，100），試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。33.試寫出一