課程**：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1.在順序表中查詢第i個元素，時間效率最高的演算法的時間複雜度為( )
a.o(1) b.o()
c.o(log2n) d.o(n)
2.樹形結構中，度為0的結點稱為( )
a.樹根 b.葉子
c.路徑 d.二叉樹
3.已知有向圖g=(v,e)，其中v=，e=，則圖g的拓撲序列是
( )
a.v1,v3,v4,v6,v2,v5,v7 b.v1,v3,v2,v6,v4,v5,v7
c.v1,v3,v4,v5,v2,v6,v7 d.v1,v2,v5,v3,v4,v6,v7
4.有關圖中路徑的定義，表述正確的是( )
a.路徑是頂點和相鄰頂點偶對構成的邊所形成的序列
b.路徑是不同頂點所形成的序列
c.路徑是不同邊所形成的序列
d.路徑是不同頂點和不同邊所形成的集合
5.串的長度是指( )
a.串中所含不同字母的個數 b.串中所含字元的個數
c.串中所含不同字元的個數 d.串中所含非空格字元的個數
6.組成資料的基本單位是( )
a.資料項 b.資料型別
c.資料元素 d.資料變數
7.程式段 i=n；x=0；
dowhile （i>0）；
的時間複雜度為( )
a.o（1） b.o（n）
c.o（n2） d.o(n3)
8.與串的邏輯結構不同的資料結構是( )
a.線性表 b.棧
c.佇列 d.樹
9.二叉樹的第i（i≥1）層上所擁有的結點個數最多為( )
a.2i b.2i
c.2i-1 d.2i-1
10.設單鏈表中指標p指向結點a，若要刪除a的直接後繼，則所需修改指標的操作為
( )
a.p->next=p->next->next b.p=p->next
c.p=p->next->next d.p->next=p
11.下列排序演算法中，某一趟結束後未必能選出乙個元素放在其最終位置上的是( )
a.堆排序 b.氣泡排序
c.直接插入排序 d.快速排序
12.設字串s1=″abcdefg″，s2=″pqrst″，則運算
s=concat(substr(s1,2,length(s2)),substr(s1,length(s2),2))
後s的結果為( )
a.″bcqr″ b.″bcdef″
c.″bcdefg″ d.″bcdefef″
13.在平衡二叉樹中插入乙個結點後造成了不平衡，設最低的不平衡結點為a，並且a的左孩子的平衡因子為-1，右孩子的平衡因子為0，則使其平衡的調整方法為( )
a.ll型 b.lr型
c.rl型 d.rr型
14.如果結點a有3個兄弟結點，而且b為a的雙親，則b的度為( )
a.1 b.3
c.4 d.5
15.資料表a中每個元素距其最終位置較近，則最省時間的排序演算法是( )
a.堆排序 b.插入排序
c.直接選擇排序 d.快速排序
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16.下列程式段的時間複雜度為
i=1；
while（ii=i*2；
17.向乙個長度為n的順序表中第i（1≤i≤n）個元素之前插入乙個元素時，需向後移動個元素。
18.在迴圈雙鏈表中，刪除最後乙個結點，其演算法的時間複雜度為
19.佇列的插入操作在佇列的部分進行。
20.乙個棧的輸入序列是1，2，3，…，n，輸出序列的第乙個元素是n，則第i個輸出元素為
21.乙個10階對稱矩陣a，採用行優先順序壓縮儲存下三角，a00為第乙個元素，其儲存位址為1，每個元素占有1個儲存位址空間，則a85的位址為
22.設字串s=″i□am□a□student″（其中□表示空格字元），則s的長度為
23.在樹形結構中，沒有後繼的結點是結點。
24.一棵深度為n(n>1)的滿二叉樹中共有個結點。
25.在無向圖中，如果從頂點v到頂點v′有路徑，則稱v和v′是
26.無向完全圖g採用儲存結構較省空間。
27.在順序查詢、二分查詢、索引查詢和雜湊查詢四種查詢方法中，平均查詢長度與元素個數沒有關係的查詢方法是
28.快速排序最好情況下的時間複雜度為
三、應用題(本大題共5小題，每小題6分，共30分)
29.稀疏矩陣a如下，寫出矩陣a的三元組表及矩陣a的轉置矩陣的三元組表。
30.一棵二叉樹的前根遍歷序列為abcdefg，中根遍歷序列為cbdaegf，試構造出該二叉樹。
31.下述矩陣表示乙個無向連通網，試畫出它所表示的連通網及該連通網的最小生成樹。
32.給定表（80，90，50，70，75，60，40，100），試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成後的二叉排序樹。
33.試寫出一組鍵值（46，58，15，45，90，18，10，62）應用直接插入排序演算法從小到大排序後各趟的結果。
四、演算法設計題(本大題共2小題，每小題7分，共14分)
34.試分別寫出二叉樹的先根遍歷和中根遍歷的遞迴演算法。
35.試編寫以單鏈表為儲存結構實現直接選擇排序的演算法。
課程**：02142
一、單項選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其**填寫在題後的括號內。錯選、多選或未選均無分。
1．下列描述中正確的是( )
a.資料元素是資料的最小單位
b.資料結構是具有結構的資料物件
c.資料結構是指相互之間存在一種或多種特定關係的資料元素的集合
d.演算法和程式原則上沒有區別，在討論資料結構時兩者是通用的
2．歸併排序的時間複雜度是( )
a．o（n2） b.o（nlog2n）
c.o（n） d.o（log2n）
3．二分查詢的時間複雜度是( )
a．o（n2） b.o（nlog2n）
c.o（n） d.o（log2n）
4．順序儲存的表中有90000個元素，已按關鍵字值公升序排列，假設對每個元素進行查詢的概率相同，且每個元素的關鍵字值皆不相同，用順序查詢法查詢時，需平均比較的次數為( )
a．25000 b.30000
c.45000 d.90000
5．雜湊檔案是一種( )
a．順序檔案 b.索引檔案
c.鏈結檔案 d.計算定址檔案
6．兩個矩陣a：m×n，b：n×p相乘，其時間複雜度為( )
a．o(n) b.o(mnp)
c.o(n2) d.o（mp）
7.常用於函式呼叫的資料結構是( )
a.棧 b.佇列
c.鍊錶 d.陣列
8．二維陣列a［n］［m］以列優先順序儲存，陣列a中每個元素占用1個位元組，a［1］［1］為首元素，其位址為0，則元素a［i］［j］的位址為( )
a.（i-1）×m+(j-1) b.(j-1)×n+(i-1)
c.(j-1)×n+i d.j×n+i
9.圖的廣度優先搜尋使用的資料結構是( )
a．佇列 b.樹
c.棧 d.集合
10．序列（21,19,37,5,2）經氣泡排序法由小到大排序，在第一次執行交換後所得結果為( )
a．(19，21，37，5，2) b.(21，19，5，37，2)
c.(21，19，37，2，5) d.(2，21，19，37，5)
11．資料在計算機儲存器內表示時，根據結點的關鍵字直接計算出該結點的儲存位址，這種方法稱為( )
a．索引儲存方法 b.順序儲存方法
c.鏈式儲存方法 d.雜湊儲存方法
12．在單鏈表中，儲存每個結點有兩個域，乙個是資料域，另乙個是指標域，指標域指向該結點的( )
a．直接前趨 b.直接後繼
c.開始結點 d.終端結點
13．在已知頭指標的單鏈表中，要在其尾部插入一新結點，其演算法所需的時間複雜度為( )
a．o（1） b.o（log2n）
c.o（n） d.o（n2）
14．在鏈佇列中執行入隊操作，( )
a．需判別隊是否空 b.需判別隊是否滿
c.限制在煉表頭p進行 d.限制在鍊錶尾p進行
15．一整數序列26，59，77，31，51，11，19，42，以二路歸併排序從小到大排序，第一階段的歸併結果為( )
a.31，51，11，42，26，77，59，19 b.26，59，31，77，11，51，19，42
c.11，19，26，31，42，59，51，77 d.26，11，19，31，51，59，77，42
二、填空題(本大題共13小題，每小題2分，共26分)
請在每小題的空格中填上正確答案。錯填、不填均無分。
16．下列程式段的時間複雜度為_______。
i=0；s=0；
while（s
17．資料的儲存結構被分為順序儲存結構、_______、雜湊儲存結構和索引儲存結構4種。
18．從乙個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動_______個元素。
19．在單鏈表中，插入乙個新結點需修改_______個指標。
20．在佇列結構中，允許插入的一端稱為_______。
21．稀疏矩陣採用的壓縮儲存方法是_______。
22．向乙個棧頂指標為top的鏈棧中插入乙個新結點*p時，應執行p->next=top和_______操作。
23．有m個葉結點的哈夫曼樹所具有的結點數為_______。
自學考試資料結構導論試題
全國2007年1月高等教育自學考試 資料結構導論試題 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1 關於棧和佇列的說法中正確的是 a 棧和佇列都是線性結構 b.棧是...
全國自學考試資料結構導論試題及答案4套
課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.在順序表中查詢第i個元素，時間效率最高的演算法的時間複雜度為 a.o 1 b.o c.o log2n d.o n 2....
全國自學考試資料結構試題
課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.每個結點有且僅有乙個直接前趨和多個 或無 直接後繼 第乙個結點除外 的資料結構稱為 a.樹狀結構 b.網狀結構 c.線...