評論
打印
① 字符串’ababaabab’的nextval為
A．（0，1，0，1，0，4，1，0，1） B.（0，1，0，1，0，2，1，0，1，）
C．（0，1，0，1，0，0，0，1，1，） D.（0，1，0，1，0，1，0，1，1）
②廣義表A=（a,b,(c,d),(e,(f,g))）,則下面式子的值為 ；
Head(Tail(Head(Tail(Tail(A)))))
A．（g）B.(d)C.cD.d
③ 輸入序列為（A，B，C，D），不可能得到的輸出序列有 ；
A．（A，B，C，D） B．（D，C，B，A） C．（A，C，D，B） D．（C，A，B，D）
④ 散列函數有一個共同性質，即函數值應按 取其值域的每一個值；
A.最大概率 B.最小概率 C.同等概率 D.平均概率
⑤ 直接插入排序在最好情況下的時間復雜度為。
A. O(logn) B. O(n)C. O(n*logn)D(n2)
2.（10分）判斷下列敘述是否正確
①（101，88，46，70，34，39，45，58，66，10）是堆；
② 將一棵樹轉換成二叉樹后，根結點沒有左子樹；
③ 用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷；
④ 即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同；
⑤ 哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離很較近。
3 （10分）
有一高個比他人都至少高出一頭，找他的人都說“根本不用與別人比較，一眼就能找到他”，你認為此話正確嗎？為什么？請簡要描述兩種求N個數中最大值的方法，并給出所需的最少比較次數。
4 （10分）
圖1是用鄰接表存儲的圖，畫出此圖，并寫出從C點開始按深度優先遍歷該圖的結果。圖1 題4圖
5（10分）
下面是求無向連通圖的最小代價生成 樹的一種算法：
將圖中所有邊按權重從大到小排序為(e1,e2,…,em)
i:=1;
While (所剩邊數≥頂點數)
Begin
從圖中刪去ei
若圖不再連通，則恢復ei
i:=i+1
End
試證明這個算法所得的圖是原圖的最小代價生成樹。
6 （10分）
已知無向圖G和G’互為補圖（結點相同、邊不重疊、兩圖合起來為完全圖），試證明G或G’是連通的。
7 （10分）
用序列（46，88，45，39，70，58，101，10，66，34）建立一個排序二叉樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度。
8 （10分）
寫出下面程序段的運行結果。
Program Ex(Input, Output);
type
Ttt=Array[1..20] OF Integer;
Var
I,J,K,L,N:Integer;
A:Ttt;
Function P (Var A:Ttt; Var M,N:Integer):Integer;
var
X,Y,Z:Integer;
Begin
If N=1 Then
Begin
m:=1;
p:=a[1]
End Else
Begin
X:=N;
N:=N-1;
Y:=P(A,Z,N);
N:=X;
If A[N]>=Y Then
Begin
M:=N;
P:=A[N]
End Else
Begin
M:=Z;
P:=Y
End
End
End;
Begin
Readln(N);
For I:=1 To N Do Read(A[I]);
Readln;
L:=N;
For I:=1 To L Do
Begin
K=P9A,J,N);
A[J]:=A[N];
A[N]:=K;
N:=N-1
End;
For I;=1 To L Do Write(A[I]:3);
Writeln;
End;
輸入數據為：
8
6 1 8 4 3 5 2 7
9 （10分）
已知二叉樹用下面的順序結構存儲，寫出中序遍歷該二叉樹的算法。Type
Array [1..maxn] of
Record
Data:Char;//存結點值
Lc,Rc:Integer //左、右孩子下標，0表示無左、右孩子
如樹T=A（B（D，E），C（#，F（H，I）））存儲如表1所示：
表1 樹T的存儲
1 2 3 4 5 6 7 8 9
A B C D E F G H I
2 4 0 0 0 8 0 0 0
3 5 6 0 7 9 0 0 0
10 （10分）
試寫出以帶頭結點單鏈表為存儲結構實現簡單選擇排序的算法。
