08_09(2)數(shù)據(jù)結(jié)構(gòu)試卷A

1、精選文檔一、填空題（每空1分，共18分）1、算法的5個重要特性是_、_、_、輸入和輸出。2、單鏈表中，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由_指示。3、在雙向鏈表中，欲在p所指結(jié)點之前插入一個由s指向的結(jié)點，請完成有關(guān)操作。 s->prior=p->prior; p->prior=s; _； s->next=p;4、對于棧只能在_插入和刪除元素；對于隊列只能在_插入元素和_刪除元素。5、在模式匹配的KMP算法中用到了一個next函數(shù)，若nextj=k，則說明在模式串T中存在一個與“T1T2.Tk-1”相等的子串“_”。6、在對N個元素進(jìn)行冒泡排序時，最少的比較次數(shù)

2、是_。7、假設(shè)有二維數(shù)組A6Í8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A共占用_個字節(jié)的存儲單元，按行存儲時，元素A25的第一個字節(jié)的地址為_。8、若以4，5，6，7，8 作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度為_。9、采用分塊查找時，若表中共有256個元素，查找每個元素的概率相同，假設(shè)采用順序查找來確定結(jié)點所在的塊時，每塊應(yīng)分_個結(jié)點為最佳。10、廣義表g=( ()的表頭是_，表尾是_。11、假定對長度為300 的有序表進(jìn)行折半查找，則對應(yīng)的判定樹的高度為_，最后一層的結(jié)點數(shù)為_。二、單項選擇題（每空1分，共10

3、分）1、線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種j_的存儲結(jié)構(gòu)，線性結(jié)構(gòu)的鏈?zhǔn)酱鎯κ且环Nk_的存儲結(jié)構(gòu)。A. 隨機存取 B. 順序存取 C. 索引存取 D. 散列存取2、執(zhí)行下面程序段時，S 語句的執(zhí)行次數(shù)為_。 for (int i=1;i<=n-1;i+) for (int j=i+1;j<=n;j+) S;A. B. C. D. 3、將兩個各有N個元素的有序表歸并為一個有序表，其最少的比較次數(shù)是_。A. N; B. 2N-1; C. 2N; D. N-14、已知4個元素進(jìn)棧的順序依次為A,B,C,D，則下面哪一個出棧序列是不可能得到的_。A. ABCD; B. CBAD; C. CADB

4、; D. BCAD5、有向圖如圖1所示，由該圖得到的一個拓?fù)溆行蛐蛄袨開。V1V2V3V4V5V6圖1A. V1 , V4 , V6 , V2 , V5 , V3 B. V1 , V2 , V3 , V4 , V5 , V6 C. V1 , V4 , V2 , V3 , V6 , V5 D. V1 , V2 , V4 , V6 , V3 , V56、G是一個非連通無向圖，共有28條邊，則該圖至少有_個頂點。A. 8 B. 9 C. 10 D. 127、在下面算法中，_算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。A. 堆排序 B. 冒泡排序 C. 插入排序 D. 快

5、速排序8、與其它查找方法相比，散列查找法的特點是_。A. 通過關(guān)鍵字的比較進(jìn)行查找B. 通過關(guān)鍵字計算元素的存儲地址進(jìn)行查找C. 通過關(guān)鍵字計算元素的存儲地址并進(jìn)行一定的比較進(jìn)行查找D. 以上都不是9、某二叉樹的層序序列是abcdefgh，中序序列是dbgehacf，則該樹的后序序列是_。A . fahgbec B. eagbfdc C. dghebfca D. acdbfge三、應(yīng)用題（每小題9分，共36分）1對圖2所示的二叉樹，要求FHGEAICDB圖2（1）將其轉(zhuǎn)換為樹或森林，畫出轉(zhuǎn)換后的結(jié)果。（2）給出對該樹或森林分別進(jìn)行先根遍歷和后根遍歷得到的結(jié)點序列。2無向圖如圖3所示，畫出從頂點

6、A出發(fā)用普里姆（prim）算法構(gòu)造最小生成樹的過程，并給出一個從頂點A出發(fā)的深度優(yōu)先搜索序列。435AECDFBG216135圖33使用哈希函數(shù)H(key)=key % 11，把一個整數(shù)值轉(zhuǎn)換成哈希表下標(biāo)，現(xiàn)要把數(shù)據(jù)1、13、12、34、38、33、27、22插入到哈希表（表1）中。（1）使用線性探測再散列法構(gòu)造哈希表，請在表1所示的哈希表中與哈希地址對應(yīng)的位置上，填寫出相應(yīng)的關(guān)鍵字值和元素插入時的探查次數(shù)。（2）假設(shè)查找每個元素的概率相同，求出查找成功時的平均查找長度。表1哈希地址012345678910關(guān)鍵字值探查次數(shù)4、試說明快速排序的基本思想，并給出對關(guān)鍵字序列 47，33，61，82

7、，72，11，25，57進(jìn)行快速排序過程的示意（即畫出每一趟排序后的關(guān)鍵字序列）。四、算法閱讀題（每小題8分，共16分）1、閱讀下面算法，按要求作答，其中Push(S, d)表示將數(shù)據(jù)元素d壓入棧S中，Pop(T,d)表示T的棧頂元素出棧并存入d中。int algo (Stack S , int e) int d; Stack T; InitStack(T); while(!StackEmpty(S) Pop(S,d); if(d!=e) Push(T, d); /while while(!StackEmpty(T) Pop(T, d);Push(S, d);（1）假設(shè)棧S中的原始數(shù)據(jù)從棧底至

8、棧頂依次為：3，5，7，12，5，6，8；e的值為5。請寫出算法執(zhí)行完后棧S中從棧底至棧頂?shù)臄?shù)據(jù)元素序列。（2）簡述該算法的功能。2、已知數(shù)組a中存放著兩組數(shù)據(jù)元素序列（a0，a1，am-1，b0，b1，bn-1）。下面算法利用原存儲空間將a中的數(shù)據(jù)元素序列就地互換為（b0，b1，bn-1，a0，a1，am-1），算法思想可以描述為：（1）把數(shù)組a中的數(shù)據(jù)元素序列（a0，a1，am-1，b0，b1，bn-1）就地逆置為（bn-1，b1，b0，am-1，a1，a0）。（2）把數(shù)組a中的數(shù)據(jù)元素序列（bn-1，b1，b0，am-1，a1，a0）就地逆置為（b0，b1， bn-1，am-1，a1，a

9、0）。(3) 把數(shù)組a中的數(shù)據(jù)元素序列（b0，b1， bn-1，am-1，a1，a0）就地逆置為（b0，b1，.， bn-1，a0，a1.，am-1）。根據(jù)上述算法思想，請在空缺處填上適當(dāng)?shù)恼Z句，以完善算法功能。void converse (ElemType a,int low,int high) /將數(shù)組a中自下標(biāo)low 至high的一段數(shù)據(jù)元素逆置int n,i;ElemType x;n= (high-low+1)/2; / n 為循環(huán)次數(shù)for(i=0;i<n;i+) x=alow+i; j_; k_;void exchange (ElemType a,int m,int n) c

10、onverse(a,0,m+n-1);/將數(shù)組a中的m+n個元素就地逆置l_;m_;五、算法設(shè)計（每小題分，共分）下面兩題的數(shù)據(jù)類型定義和函數(shù)首部均已給出，請按要求完成算法設(shè)計。編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉子結(jié)點的個數(shù)。typedef struct TnodeTelemType data;/結(jié)點數(shù)據(jù)域struct Tnode *firstchild *nextsibling;/指向長子和右兄弟的指針CSnode,*CStree;void leafcount(CStree T , int *count) / 統(tǒng)計以孩子兄弟鏈表存儲表示的樹T的葉子結(jié)點數(shù)目，結(jié)果存于count 所指單元 ，/ T為指向根結(jié)點的指針 /leafcout2、寫出二分查找的遞歸算法。#define MaxL <表中最多記錄數(shù)>typedef struct KeyType key; / 主關(guān)鍵字域 OtherType otherinfo; / 其它數(shù)據(jù)域NodeType;ty