1、全國 2011 年 1 月自學考試 數(shù)據(jù)結構導論試題課程代碼： 02142一、單項選擇題(本大題共15 小題，每小題2 分，共 30 分 )在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.在順序表中查找第i 個元素，時間效率最高的算法的時間復雜度為()A.O(1)B.O( n )C.O(log 2n)D.O(n)2.樹形結構中，度為0 的結點稱為 ()A. 樹根B. 葉子C.路徑D. 二叉樹3.已知有向圖G=(V ,E)，其中 V=V 1 ,V 2,V 3,V 4,V 5,V 6,V 7 ，E=<V 1,V 2>，<

2、;V 1,V 3>，<V 1,V 4>，<V 2,V 5>，<V 3 ,V 5>,<V 3,V 6>，<V 4,V 6>， <V 5 ,V 7>,， <V 6,V 7> ，則圖 G 的拓撲序列是()A.V 1 ,V 3,V 4,V 6,V 2,V 5,V 7B.V 1,V 3,V2,V6,V4,V5,V 7C.V 1 ,V3,V 4,V5,V 2,V6,V7D.V 1,V 2,V 5,V 3,V 4,V 6,V 74.有關圖中路徑的定義，表述正確的是()A. 路徑是頂點和相鄰頂點偶對構成的邊所形成的序列B

3、.路徑是不同頂點所形成的序列C.路徑是不同邊所形成的序列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=x+5*i ； i- ； while（ i>0 ）；的時間復雜度為 ()A.O （ 1）B.O （ n）C.O（ n2）D.O(n 3)8.與串的邏輯結構不同的數(shù)據(jù)結構是()A. 線性表B. 棧C.隊列D. 樹9.二叉樹的第 i （i 1）層上所擁

4、有的結點個數(shù)最多為()A.2 iB.2iC.2i-1D.2 i-110.設單鏈表中指針p 指向結點 A ，若要刪除 A 的直接后繼，則所需修改指針的操作為()A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p11.下列排序算法中，某一趟結束后未必能選出一個元素放在其最終位置上的是()A. 堆排序B. 冒泡排序C.直接插入排序D. 快速排序12.設字符串 S1= ABCDEFG ， S2= PQRST，則運算S=CONCAT(SUBSTR(S1,2,LENGTH(S2),SUBST

5、R(S1,LENGTH(S2),2)后 S的結果為 ()A. BCQR B. BCDEF C. BCDEFG D. BCDEFEF 13.在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A ，并且 A 的左孩子的平衡因子為-1，右孩子的平衡因子為0，則使其平衡的調(diào)整方法為 ()A.LL 型B.LR 型C.RL 型D.RR 型14.如果結點 A 有 3 個兄弟結點，而且B為A的雙親，則 B的度為()A.1B.3C.4D.515.數(shù)據(jù)表 A 中每個元素距其最終位置較近，則最省時間的排序算法是()A. 堆排序B. 插入排序C.直接選擇排序D. 快速排序二、填空題 (本大題共 13 小題

6、，每小題2 分，共 26 分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.下列程序段的時間復雜度為_。i=1 ；while （ i<n ）i=i*2 ；17.向一個長度為 n 的順序表中第 i（ 1 i n）個元素之前插入一個元素時，需向后移動_個元素。18.在循環(huán)雙鏈表中，刪除最后一個結點，其算法的時間復雜度為_。19.隊列的插入操作在隊列的 _ 部分進行。20.一個棧的輸入序列是1， 2，3， n，輸出序列的第一個元素是n，則第 i 個輸出元素為 _ 。21.一個 10 階對稱矩陣A ，采用行優(yōu)先順序壓縮存儲下三角，a00 為第一個元素，其存儲地址為1，每個元素占有 1個

7、存儲地址空間，則a85 的地址為 _ 。22.設字符串S= I AM A STUDENT （其中表示空格字符），則 S 的長度為 _。23.在樹形結構中，沒有后繼的結點是_結點。24.一棵深度為n(n>1) 的滿二叉樹中共有_個結點。25.在無向圖中，如果從頂點v 到頂點v有路徑，則稱v 和v是 _ 。26.無向完全圖G 采用 _ 存儲結構較省空間。27.在順序查找、 二分查找、 索引查找和散列查找四種查找方法中，平均查找長度與元素個數(shù)沒有關系的查找方法是_。28.快速排序最好情況下的時間復雜度為_。三、應用題(本大題共5 小題，每小題6 分，共30 分)29.稀疏矩陣A 如下，寫出矩陣A 的三元組表及矩陣A 的轉置矩陣的三元組表。0300010000005-10000000040-30000030.一棵二叉樹的前根遍歷序列為ABCDEFG，中根遍歷序列為CBDAEGF ，試構造出該二叉樹。31.下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)及該連通網(wǎng)的最小生成樹。112 5101891282594102 432.給定表（ 80， 90，50，70，75， 60，40，100），試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。33.試寫出一組鍵值（46， 58， 15， 45，90， 18，10， 62）應用直接插入排