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

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

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

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

4、; D. BCAD5、有向圖如圖1所示，由該圖得到的一個(gè)拓?fù)溆行蛐蛄袨開(kāi)。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是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有_個(gè)頂點(diǎn)。A. 8 B. 9 C. 10 D. 127、在下面算法中，_算法可能出現(xiàn)下列情況：在最后一趟開(kāi)始之前，所有的元素都不在其最終的位置上。A. 堆排序 B. 冒泡排序 C. 插入排序 D. 快

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

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

7、，72，11，25，57進(jìn)行快速排序過(guò)程的示意（即畫(huà)出每一趟排序后的關(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。請(qǐng)寫(xiě)出算法執(zhí)行完后棧S中從棧底至棧頂?shù)臄?shù)據(jù)元素序列。（2）簡(jiǎn)述該算法的功能。2、已知數(shù)組a中存放著兩組數(shù)據(jù)元素序列（a0，a1，am-1，b0，b1，bn-1）。下面算法利用原存儲(chǔ)空間將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ù)上述算法思想，請(qǐng)?jiān)诳杖碧幪钌线m當(dāng)?shù)恼Z(yǔ)句，以完善算法功能。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個(gè)元素就地逆置l_;m_;五、算法設(shè)計(jì)（每小題分，共分）下面兩題的數(shù)據(jù)類(lèi)型定義和函數(shù)首部均已給出，請(qǐng)按要求完成算法設(shè)計(jì)。編寫(xiě)算法，對(duì)一棵以孩子-兄弟鏈表表示的樹(shù)統(tǒng)計(jì)其葉子結(jié)點(diǎn)的個(gè)數(shù)。typedef struct TnodeTelemType data;/結(jié)點(diǎn)數(shù)據(jù)域struct Tnode *firstchild *nextsibling;/指向長(zhǎng)子和右兄弟的指針CSnode,*CStree;void leafcount(CStree T , int *count) / 統(tǒng)計(jì)以孩子兄弟鏈表存儲(chǔ)表示的樹(shù)T的葉子結(jié)點(diǎn)數(shù)目，結(jié)果存于count 所指單元 ，/ T為指向根結(jié)點(diǎn)的指針 /leafcout2、寫(xiě)出二分查找的遞歸算法。#define MaxL <表中最多記錄數(shù)>typedef struct KeyType key; / 主關(guān)鍵字域 OtherType otherinfo; / 其它數(shù)據(jù)域NodeType;ty