用鏈接方式存儲的隊列在進行插入運算時

Ⅰ 為什麼在順序存儲結構下，棧的插入和刪除運算都不需要移動表中其他數據元素，如果在鏈式存儲結構下會怎樣

棧也被叫做"先進後出表",正是由於這種性質,讓它可以不需要移動元素實現插入和刪除.
棧的插入,其實就是壓棧,它是被嚴格限制在棧頂進行的.由於棧頂也是表中最後一個元素,所以壓棧也就相當於是在順序表的最後追加一個元素,這顯然不影響前面的元素,也就無需移動其他元素了.
刪除也是同樣的道理,彈棧(刪除操作)也是被嚴格限制在棧頂進行,這時候刪除一個元素只需要在順序表中去除最後一個元素,自然也不影響之前的元素.

鏈式結構對於棧來說,同樣不需要作任何其他元素的移動.事實上,鏈式結構的刪除和插入操作本身就不需要移動其他元素,無論是對於棧來說還是對於一般的鏈表.

Ⅱ 用鏈接方式存儲的隊列，在進行插入運算時。。。（為什麼選D請詳細說明，謝謝！我會增加懸賞分的~）

不帶頭結點的隊列進行插入或刪除操作時都有可能將頭尾指針修改，題目未明確說明帶不帶頭節點，所以應該考慮這種情況，選D,我做的卷子上也是選D

Ⅲ java中的linklist有哪些用法，list.add,list.getFirst(),這些是什麼意思

ArrayList Vector LinkedList 區別與用法

ArrayList 和Vector是採用數組方式存儲數據，此數組元素數大於實際存儲的數據以便增加和插入元素，都允許直接序號索引元素，但是插入數據要設計到數組元素移動等內存操作，所以索引數據快插入數據慢，Vector由於使用了synchronized方法（線程安全）所以性能上比ArrayList要差，LinkedList使用雙向鏈表實現存儲，按序號索引數據需要進行向前或向後遍歷，但是插入數據時只需要記錄本項的前後項即可，所以插入數度較快！

線性表，鏈表，哈希表是常用的數據結構，在進行Java開發時，JDK已經為我們提供了一系列相應的類來實現基本的數據結構。這些類均在java.util包中。本文試圖通過簡單的描述，向讀者闡述各個類的作用以及如何正確使用這些類。

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap

Collection介面
Collection是最基本的集合介面，一個Collection代表一組Object，即Collection的元素（Elements）。一些Collection允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類，Java SDK提供的類都是繼承自Collection的「子介面」如List和Set。
所有實現Collection介面的類都必須提供兩個標準的構造函數：無參數的構造函數用於創建一個空的Collection，有一個Collection參數的構造函數用於創建一個新的Collection，這個新的Collection與傳入的Collection有相同的元素。後一個構造函數允許用戶復制一個Collection。
如何遍歷Collection中的每一個元素？不論Collection的實際類型如何，它都支持一個iterator()的方法，該方法返回一個迭代子，使用該迭代子即可逐一訪問Collection中每一個元素。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個元素
}
由Collection介面派生的兩個介面是List和Set。

List介面
List是有序的Collection，使用此介面能夠精確的控制每個元素插入的位置。用戶能夠使用索引（元素在List中的位置，類似於數組下標）來訪問List中的元素，這類似於Java的數組。
和下面要提到的Set不同，List允許有相同的元素。
除了具有Collection介面必備的iterator()方法外，List還提供一個listIterator()方法，返回一個ListIterator介面，和標準的Iterator介面相比，ListIterator多了一些add()之類的方法，允許添加，刪除，設定元素，還能向前或向後遍歷。
實現List介面的常用類有LinkedList，ArrayList，Vector和Stack。

LinkedList類
LinkedList實現了List介面，允許null元素。此外LinkedList提供額外的get，remove，insert方法在LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。
注意LinkedList沒有同步方法。如果多個線程同時訪問一個List，則必須自己實現訪問同步。一種解決方法是在創建List時構造一個同步的List：
List list = Collections.synchronizedList(new LinkedList(...));

ArrayList類
ArrayList實現了可變大小的數組。它允許所有元素，包括null。ArrayList沒有同步。
size，isEmpty，get，set方法運行時間為常數。但是add方法開銷為分攤的常數，添加n個元素需要O(n)的時間。其他的方法運行時間為線性。
每個ArrayList實例都有一個容量（Capacity），即用於存儲元素的數組的大小。這個容量可隨著不斷添加新元素而自動增加，但是增長演算法並沒有定義。當需要插入大量元素時，在插入前可以調用ensureCapacity方法來增加ArrayList的容量以提高插入效率。
和LinkedList一樣，ArrayList也是非同步的（unsynchronized）。

Vector類
Vector非常類似ArrayList，但是Vector是同步的。由Vector創建的Iterator，雖然和ArrayList創建的Iterator是同一介面，但是，因為Vector是同步的，當一個Iterator被創建而且正在被使用，另一個線程改變了Vector的狀態（例如，添加或刪除了一些元素），這時調用Iterator的方法時將拋出，因此必須捕獲該異常。

Stack 類
Stack繼承自Vector，實現一個後進先出的堆棧。Stack提供5個額外的方法使得Vector得以被當作堆棧使用。基本的push和pop方法，還有peek方法得到棧頂的元素，empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置。Stack剛創建後是空棧。

Set介面
Set是一種不包含重復的元素的Collection，即任意的兩個元素e1和e2都有e1.equals(e2)=false，Set最多有一個null元素。
很明顯，Set的構造函數有一個約束條件，傳入的Collection參數不能包含重復的元素。
請注意：必須小心操作可變對象（Mutable Object）。如果一個Set中的可變元素改變了自身狀態導致Object.equals(Object)=true將導致一些問題。

Map介面
請注意，Map沒有繼承Collection介面，Map提供key到value的映射。一個Map中不能包含相同的key，每個key只能映射一個value。Map介面提供3種集合的視圖，Map的內容可以被當作一組key集合，一組value集合，或者一組key-value映射。

Hashtable類
Hashtable繼承Map介面，實現一個key-value映射的哈希表。任何非空（non-null）的對象都可作為key或者value。
添加數據使用put(key, value)，取出數據使用get(key)，這兩個基本操作的時間開銷為常數。
Hashtable通過initial capacity和load factor兩個參數調整性能。通常預設的load factor 0.75較好地實現了時間和空間的均衡。增大load factor可以節省空間但相應的查找時間將增大，這會影響像get和put這樣的操作。
使用Hashtable的簡單示例如下，將1，2，3放到Hashtable中，他們的key分別是」one」，」two」，」three」：
Hashtable numbers = new Hashtable();
numbers.put(「one」, new Integer(1));
numbers.put(「two」, new Integer(2));
numbers.put(「three」, new Integer(3));
要取出一個數，比如2，用相應的key：
Integer n = (Integer)numbers.get(「two」);
System.out.println(「two = 」 + n);
由於作為key的對象將通過計算其散列函數來確定與之對應的value的位置，因此任何作為key的對象都必須實現hashCode和equals方法。hashCode和equals方法繼承自根類Object，如果你用自定義的類當作key的話，要相當小心，按照散列函數的定義，如果兩個對象相同，即obj1.equals(obj2)=true，則它們的hashCode必須相同，但如果兩個對象不同，則它們的hashCode不一定不同，如果兩個不同對象的hashCode相同，這種現象稱為沖突，沖突會導致操作哈希表的時間開銷增大，所以盡量定義好的hashCode()方法，能加快哈希表的操作。
如果相同的對象有不同的hashCode，對哈希表的操作會出現意想不到的結果（期待的get方法返回null），要避免這種問題，只需要牢記一條：要同時復寫equals方法和hashCode方法，而不要只寫其中一個。
Hashtable是同步的。

HashMap類
HashMap和Hashtable類似，不同之處在於HashMap是非同步的，並且允許null，即null value和null key。，但是將HashMap視為Collection時（values()方法可返回Collection），其迭代子操作時間開銷和HashMap的容量成比例。因此，如果迭代操作的性能相當重要的話，不要將HashMap的初始化容量設得過高，或者load factor過低。

WeakHashMap類
WeakHashMap是一種改進的HashMap，它對key實行「弱引用」，如果一個key不再被外部所引用，那麼該key可以被GC回收。

總結
如果涉及到堆棧，隊列等操作，應該考慮用List，對於需要快速插入，刪除元素，應該使用LinkedList，如果需要快速隨機訪問元素，應該使用ArrayList。
如果程序在單線程環境中，或者訪問僅僅在一個線程中進行，考慮非同步的類，其效率較高，如果多個線程可能同時操作一個類，應該使用同步的類。
要特別注意對哈希表的操作，作為key的對象要正確復寫equals和hashCode方法。
盡量返回介面而非實際的類型，如返回List而非ArrayList，這樣如果以後需要將ArrayList換成LinkedList時，客戶端代碼不用改變。這就是針對抽象編程。

同步性
Vector是同步的。這個類中的一些方法保證了Vector中的對象是線程安全的。而ArrayList則是非同步的，因此ArrayList中的對象並不是線程安全的。因為同步的要求會影響執行的效率，所以如果你不需要線程安全的集合那麼使用ArrayList是一個很好的選擇，這樣可以避免由於同步帶來的不必要的性能開銷。
數據增長
從內部實現機制來講ArrayList和Vector都是使用數組(Array)來控制集合中的對象。當你向這兩種類型中增加元素的時候，如果元素的數目超出了內部數組目前的長度它們都需要擴展內部數組的長度，Vector預設情況下自動增長原來一倍的數組長度，ArrayList是原來的50%,所以最後你獲得的這個集合所佔的空間總是比你實際需要的要大。所以如果你要在集合中保存大量的數據那麼使用Vector有一些優勢，因為你可以通過設置集合的初始化大小來避免不必要的資源開銷。
使用模式
在ArrayList和Vector中，從一個指定的位置（通過索引）查找數據或是在集合的末尾增加、移除一個元素所花費的時間是一樣的，這個時間我們用O(1)表示。但是，如果在集合的其他位置增加或移除元素那麼花費的時間會呈線形增長：O(n-i)，其中n代表集合中元素的個數，i代表元素增加或移除元素的索引位置。為什麼會這樣呢？以為在進行上述操作的時候集合中第i和第i個元素之後的所有元素都要執行位移的操作。這一切意味著什麼呢？
這意味著，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那麼使用Vector或ArrayList都可以。如果是其他操作，你最好選擇其他的集合操作類。比如，LinkList集合類在增加或移除集合中任何位置的元素所花費的時間都是一樣的?O(1)，但它在索引一個元素的使用缺比較慢－O(i),其中i是索引的位置.使用ArrayList也很容易，因為你可以簡單的使用索引來代替創建iterator對象的操作。LinkList也會為每個插入的元素創建對象，所有你要明白它也會帶來額外的開銷。
最後，在《Practical Java》一書中Peter Haggar建議使用一個簡單的數組（Array）來代替Vector或ArrayList。尤其是對於執行效率要求高的程序更應如此。因為使用數組(Array)避免了同步、額外的方法調用和不必要的重新分配空間的操作。

Ⅳ 設循環隊列的存儲空間為Q(1:35),初始狀態為front=rear=35.現經過一系列入隊與退隊運算後，

答案是0或35。前提條件是：此循環隊列的存儲空間全部用於存儲數據，而沒有留出一個存儲空間用於判別隊滿與隊空。

在上述循環隊列中，當front = rear時，

（1）有可能是隊空：先入隊15個元素，rear = 15；再出隊15個元素，front = 15。

（2）有可能是隊滿：先入隊15個元素，rear = 15；再出隊15個元素，front =
15；最後再入隊35個元素，rear指針循環一圈後再次等於15。

綜上，隊列中元素個數為0或35。

但應注意，上述的循環隊列由於無法判別隊滿與隊空，導致其產生二義性（即有歧義），可用性降低。因此，改進的方法是少用一個存儲空間，即隊列最大隻存儲34個元素，此時可用下列方法區分隊滿與隊空：

（1）隊滿：（rear + 1）% MaxSize == front

（2）隊空：rear == front

Ⅳ SJTU 《演算法設計與分析》備考題

1、除根結點外，樹上每個結點( )。
a. 可有一個孩子、任意多個雙親
b. 可有任意多個孩子、一個雙親
c. 只有一個孩子、一個雙親
d. 可有任意多個孩子、任意多個雙親
2、採用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（ ）。
a. (n+1)/2
b. n/2
c. (n-1)/2
d. n
3、採用二分查找方法查找長度為n的線性表時,每個元素的平均查找長度為（ ）。
a. O(log2n)
b. O(n2)
c. O(n)
d. O(nlog2n)
4、設順序線性表中有n個數據元素，則刪除表中第i個元素需向前移動（ ）個元素。
a. n-1-i
b. n-i
c. i
d. n+1-i
5、設順序循環隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環隊列中的元素個數為（ ）。
a. (R-F+M)％M
b. F-R
c. (F-R+M)％M
d. R-F
6、設輸入序列是1、2、3、…、n，經過棧的作用後輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（ ）。
a. n-1-i
b. 不能確定
c. n-i
d. n+1-i
7、設輸入序列為1、2、3、4、5、6，則通過棧的作用後可以得到的輸出序列為（ ）。
a. 5，3，4，6，1，2
b. 1，5，4，6，2，3
c. 3，1，2，5，4，6
d. 3，2，5，6，4，1
8、設用鏈表作為棧的存儲結構，則退棧操作（ ）。
a. 必須判別棧是否為滿
b. 必須判別棧是否為空
c. 對棧不作任何判別
d. 必須判別棧元素的類型
9、設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為( )。
a. 第i列0元素的個數之和
b. 第i行0元素的個數之和
c. 第i列非0元素的個數之和
d. 第i行非0元素的個數之和
10、設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（ ）存儲方式最節省運算時間。
a. 雙向鏈表
b. 雙向循環鏈表
c. 單向循環鏈表
d. 單向鏈表
11、設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有( )。
a. 1024
b. 256
c. 20
d. 512
12、設某棵二叉樹的中序遍歷序列為ABCD，先序遍歷序列為CABD，則後序遍歷該二叉樹得到序列為( )。
a. CDAB
b. BADC
c. CBDA
d. BCDA
13、設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為( )。
a. 9
b. 11
c. 12
d. 10
14、設某棵二叉樹中只有度數為0和度數為2的結點，且度數為0的結點數為n，則這棵二叉樹中共有( )個結點。
a. n+1
b. 2n
c. 2n+1
d. 2n-1
15、設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有( )條有向邊。
a. n-1
b. m
c. n
d. m-1
16、設某無向圖有n個頂點，則該無向圖的鄰接表中有( )個表頭結點。
a. 2n-1
b. n
c. n/2
d. 2n
17、設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的度之和為( )。
a. 2e
b. n
c. e
d. 2n
18、設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為( )。
a. O(n\*e)
b. O(n+e)
c. O(n2)
d. O(n3)
19、設某數據結構的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數據結構A是( )。
a. 圖結構
b. 物理結構
c. 線性結構
d. 樹型結構
20、設某強連通圖中有n個頂點，則該強連通圖中至少有( )條邊。
a. n(n-1)
b. n
c. n+1
d. n(n+1)
21、設某完全無向圖中有n個頂點，則該完全無向圖中有( )條邊。
a. n
b. n-1
c. n(n-1)
d. n(n-1)/2
22、設某哈夫曼樹中有199個結點，則該哈夫曼樹中有( )個葉子結點。
a. 99
b. 101
c. 100
d. 102
23、設某二叉樹中度數為0的結點數為N0，度數為1的結點數為N1，度數為2的結點數為N2，則下列等式成立的是( )。
a. N0=N1+N2
b. N0=N2+1
c. N0=2N1+1
d. N0=N1+1
24、設有6個結點的無向圖，該圖至少應有( )條邊才能確保是一個連通圖。
a. 7
b. 6
c. 8
d. 5
25、設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（ ）條邊。
a. 2n-1
b. n
c. n-1
d. 2n
26、設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為( )。
a. i/2
b. 2i+1
c. 2i
d. 2i-1
27、設指針變數top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作為（ ）。
a. top=top+1;
b. top->next=top;
c. top=top->next;
d. top=top-1;
28、設指針變數p指向雙向鏈表中結點A，指針變數s指向被插入的結點X，則在結點A的後面插入結點X的操作序列為（ ）。
a. p->next=s； s->prior=p； p->next->prior=s； s->next=p->next；
b. s->prior=p； s->next=p->next； p->next=s； p->next->prior=s；
c. p->next=s； p->next->prior=s； s->prior=p； s->next=p->next；
d. s->prior=p；s->next=p->next；p->next->prior=s； p->next=s；
29、設指針變數p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（ ）。
a. q=p->next；q->data=p->data；p->next=q->next；free(q)；
b. q=p->next；p->data=q->data；free(q)；
c. q=p->next；p->next=q->next；free(q)；
d. q=p->next；p->data=q->data；p->next=q->next；free(q)；
30、設指針變數front表示鏈式隊列的隊頭指針，指針變數rear表示鏈式隊列的隊尾指針，指針變數s指向將要入隊列的結點X，則入隊列的操作序列為（ ）。
a. front->next=s；front=s；
b. rear->next=s；rear=s；
c. s->next=front；front=s；
d. s->next=rear；rear=s；
31、設指針q指向單鏈表中結點A，指針p指向單鏈表中結點A的後繼結點B，指針s指向被插入的結點X，則在結點A和結點B插入結點X的操作序列為（ ）。
a. p->next=s->next；s->next=p；
b. p->next=s；s->next=q；
c. s->next=p->next；p->next=-s；
d. q->next=s； s->next=p；
32、設帶有頭結點的單循環鏈表的頭指針為head，則其判空條件是（ ）。
a. head->next==head
b. head==NULL
c. head->next==NULL
d. head!= NULL
33、設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有( )個空指針域。
a. 4m
b. 2m-1
c. 2m+1
d. 2m
34、設二叉樹的先序遍歷序列和後序遍歷序列正好相反，則該二叉樹滿足的條件是( )。
a. 任一結點無左孩子
b. 任一結點無右孩子
c. 高度等於其結點數
d. 空或只有一個結點
35、設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（ ）。
a. O(1)
b. O(n)
c. O(n2)
d. O(nlog2n)
36、設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為( )。
a. 40
b. 45
c. 30
d. 20
37、設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為( )。
a. 7
b. 6
c. 5
d. 8
38、設一條單鏈表的頭指針為head，且該鏈表沒有頭結點，則其判空條件是（ ）。
a. head==NULL
b. head->next==head
c. head->next==NULL
d. head!=NULL
39、設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數為( )。
a. N2+N3
b. N1-1
c. N1+N3
d. N2-1
40、若採用鄰接表存儲結構，則圖的深度優先搜索類似於二叉樹的（）
a. 層次遍歷
b. 先根遍歷
c. 中根遍歷
d. 後根遍歷
41、若採用鄰接表存儲結構，則圖的廣度優先搜索類似於二叉樹的（）
a. 先根遍歷
b. 後根遍歷
c. 層次遍歷
d. 中根遍歷
42、若線性表最常用的操作是存取第i個元素及其前驅的值，則採用（ ）存儲方式最節省時間。
a. 雙向鏈表
b. 順序表
c. 單鏈表
d. 單循環鏈表
43、若一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的第一趟結果為（ ）。
a. 40，38，46，56，79，84
b. 40，38，46，84，56，79
c. 38，40，46，56，79，84
d. 40，38，46，79，56，84
44、若一個圖的邊集為 {(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)} ，則從頂點 A 開始對該圖進行深度優先搜索，得到的頂點序列可能為（ ）。
a. A,B,C,F,D,E
b. A,C,F,D,E,B
c. A,B,D,F,E,C
d. A,B,D,C,F,E
45、若一個圖的邊集為 {(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)} ，則從頂點 A 開始對該圖進行廣度優先搜索，得到的頂點序列可能為（ ）。
a. A,B,C,F,D,E
b. A,B,C,D,E,F
c. A,B,D,C,E,F
d. A,C,B,F,D,E
46、線性表若採用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）。
a. 連續或不連續都可以
b. 必須是連續的
c. 部分地址必須是連續的
d. 一定是不連續的
47、用鏈接方式存儲的隊列，在進行插入運算時（ ）。
a. 僅修改尾指針
b. 頭、尾指針都要修改
c. 僅修改頭指針
d. 頭、尾指針都不要修改
48、用鄰接表存儲圖所用的空間大小（ ）。
a. 只與圖的邊數有關
b. 與圖的頂點數和邊數都有關
c. 只與圖的頂點數有關
d. 與邊數的平方有關
49、樹的後根遍歷序列等同於該樹對應的二叉樹的( )。
a. 先序序列
b. 中序序列
c. 後序序列
d. 層次序列
50、樹型結構最適合用來表示( )。
a. 無序數據元素
b. 有序數據元素
c. 元素之間無聯系的數據
d. 元素之間具有分支層次關系的數據
51、棧。和隊列的共同點是（ ）。
a. 只允許在端點處插入和刪除元素
b. 都是先進後出
c. 都是先進先出
d. 沒有共同點
52、數據結構是研究數據的（ ）以及它們之間的相互關系。
a. 理想結構，抽象結構
b. 物理結構，邏輯結構
c. 理想結構，物理結構
d. 抽象結構，邏輯結構
53、數據的最小單位是（ ）。
a. 數據元素
b. 數據項
c. 數據類型
d. 數據變數
54、已知一個有向圖的邊集為 {<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>} ，則由該圖產生的一種可能的拓撲序列為( )。
a. a,b,c,d,e
b. a,c,b,e,d
c. a,b,d,e,b
d. a,c,d,b,e
55、對線性表進行二分查找時，要求線性表必須（ ）。
a. 以鏈接方式存儲
b. 以鏈接方式存儲，且結點按關鍵字有序排序
c. 以順序方式存儲，且結點按關鍵字有序排序
d. 以順序方式存儲
56、在長度為n的順序存儲的線性表中插入第i個元素(1≤i≤n)需向後移動（ ）個元素。
a. n-i
b. i
c. n-1-i
d. n-i+1
57、在用鄰接表表示圖時，對圖進行深度優先搜索遍歷的演算法的時間復雜度為（ ）。
a. O(n2)
b. O(n+e)
c. O(n3)
d. O(n)
58、在有向圖的鄰接表存儲結構中，頂點v在鏈表中出現的次數是( )。
a. 頂點v的度
b. 依附於頂點v的邊數
c. 頂點v的入度
d. 頂點v的出度
59、在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現的是（ ）。
a. G中有一條從Vi到Vj的路徑
b. G中有弧
c. G中沒有弧
d. G中有一條從Vj到Vi的路徑
60、在下列存儲形式中，哪一個不是樹的存儲形式？( )
a. 孩子鏈表表示法
b. 順序存儲表示法
c. 孩子兄弟表示法
d. 雙親表示法
61、在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執行（ ）。
a. q->next = s；s->next = p；
b. s->next = p->next；p->next = s；
c. p->next = s->next；s->next = p；
d. p->next = s；s->next = q；
62、在一個具有n個頂點的無向圖中，每個頂點度的最大值為（ ）
a. n-1
b. n+1
c. n
d. 2(n-1)
63、圖的BFS生成樹的樹高比DFS生成樹的樹高（ ）。
a. 大或相等
b. 小
c. 小或相等
d. 大
64、含有n個結點的二叉樹採用二叉鏈表存儲時，空指針域的個數為( )。
a. n
b. n+1
c. n+2
d. n-1
65、關於無向圖的鄰接矩陣的說法中正確的是（ ）。
a. 矩陣中的非零元素個數等於圖的邊數
b. 矩陣中非全零元素的行數等於圖中的頂點數
c. 第i行上非零元素個數和第i列上非零元素個數一定相等
d. 第i行上與第i列上非零元素總和等於頂點Vi的度數
66、二叉樹的第k層的結點數最多為( )。
a. 2k
b. 2k -1
c.2k
d. 2k-1
67、二叉排序樹按( )遍歷可以得到一個從小到大的有序序列。
a. 後序
b. 中序
c. 層次
d. 先序
68、下面程序的時間復雜為（ ）。
for(i=1, s=0; i<=n; i++)
{ t=1;
for(j=1; j<=i; j++)
t=t*j; s=s+t;
}
a. O(n3)
b. O(n)
c. O(n2)
d. O(n4)
69、下面程序段的時間復雜度為（ ）。
s=i=0;
do { i=i+1; s=s+i;
} while(i<=n);
a. O(n)
b. O(nlog2n)
c. O(n2)
d. O(1)
70、下面關於線性表的敘述錯誤的是（ ）。
a. 線性表採用鏈式存儲不必佔用一片連續的存儲空間
b. 線性表採用順序存儲必須佔用一片連續的存儲空間
c. 線性表採用順序存儲便於插入和刪除操作的實現
d. 線性表採用鏈式存儲便於插入和刪除操作的實現
71、下述編碼中哪一個不是前綴編碼( )。
a. 0,10,110,111
b. 00,01,10,11
c. 1,01,000,001
d. 0,1,00,11
72、下列說法不正確的是（ ）。
a. 圖的深度遍歷不適用於有向圖
b. 圖的深度遍歷是一個遞歸過程
c. 遍歷的基本方法有兩種：深度遍歷和廣度遍歷
d. 圖的遍歷是從給定的源點出發每個頂點僅被訪問一次
73、下列有關圖遍歷的說法中不正確的是（）。
a. 非連通圖不能用深度優先搜索法
b. 連通圖的深度優先搜索是一個遞歸過程
c. 圖的遍歷要求每一頂點僅被訪問一次
d. 圖的廣度優先搜索中鄰接點的尋找具有「先進先出」的特徵
74、下列哪種圖的鄰接矩陣為對稱矩陣? ( )
a. 帶權有向圖
b. 有向圖
c. 無向圖
d. 有向圖或無向圖
75、一個帶權的無向連通圖的最小生成樹（ ）。
a. 只有一棵
b. 一定有多棵
c. 有一棵或多棵
d. 可能不存在
76、順序表是線性表的（）
a. 鏈式存儲結構
b. 順序存儲結構
c. 索引存儲結構
d. 散列存儲結構
77、線性表若採用鏈式存儲結構時，要求內存中可用存儲單元的地址（）
a. 必須是連續的
b. 部分地址必須是連續的
c. 一定是不連續的
d. 連續或不連續都可以
78、一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（）
a. e,d,c,b,a
b. d,e,c,b,a
c. d,c,e,a,b
d. a,b,c,d,e
79、在下列鏈表中，不能從任一結點出發訪問到表中的所有結點的是（）
a. 單鏈表
b. 單向循環鏈表
c. 雙向循環鏈表
d. 循環鏈表
80、二叉樹結點度的集合為（）。
a. （1）
b. （0，1，2）
c. （1，2）
d. （0）
81、以二分查找方法查找一個線性表時，此線性表必須是（）。
a. 順序存儲的有序表
b. 鏈式存儲的有序表
c. 鏈表
d. 順序表
82、設哈夫曼樹的葉子結點的個數為n，那麼該樹的結點總數為（）
a.2n
b.2n+1
c.2n-1
c.不能唯一確定
83、對二叉樹來說，第i層上至多有（）個結點。
a. 2i
b. 2i-1
c. 2i-1
d. 2i-1-1
84、數據結構包括3個方面的內容，它們是（）。
a. 數據、數據元素、數據項
b. 數據元素、數據處理、演算法實現
c. 數據元素、數據的邏輯結構、數據的存儲結構
d. 數據的邏輯結構、數據的存儲結構、數據的操作
85、數據在計算機存儲器內表示時，存儲結點連續存放且存儲順序與邏輯順序相同，這種存儲方式稱為（）。
a. 索引存儲方式
b. 順序存儲方式
c. 鏈式存儲方式
d. 散列存儲方式
86、冒泡排序屬於（）。
a. 插入排序
b. 選擇排序
c. 快速排序
d. 交換排序
87、下列程序段的時間復雜度為（）。
i=1;j=0;
while（i+j<=n）
{if（i>j）j++;
elsei++;
}
a. O（n）
b. O（nlog2n）
c. O（i*j）
d. O（i+j）
88、下面程序的時間復雜為（）。
for（i=1,s=0;i<=n;i++）
{t=1;for（j=1;j<=i;j++）t=t*j;s=s+t;}
a. O（n）
b. O（n2）
c. O（n3）
d. O（n4）
89、含有n個結點的二叉樹採用二叉鏈表存儲時，空指針域的個數為（）。
a. n-1
b. n
c. n+1
d. n+2
90、設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。
a. n（n-1）/2
b. n（n-1）
c. n
d. n-1

1、調用一次深度優先遍歷可以訪問到圖中的所有頂點。（F）
2、分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（T）
3、冒泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。（T）
4、滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（T）
5、設一棵二叉樹的先序序列和後序序列，則能夠唯一確定出該二叉樹的形狀。（F）
6、線性表的順序存儲結構比鏈式存儲結構更好。（F）
7、不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮「溢出」情況。（T）
8、完全二叉樹中的葉子結點只可能在最後兩層中出現。（T）
9、由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（F）
10、線性表中的所有元素都有一個前驅元素和後繼元素。（F)

1、head指向單鏈表的表頭，p指向單鏈表的表尾結點，則執行p->next=head後，該單鏈表構成 循環鏈表
2、在單鏈表中，若p和s是兩個指針，且滿足p->next與s相同，則語句p->next=s->next的作用是 刪除 s指向的結點。
3、在一個長度為n的順序表中的第i(1≤i≤n＋1)個元素之前插入一個元素時，需向後移動的元素個數為 n-i+1 。
4、設順序線性表中有n個數據元素，則刪除表中第i個元素需向前移動 n-i 個元素。
5、衡量一個演算法，除了正確性之外，主要考慮的兩個方面是 時間復雜度 和 空間復雜度 。
6、在一個具有n個頂點的無向完全圖中，包含 n(n-1)/2 條邊。
7、對於一個具有n個頂點的圖，若採用鄰接矩陣表示，則矩陣大小為 n^2 。
8、採用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為 (n+1)/2 。
9、樹型結構最適合用來表示元素之間具有 分支層次關系 的數據。

1、已知一棵二叉樹的先（前）序遍歷序列為ABDEGCFH,中序遍歷序列為DBGEACFH,請畫出該二叉樹,並寫出該二叉樹的後序序列。

2、畫出一棵二叉樹,使其：中序序列為DCBGEAHFIJK,後序序列：DCEGBFHKJIA

3、請寫出對(53, 87, 12, 61,98,17, 97, 75, 53, 26)進行一次劃分的過程。

4、有一結點序列為(7,19,2,6,32,3,21,10),要求以該序列作為帶權二叉樹中結點的權值,構造並畫出一棵哈夫曼樹,並計算其帶權路徑長度。

5、對下面所示的無向網,要求構造出一棵最小生成樹（中間過程可以省略）,並計算該最小生成樹的權。

6、下面所示為有向圖的鄰接表,試畫出該有向圖,並給出由頂點V1開始的深度優先遍歷和廣度優先遍歷的結果。

7、有一結點序列為(45,24,53,12,28,90),要求構造並畫出一棵二叉排序樹,並輸出以中序方式遍歷該樹的序列。