安徽大學(xué)2010—2011學(xué)年第2學(xué)期

《數(shù)據(jù)結(jié)構(gòu)》考試試卷（B卷）（閉卷時間120分鐘）一、填空題（每小題1.5分，共15分）一、填空題（每小題1.5分，共15分）得分題號一二三四五六七總分得分閱卷人含有36個元素的有序表，進行二分查找時的判定樹的深度為TOC\o"1-5"\h\z在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的2—倍。由帶權(quán)為9、2、5、7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為44由a,b,c三個結(jié)點構(gòu)成的二叉樹，共有5種不同形態(tài)。二維數(shù)組A[0??5][5??10]以行序為主序存儲，每個元素占4個存儲單元，且A[0][5]的業(yè)題專技答\o"CurrentDocument"存儲地址是1000，則A[3][9]的地址是1088若串s='soft，則其子串個數(shù)是11設(shè)循環(huán)隊列的空間大小為M，A隊時修改隊尾指針rear的語句為rear=（rear+1）%M在順序存儲結(jié)構(gòu)的線性表中，插入或刪除一個數(shù)據(jù)元素大約需移動表中一半元素。業(yè)題專技答下列程序段的時間復(fù)雜度是O（m*n）for（i=0;i<n;i++）for（j=0;j<m;j++）A[i][j]+=5;在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的邏輯結(jié)構(gòu)。二、單項選擇題（每小題2分，共20分）得分1.數(shù)據(jù)結(jié)構(gòu)可以用二元組來表示，它包括（二、單項選擇題（每小題2分，共20分）得分1.數(shù)據(jù)結(jié)構(gòu)可以用二元組來表示，它包括（A）集合D和定義在D上的（C）B、存儲結(jié)構(gòu)D、B、存儲結(jié)構(gòu)D、邏輯結(jié)構(gòu)A、數(shù)據(jù)元素C、元素之間的關(guān)系已知L是一個不帶頭結(jié)點的單鏈表，p指向其中的一個結(jié)點，選擇合適的語句實現(xiàn)在p結(jié)點的后面插入一個結(jié)點s的操作（B）。A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;s->next=p;D、s->next=p;p->next=s;假設(shè)以I和O分別表示入棧和出棧操作，棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列。則下列序列（A）是合法的。A、IOIIOIOOB、IOOIOIIOC、IIIOIOIOD、OIIOIOIO4、空串和空格串是（B）。A、相同的B、不相同的C、不能確定5、設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用6個字節(jié)，行下標(biāo)范圍從0到8,列下標(biāo)范圍從2到5，則二維數(shù)組W的數(shù)據(jù)元素共占用（C）個字節(jié)。A、480B、192C、216D、1446、假設(shè)在一棵二叉樹中，度為2的分支結(jié)點個數(shù)為15,度為1的分支結(jié)點個數(shù)為30，則該二叉樹的結(jié)點總數(shù)為（D）。A、45B、60C、46D、61對用鄰接矩陣表示的圖進行任一種遍歷時，其時間復(fù)雜度為（A）。A、O（n2）B、O（e）C、O（n）D、O（n+e）對線性表進行折半查找時，要求線性表必須（C）。A、以順序方式存儲B、以鏈接方式存儲C、以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列D、以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列9、設(shè)散列表長m=14，散列函數(shù)H（key）=key%11。表中已有4個結(jié)點：addr（15）=4、addr（38）=5、addr（61）=6、addr（84）=7，其余地址為空，如用二次探測再散列解決沖突，關(guān)鍵字為49的結(jié)點的散列地址是（D）。A、8B、3C、5D、9一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（B）。

A、79,46,56,38,40,80C、84,79,56,46,40,38B、84,79,A、79,46,56,38,40,80C、84,79,56,46,40,38B、84,79,56,38,40,46D、84,56,79,40,46,38堆排序、快速排序和希爾排序都是不穩(wěn)定的排序方法。(V二叉樹是度為2的有序樹。循環(huán)隊列是指用循環(huán)鏈表存儲的隊列。5.若入棧序列為abcd，則出棧序列不可能為cdab。6.在拓?fù)渑判蜻^程中，如果圖中已不存在無前驅(qū)的頂點了，而此時還有頂點沒有輸出，V說明圖中存在環(huán)。7.平衡二叉樹是指這樣的二叉樹：樹中任一結(jié)點的左右子樹深度都相同。(X裝超訂5.若入棧序列為abcd，則出棧序列不可能為cdab。6.在拓?fù)渑判蜻^程中，如果圖中已不存在無前驅(qū)的頂點了，而此時還有頂點沒有輸出，V說明圖中存在環(huán)。7.平衡二叉樹是指這樣的二叉樹：樹中任一結(jié)點的左右子樹深度都相同。(X裝超訂勿題:8.在任何情況下，快速排序都是最快的。(X)則)))四、簡答題(每小題10分，共40分)1.已知二叉樹如圖1所示，要求:得分(1)將其轉(zhuǎn)換為樹，并畫出該樹;(2)裝圖1分別寫出對(1)所得到的樹進行先根遍歷和后根遍歷得到的結(jié)點序列。(2)裝圖12.對如圖2所示的連通圖，試分別用普里姆(Prim)算法和克魯斯卡爾(Kruskar)算法構(gòu)造其最小生成樹，并給出其構(gòu)造過程。

33.假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,36,18,70)，散列地址空間為HT[0~12]，若采用除留余數(shù)法構(gòu)造散列函數(shù)H(key)=key%13和線性探測法處理沖突，試求出每個元素的散列地址，畫出最后得到的散列表，并求出平均查找長度。3散列地址為:H(32)=32%13=6H(63)=63%13=11H(94)=94%13=3(沖突)H(75)=75%13=10H(48)=48%13=9H1=(3+1)%13=4H(29)=29%13=3

H(25)=25%13=12H(36)=36%13=10(沖突)H(32)=32%13=6H(63)=63%13=11H(94)=94%13=3(沖突)H(75)=75%13=10H(48)=48%13=9H1=(3+1)%13=4H(29)=29%13=3H(18)=18%13=5H(70)=70%13=5(沖突)H1=(5+1)%13=6(沖突)H2=(5+2)%13=7散列表為:012345678910111236299418327048756325我:ASL=(7*1+1*2+1*3+1*4)/10=16/10=1.6得分4.對一組記錄(50,40,95,20,15,70,4.對一組記錄(50,40,95,20,初始序列：504095201570604580第一趟結(jié)束后：{45401520}50{70609580}第二趟結(jié)束后：{204015}4550{60}70{9580}第三趟結(jié)束后：{15}20{40}4550607080{95}第四趟結(jié)束后：152040455060708095排序結(jié)束時的序列。五、算法閱讀題（第1小題4分，第2小題3分，共7分）1、畫出執(zhí)行下列程序段后得到的鏈表示意圖。L=(LinkList)malloc(sizeof(LNode);P=L;for(k=1;k<=4;k++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=2*k-1;P->next=NULL;2、已知q是指向中序線索二叉樹上某個結(jié)點的指針，請閱讀下面函數(shù)，說明其功能。BiTr