自考數(shù)據(jù)結(jié)構(gòu)歷年試題及答案

全國(guó)2001年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331第一部分選擇題（30分）一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1.算法指的是（）計(jì)算機(jī)程序B.解決問(wèn)題的計(jì)算方法C.排序算法D.解決問(wèn)題的有限運(yùn)算序列線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）必須是不連續(xù)的連續(xù)與否均可必須是連續(xù)的和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(m)D.O(m+n)由兩個(gè)棧共享一個(gè)向量空間的好處是：（）減少存取時(shí)間，降低下溢發(fā)生的機(jī)率節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率減少存取時(shí)間，降低上溢發(fā)生的機(jī)率節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率5.設(shè)數(shù)組data［m］作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（）B.front=(front+1)%(m-1)D.front=(front+1)%mB.串的長(zhǎng)度必須大于零DB.front=(front+1)%(m-1)D.front=(front+1)%mB.串的長(zhǎng)度必須大于零D.空串就是空白串C.front=（front-1）%m如下陳述中正確的是（）串是一種特殊的線性表C.串中元素只能是字母若目標(biāo)串的長(zhǎng)度為n，模式串的長(zhǎng)度為［n/3］，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（）nA.O(3)B.OnA.O(3)B.O(n)C.O(n2)D.O(n3)一個(gè)非空廣義表的表頭（不可能是子表C.只能是原子）只能是子表可以是子表或原子9.假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表「0-806「「0-806「70007000A.0000B.-5040-50400000_0000_0300-0-806「-0-806"00000000C.0200D.7000-5040-504000000300在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為（）A.4B.5C.6D.7在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）A.eB.2eC.n2—eD.n2—2e假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)％相關(guān)的所有弧的時(shí)間復(fù)雜度是（）A.O（n）B.O（e）C.O（n+e）D.O（n*e）用某種排序方法對(duì)關(guān)鍵字序列（25,84,21,47,15,27,68,35,20）進(jìn)行排序時(shí)，序列的變化情況如下：20,15,21,25,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.快速排序適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）有序表B.分塊有序表C.三叉排序樹(shù)D.線性鏈表15.不定長(zhǎng)文件是指（）文件的長(zhǎng)度不固定B.記錄的長(zhǎng)度不固定字段的長(zhǎng)度不固定D.關(guān)鍵字項(xiàng)的長(zhǎng)度不固定第二部分非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）不寫(xiě)解答過(guò)程，將正確的答案寫(xiě)在每小題的空格內(nèi)。錯(cuò)填或不填均無(wú)分。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=。棧頂?shù)奈恢檬请S著操作而變化的。在串S=“structure”中，以t為首字符的子串有個(gè)。假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B[0]存儲(chǔ)

矩陣中第1個(gè)元素氣1,則B[31]中存放的元素是。已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有個(gè)葉子結(jié)點(diǎn)。已知一個(gè)圖的廣度優(yōu)先生成樹(shù)如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為?！觥鲈趩捂湵砩想y以實(shí)現(xiàn)的排序方法有和。在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為。多重表文件和倒排文件都?xì)w屬于文件。三、解答題(本大題共4小題，每小題5分，共20分)畫(huà)出下列廣義表的共享結(jié)構(gòu)圖形表示P=(((z),(x,y)),((x,y),x),(z))請(qǐng)畫(huà)出與下列二叉樹(shù)對(duì)應(yīng)的森林。已知一個(gè)無(wú)向圖的頂點(diǎn)集為｛a,b,c,d,e｝，其鄰接矩陣如下所示bcdbcde10010000110110110110畫(huà)出該圖的圖形；根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫(xiě)出相應(yīng)的遍歷序列。已知一個(gè)散列表如下圖所示：35203348590123456789101112其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：h.=(h(key)+i*h1(key))%mi=0,1,…，m—1其中1h1(key)=key%11+1回答下列問(wèn)題：對(duì)表中關(guān)鍵字35,20,33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少?該散列表在等概率查找時(shí)查找成功的平均查找長(zhǎng)度為多少？四、算法閱讀題(本大題共4小題，每小題5分，共20分)(3)下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為:(3)T當(dāng)SiV%

comstr(s1,s2)=<0當(dāng)s=s1當(dāng)s>sI12請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。intcomstr(LinkStrings1,LinkStrings2){//s1和s2為兩個(gè)鏈串的頭指針while(s1&&s2){if(s1—>date<s2—>date)return—1；if(s1—>date>s2—>date)return1；_;_;}if(③)return—1；if(④)return1；⑤：}①②③④⑤31.閱讀下面的算法LinkListmynote(LinkListL){//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next){q=L；L=L—>next；p=L；S1：while(p—>next)p=p—>next；S2：p—>next=q；q—>next=NULL；returnL；}請(qǐng)回答下列問(wèn)題：說(shuō)明語(yǔ)句S1的功能；說(shuō)明語(yǔ)句組S2的功能;設(shè)鏈表表示的線性表為(a],a2,…,an),寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間(參見(jiàn)右下圖)，11WjiJJ其類型Queue2定義如下：typedefstruct{rearfujDateTypedata[MaxSize]；rearfujintfront[2],rear[2]；}Queue2；對(duì)于i=0或1,front[i]和rear[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。intEnQueue(Queue2*Q,inti,DateTypex){//若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0if(i<0||i>1)return0；if(Q—>rear[i]==Q—>front[①]return0；Q—>data[②]=x；Q—>rear[i]=[③];return1；}①②③已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；VoidInorder(BinTreeT){LinkLists；If(T){Inorder(T—>lchild)；If((!T—>lchild)&&(!T—>rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s—>data=T—>data；s—>next=Leafhead；Leafhead=s；}Inorder(T—>rchild)；}}對(duì)于如下所示的二叉樹(shù)

畫(huà)出執(zhí)行上述算法后所建立的結(jié)構(gòu)；說(shuō)明該算法的功能。五、算法設(shè)計(jì)題(本題共10分)34.閱讀下列函數(shù)arrange()intarrange(inta[],int1,inth,intx){//1和h分別為數(shù)據(jù)區(qū)的下界和上界inti,j,t；i=1;j=h；while(i<j){while(i<j&&a[j]>=x)j--；while(i<j&&a[j]>=x)i++；if(i<j){t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]<x)returni；elsereturni—1；}寫(xiě)出該函數(shù)的功能；寫(xiě)一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法:對(duì)一整型數(shù)組b[n]中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè)數(shù)。全國(guó)2001年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題參考答案課程代碼：02331一、單項(xiàng)選擇題(本大題共15小題，每小題課程代碼：02331一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)D1.D2.B3.C4.B5.6.A7.C8,D9,A10.C11.D12.C13.D14.C二、填空題(本大題共10小題,每小題2分，共20分)16.存儲(chǔ)(或存儲(chǔ)結(jié)構(gòu))17.p—>next—>next18.進(jìn)棧和退棧19.1220.a"22.23.快速排序、堆排序、希爾排序24.225.多關(guān)鍵字三、解答題(本大題共4小題，每小題5分，-共20分)15.B21.384abefcdg27.28.該圖的圖形為:27.28.該圖的圖形為:深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc(1)對(duì)關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、1；(2)平均查找長(zhǎng)度ASL=3+2+1+*2=955四、算法閱讀題(本大題共4小題，每小題5分，共20分)①S1=S1—>nexts2=s2—>nexts2(或s2!=NULL或s2&&!s1)s1(或s1!=NULL或s1&&!s2)return0(1)查詢鏈表的尾結(jié)點(diǎn)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)返回的線性表為(a2,a3，…,an,a])①(i+1)%2(或1—i)Q—>rear[i](Q—>rear[i]+)%Maxsize(1)LeafheadF——HG——>DA中序遍歷二叉樹(shù)，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指針的逆序單鏈表(或按二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表)。五、算法設(shè)計(jì)題(本題共10分)(1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a[]中的元素并返回分界值i,使所有<x的元素均落在a[1..i]上，使所有Nx的元素均落在a[i+1..h]上。

intf(intb[],intn){intp,q；p=arrange(b,0,n—1,1)；q=arrange(b,0,p,0)；returnp—q；}(2)intf(intb[],intn)或{intf(intb[],intn){intp,q；p=arrange(b,0,n—1,1)；q=arrange(b,0,p,0)；returnp—q；}一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分。在每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)）下面程序段的時(shí)間復(fù)雜度是（D）for（i=0;i<n;i++）for（j=1;j<m;j++）A[i][j]=0；A.O（n）B.O（m+n+1）C.O（m+n）D.O（m*n）在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語(yǔ)句是（B）A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p->next->next=head，則（D）A.p指向頭結(jié)點(diǎn)B.p指向尾結(jié)點(diǎn)C.*p的直接后繼是頭結(jié)點(diǎn)D?*P的直接后繼是尾結(jié)點(diǎn)判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是（C）A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!=Q.rear設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作（D）聯(lián)接B.求子串C.字符定位D?子串定位廣義表A=（a,（b）,（）,（c,d,e））的長(zhǎng)度為（A）A.4B.5C.6D.7一棵含18個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度至少為（C）A.3B.4C.5D.6已知二叉樹(shù)的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為（D）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中（B）A.通過(guò)該頂點(diǎn)的簡(jiǎn)單路徑數(shù)B?與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)C.通過(guò)該頂點(diǎn)的回路數(shù)D.與該頂點(diǎn)連通的頂點(diǎn)數(shù)已知一個(gè)圖如下所示，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的序列為（C）A.acefbdB.acbdfeC.acbdefD.acdbfe11.在下列排序方法中，平均時(shí)間性能為O（nlogn）且空間性能最好的是（B）D.基數(shù)排序其中每相鄰兩個(gè)為有序子序列。對(duì)這A.快速排序B?堆排序C.歸并排序已知一組關(guān)鍵字為{25,48,36,72,79,82,23,40,16,35}，些子序列進(jìn)行一趟兩兩歸并的結(jié)果是（A）A?{25,36,48,72,23,40,79,82,16,35}C.{25,36,48,72,16,23,35,40,79,82}B.{25,36,48,72,16,23,40,79,82,35}D.{16,23,25,35,36,40,48,72,79,82}設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用則在查找概率相等的情況下，分塊查找順序查找來(lái)確定塊，并在確定的塊中進(jìn)行順序查找成功時(shí)的平均查找長(zhǎng)度為（B）A,21B.23C.41索引非順序文件的特點(diǎn)是（A?主文件無(wú)序，索引表有序C.主文件有序，索引表有序倒排文件的主要優(yōu)點(diǎn)是（CA.便于進(jìn)行插入和刪除運(yùn)算C.便于進(jìn)行多關(guān)鍵字查詢二、填空題（本大題共10小題抽象數(shù)據(jù)類型的特點(diǎn)是將—數(shù)據(jù)和―運(yùn)算―封裝在一起，從而現(xiàn)實(shí)信息隱藏。從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需___前移―一個(gè)位置。在隊(duì)列中，允許進(jìn)行插入操作的一端稱為隊(duì)尾，允許進(jìn)行刪除操作的一端稱為隊(duì)頭。如圖兩個(gè)棧共享一個(gè)向量空間，top1和top2分別為指向兩個(gè)棧頂元素的指針，則“棧滿”D.62）B.主文件有序D.主文件無(wú)序索引表無(wú)序索引表無(wú)序B.便于進(jìn)行文件的恢復(fù)D.節(jié)省存儲(chǔ)空間每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）.和慰T9封的判定條件是__top1=top2-1。設(shè)S1="good",S2="",S3="book"，則S1，S2和S3依次聯(lián)接后的結(jié)果是_goodbook__。假設(shè)三維數(shù)組A[10][9][8]按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且首地址為100,則元素A[9][8][7]的存儲(chǔ)地址是__2257。已知在一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹(shù)中含有的葉子結(jié)點(diǎn)的數(shù)目為—((n-1)/k)*(虹1)+1_或n-(n-1)/k__o能夠成功完全拓?fù)渑判虻膱D一定是一個(gè)__有向無(wú)環(huán)圖_。如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用—堆排序—較為適當(dāng)。假設(shè)哈希表的表長(zhǎng)為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達(dá)為—hi=(H(key)+I)/m。三、解答題(本大題共4小題，每小題5分，共20分)假設(shè)通信電文使用的字符集為｛a,b,c,d,e,f｝，名字符在電文中出現(xiàn)的頻度分別為：34,5,12,23,8，18，試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫(huà)出你所構(gòu)造的哈夫曼樹(shù)(要求樹(shù)中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值)，然后分別寫(xiě)出每個(gè)字符對(duì)應(yīng)的編碼?！癈ioo)26.八0/、127.已知一個(gè)圖如下所示，其頂點(diǎn)按a、b、c、d、e、f順序存放在鄰接表的頂點(diǎn)表中，請(qǐng)畫(huà)出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbdfeo答案:012345a"I?1十Til1Ala四T1川l-HI今18IR宵題圖初3內(nèi)hcd—ef28.已知兩個(gè)4X5的稀疏矩陣的三元組表分別如下:014160113212218122-22234一2522569342283342544251請(qǐng)畫(huà)出這兩個(gè)稀疏矩陣之和的三元組表。解：11321416212-4125694279WX題圖從空樹(shù)起，依次插入關(guān)鍵字40,8,90,15,62,95,12,23,56,序樹(shù)。畫(huà)出該二叉排序樹(shù)畫(huà)出刪去該樹(shù)中元素值為90的結(jié)點(diǎn)之后的二叉排序樹(shù)。：40i8■9015629512i23'：56)32'32,構(gòu)造一棵二叉排40；122332四、算法閱讀題(本大題共4小題，每小題5分，共20分)如圖所示，利用同一循環(huán)向量空間實(shí)現(xiàn)兩個(gè)隊(duì)列，其類型Queue2定義如下:typedefstruct(DataTypedata[MaxSize];intfront[2],length[2];}Queue2;對(duì)于i=0或1,front[i]和length[i]分別為第i個(gè)隊(duì)列的頭指針和長(zhǎng)度域。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，實(shí)現(xiàn)第i個(gè)循環(huán)隊(duì)列的入隊(duì)操作。intEnQueue(Queue2*Q,inti,DataTypex){//若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1，否則返回0if(i<0||i>1)return0;if((1))return0;Q->data[(2)]=x;Q->length[(3)]++;return1;}解：(Q->front[i]+Q->length[i]%Maxsize==Q->front[(i+1)%2](Q->front[i]+->length[i]%MaxsizeI某二叉樹(shù)的線索鏈表存儲(chǔ)結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點(diǎn)的指針，圖(a)為結(jié)點(diǎn)結(jié)構(gòu)。閱讀下列算法，并回答問(wèn)題：寫(xiě)出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果；簡(jiǎn)述函數(shù)f的功能。voidf(BinThrTreet){while(t){printf(t->data);if(t->lchild)t=t->lchild;elset=t->rchild;}}答案(1)ABDFCEGH(2)先根遍歷32.下列函數(shù)FindCycle(Gi)的功能是，對(duì)一個(gè)采用鄰接表作存儲(chǔ)結(jié)構(gòu)的有向圖G，利用深度優(yōu)先搜索策略尋找一條經(jīng)過(guò)頂點(diǎn)vi的簡(jiǎn)單回路。數(shù)組cycle_path用于保存搜索過(guò)程中形成的回路，cycle_path[k]=j(jN0)表示在回路中頂點(diǎn)vk的下一個(gè)頂點(diǎn)是vj。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。vertexfirstedge已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為：adjvexnext邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為：intcycle_path[MaxNum];intFindCycle(ALGraph*Ginti){//若回路存在，則返回1，否則返回0intj;for(j=0;j<G->n;j++)cycle_path[j]=-1;returnDFSPath(G,i,i);}intDFSPath(ALGraph*Gintj,inti){EdgeNode*p;intcycled=0;for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next){cycle_path[j]=p->adjvex;if((1))cycled=1;//已找到回路elseif(cycle_path[p->adjvex]==-1)cycled=(2);}return(3)}(1)(2)(3)32題答案：(1)p->adjvex==iDFSpath(G,p->adjvex,i)cycled33.閱讀下列函數(shù)algo,并回答問(wèn)題。(1)假設(shè)整型數(shù)組A[1..8]中的元素依次為(3,8,9,1,7,4,2,6)。執(zhí)行函數(shù)調(diào)用algo(A,8)時(shí)，外層while的循環(huán)體執(zhí)行多少次?函數(shù)的返回值是多少？(2)簡(jiǎn)述函數(shù)algo(L,n)的功能。intalgo(intL[],intn){inti=0,j,s=1,t=n;while(i!=(n+1)/2){intx=L[s]；i=s;j=t;while(i<j){while(i<j&&L[j]>=x)j--;L[i]=L[j];while(i<j&&L[i]<=x)i++;L[j]=L[i];}L[i]=x;if(i<(n+1)/2)s=i+1;elset=i-1;}if(i==0)return0;elsereturnL[i];}(1)(2)(3)33題答案：外循環(huán)執(zhí)行4次，函數(shù)返回值為3。將A[1]至A[8]中不小于A[1]的元素進(jìn)行遞增排序，如調(diào)用algo(A,8)時(shí)最終排序結(jié)果為21346789五、算法設(shè)計(jì)題(本大題共10分)34.假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表作非遞減有序線性表的存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點(diǎn)空間。例如：(7,10,10,21,30,42,42,42,51，70)經(jīng)算法操作后變?yōu)?7，10,21,30,42,51，70)34題答案：Exam4(Linklist,L){listnode*p,*q;p=L->next;while(p!=L){q=p->next;while(q&&q->data==p->data){p->next=q->next;free(q);

q=p->next;}p->next;}}2003年10月全國(guó)數(shù)據(jù)結(jié)構(gòu)試題(2006-7-252:07:00計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為(b)A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并使鏈表仍然有序的時(shí)間復(fù)雜度是(b)B.O(n)D.O(n2)B.存儲(chǔ)結(jié)構(gòu)不D.限定插入和刪除的位)B.刪除操作更加方D.不會(huì)出現(xiàn)上溢的情況b)A.O(1)C.O(nlogn)3?隊(duì)和棧的主要區(qū)別是(d)A.邏輯結(jié)構(gòu)不同同C.所包含的運(yùn)算個(gè)數(shù)不同置不同鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是(dA.插入操作更加方便便C.不會(huì)出現(xiàn)下溢的情況采用兩類不同存儲(chǔ)結(jié)構(gòu)的字符串可分別簡(jiǎn)稱為(B.順序串和鏈串D.變量串和常量串=〃xy〃進(jìn)行子串定位操作的結(jié)A.主串和子串C.目標(biāo)串和模式串在目標(biāo)串T[0..nT]="xwxxyxy"中，對(duì)模式串P[0..mT]TOC\o"1-5"\h\z果是(c)A.0B.2C.3D.5)B.(a,b,c)D.((a,b,c))若A[1][1]的存儲(chǔ)地址為)已知廣義表的表頭為a,表尾為(b,c),則此廣義表為(bB.O(n)D.O(n2)B.存儲(chǔ)結(jié)構(gòu)不D.限定插入和刪除的位)B.刪除操作更加方D.不會(huì)出現(xiàn)上溢的情況b)B.順序串和鏈串D.變量串和常量串=〃xy〃進(jìn)行子串定位操作的結(jié))B.(a,b,c)D.((a,b,c))若A[1][1]的存儲(chǔ)地址為)420,A[3][3]的存儲(chǔ)地址為446,則A[5][5]的存儲(chǔ)地址為(TOC\o"1-5"\h\zA.470B.471C.472D.473二叉樹(shù)中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為(d)A.8B.15C.16D.32下列編碼中屬前綴碼的是(aA.{1,01,000,001}B.{1,01,011,010}C.{0,10,110,11}D.{0,1,00,11}TOC\o"1-5"\h\z如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是（d）A.有向完全圖B.連通圖C.強(qiáng)連通圖D.有向無(wú)環(huán)圖對(duì)n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為（d）A.O（1）B.O（logn）C.O（n）D.O（nlogn）對(duì)表長(zhǎng)為n的順序表進(jìn)行順序查找，在查找概率相等的情況下，查找成功的平均查找長(zhǎng)度為（n/2）A.B.C.D.n對(duì)于哈希函數(shù)H（key）=key%13,被稱為同義詞的關(guān)鍵字是（d）A.35和41B.23和39C.15和44D.25和51稠密索引是在索引表中（）A.為每個(gè)記錄建立一個(gè)索引項(xiàng)B.為每個(gè)頁(yè)塊建立一個(gè)索引項(xiàng)C.為每組記錄建立一個(gè)索引項(xiàng)D.為每個(gè)字段建立一個(gè)索引項(xiàng)二、填空題（每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分）當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，算法執(zhí)行時(shí)間T（n）的數(shù)量級(jí)被稱為算法的__（_時(shí)間復(fù)雜度_）在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)量之比稱作_（存儲(chǔ)密度）datenext已知鏈棧的結(jié)點(diǎn)結(jié)構(gòu)為棧頂指針為top，則實(shí)現(xiàn)將指針p所指結(jié)點(diǎn)插入棧頂?shù)恼Z(yǔ)句依次為和。空串的長(zhǎng)度是0；空格串的長(zhǎng)度是（空格的數(shù)目_）。假設(shè)一個(gè)6階的下三角矩陣B按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組A中，其中A[0]存儲(chǔ)矩陣的第一個(gè)元素b11,則A[14]存儲(chǔ)的元素是b63__。在一棵度為3的樹(shù)中，度為2的結(jié)點(diǎn)個(gè)數(shù)是1，度為0的結(jié)點(diǎn)個(gè)數(shù)是6,則度為3的結(jié)點(diǎn)個(gè)數(shù)是2。如圖所示的有向無(wú)環(huán)圖可以排出種不同的拓?fù)湫蛄?。利用篩選法將關(guān)鍵字序列（37，66，48，29，31，75）建成的大根堆為（―75,66,48,29,31,37）。對(duì)長(zhǎng)度為20的有序表進(jìn)行二分查找的判定樹(shù)的高度為—5。在多重表文件中，次關(guān)鍵字索引的組織方式是將的記錄鏈接成一個(gè)鏈表。對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個(gè)指向鏈表中某結(jié)點(diǎn)的指針p，能否將p所指結(jié)點(diǎn)的數(shù)據(jù)元素與其確實(shí)存在的直接前驅(qū)交換？請(qǐng)對(duì)每一種鏈表作出判斷，若可以，寫(xiě)出程序段；否則說(shuō)明理由。datenext單鏈表和單循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)為priordatenext雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為單鏈表：(不可以,無(wú)法找到前驅(qū)接點(diǎn))單循環(huán)鏈表(可以：q=p->next;while(q->next!=p)q=q->next;q->data<->p->data;雙向鏈表(可以:p->prior->data<->p->data;)假設(shè)通信電文使用的字符集為{a,b,c,d,e,f,g}，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。請(qǐng)根據(jù)哈夫曼編碼畫(huà)出此哈夫曼樹(shù)，并在葉子結(jié)點(diǎn)中標(biāo)注相應(yīng)字符；若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度。當(dāng)采用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，也可將鄰接表中的頂點(diǎn)表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。(1)請(qǐng)分別畫(huà)出這種鄰接表的頂點(diǎn)鏈表結(jié)點(diǎn)和邊表結(jié)點(diǎn)，并說(shuō)明結(jié)點(diǎn)中各個(gè)域的作用；⑵對(duì)如圖所示的有向圖畫(huà)出這種鄰接表。已知4階B-樹(shù)如圖所示。分別畫(huà)出將關(guān)鍵字23和89相繼插入之后的B-樹(shù)。畫(huà)出從插入之前的B-樹(shù)中刪除關(guān)鍵字51之后的B-樹(shù)。四、算法閱讀題(每小題5分，共20分)閱讀下列函數(shù)algo,并回答問(wèn)題：假設(shè)隊(duì)列q中的元素為(2,4,5,7,8),其中“2”為隊(duì)頭元素。寫(xiě)出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊(duì)列q；簡(jiǎn)述算法algo的功能。voidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,DeQueue(Q));while(!StackEmpty(&S))EnQueue(Q,Pop(&S));}87542隊(duì)列倒置閱讀下列函數(shù)F，并回答問(wèn)題：已知如圖所示的二叉樹(shù)以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，rt為指向根結(jié)點(diǎn)的指針。寫(xiě)出執(zhí)行函數(shù)調(diào)用F(rt)的輸出結(jié)果。說(shuō)明函數(shù)F的功能。voidF(BinTreeT){StackS;if(T)InitStack(&S);Push(&S,NULL);while(T){printf("%c",T->data);if(T->rchild)Push(&S,T->rchild);if(T->lchild)T=T->lchild;elseT=Pop(&S);}}}(1)前序遍歷二叉數(shù)vertexfirstedge已知鄰接表的頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為adjvexnext邊表結(jié)點(diǎn)EdgeNode的結(jié)構(gòu)為下列算法計(jì)算有向圖G中頂點(diǎn)vi的入度。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。intFindDegree(ALGraph*G,inti)//ALGraph為圖的鄰接表類型{intdgree,j;EdgeNode*p;TOC\o"1-5"\h\zdegree=(1);for(j=0;j<G->n;j++){p=G->adjlist[j].firstedge;while((2)){if((3)){degree++;break;}p=p->next;}}returndegree;}degree=0;pp->adj==vi

datanext已知單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為下列算法對(duì)帶頭結(jié)點(diǎn)的單鏈表L進(jìn)行簡(jiǎn)單選擇排序，使得L中的元素按值從小到大排列。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。voidSelectSort(LinkedListL){LinkedListp,q,min;DataTypercd;p=(1);while(p!=NULL){min=p;q=p->next;while(q!=NULL){if((2))min=q;q=q->next;}if((3)){rcd=p->data;p->data=min->data;min->data=rcd;};}}L->nextq->data<min->datap!=minp=p->next五、算法設(shè)計(jì)題(本題10分)設(shè)線性表A=(a1,a2,a3,…，an)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。編寫(xiě)一個(gè)函數(shù)，對(duì)A進(jìn)行調(diào)整，使得當(dāng)n為奇數(shù)時(shí)A=(a2,a4,…，an-1,a1,a3,…，an)，當(dāng)n為偶數(shù)時(shí)A=(a2,a4,…，an,a1,a3,…，an-1)。typedefstructnode{intx;structnode*next;typedefNODEvoidadjust({NODE*pTmpNODE*pCur}NODE;*LinkList;typedefNODEvoidadjust({NODE*pTmpNODE*pCurNODE*pOddHdr=header->next;//奇數(shù)鏈表頭指針NODE*pOddTail=header->next;//奇數(shù)鏈表尾指針intbIsOdd=true;//奇數(shù)結(jié)點(diǎn)標(biāo)志，第一個(gè)結(jié)點(diǎn)是奇數(shù)結(jié)點(diǎn)if（NULL==pCur）//空鏈表，不需要處理return;while（pCur->next!=NULL）//從第二個(gè)結(jié)點(diǎn)開(kāi)始遍歷{pCur=pCur->next;bIsOdd=!bIsOdd;if（bIsOdd）//（這步錯(cuò)誤，未將原鏈表的接點(diǎn)連接）（//奇數(shù)結(jié)點(diǎn)，加入奇數(shù)鏈表表尾pOddTail->next=pCur;pOddTail=pCur;}else（//偶數(shù)結(jié)點(diǎn)，加入偶數(shù)鏈表表尾pTmp->next=pCur;pTmp=pCur;}}pOddTail->next=NULL;//奇數(shù)鏈表表尾結(jié)點(diǎn)的next置空pTmp->next=pOddHdr;//奇數(shù)鏈表插入偶數(shù)鏈表表尾（這步錯(cuò)誤，未考慮最后接點(diǎn)的奇偶性。）return;}全國(guó)2004年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成（）A.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B?線性結(jié)構(gòu)和非線性結(jié)構(gòu)C.緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu)D.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)在以單鏈表為存儲(chǔ)結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（）A.數(shù)據(jù)元素的相鄰地址表示B.數(shù)據(jù)元素在表中的序號(hào)表示C.指向后繼元素的指針表示D.數(shù)據(jù)元素的值表示設(shè)p指向單鏈表中的一個(gè)結(jié)點(diǎn)，s指向待插入的結(jié)點(diǎn)，則下述程序段的功能是()s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;結(jié)點(diǎn)*p與結(jié)點(diǎn)*s的數(shù)據(jù)域互換在p所指結(jié)點(diǎn)的元素之前插入元素在p所指結(jié)點(diǎn)的元素之后插入元素在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s棧和隊(duì)列都是()A.限制存取位置的線性結(jié)構(gòu)B.順序存儲(chǔ)的線性結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)D.限制存取位置的非線性結(jié)構(gòu)若數(shù)組s[0..n-1]為兩個(gè)棧si和s2的共用存儲(chǔ)空間，且僅當(dāng)s[0..n-1]全滿時(shí)，各棧才不能進(jìn)行進(jìn)棧操作，則為這兩個(gè)棧分配空間的最佳方案是：si和s2的棧頂指針的初值分別為()A.1和n+1B.1和n/2C.—1和nD.—1和n+1執(zhí)行下列程序段后，串X的值為()S=abcdeigh;1—xyzw;substr(X,S,2,strlen(T));substr(Y,S,stelen(T),2);strcat(X,Y);A."cdefgh"B."cdxyzw”C."cdefxy"D."cdefef"TOC\o"1-5"\h\z多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲(chǔ)方式是因?yàn)?)A.數(shù)組的元素處在行和列兩個(gè)關(guān)系中B.數(shù)組的元素必須從左到右順序排列C.數(shù)組的元素之間存在次序關(guān)系D.數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)從廣義表LS=((p,q),r,s)中分解出原子q的運(yùn)算是()A.tail(head(LS))B.head(tail(head(LS)))C.head(tail(LS))D.tail(tail(head(LS)))在具有n個(gè)葉子結(jié)點(diǎn)的嚴(yán)格二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為()A.2n+1B.2nC.2n-1D.2n-2若<vi,vj>是有向圖的一條邊，則稱()A.vi鄰接于vjB.vj鄰接于viC.vi和vj相互鄰接D.vi與vj-不相鄰接在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在6的()A.最小生成樹(shù)中B.深度優(yōu)先生成樹(shù)中C.廣度優(yōu)先生成樹(shù)中D.深度優(yōu)先生成森林中當(dāng)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)時(shí)，若樹(shù)中不存在與待插入結(jié)點(diǎn)的關(guān)鍵字相同的結(jié)點(diǎn)，且新結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字，則新結(jié)點(diǎn)將成為()A.左子樹(shù)的葉子結(jié)點(diǎn)B.左子樹(shù)的分支結(jié)點(diǎn)C.右子樹(shù)的葉子結(jié)點(diǎn)D.右子樹(shù)的分支結(jié)點(diǎn)希爾排序的增量序列必須是()A.遞增的B.隨機(jī)的C.遞減的D.非遞減的如果在排序過(guò)程中，每次均將一個(gè)待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當(dāng)位置，則該排序方法稱為()A.插入排序B.歸并排序C.冒泡排序D.堆排序設(shè)置溢出區(qū)的文件是()A.索引非順序文件B.ISAM文件C.VSAM文件D.順序文件二、填空題(本大題共10小題，每小題2分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。下列程序段的時(shí)間復(fù)雜度為_(kāi)。(小2)_product=1;for(i=n;i>0;i—)for(j=i+1;j<n;j++)product*=j;已知指針p指向單鏈表中某個(gè)結(jié)點(diǎn)，則語(yǔ)句p->next=p->next->next的作用是。刪除*P的直接后繼結(jié)點(diǎn)假設(shè)元素只能按a,b,c,d的順序依次進(jìn)棧，且得到的出棧序列中的第一個(gè)元素為c，則可能得到的出棧序列為，不可能得到的出棧序列為cbad,cbda,cdbacabd,cadb,cdab若鏈串結(jié)點(diǎn)中的指針占4個(gè)字節(jié)，每個(gè)字符占1個(gè)字節(jié)，則結(jié)點(diǎn)大小為2的鏈串的存儲(chǔ)密度為。2/(4+2)=1/3右圖表示的廣義表為。[img]/離/uploadimages/20046615335847449.jpg[img]((e),((e),(b,c)),(L))若一棵滿三叉樹(shù)中含有121個(gè)結(jié)點(diǎn)，則該樹(shù)的深度為。5//(3"5-1)/(3-1)=121若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的。出度若希望只進(jìn)行8趟排序便能在4800個(gè)元素中找出其中值最小的8個(gè)元素，并且要求排序過(guò)程中所進(jìn)行的關(guān)鍵字比較次數(shù)盡可能少，則應(yīng)該選用排序方法。在含20個(gè)關(guān)鍵字的3階B樹(shù)（2—3樹(shù)）上查找一個(gè)關(guān)鍵字，至多需要訪問(wèn)次外存。文件上的兩類主要操作為和。檢索和維護(hù)三、解答題（本大題共4小題，每小題5分，共20分）設(shè)棧，1的入棧序列為1234（每個(gè)數(shù)字為13個(gè)元素），則不可能得到出棧序列3142。但可通過(guò)增設(shè)棧S2來(lái)實(shí)現(xiàn)。例如，按下圖中的箭頭指示，依次經(jīng)過(guò)棧S1和S2,便可得到序列3142。如果用H1和H2分別表示棧S1和S2的進(jìn)棧操作，用P1和P2分別表示兩個(gè)棧的出棧操作，則得到3142的一個(gè)操作步驟為H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2請(qǐng)仿照上例寫(xiě)出利用兩個(gè)棧從1234得到4132的操作步驟。H1,P1,H2,H1,H1,H1,P1,H2,P2,P2,P1,H2,P2,P1,H2,P2題衛(wèi)7困已知樹(shù)如右圖所示，（1）寫(xiě)出該樹(shù)的后序序列；（2）畫(huà)出由該樹(shù)轉(zhuǎn)換得到的二叉樹(shù)。1）EBJKFGHICDA2）樹(shù)變二叉樹(shù):兄弟相連，保留長(zhǎng)子的連線TOC\o"1-5"\h\z.A./.B./\\.EC./\\.F\\TOC\o"1-5"\h\z.\\\\.KH.\\.I為關(guān)鍵字(17,33,31,40,48)構(gòu)造一個(gè)長(zhǎng)度為7的散列表，設(shè)散列函數(shù)為h(key)=key%7,用開(kāi)放定址法解決沖突的探查序列是hi=(h(key)+i(key%5+1))%70WiW6畫(huà)出構(gòu)造所得的散列表；求出在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。1).0123456.31174833402)(1+1+3+2+4)/5=11/5已知R[1..8]中的元素依次為(12,5,9,20,6,31,24,27)，寫(xiě)出按算法MergeSortDC對(duì)R進(jìn)行自頂向下的二路歸并排序過(guò)程中，前5次調(diào)用函數(shù)Merge(R,low,mid,high)時(shí)參數(shù)low,mid和high的值。voidMergeSortDC(intR[],intlow,inthigh){intmidif(low<high){mid=(low+high)/2;MergeSortDC(R,low,mid);MergeSortDC(R,mid+1,high);Merge(R,low,mid,high);}}//MergeSortDC第一次調(diào)用時(shí)的參數(shù)值；第二次調(diào)用時(shí)的參數(shù)值；第三次調(diào)用時(shí)的參數(shù)值；第四次調(diào)用時(shí)的參數(shù)值；第五次調(diào)用時(shí)的參數(shù)值；〃此題有一定的難度，涉及到遞歸調(diào)用時(shí)，系統(tǒng)堆棧的情況.lowmidhigh1)1122)3343)1244)5565)7786)5867)184四、算法閱讀題(本大題共4小題，每小題5分，共20分)下列函數(shù)的功能是，對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表(表中不存在值相同的數(shù)據(jù)元素)進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。voidunion(LinkListLa,LinkListLb)〃本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La表中LinkListpre=La,q;LinkListpa=La->next;LinkListpb=Lb->next;free(Lb);while(pa&&pd){if(pa->data<pb->data){pre=pa;pa=pa->next;}elseif(pa->data>pb->data){(1);pre=pb;pb=pb->next;;}else{(q);q=pb;pb=pb->next;free(q);}}if(pb);pre->next=pbpre->next=papre->next=pb已知串的存儲(chǔ)結(jié)構(gòu)為動(dòng)態(tài)存儲(chǔ)分配的順序串。閱讀下列算法，并回答問(wèn)題：寫(xiě)出執(zhí)行函數(shù)調(diào)用strc(s,r)的返回結(jié)果，其中s=〃aba〃，r=〃abababa〃；簡(jiǎn)述函數(shù)strc的功能。intstrc(HString*sub,HString*str){inti=0,j,k,count=0;while(i<str->length-sub->length+1){j=i;k=0;

while(k<sub->length&&str->ch[j]==sub->ch[k]){j++；k++;}if(k==sub->length){count++;i=j-sub->length+1;}elsei++;}returncount;}3求串str中子串sub的個(gè)數(shù)下列函數(shù)MDFSForest的功能是，對(duì)一個(gè)采用鄰接矩陣作存儲(chǔ)結(jié)構(gòu)的圖進(jìn)行深度優(yōu)先搜索遍歷，輸出所得深度優(yōu)先生成森林中各條邊。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。#defineMaxMun20〃圖的最大頂點(diǎn)數(shù)typedefstruct{charvexs[MaxNum];〃字符類型的頂點(diǎn)表intedges[MaxNum][MaxNum];〃鄰接矩陣intn,e;〃圖的頂點(diǎn)數(shù)和邊數(shù))MGraph;〃圖的鄰接矩陣結(jié)構(gòu)描述typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxNum];voidMDFSTree(MGraph*G,inti);voidMDFSForest(MGraph*G){inti,k;for(i=0;i<G->n;i++)visited[i]=(1);for(k=0;k<G->n;k++)if(!visited[k])MDFSTree(G,k);voidMDFSTree(MGraph*G,inti)intj;visitedvoidMDFSTree(MGraph*G,inti)intj;visited[i]=TRUE;for(j=0;j<G->n;j++)if(2)printf(〃<%c,%c>〃G->vexs[i],G->vexs[j]);}}FALSE//初始化，所有結(jié)點(diǎn)未訪問(wèn)!visited[j]&&G->edge[i][j]==1//結(jié)點(diǎn)j未訪問(wèn)且i到j(luò)有邊MDFSTree(G,j)〃從j結(jié)點(diǎn)繼續(xù),深度優(yōu)先搜索已知整形數(shù)組L[1..8]中的元素依次為(9,8,5,7,6,3,2,1),閱讀下列函數(shù)，并寫(xiě)出執(zhí)行函數(shù)調(diào)用sort(L,8)時(shí)，對(duì)L進(jìn)行的頭兩趟(pass分別為0和1)處理結(jié)果。Voidsort(intR[],intn){intpass=0,k,exchange,x;do{k=pass%2+1;exchange=0;while(k<n){if(R[k]>R[k+1]){x=R[k];R[k]=R[k+1];R[k+1]=x;exchange=1;}K+=2}pass++;}while}(exchange==1||pass<=1)第一趟（pass=0):89573612第二趟（pass=1）:859五、算法設(shè)計(jì)題（本大題共10分）37162已知二叉排序樹(shù)中結(jié)點(diǎn)的關(guān)鍵字為整數(shù)，設(shè)計(jì)遞歸算法按遞增有序性輸出樹(shù)中所有大于或等于給定值x的結(jié)點(diǎn)，并以函數(shù)的參數(shù)返回輸出的結(jié)點(diǎn)個(gè)數(shù)。假設(shè)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)為：Ichildichild.*3voidfind(BT*root,intx,int*count){if(!root)return;if(root->key>=x)(//因?yàn)槭桥判驑?shù)，只有當(dāng)key>=x時(shí)，才需要查找其左子樹(shù)if(root->Ichild)find(root->lchild,x,count);(*count)++;printf("%d\t",root->key);}if(root->rchild)find(root->rchild,x,count);}全國(guó)2004年10月卷答案一、單項(xiàng)選擇題DABACCCBDAABABD//5.可以簡(jiǎn)單的計(jì)算，空域?yàn)?->7，總共5個(gè)，對(duì)長(zhǎng)則為21-5=167.c//BDBABDABDABBDA123失敗，比較3次BDBABDABDABBDA1失敗，比較1次BDBABDABDABBDA12失敗，比較2次BDBABDABDABBDA1失敗，比較1次BDBABDABDABBDA123成功，比較3次共計(jì)10次10.dA/B/I\CDF二、填空題(一組)運(yùn)算直接前驅(qū)SXSSXXSSXSSXXX模式匹配5n-6N+2N-2+2N-4=5N-6//n階5對(duì)角陣//11100//11110//111110//0111110//00111110//0111110////TOC\o"1-5"\h\z50//63<100<127,最下一層葉子數(shù)：100-63=37//倒數(shù)第2層葉子數(shù):32-:37/2]=13口向上取整徑？待排關(guān)鍵字(記錄)？有序的？?//一些概念題，因?yàn)闆](méi)書(shū)，很久沒(méi)接觸了，可能不準(zhǔn)確。三、解答題略28劃分后左邊:(55)(28)(73)(91)(37)右邊：(64),(19),(82),(46)第一次Merge之后:(28,55)(73)(91)(37)右邊：(64),(19),(82),(46)第二次Merge之后:(28,55)(73,91)(37)右邊：(64),(19),(82),(46)第三次Merge之后:(28,55,73,91)(37)右邊：(64),(19),(82),(46)第四次Merge之后:(28,37,55,73,91)右邊：(64),(19),(82),(46)第五次Merge之后:(28,37,55,73,91)右邊：(19,64),(82),(46)所以.....28,37,55,73,91,19,64,82,46四、算法閱讀題30.p=pre->next;或p=L->next;//p指向第一個(gè)結(jié)點(diǎn)p->next=Lc->next;//數(shù)據(jù)大于c的p結(jié)點(diǎn)插入Lc鏈表表頭p=pre->next;或p=p->next;//下一個(gè)結(jié)點(diǎn)此題有誤，...if((i=!t)!=0)...應(yīng)該是...if((i=!i)!=0)...1,3,5,7,6,4,2堆棧S中的元素依次出棧，奇數(shù)次序的入?！概紨?shù)次序的入隊(duì)。圖G的鄰接矩陣不對(duì)稱，因此，是有向圖5計(jì)算有向圖G中的端點(diǎn)i(第i+1個(gè)端點(diǎn))的度，包括出度和入度O(n)此題明顯有錯(cuò)誤if(low>high)應(yīng)為if(low<high)因?yàn)閕f(){...}里有while(low<high)-8,-3,-2,-1,4,2,5,7:-8-32-1-2457將數(shù)組R中的前n個(gè)數(shù)調(diào)整為所有負(fù)數(shù)在前，所有整數(shù)在后五、算法設(shè)計(jì)題看原型，應(yīng)該是要使用遞歸了，題目很傻地把解法都告訴我們了。f34(BinTreeT,intlevel,int*lmin,int*lmax){if(T)(if(T->lchild==NULL&&T->rchild==NULL){if(*lmin==0||level<*lmin)*lmin=level;if(level>*lmax)*lmax=level;return;}if(T->lchild)f34(T->lchild,level+1,lmin,lmax);if(T->rchlid)f34(T->rchild,level+1,lmin,lmax);}}2005.1全國(guó)卷答案（18號(hào)更新）一、單項(xiàng)選擇題BDBBBADDCACBACC二、填空題O(n)p->next&&p->next->next==NULL410?1100+2*(4*6*7+3*7+2)=1482CBDAn-13//56前面，比56大的數(shù)的個(gè)數(shù)+1表結(jié)點(diǎn)的個(gè)數(shù)lgn三、解答題26.1)(((a),((b),c)))27.[方法1,liangliangzai]b個(gè)非葉子節(jié)點(diǎn)，有k*b個(gè)孩子，加上根節(jié)點(diǎn)，節(jié)點(diǎn)總數(shù)：k*b+1節(jié)點(diǎn)總數(shù)=非葉節(jié)點(diǎn)+葉節(jié)點(diǎn)=a+b得a=(k-1)b+1[方法2]設(shè)滿k叉樹(shù)的高度為n,則：葉子結(jié)點(diǎn)數(shù)a=k"(n-1)非葉結(jié)點(diǎn)數(shù)b=1+k+k"2...+k"(n-2)=:k"(n-1)-1:/(k-1)=>b=(a-1)/(k-1)=>a=(k-1)b+128最短路徑長(zhǎng)度已確定點(diǎn)集最短路徑直接刖趨bcdefbcdef2060*1065(a)aa*aa2060*-30(ae)aa*ae-50*-30(aeb)ab*ae-45110--(aebf)affae--85--(aebfc)afcae.-----(aebfcd)afcae所以a->b20a,b.a->e10a,e.a->f30a,e,f.a->c45a,e,f,c.a->d85a,e,f,c,d29TOC\o"1-5"\h\z4870339224561265487056922433126548925670243312659270566524331248四、算法閱讀題Q->rear==Q->front&&tag==1;if(Q->rear==Q->front)tag=1;Q->rear==Q->front&&tag==0;Q->front==(Q->front+1)%MAXQSIZE;if(Q->rear==Q->front)tag=0;ABDECF2)先根遍歷BT3,3,3,1,1,1,2,2,2swap()調(diào)用6次2)將f口中的元素，所有值為x的放在y前，其他的放在所有y后。(low+high)/2low=mid+1//while循環(huán)結(jié)束時(shí)，low=high+1r>=lowr[low]=x五、算法設(shè)計(jì)題34.voidf35(LinkListh,LinkList*h1,LinkList*h2){LinkListpre=h,p=h->next,ph2;*h1=h;*h2=malloc(sizeof(structPNode));*h2->next=*h2;ph2=*h2;while(p!=h){if((p->exp)%2)(//奇次項(xiàng)保留pre=p;p=pre->next;}else(//偶次項(xiàng)插入*h2pre->next=p->next;//偶次項(xiàng)脫離hph2->next=p;〃尾插入*h2p->next=*h2;ph2=p;p=pre->next;}

全國(guó)2005年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組（K，R），其中K是數(shù)據(jù)元素的有限集合，則R是K上A.操作的有限集合B.映象的有限集合C.類型的有限集合D.關(guān)系的有限集合TOC\o"1-5"\h\z在長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1WiWn）時(shí)，元素移動(dòng)的次數(shù)為（）A.n-i+1B.iC.i+1D.n-i若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則該鏈表為空的判定條件是（）A.head==NULLB.head->next==NULLC.head!=NULLD.head->next==head引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是（）A.出隊(duì)B.入隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素若進(jìn)棧序列為1，2,3,4,5,6,且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是（）A.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，4字符串通常采用的兩種存儲(chǔ)方式是（）A.散列存儲(chǔ)和索引存儲(chǔ)B.索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)C.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)D.散列存儲(chǔ)和順序存儲(chǔ)設(shè)主串長(zhǎng)為n,模式串長(zhǎng)為m（mWn），則在匹配失敗情況下，樸素匹配算法進(jìn)行的無(wú)效位移次數(shù)為（A.mn-mD.n若每個(gè)元素各占3個(gè)存儲(chǔ)單元，且第1個(gè)）n-m+1二維數(shù)組A[12][18]采用列優(yōu)先的存儲(chǔ)方法，元素的地址為150,則元素A[9][7]的地址為（A.429B.432C.435D.438對(duì)廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是()A.(e,f)B.((e,f))C.(f)D.()下列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二叉樹(shù)是(A)

A.mD.n若每個(gè)元素各占3個(gè)存儲(chǔ)單元，且第1個(gè)）|6「a『r|c|mjc]||工["!。I2345675910II1Wn個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有（A.n-1條有向邊C.n（n-1）/2條有向邊對(duì)關(guān)鍵字序列（56，23，78，92，88，67,n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有（A.n-1條有向邊C.n（n-1）/2條有向邊對(duì)關(guān)鍵字序列（56，23，78，92，88，67,）n條有向邊n（n-1）條有向邊34）進(jìn)行增量為3的一趟希爾排序的結(jié)果為()B.(23，56，78，66，88，92，1D.(19，23，67，56，34，78，9A.(19，23，56，34，78，67，88，92)9，34)(19，23，34，56，67，78，88，92)2，88)TOC\o"1-5"\h\z若在9階B-樹(shù)中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為（）A.4B.5C.8D.9由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù)（）其形態(tài)不一定相同，但平均查找長(zhǎng)度相同其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同其形態(tài)均相同，平均查找長(zhǎng)度也都相同ISAM文件和VSAM文件的區(qū)別之一是（）前者是索引順序文件，后者是索引非順序文件前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)前者的存儲(chǔ)介質(zhì)是磁盤，后者的存儲(chǔ)介質(zhì)不是磁盤二、填空題（本大題共10小題，每空2分，共20分）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(diǎn)（存在）應(yīng)執(zhí)行的語(yǔ)句是。B.(23，56，78，66，88，92，1D.(19，23，67，56，34，78，9q=p->pre;q->pre->next=p;p->pre=q->pre;free(q);棧下溢是指在?？諘r(shí)進(jìn)行出棧操作。已知substr(s,i,len)函數(shù)的功能是返回串s中第i個(gè)字符開(kāi)始長(zhǎng)度為len的子串，strlen(s)函數(shù)的功能是返回串s的長(zhǎng)度。若s=〃ABCDEFGHIJK〃，t=〃ABCD〃，執(zhí)行運(yùn)算substr(s,strlen(t),strlen(t))后的返回值為"DEFG"〃注意雙引號(hào)不能少。去除廣義表LS=(a1,a2,…，an)中第1個(gè)元素，由其余元素構(gòu)成的廣義表稱為L(zhǎng)S的—表尾__。已知完全二叉樹(shù)T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹(shù)共有—2"3+7/2=11—個(gè)葉子結(jié)點(diǎn)。在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的入度。當(dāng)關(guān)鍵字的取值范圍是實(shí)數(shù)集合時(shí)，無(wú)法進(jìn)行箱排序和基數(shù)排序。產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞。假設(shè)散列文件中一個(gè)桶能存放m個(gè)記錄，則桶“溢出”的含義是，當(dāng)需要插入新的記錄時(shí)，該桶中已有m個(gè)同義詞記錄―。三、解答題(本大題共4小題，每小題5分，共20分)假設(shè)以數(shù)組seqn[m]存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個(gè)數(shù)。寫(xiě)出隊(duì)滿的條件表達(dá)式；寫(xiě)出隊(duì)空的條件表達(dá)式；設(shè)m=40,rear=13,quelen=19,求隊(duì)頭元素的位置；寫(xiě)出一般情況下隊(duì)頭元素位置的表達(dá)式。quelen==mquelen==0(13-19+40)%40=34(rear-quelen+m)%m已知一棵二叉樹(shù)的中序序列為ABCDEFG，層序序列為BAFEGCD，請(qǐng)畫(huà)出該二叉樹(shù)。(A),B,(CDEFG)(A),B,((CDE),F,(G))B/\AF/\EG/\畫(huà)出下圖所示有向圖的所有強(qiáng)連通分量。3個(gè)：a、bce、dfg29.對(duì)7個(gè)關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。假設(shè)關(guān)鍵字集合為｛1,2,3,4,5,6,7｝，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列;對(duì)所舉序列進(jìn)行快速排序，寫(xiě)出排序過(guò)程。3個(gè)：a、bce、dfg29.對(duì)7個(gè)關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。假設(shè)關(guān)鍵字集合為｛1,2,3,4,5,6,7｝，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列;對(duì)所舉序列進(jìn)行快速排序，寫(xiě)出排序過(guò)程。我們知道，對(duì)n個(gè)關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個(gè)關(guān)鍵字比較。這里要求10次，而7-1+2*(3-1)=法結(jié)束。所以，⑴4或或或10,這就要求2趟快速排序后，算列舉出來(lái)的序列1要求在做partition的時(shí)候，正好將序列平分7(2)自己列吧5:)四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.閱讀下列算法，并回答問(wèn)題：設(shè)順序表L=(3,7,11,14,20,51)，寫(xiě)出執(zhí)行f30(&L,15)之后的L；設(shè)順序表L=(4,7,10,14,20,51)，寫(xiě)出執(zhí)行f30(&L,10)之后的L；簡(jiǎn)述算法的功能。voidf30(SeqList*L,DataTypex){inti=0,j;while(i<L->length&&x>L->data[i])i++;if(i<L->length&&x==L->data[i])(//找到x，則刪除x，大于x的數(shù)前移for(j=i+1;j<L->length;j++)L->data[j-1]=L->data[j];L->length--;}else(//沒(méi)找到，插入乂，大于x的數(shù)后移for(j=L->length;j>i;j--)L->data[j]=L->data[j-1];L->data[i]=x;L->length++;}L=(3,7,11,14,15,20,51)L=(4,7,14,20,51)在順序表L中查找數(shù)x,找到，則刪除x,沒(méi)找到，則在適當(dāng)?shù)奈恢貌迦雭V，插入后，L依然有序.31.已知圖的鄰接表表示的形式說(shuō)明如下：#defineMaxNum50

typedefstructnode{

intadjvex;#defineMaxNum50

typedefstructnode{

intadjvex;*next;〃圖的最大頂點(diǎn)數(shù)structnode}EdgeNode;typedefstructcharvertex;EdgeNode}VertexNode;typedefstructVertexNode〃鄰接點(diǎn)域〃鏈指針域〃邊表結(jié)點(diǎn)結(jié)構(gòu)描述*firstedge;//頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述{adjlist[MaxNum];//頂點(diǎn)域〃邊表頭指針//鄰接表〃鄰接表結(jié)構(gòu)描述〃圖中當(dāng)前的頂點(diǎn)數(shù)和邊intn,e;數(shù)}ALGraph;下列算法輸出圖G的深度優(yōu)先生成樹(shù)(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個(gè)完整的算法?！ㄠ徑颖斫Y(jié)構(gòu)描述〃圖中當(dāng)前的頂點(diǎn)數(shù)和邊typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxNum];voidDFSForest(ALGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=(1);for(i=0;i<G->n;i++)if(!visited[i])DFSTree(G,i);}voidDFSTree(ALGraph*G,inti){EdgeNode*p;visited[i]=TRUE;p=G->adjlist[i].firstedge;while(p!=NULL){if(!visited[p->adjvex]){printf(〃<%c,%c>〃，G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex);(2)}(3)}FALSE〃初始化為未訪問(wèn)DSFTree(G,p->adjvex);〃從相鄰結(jié)點(diǎn)往下繼續(xù)深度搜索p=p->next;〃下一個(gè)未訪問(wèn)的相鄰結(jié)點(diǎn)閱讀下列算法，并回答問(wèn)題：假設(shè)數(shù)組L[8]={3,0,5,1,6,4,2,7}，寫(xiě)出執(zhí)行函數(shù)調(diào)用f32(L,8)后的L；寫(xiě)出上述函數(shù)調(diào)用過(guò)程中進(jìn)行元素交換操作的總次數(shù)。voidf32(intR[],intn){inti,t;for(i=0;i<n-1;i++)while(R[i]!=i){t=R[R[i]];R[R[i]]=R[i];R[i]=t;}}while(){}里是把R[i]和R[R[i]]交換；L=(0,1,2,3,4,5,6,7};5次已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長(zhǎng)度為m,散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)內(nèi)容，使其成為一個(gè)完整算法。voidf33(LinkListL,LinkListH[],intm){//由帶頭結(jié)點(diǎn)的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在inti,j;LinkListp,q;for(i=0;i<m;i++)H[i]=(1);p=L->next;while(p){q=p->next;j=p->key%m;(2);H[j]=p;(3);}free(L);}NULL//初始化p->next=H[j]〃和下面一句完成頭插法

p=q；〃繼續(xù)遍歷L五、算法設(shè)計(jì)題(本大題10分)假設(shè)以帶雙親指針的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)的類型說(shuō)明如下所示：typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;//左右孩子指針structnode*parent;〃指向雙親的指針}BinTNode;typedefBinTNode*BinTree;若px為指向非空二叉樹(shù)中某個(gè)結(jié)點(diǎn)的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點(diǎn)在二叉樹(shù)的中序序列中的后繼。就后繼的不同情況，簡(jiǎn)要敘述實(shí)現(xiàn)求后繼操作的方法；編寫(xiě)算法求px所指結(jié)點(diǎn)的中序序列后繼，并在算法語(yǔ)句中加注注釋。1)*px有右孩子，則其右孩子為其中序序列中的后繼*px無(wú)右孩子，從*px開(kāi)始回溯其祖先結(jié)點(diǎn)，找到第1個(gè)身份為左孩子的結(jié)點(diǎn)，找到，則該結(jié)點(diǎn)的父結(jié)點(diǎn)為*px的中序序列中的后繼。找不到，則無(wú)后繼。2)BinTNode*fintNext(BinTNode{if(px->rchild)returnBinTNode*q,*qp;q=px;while(qp=q->parent){if(2)BinTNode*fintNext(BinTNode{if(px->rchild)returnBinTNode*q,*qp;q=px;while(qp=q->parent){if(qp->lchild==q)q=qp;〃往上回溯}returnNULL;//未找到}*px)px->rchild;//*px有右孩子〃未回溯到根結(jié)點(diǎn)returnqp;〃找到1)b)所述結(jié)點(diǎn)1.根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該元素存儲(chǔ)地址的存儲(chǔ)方法是(D)順序存儲(chǔ)方法B.鏈?zhǔn)酱鎯?chǔ)方法C.索引存儲(chǔ)方法D.散列存儲(chǔ)方法下述程序段中語(yǔ)句①的頻度是(C)s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)①s+=j;A.B.C.D.求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(fù)雜度分別是(C)A.O(n)和O(1)B.O(1)和O(1)C.O(1)和O(n)D.O(n)和O(n)非空的單循環(huán)鏈表的頭指針為head，尾指針為rear，則下列條件成立的是(A)A.rear->next==headB.rear->next->next==headC.head->next==rearD.head->next->next==rear若允許表達(dá)式內(nèi)多種括號(hào)混合嵌套，則為檢查表達(dá)式中括號(hào)是否正確配對(duì)的算法，通常選用的輔助結(jié)構(gòu)是(A)A?棧B.線性表C.隊(duì)列D.二叉排序樹(shù)已知主串s=〃ADBADABBAAB〃，模式串t=〃ADAB〃，則應(yīng)用樸素的串匹配算法進(jìn)行模式匹配過(guò)程中，無(wú)效位移的次數(shù)是(B)A.2B.3C.4D.5串s=〃DataStructure”中長(zhǎng)度為3的子串的數(shù)目是(C)A.9B.11C.12D.14假設(shè)以行優(yōu)先順序存儲(chǔ)三維數(shù)組R[6][9][6]，其中元素R[0][0][0]的地址為2100，且每個(gè)元素占4個(gè)存儲(chǔ)單元，則存儲(chǔ)地址為2836的元素是(B)A.R[3][3][3]B.R[3][3][4]C.R[4][3][5]D.R[4][3][4]除第一層外，滿二叉樹(shù)中每一層結(jié)點(diǎn)個(gè)數(shù)是上一層結(jié)點(diǎn)個(gè)數(shù)的(C)A.1/2倍B.1倍C.2倍D.3倍對(duì)于含n個(gè)頂點(diǎn)和e條邊的圖，采用鄰接矩陣表示的空間復(fù)雜度為(D)A.O(n)B.O(e)C.O(n+e)D.O(n2)如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹(shù)，應(yīng)采用(B)A.深度優(yōu)先搜索算法B.廣度優(yōu)先搜索算法C.求最小生成樹(shù)的prim算法D.拓?fù)渑判蛩惴焖倥判蛟谧顗那闆r下的時(shí)間復(fù)雜度是(B)A.O(n2log2n)B.O(n2)C.O(nlog2n)D.O(log2n)13.能進(jìn)行二分查找的線性表，必須以(A)順序方式存儲(chǔ)，且元素按關(guān)鍵字有序鏈?zhǔn)椒绞酱鎯?chǔ)，且元素按關(guān)鍵字有序順序方式存儲(chǔ)，且元素按關(guān)鍵字分塊有序鏈?zhǔn)椒绞酱鎯?chǔ)，且元素按關(guān)鍵字分塊有序14.為使平均查找長(zhǎng)度達(dá)到最小，當(dāng)由關(guān)鍵字集合(05，11，21，25,37,40,41，62,84｝構(gòu)建二叉排