2、向進行插入和刪除的操作B.便于雙向進行插入和刪除的操作C.節(jié)省空間D.便于銷毀結(jié)構(gòu)釋放空間5.設(shè)鏈式棧中結(jié)點的結(jié)構(gòu)為（data,link），且top是指向棧頂?shù)闹羔?。若想在鏈式棧的棧頂插入一個由指針s所指的結(jié)點，則應(yīng)執(zhí)行()操作。A.top->link=s;B.s->link=top->link;top->link=s;C.s->link=top;top=s;D.s->link=top;top=top->link;6.設(shè)有一個遞歸算法如下intX(intn){if(n<=3)return1;elsereturnX(n-2)+X(n-4)+1;}
3、試問計算X(X(5))時需要調(diào)用（）次X函數(shù)。A．2B．3C．4D．57.一棵具有35個結(jié)點的完全二叉樹的高度為()。假定空樹的高度為-1。A.5B.6C.7D.88.向具有n個結(jié)點的堆中插入一個新元素的時間復(fù)雜度為()。A.O(1)B.O(n)C.O(log2n)D.O(nlog2n)9.在一棵AVL樹中，每個結(jié)點的平衡因子的取值范圍是()。A.-1~1B.-2~2C.1~2D.0~110.一個有n個頂點和n條邊的無向圖一定是()。A．連通的B．不連通的C．無環(huán)的D．有環(huán)的11.在用Kruskal算法求解帶權(quán)連通圖的最小（代價）生成樹時，通常
4、采用一個（）輔助結(jié)構(gòu)，判斷一條邊的兩個端點是否在同一個連通分量上。A.位向量B.堆C.并查集D.生成樹頂點集合12.設(shè)有一個含有200個元素的表待散列存儲，用線性探查法解決沖突，按關(guān)鍵碼查詢時找到一個元素的平均探查次數(shù)不能超過1.5，則散列表的長度應(yīng)至少為（）。（注：平均探查次數(shù)的計算公式為Snl={1+1/(1-α)}/2,其中α為裝填因子）A.400B.526C.624D.676二、填空題，在橫線處填寫合適內(nèi)容（每小題1分，共12分）1.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)和________結(jié)構(gòu)兩大類。2.在程序運行過程中不能擴充的數(shù)組是____
5、______分配的數(shù)組。這種數(shù)組在聲明它時必須指定它的大小。3.鏈表只適用于查找。4.設(shè)雙向循環(huán)鏈表中每個結(jié)點的結(jié)構(gòu)為(data,llink,rlink),則結(jié)點*p的前驅(qū)結(jié)點的地址為__________。5.在一個鏈式隊列中，若隊頭指針與隊尾指針的值相同，則表示該隊列至多有________個結(jié)點。6.一棵樹的廣義表表示為a(b(c,d(e,f),g(h)),i(j,k(x,y)))，結(jié)點k的所有祖先的結(jié)點數(shù)為________個。7.若將一棵樹A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法轉(zhuǎn)換為二叉樹，該二叉樹中度為2的結(jié)點
6、的個數(shù)為________個。8.從一棵二叉搜索樹中搜索一個元素時，若給定值大于根結(jié)點的值，則需要向________繼續(xù)搜索。9.設(shè)圖G=(V,E)，其中則從頂點V0開始對圖G的深度優(yōu)先序列總共有________種。10.第i(i=0,1,...,n-2)趟從參加排序的序列中第i個至第n-1個元素中挑選出一個最小元素，把它交換到第i個位置，此種排序方法叫做_____________排序。11.快速排序在最壞情況下的時間復(fù)雜度為____________。12.假定對長度n=100的線性表進行索引順序搜索，并假定每個子表的長度均為n，則進行索引順序搜
7、索的平均搜索長度為________。三、判斷題，在每小題前面打?qū)μ柋硎菊_或打叉號表示錯誤（每小題1分，共10分）1.算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時二者是通用的。2.插入與刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，因此這兩種操作在數(shù)組中也經(jīng)常被使用。3.棧和隊列都是順序存取的線性表,但它們對存取位置的限制不同。4.將f=1+1/2+1/3+…+1/n轉(zhuǎn)化為遞歸函數(shù)時，遞歸部分為f(n)=f(n-1)+1/n，遞歸結(jié)束條件為f(1)=1。5.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進行前序遍歷和中根遍歷，則具有相同的結(jié)
8、果。6.進行折半搜索的表必須是順序存儲的有序表。7.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點個數(shù)有關(guān)，而與
