一、單選題（題數：30，共60.0分）1算法分析的兩個主要方面是()。（2.0分）A、[url=]空間復雜度和時間復雜度[/url]B、[url=]正確性和簡單性[/url]C、[url=]可讀性和文檔性[/url]D、[url=]數據復雜性和程序復雜性[/url]正確答案：A我的答案：A答案解析：2具有線性結構的數據結構是()。（2.0分）A、[url=]圖[/url]B、[url=]樹[/url]C、[url=]二叉樹[/url]D、[url=]棧[/url]正確答案：D我的答案：D答案解析：3下面程序段的時間復雜度是()。

for(i=0;i<m;i++)

for(j=0;j<n;j++)

a[j]=i*j;（2.0分）A、[url=]O(m2)[/url]B、[url=]O(n2)[/url]C、[url=]O(m*n)[/url]D、[url=]O(m+n)[/url]正確答案：C我的答案：B答案解析：4抽象數據類型的三個組成部分分別為()。（2.0分）A、[url=]數據對象、數據關系和基本操作[/url]B、[url=]數據元素、邏輯結構和存儲結構[/url]C、[url=]數據項、數據元素和數據類型[/url]D、[url=]數據元素、數據結構和數據類型[/url]正確答案：A我的答案：A答案解析：5線性表是n個()的有限序列。（2.0分）A、[url=]表元素[/url]B、[url=]字符[/url]C、[url=]數據元素[/url]D、[url=]數據項[/url]正確答案：C我的答案：C答案解析：6一個順序表的第一個元素的存儲地址是90,每個元素的長度為2,則第6個元素的存儲地址是()。（2.0分）A、[url=]98[/url]B、[url=]100[/url]C、[url=]102[/url]D、[url=]106[/url]正確答案：C我的答案：B答案解析：7向一個有127個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動()個元素。（2.0分）A、[url=]8[/url]B、[url=]63.5[/url]C、[url=]63[/url]D、[url=]7[/url]正確答案：C我的答案：B答案解析：8在一個長度為n的順序表中刪除第i個元素,需要向前移動()個元素。（2.0分）A、[url=]n-i[/url]B、[url=]n-i+1[/url]C、[url=]n-i-1[/url]D、[url=]i+1[/url]正確答案：C我的答案：A答案解析：9在線性表的下列存儲結構中,讀取元素花費的時間最少的是()。（2.0分）A、[url=]單鏈表[/url]B、[url=]雙鏈表[/url]C、[url=]循環鏈表[/url]D、[url=]順序表[/url]正確答案：D我的答案：D答案解析：10棧的插入和刪除操作在()。（2.0分）A、[url=]棧底[/url]B、[url=]棧頂[/url]C、[url=]任意位置[/url]D、[url=]指定位置[/url]正確答案：B我的答案：B答案解析：11棧中元素的進出原則是()。（2.0分）A、[url=]先進先出[/url]B、[url=]后進先出[/url]C、[url=]棧空則進[/url]D、[url=]棧滿則出[/url]正確答案：B我的答案：B答案解析：12正常情況下,刪除非空的順序存儲結構的堆棧的棧頂元素,棧頂指針top的變化是()。（2.0分）A、[url=]top不變[/url]B、[url=]top=0[/url]C、[url=]top=top+1[/url]D、[url=]top=top-1[/url]正確答案：D我的答案：D答案解析：13隊列的插入操作是在()。（2.0分）A、[url=]隊尾[/url]B、[url=]隊頭[/url]C、[url=]隊列任意位置[/url]D、[url=]隊頭元素后[/url]正確答案：A我的答案：A答案解析：14隊列的刪除操作是在()。（2.0分）A、[url=]隊尾[/url]B、[url=]隊頭[/url]C、[url=]隊列任意位置[/url]D、[url=]隊頭元素后[/url]正確答案：D我的答案：B答案解析：15設有兩個串S1和S2,求串S2在S1中首次出現位置的運算稱作()。（2.0分）A、[url=]連接[/url]B、[url=]求子串[/url]C、[url=]模式匹配[/url]D、[url=]判斷子串[/url]正確答案：C我的答案：C答案解析：16廣義表((a),a)的表尾是()。（2.0分）A、[url=]a[/url]B、[url=](a)[/url]C、[url=]()[/url]D、[url=]((a))[/url]正確答案：B我的答案：B答案解析：17廣義表G=(a,(b,c,d,(e,f)),g)的長度是()。（2.0分）A、[url=]3[/url]B、[url=]4[/url]C、[url=]7[/url]D、[url=]8[/url]正確答案：A我的答案：A答案解析：18常對數組進行兩種基本操作是()。（2.0分）A、[url=]建立和刪除[/url]B、[url=]索引和修改[/url]C、[url=]查找和修改[/url]D、[url=]查找與索引[/url]正確答案：C我的答案：C答案解析：19對一些特殊矩陣采用壓縮存儲的目的主要是為了()。（2.0分）A、[url=]表達變得簡單[/url]B、[url=]對矩陣元素的存取變得簡單[/url]C、[url=]去掉矩陣中的多余元素[/url]D、[url=]減少不必要的存儲空間的開銷[/url]正確答案：D我的答案：D答案解析：20稀疏矩陣一般的壓縮存儲方法有兩種,即()。（2.0分）A、[url=]空間復雜度和時間復雜度[/url]B、[url=]正確性和簡單性[/url]C、[url=]可讀性和文檔性[/url]D、[url=]數據復雜性和程序復雜性[/url]正確答案：A我的答案：B答案解析：21樹最適合用來表示()。（2.0分）A、[url=]有序數據元素[/url]B、[url=]無序數據元素[/url]C、[url=]元素之間具有分支層次關系的數據[/url]D、[url=]元素之間無聯系的數據[/url]正確答案：C我的答案：C答案解析：22把一棵樹轉換為二叉樹后,這棵二叉樹的形態是()。（2.0分）A、[url=]唯一的[/url]B、[url=]有多種[/url]C、[url=]有多種,但根結點都沒有左孩子[/url]D、[url=]有多種,但根結點都沒有右孩子[/url]正確答案：A我的答案：A答案解析：23關鍵路徑是事件結點網絡中()。（2.0分）A、[url=]從源點到匯點的最長路徑[/url]B、[url=]從源點到匯點的最短路徑[/url]C、[url=]最長的回路[/url]D、[url=]求關鍵路徑[/url]正確答案：A我的答案：A答案解析：24無向圖的鄰接矩陣是一個()。（2.0分）A、[url=]上三角矩陣[/url]B、[url=]下三角矩陣[/url]C、[url=]零矩陣[/url]D、[url=]對稱矩陣[/url]正確答案：D我的答案：D答案解析：25一個具有n個頂點的有向圖最多有()條邊。（2.0分）A、[url=]n×(n-1)[/url]B、[url=]n×(n-1)/2[/url]C、[url=]n×(n+1)/2[/url]D、[url=]n2[/url]正確答案：B我的答案：A答案解析：26在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的()倍。（2.0分）A、[url=]1/2[/url]B、[url=]1[/url]C、[url=]2[/url]D、[url=]4[/url]正確答案：B我的答案：B答案解析：27已知一個有序表為(11,22,33,44,55,66,77,88,99),則折半查找55需要比較()次。。（2.0分）A、[url=]1[/url]B、[url=]2[/url]C、[url=]3[/url]D、[url=]4[/url]正確答案：A我的答案：A答案解析：28在散列查找中,平均查找長度主要與()有關。。（2.0分）A、[url=]散列表長度[/url]B、[url=]散列元素個數[/url]C、[url=]裝填因子[/url]D、[url=]處理沖突方法[/url]正確答案：C我的答案：C答案解析：29在各種查找方法中,平均查找次數與結點個數n無關的查找方法是()。（2.0分）A、[url=]順序查找[/url]B、[url=]折半查找[/url]C、[url=]哈希查找[/url]D、[url=]分塊查找[/url]正確答案：C我的答案：C答案解析：30

研究數據結構就是研究（

）

（2.0分）A、[url=]數據的邏輯結構

[/url]B、[url=]數據的存儲結構

[/url]C、[url=]數據的基本操作

[/url]D、[url=]數據的邏輯結構、存儲結構及其基本操作

[/url]正確答案：D我的答案：D

二、填空題（題數：11，共20.0分）1在線性結構中,第一個結點____前驅結點,其余每個結點有且只有____個前驅結點;最后一個結點____后繼結點,其余每個結點有且只有1個后續結點

（3.0分）

[url=]正確答案[/url]

第一空：無

第二空：一

第三空：無

我的答案:第一空：沒有

第二空：1

第三空：沒有

2在樹形結構中,結點的上層結點稱為____結點。葉子結點沒有____結點。

（2.0分）

[url=]正確答案[/url]

第一空：父親

第二空：孩子

我的答案:第一空：前驅

第二空：后繼

3線性表的邏輯結構是____(“線性結構”或者“樹結構”、“圖結構”),其所含元素的個數稱為線性表的____,結點間的關系是____(“一對一”或者“一對多”、“多對多”)的

（3.0分）

[url=]正確答案[/url]

第一空：線性結構

第二空：長度

第三空：一對一

我的答案:第一空：

第二空：

第三空：

4順序表中邏輯上相鄰元素的物理位置____(“必定”還是“不一定”)相鄰。單鏈表中邏輯上相鄰的元素的物理位置____相鄰

（2.0分）

[url=]正確答案[/url]

第一空：必定

第二空：不一定

我的答案:

5在具有n個元素的循環隊列中,隊滿時具有____個元素

（1.0分）

[url=]正確答案[/url]

第一空：n-1

我的答案:

6廣義表運算式HEAD(TAIL((a,b,c),(x,y,z)))的結果是:____。

（1.0分）

[url=]正確答案[/url]

第一空：(x,y,z)

我的答案:

7哈夫曼樹是其樹的帶權路徑長度____的二叉樹

（1.0分）

[url=]正確答案[/url]

第一空：最小

我的答案:

8在無向圖G的鄰接矩陣A中,若A[j]等于1,則A[j]等于____

（1.0分）

[url=]正確答案[/url]

第一空：1

我的答案:

9圖有____、____等存儲結構,遍歷圖有____、____等方法

（4.0分）

[url=]正確答案[/url]

第一空：鄰接矩陣

第二空：鄰接表

第三空：深度優先遍歷

第四空：廣度優先遍歷

我的答案:

10帶頭結點的單鏈表head為空的條件是____。

（1.0分）

[url=]正確答案[/url]

第一空：head->next==NULL

我的答案:

11在一個長度為n的向量中刪除第i個元素(1≤i≤n)時,需向前移動____個元素

（1.0分）

[url=]正確答案[/url]

第一空：n-i

我的答案:

三、判斷題（題數：15，共15.0分）1線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可以是一個復雜類型。()

（1.0分）

正確答案：×我的答案：×答案解析：2在單鏈表中,要訪問某個結點,只要知道該結點的地址即可;因此,單鏈表是一種隨機存取結構。()

（1.0分）

正確答案：×我的答案：×答案解析：3在具有頭結點的單鏈表中,頭指針指向鏈表的第一個數據結點。()

（1.0分）

正確答案：√我的答案：×答案解析：4在表結構中最常用的是線性表,棧和隊列不太常用。()

（1.0分）

正確答案：×我的答案：×答案解析：5兩個棧共享一片連續內存空間時,為提高內存利用率,減少溢出機會,應把兩個棧的棧底分別設在這片內存空間的兩端。()

（1.0分）

正確答案：√我的答案：√答案解析：6一個棧的輸入序列是12345,則棧的輸出序列不可能是12345。()

（1.0分）

正確答案：√我的答案：×答案解析：7廣義表是一種多層次的數據結構,其元素可以是單原子也可以是子表。()

（1.0分）

正確答案：√我的答案：√答案解析：8存在這樣的二叉樹,對它采用任何次序的遍歷,結果相同。()

（1.0分）

正確答案：×我的答案：√答案解析：9中序