10月-1月自考2331數(shù)據(jù)結構歷年試題和答案

PAGE1/3全國2012年10月高等教育自學考試數(shù)據(jù)結構試題課程代碼：02331請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項：1.答題前，考生務必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。2.每小題選出答案后，用2B鉛筆把答題紙上對應題目的答案標號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標號。不能答在試題卷上。一、單項選擇題(本大題共l5小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應代碼涂黑。錯涂、多涂或未涂均無分。1．一個算法的時間耗費的數(shù)量級稱為該算法的A．效率 B．難度C．可實現(xiàn)性 D．時間復雜度2．順序表便于A．插入結點 B．刪除結點C．按值查找結點 D．按序號查找結點3．設帶頭結點的單循環(huán)鏈表的頭指針為head，指針變量P指向尾結點的條件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．設以數(shù)組A[0..m-1]存放循環(huán)隊列，front指向隊頭元素，rear指向隊尾元素的下一個位置，則當前隊列中的元素個數(shù)為A．(rear-front+m)％m B．rear-front+1C．(front-rear+m)％m D．(rear-front)％m5．下列關于順序棧的敘述中，正確的是A．入棧操作需要判斷棧滿，出棧操作需要判斷?？誃．入棧操作不需要判斷棧滿，出棧操作需要判斷棧空C．入棧操作需要判斷棧滿，出棧操作不需要判斷?？誅．入棧操作不需要判斷棧滿，出棧操作不需要判斷?？?．A是一個10×10的對稱矩陣，若采用行優(yōu)先的下三角壓縮存儲，第一個元素a0,0的存儲地址為1，每個元素占一個存儲單元，則a7,5的地址為A．25 B．26C．33 D．347．樹的后序遍歷等價于該樹對應二叉樹的A．層次遍歷 B．前序遍歷C．中序遍歷 D．后序遍歷8．使用二叉線索樹的目的是便于A．二叉樹中結點的插入與刪除 B．在二叉樹中查找雙親C．確定二叉樹的高度 D．查找一個結點的前趨和后繼9．設無向圖的頂點個數(shù)為n，則該圖邊的數(shù)目最多為A．n-l B．n(n-1)／2C．n(n+1)／2 D．n210．可進行拓撲排序的圖只能是A．有向圖 B．無向圖C．有向無環(huán)圖 D．無向連通圖11．下列排序方法中穩(wěn)定的是A．直接插入排序 B．直接選擇排序C．堆排序 D．快速排序12．下列序列不為堆的是A．75,45,65,30,15,25 B．75,65,45,30,25,15C．75,65,30,l5,25,45 D．75,45,65,25,30,1513．對線性表進行二分查找時，要求線性表必須是A．順序存儲 B．鏈式存儲C．順序存儲且按關鍵字有序 D．鏈式存儲且按關鍵字有序14．分別用以下序列生成二叉排序樹，其中三個序列生成的二叉排序樹是相同的，不同的序列是A．(4,1,2,3,5) B．(4,2,3,l,5)C．(4,5,2,1,3) D．(4,2,1,5,3)15．下列關于m階B樹的敘述中，錯誤的是A．每個結點至多有m個關鍵字B．每個結點至多有m棵子樹C．插入關鍵字時，通過結點分裂使樹高增加D．刪除關鍵字時通過結點合并使樹高降低非選擇題部分注意事項：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題(本大題共10小題，每小題2分，共20分)16．數(shù)據(jù)元素之間的邏輯關系稱為數(shù)據(jù)的______結構。17．在線性表中，表的長度定義為______。18．用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1、2、3、4，為了得到1、3、4、2的出棧順序，相應的S和X的操作序列為______。19．在二叉樹中，帶權路徑長度最短的樹稱為______。20．已知廣義表G，head(G)與tail(G)的深度分別為4和6，則G的深度是______。21．一組字符(a,b,c,d)在文中出現(xiàn)的次數(shù)分別為(7，6，3，5)，字符＇d＇的哈夫曼編碼的長度為______。22．在一個具有n個頂點的無向圖中，要連通全部頂點至少需要______條邊。23．直接選擇排序算法的時間復雜度是______。24．對于長度為81的表，若采用分塊查找，每塊的最佳長度為______。25．用二叉鏈表保存有n個結點的二叉樹，則結點中有______個空指針域。三、解答題(本大題共4小題，每小題5分，共20分)26．假設Q是一個具有11個元素存儲空間的循環(huán)隊列(隊尾指針指向隊尾元素的下一個位置，隊頭指針指向隊頭元素)，初始狀態(tài)Q.front=Q.rear=0；寫出依次執(zhí)行下列操作后頭、尾指針的當前值。a,b,c,d,e,f入隊，a,b,c,d出隊；(1)Q.front=______；Q.rear=______。g,h,i,j,k,l入隊，e,f,g,h出隊；(2)Q.front=______；Q.rear=______。M,n,o,P入隊，i,j,k,l,m出隊；(3)Q.front=______；Q.rear=______。27．已知一個無向圖如題27圖所示，以①為起點，用普里姆(Prim)算法求其最小生成樹，畫出最小生成樹的構造過程。28．用歸并排序法對序列(98,36,-9,0,47,23,1,8)進行排序，問：(1)一共需要幾趟歸并可完成排序。(2)寫出第一趟歸并后數(shù)據(jù)的排列次序。29．一組記錄關鍵字(55,76,44,32,64,82,20,16,43)，用散列函數(shù)H(key)=key％11將記錄散列到散列表HT[0..12]中去，用線性探測法解決沖突。(1)畫出存入所有記錄后的散列表。(2)求在等概率情況下，查找成功的平均查找長度。四、算法閱讀題(本大題共4小題，每小題5分，共20分)30．順序表類型定義如下：#defineListSize100typedefstruct{intdata[ListSize]；intlength；}SeqList；閱讀下列算法，并回答問題：voidf30(SeqList*L){inti,j；i=0；while(i<L->length)if(L->data[i]％2!=0){for(j=i+1;j<L->length;j++}L->data[j-1]=L->data[j];L->length--;}elsei++}（1）若L->data中的數(shù)據(jù)為（22,4,63,0,15,29,34,42,3）,則執(zhí)行上述算法后L->data中的數(shù)據(jù)以及L->length的值各是什么？（2）該算法的功能是什么？31.有向圖的鄰接矩陣類型定義如下：#defineMVN100∥最大頂點數(shù)typedefintEType;∥邊上權值類型typedefstruct{ETypeedges[MVN][MVN];∥鄰接矩陣，即邊表intn;∥圖的頂點數(shù)｝MGraph;∥圖類型例如，一個有向圖的鄰接矩陣如下所示：閱讀下列算法，并回答問題：Voidf31(MGraphG){Inti,j,k=0;Step1:for(i=0;i<G.n;i++)for(j=0;j<G.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k);step2:for(j=0;j<G.n;j++){k=0;for(i=0;i<G.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k);}}(1)stepl到step2之間的二重循環(huán)語句的功能是什么?(2)step2之后的二重循環(huán)語句的功能是什么?32．閱讀下列算法，并回答問題：voidf32(intr[]，intn){Inti，j；for(i=2；i<n；i++){r[0]=r[i]；j=i-l；while(r[0]<r[j]){r[j+l]=r[j]；j=j-1；}r[j+l]=r[0]；}}(1)這是哪一種插入排序算法?該算法是否穩(wěn)定?(2)設置r[0]的作用是什么?33．順序表類型定義如下：typedefintSeqList[100]；閱讀下列算法，并回答問題：voidf33(SeqListr，intn){inta,b，i；if(r[0]<r[1]){a=r[0]；b=r[1]；>else{a=r[1]；b=r[0]；}for(i=2；i<n；i++)if(r[i]<a)a=r[i];elseif(r[i]>b)b=r[i]；printf(＂a=％d，b=％d。n＂，a，b)；}(1)給出該算法的功能；(2)給出該算法的時間復雜度。五、算法設計題(本題10分)34．二叉樹的存儲結構類型定義如下typedefstructnode{intdata；structnode*lchild，*rchild；}BinNode；typedefBinNode*BinTree；編寫遞歸算法，求只有一個孩子結點的結點總數(shù)，并計算這些結點的數(shù)據(jù)值的和。函數(shù)的原型為：voidf34(BinTreeT,int*count,int*sum)*count和*sum的初值為0。2012年1月高等教育自學考試全國統(tǒng)一命題考試數(shù)據(jù)結構試題課程代碼：02331考生答題注意事項：本卷所有試卷必須在答題卡上作答。答在試卷和草稿紙上的無效。第一部分為選擇題。必須對應試卷上的題號使用2B鉛筆將“答題卡”的相應代碼涂黑。第二部分為非選擇題。必須注明大、小題號，使用0.5毫米黑色字跡筆作答。合理安排答題空間，超出答題區(qū)域無效。一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1.每個結點有且僅有一個直接前趨和多個(或無)直接后繼(第一個結點除外)的數(shù)據(jù)結構稱為A.樹狀結構 B.網(wǎng)狀結構C.線性結構 D.層次結構2.某線性表中最常用的操作是在最后一個元素之后插入元素和刪除第一個元素，則最節(jié)省運算時間的存儲結構是A.單鏈表 B.雙鏈表C.僅有頭指針的單循環(huán)鏈表 D.僅有尾指針的單循環(huán)鏈表3.已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為pl，p2，p3….，pn，若p1是n，則pi是A.i B.n-iC.n-i+l D.不確定4.下面關于串的敘述中，正確的是A.串是一種特殊的線性表 B.串中元素只能是字母C.空串就是空白串 D.串的長度必須大于零5.無向完全圖G有n個結點，則它的邊的總數(shù)為A.n2 B.n(n-1)C.n(n-1)/2 D.(n-1)6.若一棵二叉樹有10個度為2的結點，5個度為1的結點，則度為0的結點數(shù)是A.9 B.11C.15 D.不確定7.如圖所示，在下面的4個序列中，不符合深度優(yōu)先遍歷的序列是A.acfdeb B.aebdfcC.aedfbc D.aefdbc8.無論待排序列是否有序，排序算法時間復雜度都是O(n2)的排序方法是A.快速排序 B.歸并排序C.冒泡排序 D.直接選擇排序9.已知二叉排序樹G，要輸出其結點的有序序列，則采用的遍歷方法是A.按層遍歷 B.前序遍歷C.中序遍歷 D.后序遍歷10.用ISAM和VSAM組織的文件都屬于A.散列文件 B.索引順序文件C.索引非順序文件 D.多關鍵字文件11.對序列(15，9，7，8，20，-1，4)進行排序，第一趟排序后的序列變?yōu)?4，9，-1，8，20，7，15)，則采用的排序方法是A.選擇 B.快速C.希爾 D.冒泡12.當采用分塊查找時，數(shù)據(jù)的組織方式為A.數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序B.數(shù)據(jù)分成若干塊，每塊中數(shù)據(jù)個數(shù)必須相同C.數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序，塊間是否有序均可D.數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)不必有序，但塊間必須有序13.下述編碼中不是前綴碼的是A.(00，01，10，11) B.(0，1，00，11)C.(0，10，110，111) D.(1，01，000，001)14.若一個棧以向量V[1..n]存儲，初始棧頂指針top為n+l，則x進棧的正確操作是A.top=top-1；V[top]=x B.V[top]=x；top=top+1C.top=top+1；V[top]=x D.V[top]=x；top=top-115.在一個以head為頭結點指針的非空單循環(huán)鏈表中，指針p指向鏈尾結點的條件是A.p->data=-1 B.p->next=NULLC.p->next->next=head D.p->next=head二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)請在每個空格中填上正確答案。錯填、不填均無分。16.在數(shù)據(jù)的邏輯結構和存儲結構中，與計算機無關的是______。17.線性表L=(a1,a2,…，an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是______。18.設循環(huán)隊列的容量為50(序號從0到49)，現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有①front=11，rear=29；②front=29，rear=11；在這兩種情況下，循環(huán)隊列中的元素個數(shù)分別是______和______。19.設T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為______。20.已知三對角矩陣A[10][10]的每個元素占2個單元，現(xiàn)將其三條對角線上的元素逐行存儲在起始地址為1000的連續(xù)的內存單元中，則元素A[6][7]的地址為______。21.若以(4，5，6，7，8)作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是______。22.有向圖G如圖所示，它的兩個拓撲排序序列分別為______和______。23.一組記錄的關鍵字為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為______。24.已知廣義表A=(x，((a，b)，c，))，函數(shù)head(head(tail(A)))的運算結果是______。25.索引順序文件既可以順序存取，也可以______。三、解答題(本大題共4小題，每小題5分，共20分)26.對關鍵字序列(26，18，60，14，7，45，13，32)進行降序的堆排序，寫出構建的初始堆(小根堆)及前兩趟重建堆之后序列狀態(tài)。初始堆：第一趟：第二趟：27.設散列函數(shù)為H(key)=key％11，散列地址空間為0··10，對關鍵字序列(27，13，55，32，18，49，24，38，43)用線性探查法解決沖突，構建散列表?，F(xiàn)已有前4個關鍵字構建的散列表如下所示，請將剩余5個關鍵字填入表中相應的位置。28.已知一棵二叉樹的前序遍歷和中序遍歷序列分別為：ABCDEFG和CBDAEGF，請畫出此二叉樹，并給出后序遍歷序列。29.已知如圖所示的帶權無向圖，請畫出用普里姆算法從頂點1開始的最小生成樹的構造過程。四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.閱讀下列算法，并回答下列問題：(1)簡述該算法的功能；(2)寫出分別輸入字符串："abcba"和"abcbde"，調用算法函數(shù)的返回值。intsymmetry(void){inti=0,j,k；.charstr[80]；SeqStacks；InitStack(&s)；gets(str)；while(str[i]!='＼0')i++；for(j=0;j<i/2.j++)push(&s,str[j])；if(i％2!=0)k=i/2+1；elsek=i／2；for(j=k;j<i;j++)if(str[j]!=pop(&s))return0；return1；}(1)(2)31.下列算法是利用二分查找方法在遞減有序表R中插入元素x，并保持表R的有序性。請在空缺處填入適當?shù)膬热?，使其成為一個完整的算法。typedefstruct{KeyTypekey；InfoTyepotherinfo；}RecType；typedefRecTypeSeqList[Maxlen]voidBinInsert(SeqListR,int*n，RecTypex){intlow=1，high=*n；intmid，i;while(low<=high){mid=(low+high)/2；if(x.key>R[mid].key)(1)；else(2)；}for(i=*n；i>=low；i--)R[i+1]=R[i]；(3)；++(*n)；}(1)(2)(3)32.閱讀下列算法，并回答下列問題：(1)簡述該算法中標號s1所指示的循環(huán)語句的功能；(2)簡述該算法中標號s2所指示的循環(huán)語句的功能。LinkListInsertmnode(LinkListhead，charx，intm){LinkNode*p，*q，*s;inti;charch；p=head->next；s1：while(p&&p->data!=x)p=p->next；if(p==NULL)printf("error\n")；else{q=p->next；s2：for(i=1；i<=m；i++){s=(LinkNode*)malloc(sizeof(LinkNode))；scanf("％c"，&ch)；s->data=ch；p->next=s；p=s；}p->next=q；}returnhead；}(1)(2)33.閱讀下列算法，并回答下列問題：(1)該算法采用的是何種排序方法?(2)算法中的R[n+1]的作用是什么?typedefstruct{KeyTypekey；InfoTypeotherinfo；}RecType；typedefRecTypeSeqList[MaxLen]；voidsort(SeqListR，intn){//n<MaxLen-1intk，i；for(k=n-1;k>=1;k--)if(R[k].key>R[k+l].key){R[n+1]=R[k]；for(i=k+1；R[i].key<R[n+1].key;i++)R[i-1]=R[i];R[i-l]=R[n+1]；}}(1)(2)五、算法設計題(本題10分)34.假設以單鏈表表示線性表，單鏈表的類型定義如下：typedefstructnode{DataTypedata；Structnode*next；}LinkNode，*LinkList；編寫算法，在一個頭指針為head且?guī)ь^結點的單鏈表中，刪除所有結點數(shù)據(jù)域值為x的結點。函數(shù)原型為：LinkListdelnode(LinkListhead，DataTypex)全國2011年10月高等教育自學考試數(shù)據(jù)結構試題課程代碼：02331一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1、在數(shù)據(jù)的邏輯結構中，樹結構和圖結構都是（）A.非線性結構 B.線性結構C.動態(tài)結構 D.靜態(tài)結構2.在一個長度為n的順序表中插入一個元素的算法的時間復雜度為（）A.O（1） B.Ｏ（logn） C.O（n） D.O（n2）3.指針p1和p2分別指向兩個無頭結點的非空單循環(huán)鏈表中的尾結點，要將兩個鏈表鏈接成一個新的單循環(huán)鏈表，應執(zhí)行的操作為（）A.p1－＞next=p2－＞next;p2－＞next=p1－＞next;B.p2－＞next=p1－＞next;p1－＞next=p2－＞next;C.p=p2－＞next;p1－＞next=p;p2－＞next=p1－＞next;D.p=p1－＞next;p1－＞next=p2－＞next；p2－＞next=p;4.設棧的初始狀態(tài)為空，入棧序列為1，2，3，4，5，6，若出棧序列為2，4，3，6，5，1，則操作過程中棧中元素個數(shù)最多時為（）A.2個 B.3個C.4個 D.6個5.隊列的特點是（）A.允許在表的任何位置進行插入和刪除B.只允許在表的一端進行插入和刪除C.允許在表的兩端進行插入和刪除D.只允許在表的一端進行插入，在另一端進行刪除6.一個鏈串的結點類型定義為﹟defineNodeSize6typedefstructnode{chardata[NodeSize];structnode*next;}LinkStrNode;如果每個字符占1個字節(jié)，指針占2個字節(jié)，該鏈串的存儲密度為（）A.1/3 B.1/2C.2/3 D.3/47.廣義表A=（a,B,(a,B,(a,B,……）））的長度為（）A.1 B.2 C.3 D.無限值8.已知10×12的二維數(shù)組A，按“行優(yōu)先順序”存儲，每個元素占1個存儲單元，已知A[1][1]的存儲地址為420，則A[5][5]的存儲地址為（）A.470 B.471 C.472 D.4739.在一棵二叉樹中，度為2的結點數(shù)為15，度為1的結點數(shù)為3，則葉子結點數(shù)為（）A.12 B.16 C.18 D.2010.在帶權圖的最短路徑問題中，路徑長度是指（）A.路徑上的頂點數(shù) B.路徑上的邊數(shù)C.路徑上的頂點數(shù)與邊數(shù)之和 D.路徑上各邊的權值之和11.具有n個頂點、e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）A.e B.2e C.n2-2e D.n2-112.要以O（nlogn）時間復雜度進行穩(wěn)定的排序，可用的排序方法是（）A.歸并排序 B.快速排序C.堆排序 D.冒泡排序13.若希望在1000個無序元素中盡快求得前10個最大元素，應借用（）A.堆排序 B.快速排序 C.冒泡排序 D.歸并排序14.對有序表進行二分查找成功時，元素比較的次數(shù)（）A.僅與表中元素的值有關 B.僅與表的長度和被查元素的位置有關C.僅與被查元素的值有關 D.僅與表中元素按升序或降序排列有關15.散列文件是一種（）A.順序存取的文件 B.隨機存取的文件C.索引存取的文件 D.索引順序存取的文件二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。16.若一個算法中的語句頻度之和為T（n）=3n3-200nlog2n+50n，則該算法的漸近時間復雜度為__________.17.在單鏈表中，除了第1個元素結點外，任一結點的存儲位置均由_____________指示。18.棧的修改是按__________的原則進行。19.字符串中任意個連續(xù)的字符組成的子序列稱為該串的__________。20.假設一個10階的上三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，若矩陣中的第一個元素a11在B中的存儲位置k=0，則元素a55在B中的存儲位置k=__________。21.在一棵具有n個結點的嚴格二叉樹中，度為1的結點個數(shù)為__________。22.對于稀疏圖，采用__________表示法較為節(jié)省存儲空間。23.在排序過程中，如果_____________，則稱其為外部排序。24.設有一組記錄的關鍵字為｛19，14，23，1，68，12，10，78，25｝，用鏈地址法構造散列表，散列函數(shù)為h（key）=key％11,散列地址為1的鏈中有__________個記錄。25.多關鍵字文件的特點是除主文件和主索引外，還建有__________。三、解答題（本大題共4小題，每小題5分，共20分）26.對于下列稀疏矩陣（注：矩陣元素的行列下標均從1開始）（1）畫出三元組表；（2）畫出三元組表的行表。(1)(2)27.已知一個森林的前序遍歷序列為CBADHEGF，后序遍歷序列為ABCDEFGH。（1）畫出該森林；（2）畫出該森林所對應的二叉樹。(1)(2)28.對關鍵字序列（429，653，275，897，170，908，473，256，726）進行基數(shù)排序，寫出每一趟的排序結果。29.對下列關鍵字序列（87，25，310，08，27，132，68，96，187，133，70，63，47，135）構造散列表，假設散列函數(shù)為h（key）=key％13,用拉鏈法解決沖突。（1）畫出該散列表；（2）求等概率情況下查找成功的平均查找長度ASL;（3）寫出刪除值為70的關鍵字時所需進行的關鍵字比較次數(shù)。(1)(2)(3)四、算法閱讀題（本大題共4小題，每小題5分，共20分）30.閱讀下列算法，并回答問題：（1）假設L=（3，7，7，11，20，20，20，51，51），寫出執(zhí)行函數(shù)f30（&L）后的L；（2）簡述f30的功能。voidf30(SeqList*L){∥L為非空的有序表inti=1,k=0;while(i＜L－＞length）｛if(L－＞data[i]!=L－＞data[k])L－＞data[++k]=L－＞data[i];i++;}L－＞length=k+1；}(1)(2)31.閱讀下列算法，并回答問題：（1）假設棧S=（3，8，6，2，5），其中5為棧頂元素，寫出執(zhí)行函數(shù)f31（&S）后的S；（2）簡述函數(shù)f31的功能。voidf31(Stack*S){QueueQ；InitQueue(&Q);while(!StackEmpty(S))EnQueue(&Q,Pop(&S));while(!QueueEmpty(Q))Push(&S,DeQueue(&Q));}（1）（2）32.假設具有n個結點的完全二叉樹順序存儲在向量BT[1..n]中，閱讀下列算法，并回答問題：（1）若向量BT為：ABCDEFG1234567畫出執(zhí)行函數(shù)f32（BT,7,1）的返回結果;(2)簡述函數(shù)f32的功能。BinTreef32(DataTypeBT[],intn,inti){BinTreep;if(i＞n)returnNULL;p=（BinTNode*）malloc(sizeof(BinTNode));p－＞data=BT[i];p－＞lchild=f32(BT,n,i*2);p－＞rchild=f32(BT,n,i*2+1);returnp;}(1)(2)33.已知有向圖的鄰接表和鄰接矩陣定義如下：﹟defineMaxNum50 ∥圖的最大頂點數(shù)typedefstructnode{intadjvex; ∥鄰接點域structnode*next; ∥鏈指針域}EdgeNode; ∥邊表結點結構typedefstruct{charvertex； ∥頂點域EdgeNode*firstedge; ∥邊表頭指針}VertexNode; ∥頂點表結點結構typedefstruct{VertexNodeadjlist[MaxNum]; ∥鄰接表intn,e; ∥圖中當前頂點數(shù)和邊數(shù)}ALGraph; ∥鄰接表描述的圖typedefstruct{charvertex[MaxNum]; ∥頂點表intadjmatrix[MaxNum][MaxNum]; ∥鄰接矩陣intn,e; ∥圖中當前頂點數(shù)和邊數(shù)}AMGraph; ∥鄰接矩陣描述的圖下列算法是將鄰接表描述的圖G1改為鄰接矩陣描述的圖G2，在空白處填上適當內容使算法完整：voidf33（ALGraphG1,AMGraph*G2）{inti,j;EdgeNode*p;G2－＞n=G1.n;G2－＞e=(1);for(i=0;i＜G1.n;i++){G2－＞vertex[i]=(2);p=G1.adjlist[i].firstedge;for(j=0;j＜G1.n;j++）G2－＞adjmatrix[i][j]=0;while(p){G2－＞adjmatrix[i][p－＞adjvex]=1;(3);}}}(1)(2)(3)五、算法設計題（本題10分）34.設順序表Ｌ是一個遞增有序表。編寫算法，要求利用二分查找法確定插入位置，將元素ｘ插入到Ｌ中，使Ｌ保持有序。全國2011年1月自考數(shù)據(jù)結構試題及答案課程代碼：02331一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1.下列選項中與數(shù)據(jù)存儲結構無關的術語是（）A.順序表 B.鏈表C.鏈隊列 D.棧2.將兩個各有n個元素的有序表歸并成一個有序表，最少的比較次數(shù)是（）A.n-1 B.nC.2n-1 D.2n3.已知循環(huán)隊列的存儲空間大小為m，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素的下一個位置，則向隊列中插入新元素時，修改指針的操作是（）A.rear=(rear-1)%m; B.front=(front+1)%m;C.front=(front-1)%m; D.rear=(rear+1)%m;4.遞歸實現(xiàn)或函數(shù)調用時，處理參數(shù)及返回地址，應采用的數(shù)據(jù)結構是（）A.堆棧 B.多維數(shù)組C.隊列 D.線性表5.設有兩個串p和q，其中q是p的子串，則求q在p中首次出現(xiàn)位置的算法稱為（）A.求子串 B.串聯(lián)接C.串匹配 D.求串長6.對于廣義表A，若head(A)等于tail(A)，則表A為（）A.() B.(())C.((),()) D.((),(),())7.若一棵具有n(n>0)個結點的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是（）A.結點均無左孩子的二叉樹 B.結點均無右孩子的二叉樹C.高度為n的二叉樹 D.存在度為2的結點的二叉樹8.若一棵二叉樹中度為l的結點個數(shù)是3，度為2的結點個數(shù)是4，則該二叉樹葉子結點的個數(shù)是（）A.4 B.5C.7 D.89.下列敘述中錯誤的是（）A.圖的遍歷是從給定的源點出發(fā)對每一個頂點訪問且僅訪問一次B.圖的遍歷可以采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷C.圖的廣度優(yōu)先遍歷只適用于無向圖D.圖的深度優(yōu)先遍歷是一個遞歸過程10.已知有向圖G=(V，E)，其中V={V1，V2，V3，V4}，E={<V1，V2>，<V1，V3>，<V2，V3>，<V2，V4>，<V3，V4>}，圖G的拓撲序列是（）A.V1,V2,V3,V4 B.V1,V3,V2,V4C.V1,V3,V4,V2 D.V1,V2,V4,V311.平均時間復雜度為O(nlogn)的穩(wěn)定排序算法是（）A.快速排序 B.堆排序C.歸并排序 D.冒泡排序12.已知關鍵字序列為(51，22，83，46，75，18，68，30)，對其進行快速排序，第一趟劃分完成后的關鍵字序列是（）A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68)C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83)13.某索引順序表共有元素395個，平均分成5塊。若先對索引表采用順序查找，再對塊中元素進行順序查找，則在等概率情況下，分塊查找成功的平均查找長度是（）A.43 B.79C.198 D.20014.在含有10個關鍵字的3階B-樹中進行查找，至多訪問的結點個數(shù)為（）A.2 B.3C.4 D.515.ISAM文件系統(tǒng)中采用多級索引的目的是（）A.提高檢索效率 B.提高存儲效率C.減少數(shù)據(jù)的冗余 D.方便文件的修改二、填空題（本大題共10小題，每小題2分，共20分）請在每小題的空格中填上正確答案。錯填、不填均無分。16.數(shù)據(jù)結構由數(shù)據(jù)的邏輯結構、存儲結構和數(shù)據(jù)的____________三部分組成。17.在單鏈表中某結點后插入一個新結點，需要修改_______________個結點指針域的值。18.設棧S的初始狀態(tài)為空，若元素a、b、c、d、e、f依次進棧，得到的出棧序列是b、d、c、f、e、a，則棧S的容量至少是________________。19.長度為零的串稱為________________。20.廣義表G=(a,b，(c，d，(e，f))，G)的長度為________________。21.一棵樹T采用孩子兄弟鏈表存儲，如果樹T中某個結點為葉子結點，則該結點在二叉鏈表中所對應的結點一定是________________。22.一個有n個頂點的無向連通圖，最少有________________條邊。23.當待排關鍵字序列基本有序時，快速排序、簡單選擇排序和直接插入排序三種排序方法中，運行效率最高的是________________。24.在一棵深度為h的具有n個結點的二叉排序樹中，查找任一結點的最多比較次數(shù)是______________。25.不定長文件指的是文件的____________大小不固定。三、解答題（本大題共4小題，每小題5分，共20分）26.已知一棵二叉排序樹（結點值大小按字母順序）的前序遍歷序列為EBACDFHG，請回答下列問題：(1)畫出此二叉排序樹；(2)若將此二叉排序樹看作森林的二叉鏈表存儲，請畫出對應的森林。27.已知有向圖的鄰接表如圖所示，請回答下面問題：(1)給出該圖的鄰接矩陣；(2)從結點A出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。28.已知待排記錄的關鍵字序列為{25，96，11，63，57，78，44}，請回答下列問題：(1)畫出堆排序的初始堆（大根堆）；(2)畫出第二次重建堆之后的堆。29.已知關鍵字序列為(56，23，41，79，38，62，18)，用散列函數(shù)H(key)=key%11將其散列到散列表HT[0..10]中，采用線性探測法處理沖突。請回答下列問題：(1)畫出散列存儲后的散列表：(2)求在等概率情況下查找成功的平均查找長度。四、算法閱讀題（本大題共4小題，每小題5分，共20分）30.閱讀下列程序。voidf30(intA[]，intn){inti,j,m;for(i=1；i<n；i++)for(j=0；j<i；j++){m=A[i*n+j]；A[i*n+j]=A[j*n+i]；A[j*n+i]=m；}}回答下列問題：(1)已知矩陣B=，將其按行優(yōu)先存于一維數(shù)組A中，給出執(zhí)行函數(shù)調用f30(A，3)后矩陣B的值；(2)簡述函數(shù)f30的功能。31.假設以二叉鏈表表示二叉樹，其類型定義如下：typedefstructnode{chardata;structnode*Ichild,*rchild;∥左右孩子指針}*BinTree；閱讀下列程序。voidf31(BinTreeT){InitStack(S);∥初始化一個堆棧Swhile(T||!StackEmpty(S){while(T){Push(S,T);T=T->lchild;}if(!StackEmpty(S)){T=Pop(S);printf(“%c”,T->data);T=T->rchild;}}}回答下列問題：(1)已知以T為根指針的二叉樹如圖所示，請寫出執(zhí)行f31(T)的輸出結果：(2)簡述算法f31的功能。32.閱讀下列程序。voidf32(intA[],intn){inti,j,m=l,t；for(i=0;i<n-l&&m;i++){for(j=0；j<n；j++)printf(“%d”,A[j])；printf(“＼n”);m=0：for(j=1;j<n-i;j++)if(A[j-1]>A[j]){t=A[j-l];A[j-1]=A[j]；A[j]=t；m=1；}}}回答問題：已知整型數(shù)組A[]={34,26,15,89,42}，寫出執(zhí)行函數(shù)調用f32(A,5)后的輸出結果。33.已知順序表的表結構定義如下：#defineMAXLEN100typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}NodeType；typedefNodeTypeSqList[MAXLEN];閱讀下列程序。Intf33(SqListR，NodeTypeX,intp,intq){intm;if(p>q)return-1;m=(p+q)／2；if(R[m].key==X.key)returnm;if(R[m].key>X.key)returnf33(R,X,p,m-l);elsereturnf33(R,X,m+l,q);}請回答下列問題：(1)若有序的順序表R的關鍵字序列為(2,5，13,26,55,80,105)，分別寫出X.key=18和X.key=26時，執(zhí)行函數(shù)調用f33(R,X,0,6)的函數(shù)返回值。(2)簡述算法f33的功能。五、算法設計題（本題10分）34.假設用帶頭結點的單循環(huán)鏈表表示線性表，單鏈表的類型定義如下：typedefstructnode{intdata;structnode*next;}LinkNode，*LinkList;編寫程序，求頭指針為head的單循環(huán)鏈表中data域值為正整數(shù)的結點個數(shù)占結點總數(shù)的比例，若為空表輸出0，并給出所寫算法的時間復雜度。函數(shù)原型為：floatf34(LinkListhead):全國2010年10月高等教育自學考試數(shù)據(jù)結構試題課程代碼：02331一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1.數(shù)據(jù)的四種存儲結構是()A.順序存儲結構、鏈接存儲結構、索引存儲結構和散列存儲結構B.線性存儲結構、非線性存儲結構、樹型存儲結構和圖型存儲結構C.集合存儲結構、一對一存儲結構、一對多存儲結構和多對多存儲結構D.順序存儲結構、樹型存儲結構、圖型存儲結構和散列存儲結構2.若對某線性表最常用的操作是在最后一個結點之后插入一個新結點或刪除最后一個結點，要使操作時間最少，下列選項中，應選擇的存儲結構是()A.無頭結點的單向鏈表 B.帶頭結點的單向鏈表C.帶頭結點的雙循環(huán)鏈表 D.帶頭結點的單循環(huán)鏈表3.若帶頭結點的單鏈表的頭指針為head，則判斷鏈表是否為空的條件是()A.head=NULL B.head->next=NULLC.head!=NULL D.head->next!=head4.若元素的入棧順序為1，2，3，n，如果第2個出棧的元素是n，則輸出的第i(1<=i<=n)個元素是()A.n-i B.n-i+lC.n-i+2 D.無法確定5.串匹配算法的本質是()A.串復制 B.串比較C.子串定位 D.子串鏈接6.設有一個10階的對稱矩陣A，采用行優(yōu)先壓縮存儲方式，a11為第一個元素，其存儲地址為1，每個元素占一個字節(jié)空間，則a85的地址為()A.13 B.18C.33 D.407.若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二叉樹可能的形狀是()A.樹中沒有度為2的結點 B.樹中只有一個根結點C.樹中非葉結點均只有左子樹 D.樹中非葉結點均只有右子樹8.若根結點的層數(shù)為1，則具有n個結點的二叉樹的最大高度是()A.n B.C.+1 D.n/29.在圖G中求兩個結點之間的最短路徑可以采用的算法是()A.迪杰斯特拉（Dijkstra）算法 B.克魯斯卡爾（Kruskal）算法C.普里姆(Prim)算法 D.廣度優(yōu)先遍歷(BFS)算法10.下圖G=(V,E)是一個帶權連通圖，G的最小生成樹的權為()A.15B.16C.17D.1811.在下圖中，從頂點1出發(fā)進行深度優(yōu)先遍歷可得到的序列是()A.1234567B.1426375C.1425367D.124653712.如果在排序過程中不改變關鍵字相同元素的相對位置，則認為該排序方法是()A.不穩(wěn)定的 B.穩(wěn)定的C.基于交換的 D.基于選擇的13.設有一組關鍵字(19,14,23,1，6，20,4，27,5，11,10,9)，用散列函數(shù)H(key)=key%13構造散列表，用拉鏈法解決沖突，散列地址為1的鏈中記錄個數(shù)為()A.1 B.2C.3 D.414.已知二叉樹結點關鍵字類型為字符，下列二叉樹中符合二叉排序樹性質的是()15.若需高效地查詢多關鍵字文件，可以采用的文件組織方式為()A.順序文件 B.索引文件C.散列文件 D.倒排文件二、填空題（本大題共10小題，每小題2分，共20分）請每小題的空格中填上正確答案。錯填、不填均無分。16.下面程序段的時間復雜度為___________。sum=1；for（i=0；sum<n;i++）sum+=1；17.已知鏈表結點定義如下：typedefstructnode{chardata［16］；structnode*next;}LinkStrNode；如果每個字符占1個字節(jié)，指針占4個字節(jié)，則該鏈表的存儲密度是___________。18.使用一個100個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，約定隊頭指針front等于隊尾指針rear時表示隊空。若為front=8，rear=7，則隊列中的元素個數(shù)為___________。19.3個結點可以組成___________種不同樹型的二叉樹。20.用5個權值{3,2，4，5，1}構造的哈夫曼(Huffman)樹的帶權路徑長度是___________。21.若無向圖G中有n個頂點m條邊，采用鄰接矩陣存儲，則該矩陣中非0元素的個數(shù)為___________。22.影響排序效率的兩個因素是關鍵字的___________次數(shù)和記錄的移動次數(shù)。23.對任一m階的B樹，每個結點中最多包含___________個關鍵字。24.若兩個關鍵字通過散列函數(shù)映射到同一個散列地址，這種現(xiàn)象稱為___________。25.如果要為文件中的每個記錄建立一個索引項，則這樣建立的索引表稱為___________。三、解答題（本大題共4小題，每小題5分，共20分）26.要在［0..n-l］的向量空間中建立兩個棧stackl和stack2，請回答：(1)應該如何設計這兩個棧才能充分利用整個向量空間？(2)若stackl的棧頂指針為topl,stack2的棧頂指針為top2，如果需要充分利用整個向量空間，則：棧stackl空的條件是：___________；棧stack2空的條件是：___________；棧stackl和棧stack2滿的條件是：___________。27.已知廣義表如下：A=(B,y)B=(x，L)L=(a，b)要求：(1)寫出下列操作的結果tail(A)=_______________.head(B)=______________。(2)請畫出廣義表A對應的圖形表示。28.已知二叉樹如下：請畫出該二叉樹對應的森林。29.請回答下列問題：(1)英文縮寫DAG的中文含義是什么？(2)請給出下面DAG圖的全部拓撲排序。四、算法閱讀題（本大題共4小題，每小題5分，共20分）30.已知線性表(a1,a2,a3...，an)按順序存放在數(shù)組a中，每個元素均為整數(shù)，下列程序的功能是將所有小于0的元素移到全部大于等于0的元素之前。例如，有7個整數(shù)的原始序列為(x,x,-x,-x,x,x,-x)，變換后數(shù)組中保存的序列是(-x,-x,-x,x,x,x,x)。請在程序處填入合適的內容，使其成為完整的算法。f30(inta［］，intn){intk，m,temp；m=(1)；while(a［m］<0&&m<n)m=(2)；k=m;while(k<n){while(a［k］>=0&&k<n)k=(3)；if(k<n){temp=a［k］；a［k］=a［m］；a［m］=(4)；m=(5)；}}}(1)(2)(3)(4)(5)31.閱讀下列程序，并回答問題：#include<stdio.h>substr(char*t,char*s,intpos,intlen){while（len>0&&*s）{*t=*(s+pos-l);t++;s++;len--;}*t='\0';}char*f31(char*s){chart[100];if(strlen(s)=1)returns;substr(t,s,1,1);substr(s,s,2,strlen(s)-1);f31(s);returnstrcat(s,t);}main(){charstr[100]=''String'';printf(''%s\n'',f31(str));}(1)請寫出執(zhí)行該程序后的輸出結果；(2)簡述函數(shù)f31的功能。32.下面程序實現(xiàn)插入排序算法。typedefstruct{intkey;Infootherinfo;}SeqList;voidInsertSort(SeqListR［］,intn){/*待排序列保存在R［1..n］中*/SeqListx；inti，j，k，lo,hi,mi;for(i=2；i<=n；i++){(1)；lo=1；hi=i-l;while(lo<=hi){mi=(lo+hi)/2;if((2))break;if(R［mi］.key>x.key)hi=mi-l;elselo=mi+l;}if(mi=lo)k=i-mi;elsek=i-mi-1;for(j=0；j<k；j++)(3)；R［i-j］=x；}}在空白處填寫適當?shù)膬热?，使該程序功能完整?1)(2)(3)33.設有單鏈表類型定義如下：typedefstructnode{intdata;structnode*next;}*LinkList;閱讀下列算法，并回答問題：voidf33(LinkListhead,intA,intB){LinkListp=NULL;While(head!=NULL){if(head->data>A&&head->data<B)p=head;head=head->next;}if(p!=NULL)printf("%d\n",p->data);}(1)已知鏈表h如下圖所示，給出執(zhí)行f33(h，5，8)之后的輸出結果；(2)簡述算法f33的功能。五、算法設計題（本題10分）34.已知二叉樹的定義如下：typedefstructnode{intdata;structnode*lchild,*rchild;}*Bitptr；編寫遞歸算法求二叉樹的高度。函數(shù)原型為：intf34（Bitptrt）；2010年10月全國自考數(shù)據(jù)結構試題課程代碼：02331一、單項選擇題（本大題共15小題，每小題2分，共30分）1．數(shù)據(jù)的四種存儲結構是(A)A.順序存儲結構、鏈接存儲結構、索引存儲結構和散列存儲結構B.線性存儲結構、非線性存儲結構、樹型存儲結構和圖型存儲結構C.集合存儲結構、一對一存儲結構、一對多存儲結構和多對多存儲結構D.順序存儲結構、樹型存儲結構、圖型存儲結構和散列存儲結構2．若對某線性表最常用的操作是在最后一個結點之后插入一個新結點或刪除最后一個結點，要使操作時間最少，下列選項中，應選擇的存儲結構是(C)A.無頭結點的單向鏈表 B.帶頭結點的單向鏈表C.帶頭結點的雙循環(huán)鏈表 D.帶頭結點的單循環(huán)鏈表3．若帶頭結點的單鏈表的頭指針為head，則判斷鏈表是否為空的條件是(B)A.head=NULL B.head->next=NULLC.head!=NULL D.head->next!=head4．若元素的入棧順序為1，2，3，n，如果第2個出棧的元素是n，則輸出的第i(1<=i<=n)個元素是(D)A.n-iB.n-i+l C.n-i+2 D.無法確定5．串匹配算法的本質是(C)A.串復制B.串比較C.子串定位 D.子串鏈接6．設有一個10階的對稱矩陣A，采用行優(yōu)先壓縮存儲方式，a11為第一個元素，其存儲地址為1，每個元素占一個字節(jié)空間，則a85的地址為(C)A.13B.18C.33 D.407．若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二叉樹可能的形狀是(B)A.樹中沒有度為2的結點 B.樹中只有一個根結點C.樹中非葉結點均只有左子樹 D.樹中非葉結點均只有右子樹8．若根結點的層數(shù)為1，則具有n個結點的二叉樹的最大高度是(A)A.nB.C.+1 D.n/29．在圖G中求兩個結點之間的最短路徑可以采用的算法是(A)A.迪杰斯特拉（Dijkstra）算法 B.克魯斯卡爾（Kruskal）算法C.普里姆(Prim)算法 D.廣度優(yōu)先遍歷(BFS)算法10．下圖G=(V,E)是一個帶權連通圖，G的最小生成樹的權為(D)A.15B.16C.17D.1811．在下圖中，從頂點1出發(fā)進行深度優(yōu)先遍歷可得到的序列是(B)A.1234567B.1426375C.1425367D.124653712．如果在排序過程中不改變關鍵字相同元素的相對位置，則認為該排序方法是(B)A.不穩(wěn)定的B.穩(wěn)定的C.基于交換的 D.基于選擇的13．設有一組關鍵字(19,14,23,1，6，20,4，27,5，11,10,9)，用散列函數(shù)H(key)=key%13構造散列表，用拉鏈法解決沖突，散列地址為1的鏈中記錄個數(shù)為(C)A.1B.2C.3 D.414．已知二叉樹結點關鍵字類型為字符，下列二叉樹中符合二叉排序樹性質的是(D)15．若需高效地查詢多關鍵字文件，可以采用的文件組織方式為(D)A.順序文件B.索引文件C.散列文件 D.倒排文件二、填空題（本大題共10小題，每小題2分，共20分）16．下面程序段的時間復雜度為（O(n)）。sum=1；for(i=0;sum<n;i++)sum+=1；17．已知鏈表結點定義如下：typedefstructnode{chardata[16];structnode*next;}LinkStrNode;如果每個字符占1個字節(jié)，指針占4個字節(jié)，則該鏈表的存儲密度是（0.8）。18．使用一個100個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，約定隊頭指針front等于隊尾指針rear時表示隊空。若為front=8，rear=7，則隊列中的元素個數(shù)為（99）。19．3個結點可以組成（5）種不同樹型的二叉樹。20．用5個權值{3,2，4，5，1}構造的哈夫曼(Huffman)樹的帶權路徑長度是（33）。21．若無向圖G中有n個頂點m條邊，采用鄰接矩陣存儲，則該矩陣中非0元素的個數(shù)為（2m）。22．影響排序效率的兩個因素是關鍵字的（比較）次數(shù)和記錄的移動次數(shù)。23．對任m階的B樹，每個結點中最多包含（m-1）個關鍵字。24．若兩個關鍵字通過散列函數(shù)映射到同一個散列地址，這種現(xiàn)象稱為（沖突）。25．如果要為文件中的每個記錄建立一個索引項，則這樣建立的索引表稱為（稠密索引）。三、解答題（本大題共4小題，每小題5分，共20分）26．要在［0..n-l］的向量空間中建立兩個棧stackl和stack2，請回答：(1)應該如何設計這兩個棧才能充分利用整個向量空間？(2)若stackl的棧頂指針為topl,stack2的棧頂指針為top2，如果需要充分利用整個向量空間，則：棧stackl空的條件是：（）;棧stack2空的條件是：（）;棧stackl和棧stack2滿的條件是：（）。答：(1)采用雙向棧的形式，stack1的棧底設置在下標為0的元素上，stack2的棧底設置在下標為n-1的元素上。(2)top1=-1，top2=n，top1-1=top227．已知廣義表如下：A=(B,y),B=(x,L),L=(a,b),要求：(1)寫出下列操作的結果：tail(A)=（(y)）。head(B)=（x）。(2)請畫出廣義表A對應的圖形表示。答：28．已知二叉樹如下：請畫出該二叉樹對應的森林。答：29．請回答下列問題：(1)英文縮寫DAG的中文含義是什么？(2)請給出下面DAG圖的全部拓撲排序。答：(1)有向無環(huán)圖(2)abdcefg，abdcfeg，adbcefg，adbcfeg四、算法閱讀題（本大題共4小題，每小題5分，共20分）30．已知線性表(a1,a2,a3...，an)按順序存放在數(shù)組a中，每個元素均為整數(shù)，下列程序的功能是將所有小于0的元素移到全部大于等于0的元素之前。例如，有7個整數(shù)的原始序列為(x,x,-x,-x,x,x,-x)，變換后數(shù)組中保存的序列是(-x,-x,-x,x,x,x,x)。請在程序處填入合適的內容，使其成為完整的算法。f30(inta[],intn){intk,m,temp；m=(1);while(a[m]<0&&m<n)m=(2);k=m;while(k<n){while(a[k]>=0&&k<n)k=(3);if(k<n){temp=a[k];a[k]=a[m];a[m]=(4);m=(5);}}}答：(1)0(2)m+1(3)k+1(4)temp(5)m+131．閱讀下列程序，并回答問題：#include<stdio.h>substr(char*t,char*s,intpos,intlen){while(len>0&&*s){*t=*(s+pos-l);t++;s++;len--;}*t='\0';}char*f31(char*s){chart[100];if(strlen(s)=1)returns;substr(t,s,1,1);substr(s,s,2,strlen(s)-1);f31(s);returnstrcat(s,t);}main(){charstr[100]=''String'';printf(''%s\n'',f31(str));}(1)請寫出執(zhí)行該程序后的輸出結果；(2)簡述函數(shù)f31的功能。答：(1)''gnirtS''(2)將字符串s中的字符倒置。32．下面程序實現(xiàn)插入排序算法。typedefstruct{intkey;Infootherinfo;}SeqList;voidInsertSort(SeqListR[],intn){/*待排序列保存在R［1..n］中*/SeqListx;inti,j,k,lo,hi,mi;for(i=2;i<=n;i++){(1);lo=1;hi=i-l;while(lo<=hi){mi=(lo+hi)/2;if((2))break;if(R[mi].key>x.key)hi=mi-l;elselo=mi+l;}if(mi=lo)k=i-mi;elsek=i-mi-1;for(j=0;j<k;j++)(3);R[i-j]=x;}}在空白處填寫適當?shù)膬热?，使該程序功能完整。答?1)x=R[i](2)R[mi].key==x.key(3)R[i-j]=R[i-j-1]58/10033．設有單鏈表類型定義如下：typedefstructnode{intdata;structnode*next;}*LinkList;閱讀下列算法，并回答問題：voidf33(LinkListhead,intA,intB){LinkListp=NULL;while(head!=NULL){if(head->data>A&&head->data<B)p=head;head=head->next;}if(p!=NULL)printf("%d\n",p->data);}(1)已知鏈表h如下圖所示，給出執(zhí)行f33(h，5，8)之后的輸出結果；(2)簡述算法f33的功能。答：(1)7(2)輸出鏈表h中（若存在）最后一個大于A到小于B的值。五、算法設計題（本題10分）34.已知二叉樹的定義如下：typedefstructnode{intdata;structnode*lchild,*rchild;}*Bitptr;編寫遞歸算法求二叉樹的高度。函數(shù)原型為：intf34（Bitptrt）；答：intf34(Bitptrt){if(!t)return0; lh=f34(t->lchild);rh=f34(t->rchild);returnlh>rh?lh+1:rh+1全國2010年1月高等教育自學考試數(shù)據(jù)結構試題課程代碼：02331一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。1．若一個算法的時間復雜度用T(n)表示，其中n的含義是（）A．問題規(guī)模 B．語句條數(shù)C．循環(huán)層數(shù) D．函數(shù)數(shù)量2．具有線性結構的數(shù)據(jù)結構是（）A．樹 B．圖C．棧和隊列 D．廣義表3．將長度為n的單鏈表連接在長度為m的單鏈表之后，其算法的時間復雜度為（）A．O(1) B．O(m)C．O(n) D．O(m+n)4．在帶頭結點的雙向循環(huán)鏈表中插入一個新結點，需要修改的指針域數(shù)量是（）A．2個 B．3個C．4個 D．6個5．假設以數(shù)組A[60]存放循環(huán)隊列的元素，其頭指針是front=47，當前隊列有50個元素，則隊列的尾指針值為（）A．3 B．37C．50 D．976．若棧采用鏈式存儲結構，則下列說法中正確的是（）A．需要判斷棧滿且需要判斷?？誃．不需要判斷棧滿但需要判斷棧空C．需要判斷棧滿但不需要判斷?？誅．不需要判斷棧滿也不需要判斷?？?．若串str=”Software”，其子串的數(shù)目是（）A．8 B．9C．36 D．378．設有一個10階的下三角矩陣A，采用行優(yōu)先壓縮存儲方式，all為第一個元素，其存儲地址為1000，每個元素占一個地址單元，則a85的地址為（）A．1012 B．1017C．1032 D．10399．允許結點共享的廣義表稱為（）A．純表 B．線性表C．遞歸表 D．再入表10．下列數(shù)據(jù)結構中，不屬于二叉樹的是（）A．B樹 B．AVL樹C．二叉排序樹 D．哈夫曼樹11．對下面有向圖給出了四種可能的拓撲序列，其中錯誤的是（）A．1，5，2，6，3，4 B．1，5，6，2，3，4C．5，1，6，3，4，2 D．5，1，2，6，4，312．以v1為起始結點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是（）A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6C．v1，v2，v3，v4，v7，v5，v6 D．v1，v2，v5，v6，v7，v3，v413．下列排序算法中不穩(wěn)定的是（）A．快速排序 B．歸并排序C．冒泡排序 D．直接插入排序14．一個有序表為(1，3，9，12，32，41，45，62，75，77，82，95，100)，當采用折半查找方法查找值32時，查找成功需要的比較次數(shù)是（）A．2 B．3C．4 D．815．采用ISAM組織文件的方式屬于（）A．鏈組織 B．順序組織C．散列組織 D．索引組織二、填空題(本大題共10小題，每小題2分，共20分)請在每小題的空格中填上正確答案。錯填、不填均無分。16．數(shù)據(jù)元素及其關系在計算機存儲器內的表示稱為_________。17．長度為n的線性表采用單鏈表結構存儲時，在等概率情況下查找第i個元素的時間復雜度是_________。18．下面是在順序棧上實現(xiàn)的一個棧基本操作，該操作的功能是_________。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypef18(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；returnS->data[S->top]；}19．在串匹配中，一般將主串稱為目標串，將子串稱為_________。20．已知廣義表C=(a(b，c)，d)，則：tail(head(tail(C)))=_________。21．用6個權值分別為6、13、18、30、7和16的結點構造一棵哈夫曼(Huffma