B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要一致

C．每個數(shù)據(jù)元素都一樣

D．數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等

答案：B

（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動? 的元素個數(shù)為（?? ）。

A．8 ?????B．63.5 ???????C．63????? D．7

答案：B

(13) 在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應為（?? ）。

A．s->next=p+1; p->next=s;

B．(*p).next=s; (*s).next=(*p).next;

C．s->next=p->next; p->next=s->next;

D．s->next=p->next; p->next=s;?

答案：D

?(14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（?? ）。

A．p->next->prior=p->prior; p->prior->next=p->next;

B．p->next=p->next->next; p->next->prior=p;

C．p->prior->next=p; p->prior=p->prior->prior;

D．p->prior=p->next->next; p->next=p->prior->prior;

答案：A

（10）設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（?。?shù)據(jù)結(jié)構(gòu)最佳。

A．線性表的順序存儲結(jié)構(gòu)??? ??????????B．隊列????

C. 線性表的鏈式存儲結(jié)構(gòu)?? ???????????D. 棧

答案：D

（2）在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（?? ）倍。

? A．1/2??????????? B．1???????????? C．2???????????? D．4

答案：B

G是一個連通無向圖，共有21條邊，則該圖至少有__個頂點

因為在頂點數(shù)目相同的無向圖中，完全圖的邊數(shù)最多，達到n(n-1)/2。那么，當n=7時，邊數(shù)達到21。也就是說，7個頂點，最多有21條邊。因此推論出，21條邊，最少有7個頂點。

（6）若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有的頂點，則該圖一定是（?? ）圖。

A．非連通 ????????B．連通?? ???????C．強連通? ??????D．有向

答案：B

（10）深度優(yōu)先遍歷類似于二叉樹的（?? ）。

A．先序遍歷 ?????B．中序遍歷 ???????C．后序遍歷? ????D．層次遍歷

答案：A

（11）廣度優(yōu)先遍歷類似于二叉樹的（?? ）。

A．先序遍歷 ?????B．中序遍歷 ???????C．后序遍歷? ?????D．層次遍歷

答案：D

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（?? ）比較大小，查找結(jié)果是失敗。

A．20，70，30，50??????????????????? B．30，88，70，50

C．20，50 ???????????????????????????D．30，88，50

答案：A

（5）對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（?? ）次關鍵字。

A．3??? ????????B．4 ?????????C．5???? ??????D．6

答案：B

（1）從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（?? ）。

A．歸并排序?????? B．冒泡排序????? ??C．插入排序 ???????D．選擇排序

答案：C

2）從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（?? ）。

A．歸并排序?????? B．冒泡排序??????? C．插入排序??????? D．選擇排序

答案：D

（4）對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)最多為（?? ）。

A．n+1??? ????????B．n?????? ????????C．n-1 ?????????????D．n(n-1)/2

答案：D

15 i=1;

? ???while(i<=n)

??????? i=i*3;

答案：O(log3n)

解釋：語句i=i*3;的執(zhí)行次數(shù)為??log3n?。

7，關鍵字序列為{}。

?

①直接插入排序

[2? ? 12]? ?16? ?30? ?28? ?10? ?16*? ?20? ?6? ? 18? ? ? ??

[2? ? 12? ? 16]? 30? ?28? ?10? ?16*? ?20? ?6? ? 18? ? ? ??

[2? ? 12? ? 16? ?30]? 28? ?10? ?16*? ?20? ?6? ? 18? ? ? ??

[2? ? 12? ? 16? ?28? ?30]? 10? ?16*? ?20? ?6? ? 18? ? ? ??

[2? ? 10? ? 12? ?16? ?28? 30]? ?16*? ?20? ?6? ? 18? ? ? ??

[2? ? 10? ? 12? ?16? ?16*? 28? ?30]? ?20? ?6? ? 18? ? ? ??

[2? ? 10? ? 12? ?16? ?16*? 20? ?28? ?30]? ?6? ? 18? ? ? ??

[2? ? 6? ? ?10? ?12? ?16? 16*? ?20? ?28? ?30]? ?18? ? ? ??

[2? ? 6? ? ?10? ?12? ?16? 16*? ? 18? ?20? ?28? ?30]

?

② 折半插入排序 排序過程同①

?

③ 希爾排序（增量選取5，3，1）

10? ?2? ? 16? ?6? ? 18? ?12? ?16*? ?20? 30? ? 28 （增量選取5）

6? ? 2? ? 12? ?10? ?18? ?16? ?16*? ?20? 30? ? 28 （增量選取3）

2? ? 6? ? 10? ?12? ?16? ?16*? 18? ? ? 20? 28? ? 30 （增量選取1）

?

④ 冒泡排序

2? ? 12? ?16? ? 28? ?10? ?16*? 20? ?6? ? ?18? ?[30]? ? ? ?

2? ? 12? ?16? ? 10? ?16*? 20? ?6? ? 18? ? [28? ?30]? ? ? ?

2? ? 12? ?10? ? 16? ?16*? 6? ? ?18? ?[20? ?28? ?30]? ? ? ? ?

2? ? 10? ?12? ? 16? ?6? ?16*? ? [18? ?20? ?28? ?30]? ? ? ? ?

2? ? 10? ?12? ? 6? ?16? ?[16*? ? 18? ?20? ?28? ?30]? ? ? ??

2? ? 10? ?6? ? 12? ?[16? ?16*? ? 18? ?20? ?28? ?30]? ? ? ?

2? ? 6? ?10? ? [12? ?16? ?16*? ? 18? ?20? ?28? ?30]

2? ? 6? ?10? ? 12? ?16? ?16*? ? 18? ?20? ?28? ?30]? ? ??

?

⑤ 快速排序

12? [6? ? 2? 10]? 12? [28? 30? 16*? 20? ?16? 18]? ? ? ? ?

6? ?[2]? 6? ?[10]? 12? [28? 30? 16*? 20? ?16? 18 ]? ? ? ??

28? 2? ? 6? ?10? ?12? [18? 16? 16*? 20 ] 28? [30 ]? ? ??

18? 2? ?6? ?10? 12? ?[16*? 16]? 18? [20]? 28? 30? ? ? ? ?

16*? ? ?2? ?6? ?10? 12? ?16* [16]? ?18? 20? ?28? 30

左子序列遞歸深度為1，右子序列遞歸深度為3

?

⑥ 簡單選擇排序

2? ? [12? ?16? ?30? ?28? ?10? ?16*? ?20? ?6? ? 18]? ? ? ? ?

2? ? 6? ? [16? ?30? ?28? ?10? ?16*? ?20? ?12? ?18]? ? ? ? ?

2? ? 6? ? 10? ?[30? ?28? ?16? ?16*? ?20? ?12? ?18]? ? ? ? ?

2? ? 6? ? 10? ?12? ?[28? ?16? ?16*? ?20? ?30? ?18]? ? ? ? ?

2? ? 6? ? 10? ?12? ?16? ?[28? ?16*? ?20? ?30? ?18]? ? ? ? ?

2? ? 6? ? 10? ?12? ?16? ?16*? ? [28? 20? ?30? ?18]? ? ? ? ?

2? ? 6? ? 10? ?12? ?16? ?16*? ?18? ?[20? ?30? ?28]? ? ? ??

2? ? 6? ? 10? ?12? ?16? ?16*? ?18? ? 20? ?[28? 30]? ? ? ??

2? ? 6? ? 10? ?12? ?16? ?16*? ? 18? ?20? ?28? ?[30]

?

?

⑧ 二路歸并排序

2 12? ? 16 30? ? 10 28? ? 16 * 20? ? 6 18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

2 12 16 30? ? ? ? 10 16* 20 28? ? ? ?6 18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

2 10 12 16 16* 20 28 30? ?6 18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

2 6 10 12 16 16* 18 20 28 30?