《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案

1、數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案(2003-2004 學(xué)年第 2 學(xué)期)單項(xiàng)選擇題 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C一、對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為（。、正確性(B). 可行性(C). 健壯性(D).輸入性設(shè)S為C語言的語,計(jì)算機(jī)執(zhí)行下面算法時(shí)算法的時(shí)間復(fù)雜度（ d。for(i=n-1；i=0；i-) for(j=0；jnext;p-next=Q.front-next;、p=Q.front-next;Q.front-next=p-next;、p=Q.rear-next; p-next= Q.rear-next;、p

2、=Q-next; Q-next=p-next;Huffman樹的帶權(quán)路徑長(zhǎng)度WPL等于（c）（A、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和（B、所有結(jié)點(diǎn)權(quán)值之和（C、各葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和（D、根結(jié)點(diǎn)的值線索二叉鏈表是利用（ c）域存儲(chǔ)后繼結(jié)點(diǎn)的地址。A、lchild（、data（C、rchild（Droot二、填空題邏輯結(jié)構(gòu)決定了算法的設(shè)計(jì)，而存儲(chǔ)結(jié)構(gòu)決定了算法的現(xiàn)。棧和隊(duì)列都是一種特殊的線性表，棧的插入和刪除只能在棧進(jìn)行。線性表,a,a）的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)每個(gè)單元的長(zhǎng)度為L(zhǎng)，元素a12ni的存儲(chǔ)地址LOC(a )為i已知一雙向鏈表如下(指針域名為nextprior)：xxyqpe現(xiàn) 將 p

3、所 指 的 結(jié) 點(diǎn) 插 入 到 x 和 y 結(jié) 點(diǎn) 之 間 ， 其 操 作 步 驟為：；5n 個(gè)結(jié)點(diǎn)無向完全圖的的邊數(shù)為n個(gè)結(jié)點(diǎn)的生成樹的邊數(shù)為已知一有向無環(huán)圖如下：BBFADGCE任意寫出二種拓?fù)渑判蛐蛄校?、?已知二叉樹的中序遍歷序列為后序遍歷序列為 則該二叉樹的先遍歷序列為，層序遍歷序列為。三、應(yīng)用題1 設(shè)散列函數(shù)H(k)=k % 13,設(shè)關(guān)鍵字系列為22,12,24,6,45,7,8,13,21,要求用線性探測(cè)法處理沖突。(6 分)構(gòu)造HASH分別求查找成功和不成功時(shí)的平均查找長(zhǎng)度。2 給定表（19,14,22,15,20,21,56,10）.（8 分）按元素在表中的次序，建立一棵二叉

4、排序樹對(duì)(1)中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列。畫出對(duì)(2)中的遍歷序列進(jìn)行折半查找過程的判定樹。已知二個(gè)稀疏矩陣ABABijVijV13-525224633725241342-152-9529558寫出 A-B 壓縮存儲(chǔ)的三元組表。（5 分）已知一維數(shù)組中的數(shù)據(jù)為, 試寫出插入排序（升序）程。并指出具有nA(8過程)ABCDEFA A 651B 653C 5 D 15776243636246F 求從頂點(diǎn)AA0.15B0.15C0.1D0.1EA0.15B0.15C0.1D0.1E0.2F0.3把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作(7 分，要有過程)。畫出對(duì)應(yīng)的Huf

5、fman計(jì)算帶權(quán)路徑長(zhǎng)度WPL。A、C、EFHuffman7 已知有如下的有向網(wǎng)：AA25B3E646D12求頂點(diǎn)A（采用Dijkstra（6）三、 設(shè)計(jì)題（30分，每題10分,用C語言寫出算法，做在答題上）已知線性表,a,a）以順序存儲(chǔ)結(jié)構(gòu)為存儲(chǔ)結(jié)構(gòu)，其類型定義如下：12n#defineLIST_INIT_SIZE100順序表初始分配容typedefstructElemtype*elem;/順序存儲(chǔ)空間基址intlength;當(dāng)前長(zhǎng)度（存儲(chǔ)元素個(gè)數(shù)）SqList;設(shè)計(jì)一個(gè)算法，刪除其元素值為x 的結(jié)點(diǎn)（假若x 是唯一的。并求出其算法的平均時(shí)間復(fù)雜度。其算法函數(shù)頭部如下： Status Lis

6、tDelete(Sqlist &L,Elemtype x)topana a12topana a12Elemtype*base;棧底指Elemtype*top;棧頂指Stack;設(shè)計(jì)算法，將棧頂元素出棧并存入e 中base設(shè)二叉鏈樹的類型定義如下：typedefinttypedefstructnodeElemtypedata;structnode*lchild, *rchild;BinNode, *BinTree;/n is the number of leaves答案：選擇題（每題 1 分）1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C一、填空題設(shè)計(jì)、實(shí)現(xiàn)特殊

7、、棧頂3LOC（a1）+(i-1)*L4p-next=q-next;q-next-prior=p; q-next=p;p-prior=q;5n(n-1)/2、n-1ADCBFEGABCDEFFGABC、ABC二、應(yīng)用題1 （1）Hash 表（4 分）地址0123456789101112關(guān)鍵安132164572282412探測(cè)次數(shù)1712313112）查找成功的平均查找長(zhǎng)度（1分）（5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找長(zhǎng)度1 分）（2+1+9+8+7+6+5+4+3+2+1）/13=2（、構(gòu)造3 分）191914221015205621(2)、10 14 15 19

8、 20 21 22 56（2 分）（3分）3、(5 0.5)ijv13-524633741342-152185584、 初始關(guān)鍵字：1812255318第一趟：1218255318第第一趟：1218255318第二趟：1218255318第三趟：1218255318第四趟：1218182553O（n（1 分 5、7 分（1）4 分AB1C325D 4EF（2）4 分6、(1) 3 分EEFABCD（2）WPL=0.1*3+0.1*3+0.2*25*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；10 （3 分）12A-AB）1 分 A-A、） 2

9、分 A-、）1分 A-A） 2 三，設(shè)計(jì)題（20 分）1、(10 分)StatusListDelete(Sqlist &L,ElemType x)int i,j;for(i=0;ilength;i+) if(L-elemi=x) if(i=L-length) return for(j=i;jlengthi-1;j+)L-elemj=L-elemj+1; L-length-;（8 分）2 分）設(shè)元素個(gè)數(shù)記為n，則平均時(shí)間復(fù)雜度為：E 2（10 分）1 nni1(n i) n 2void pop(Stack &S,Elemtype &e)if(S.top=S.base) return ERROR;

10、 S.top-;e=*s.top;2 （10 分 ） voidCountLeaves(BinTree T,int if(T)if(!(T-lchild)&!( T-rchild) n+; CountLeaves (T-lchild,n); CountLeaves (T-rchild,n);1D 數(shù)據(jù)結(jié)構(gòu)樣卷及答案第一部分 選擇題(30 分)一、 單項(xiàng)選擇題（本大題共 15 小題，每小題 2 分，共 30 分）在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1算法指的是（ D）計(jì)算機(jī)程序 B解決問題的計(jì)算方法C排序算法 D解決問題的有限運(yùn)算序列2線性表

11、采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址A必須是不連續(xù)的連續(xù)與否均可 C必須是連續(xù)的 D3將長(zhǎng)度為n 的單鏈表鏈接在長(zhǎng)度為m AO（1） BO（n） CO（m） DO（m+n） 4由兩個(gè)棧共享一個(gè)向量空間B ） A減少存取時(shí)間，降低下溢發(fā)生的機(jī)率B節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率C減少存取時(shí)間，降低上溢發(fā)生的機(jī)率D設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ 行出隊(duì)操作后其頭指針front值為（D ）Afront=front+1 Bfront=(front+1)%(m-1)Cfront=(front-1)%m Dfront=(front+1)%m ， ， 10 11如 下 陳 述 中 正 確 的 是 ） A串是一種

12、特殊的線性表 BCD空串就是空白串若目標(biāo)串的長(zhǎng)度為 nn/3時(shí)間復(fù)雜度是 ）AO（ ） BO（n） CO（n2） DO（n3） 8一個(gè)非空廣義表的表頭（ D） AB只能是子表C只能是原子 D可以是子表或原子9假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表0 2 3 3 5對(duì)應(yīng)的稀疏矩陣是（ ）103 3 2,2 1,0 數(shù)為( )A4 B5 C6 D7Ae B2e Cn2e Dn22e12 13 14 1512假設(shè)一個(gè)有n 個(gè)頂點(diǎn)和e ,vi ( )AO(n) BO(e) CO(n+e) DO(n*e) 13用某種排序方法對(duì)關(guān)鍵字序列進(jìn)行排序時(shí)， 序列的變化情況如下：20，15，21，25，

13、47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是（ ）A選擇排序 B希爾排序 C歸并排序 D快速排序14適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（ A有序表 B分塊有序表 C三叉排序樹 D線性鏈表15不定長(zhǎng)文件是指（ ）A文件的長(zhǎng)度不固定 B記錄的長(zhǎng)度不固定C字段的長(zhǎng)度不固定 D關(guān)鍵字項(xiàng)的長(zhǎng)度不固定第二部分 非選擇題（共 70 分）二、填空題（本大題共10 小題，每小題2 分，若有兩個(gè)空格，每個(gè)空格1 分，共20 分）寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯(cuò)填或不填均無分。 16存儲(chǔ)

14、（或存儲(chǔ)結(jié)構(gòu)） 17.pnextnext 18進(jìn)棧和退棧 1912 20a4,8 21384 22abefcdg快速排序、堆排序、希爾排序25.多關(guān)鍵字?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關(guān)，是獨(dú)立于計(jì)算機(jī)的。指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針headp 表示為head= 。在串S=structuret 9 階的上三角矩陣A 按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B B1 個(gè)元素a1,1,B?768 24在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字 72 時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為 。25多重表文件和倒排文件都?xì)w屬于 文件。三、解答題（4 5 20 分2

15、6畫出下列廣義表的共享結(jié)構(gòu)圖形表示請(qǐng)畫出與下列二叉樹對(duì)應(yīng)的森林。a, b, c, d, e , ab c d e(1)畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點(diǎn) a 出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。已知一個(gè)散列表如下圖所示：35 20 33 48 590 1 2 3 4 5 6 7 8 9 10 11 12其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為：hi=(h(key)+ *h1(key)%m =0,1,.，m1其中h1(key)=key%11+1 回答下列問題：35，20，33 48 進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？四、算法

16、閱讀題（4 5 20 分） 30下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為：S1=S1nexts2=s2nexts2(s2!=NULL s2&!s1)s1(s1!=NULL s1&!s2)return 0comstr(s1,s2)=請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。int comstr(LinkString s1,LinkString s2)/s1 和 s2 為兩個(gè)鏈串的頭指針while(s1&s2) if(s1datedate)return1； if(s1dates2date)return1； ； ；if( )return1； if( )return1；閱讀下面的算法LinkList mynot

17、e(LinkList/L if(L&L-next) q=L；L=Lnext；p=L；S1： while(pnext)p=pnext；S2： pnext=q；qnext=NULL；return L；請(qǐng)回答下列問題：說明語句S1的功能；說明語句組S2的功能；設(shè)鏈表表示的線性表為表。查詢鏈表的尾結(jié)點(diǎn)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)返回的線性表為（a2,a3,.,an,a1）假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見右下圖其類型Queue2定義如下：typedef structDateType dataMaxSize； int front ,rear ；Queue2；i=0 reari分別為第

18、i i 個(gè)隊(duì)列的入隊(duì)操作。int EnQueue (Queue2*Q,int i,DateType x)/若第 i 個(gè)隊(duì)列不滿，則元素x 入隊(duì)列，并返回 1；否則返回 0 if(i1)return 0；if(Qreari=Qfront return0； Qdata =x；Qreari= ; return1；(i1)%2(或 1i)(Qreari)%Maxsize 33typedef struct node DateType Struct node * ListNode；typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inor

19、der (BinTree T)LinkList s； If(T)Inorder(Tlchild)；If (!Tlchild)&(!Trchild) sdata=Tdata； snext=Leafhead；Leafhead=s；Inorder(Trchild)；對(duì)于如下所示的二叉樹畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；說明該算法的功能。 中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead 為頭指針的逆序單鏈（或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表五、算法設(shè)計(jì)題（10 分）34閱讀下列函數(shù)arrange()int arrange(int a&#;,int 1,int h,int x)/1 和 h 分別為數(shù)據(jù)區(qū)的下界和上界int i,j,t； i=1；j=h； while(ij)while(i