2001年到2006年自考數(shù)據(jù)結(jié)構(gòu)試題和答案.doc

自考樂園-心境隨緣，誠與天下自考人共勉！ 自考樂園-分享快樂，你的快樂老家！自考樂園-引領(lǐng)成功，你的精神樂園！自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學(xué)習(xí)交流，資料共享平臺.全國2001年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331第一部分 選擇題(30分)一、 單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1算法指的是（ D ） A計算機程序 B解決問題的計算方法 C排序算法 D解決問題的有限運算序列2線性表采用鏈式存儲時，結(jié)點的存儲地址（ B ） A必須是不連續(xù)的 B連續(xù)與否均可 C必須是連續(xù)的 D和頭結(jié)點的存儲地址相連續(xù)3將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（ C） AO（1） BO（n） CO（m） DO（m+n）4由兩個棧共享一個向量空間的好處是：（ D ） A減少存取時間，降低下溢發(fā)生的機率 B節(jié)省存儲空間，降低上溢發(fā)生的機率 C減少存取時間，降低上溢發(fā)生的機率 D節(jié)省存儲空間，降低下溢發(fā)生的機率5設(shè)數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ B ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m6如下陳述中正確的是（ A ） A串是一種特殊的線性表 B串的長度必須大于零 C串中元素只能是字母 D空串就是空白串7若目標串的長度為n，模式串的長度為n/3，則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（ C ） AO（） BO（n） CO（n2） DO（n3）8一個非空廣義表的表頭（ D ） A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子9假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對應(yīng)的稀疏矩陣是（ A ） 10在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2 的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為( C ) A4 B5 C6 D711在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為( D ) Ae B2e Cn2e Dn22e12假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是( C ) AO(n) BO(e) CO(n+e) DO(n*e)13用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ D ） A選擇排序 B希爾排序 C歸并排序 D快速排序14適于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是（ C ）A有序表 B分塊有序表 C三叉排序樹 D線性鏈表15不定長文件是指（ B ）A文件的長度不固定 B記錄的長度不固定C字段的長度不固定 D關(guān)鍵字項的長度不固定第二部分 非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 存儲結(jié)構(gòu) 無關(guān)，是獨立于計算機的。17在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head= p-next-next 。18棧頂?shù)奈恢檬请S著 進棧和退棧 操作而變化的。19在串S=“structure”中，以t為首字符的子串有 12 個。20假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B0存儲矩陣中第1個元素a1,1,則B31中存放的元素是 。21已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有 個葉子結(jié)點。 22已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相 應(yīng)的廣度優(yōu)先遍歷序列為 abefcdg 。 23在單鏈表上難以實現(xiàn)的排序方法有 快速排序 和 堆排序 。 24在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為 2 。 25多重表文件和倒排文件都歸屬于 多關(guān)鍵字 文件。 三、解答題（本大題共4小題，每小題5分，共20分）26畫出下列廣義表的共享結(jié)構(gòu)圖形表示 P=（z）,(x,y)）,(x,y),x),(z)）27請畫出與下列二叉樹對應(yīng)的森林。 28已知一個無向圖的頂點集為a, b, c, d, e ,其鄰接矩陣如下所示ab cde (1)畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。29已知一個散列表如下圖所示：3520334859 0 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回答下列問題：（1）對表中關(guān)鍵字35，20，33和48進行查找時，所需進行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？四、算法閱讀題（本大題共4小題，每小題5分，共20分）30下列算法的功能是比較兩個鏈串的大小，其返回值為： comstr(s1,s2)= 請在空白處填入適當(dāng)?shù)膬?nèi)容。int comstr(LinkString s1,LinkString s2) /s1和s2為兩個鏈串的頭指針 while(s1&s2) if(s1datedate)return1； if(s1dates2date)return1； ； ； if( )return1； if( )return1； ； 31閱讀下面的算法 LinkList mynote(LinkList L) /L是不帶頭結(jié)點的單鏈表的頭指針 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。32假設(shè)兩個隊列共享一個循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typedef struct DateType dataMaxSize； int front2,rear2； Queue2；對于i=0或1，fronti和reari分別為第i個隊列的頭指針和尾指針。請對以下算法填空，實現(xiàn)第i個隊列的入隊操作。 int EnQueue (Queue2*Q,int i,DateType x) /若第 i個隊列不滿，則元素x入隊列，并返回1；否則返回0 if(i1)return 0； if(Qreari=Qfront return0； Qdata =x； Qreari= ; return1； 33已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。 typedef struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) LinkList s； If(T) Inorder(Tlchild)； If (!Tlchild)&(!Trchild) s=(ListNode*)malloc(sizeof(ListNode)； sdata=Tdata； snext=Leafhead； Leafhead=s； Inorder(Trchild)； 對于如下所示的二叉樹 （1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)； （2）說明該算法的功能。五、算法設(shè)計題（本題共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=x)j-； while(i=x)i+； if(ij) t=aj；aj=ai；ai=t； if(ainext s2=s2next s2(或s2!=NULL或s2&!s1) s1(或s1!=NULL或s1&!s2) return 031.（1）查詢鏈表的尾結(jié)點 （2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點 （3）返回的線性表為（a2,a3,an,a1）32. (i1)%2(或1i) Qreari (Qreari)%Maxsize33.(1)LeafheadFHGD （2）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點數(shù)據(jù)域的值構(gòu)建一個以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結(jié)點數(shù)據(jù)自右至左鏈接成一個鏈表）。五、算法設(shè)計題（本題共10分） 34（1）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有x的元素均落在a1.i上，使所有x的元素均落在ai1.h上。 （2）int f(int b,int n) 或 int f(int b,int n) int p,q； int p,q； p=arrange(b,0,n1,0)； p=arrange(b,0,n1,1)； q= arrange(b,p+1,n1,1)； q= arrange(b,0,p,0)； return qp； return pq； 2003.1數(shù)據(jù)結(jié)構(gòu)試題 一、單項選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內(nèi)) 1.下面程序段的時間復(fù)雜度是( D ) for(i=0;i<n;i+) for(j=1;j<m;j+) Aij=0； A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n) 2.在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是( B ) A.p=p->next; B.p->next=p->next->next;C.p->next=p; D.p=p->next->next; 3.在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結(jié)點，若p->next->next= head,則( D ) A.p指向頭結(jié)點 B.p指向尾結(jié)點 C.*p的直接后繼是頭結(jié)點 D.*P的直接后繼是尾結(jié)點4.判定“帶頭結(jié)點的鏈隊列為空”的條件是( C ) A.Q.front=NULL B.Q.rear=NULL C.Q.front=Q.rear D.Q.front!=Q.rear5.設(shè)有兩個串T和P，求P在T中首次出現(xiàn)的位置的串運算稱作( D ) A.聯(lián)接 B.求子串 C.字符定位 D.子串定位6.廣義表A=(a,(b),(),(c,d,e)的長度為( A ) A.4 B.5 C.6 D.7 7.一棵含18個結(jié)點的二叉樹的高度至少為( C ) A.3 B.4 C.5 D.6 8.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( D ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.無向圖中一個頂點的度是指圖中( B ) A.通過該頂點的簡單路徑數(shù) B.與該頂點相鄰接的頂點數(shù) C.通過該頂點的回路數(shù) D.與該頂點連通的頂點數(shù) 10.已知一個圖如下所示，從頂點a出發(fā)進行廣度優(yōu)先遍歷可能得到的序列為( C ) A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e 11.在下列排序方法中，平均時間性能為O(nlogn)且空間性能最好的是( B ) A.快速排序 B.堆排序 C.歸并排序 D.基數(shù)排序 12.已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35，其中每相鄰兩個為有序子序列。對這些子序列進行一趟兩兩歸并的結(jié)果是( A ) A.25,36,48,72,23,40,79,82,16,35 B.25,36,48,72,16,23,40,79,82,35 C.25,36,48,72,16,23,35,40,79,82 D.16,23,25,35,36,40,48,72,79,82 13.設(shè)順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為( B ) A.21 B.23 C.41 D.62 14.索引非順序文件的特點是( A ) A.主文件無序，索引表有序 B.主文件有序，索引表無序 C.主文件有序，索引表有序 D.主文件無序，索引表無序 15.倒排文件的主要優(yōu)點是( C ) A.便于進行插入和刪除運算 B.便于進行文件的恢復(fù) C.便于進行多關(guān)鍵字查詢 D.節(jié)省存儲空間 二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分) 16.抽象數(shù)據(jù)類型的特點是將_數(shù)據(jù)_和_運算_封裝在一起，從而現(xiàn)實信息隱藏。 17.從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需_前移_一個位置。 18.在隊列中，允許進行插入操作的一端稱為_隊尾_，允許進行刪除操作的一端稱為_隊頭_。 19.如圖兩個棧共享一個向量空間，top1和top2分別為指向兩個棧頂元素的指針，則“棧滿” 的判定條件是_top1=top2-1_。 20.設(shè)S1="good",S2=" ",S3="book"，則S1，S2和S3依次聯(lián)接后的結(jié)果是_ good book_。 21.假設(shè)三維數(shù)組A1098按行優(yōu)先順序存儲，若每個元素占3個存儲單元，且首地址為100，則元素A987的存儲地址是_2257_。 22.已知在一棵含有n個結(jié)點的樹中，只有度為k的分支結(jié)點和度為0的葉子結(jié)點，則該樹中含有的葉子結(jié)點的數(shù)目為_（(n-1)/k）*(k-1)+1_或 n - (n-1)/k_。 23.能夠成功完全拓撲排序的圖一定是一個_有向無環(huán)圖_。 24.如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用_堆排序_較為適當(dāng)。 25.假設(shè)哈希表的表長為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達為_hi=(H(key)+I)/m_。 三、解答題(本大題共4小題，每小題5分，共20分) 26.假設(shè)通信電文使用的字符集為a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個字符設(shè)計哈夫曼編碼。請先畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點的權(quán)值小于右孩子結(jié)點的權(quán)值)，然后分別寫出每個字符對應(yīng)的編碼。27.已知一個圖如下所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優(yōu)先遍歷時得到的頂點序列為acbefd，進行廣度優(yōu)先遍歷時得到的頂點序列為acbdfe。 答案： 28.已知兩個45的稀疏矩陣的三元組表分別如下： 0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 22 2 3 4 25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 請畫出這兩個稀疏矩陣之和的三元組表。 解: 29.從空樹起，依次插入關(guān)鍵字40，8，90，15，62，95，12，23，56，32，構(gòu)造一棵二叉排序樹。 (1)畫出該二叉排序樹 (2)畫出刪去該樹中元素值為90的結(jié)點之后的二叉排序樹。 四、算法閱讀題(本大題共4小題，每小題5分，共20分) 30.如圖所示，利用同一循環(huán)向量空間實現(xiàn)兩個隊列，其類型Queue2定義如下： typedef struct DataType dataMaxSize; int front2,length2; Queue2; 對于i=0或1,fronti和lengthi分別為第i個隊列的頭指針和長度域。請在空缺處填入合適的內(nèi)容，實現(xiàn)第i個循環(huán)隊列的入隊操作。 int EnQueue(Queue2*Q,int i,DataType x) /若第i個隊列不滿，則元素x入隊列，并返回1，否則返回0if(i<0|i>1)return 0; if( (1) ) return 0; Q->data (2) =x; Q->length (3) +; return 1; 解: (1) (Q->fronti+Q->lengthi%Maxsize=Q->front(i+1)%2 (2) (Q->fronti+->lengthi%Maxsize (3) I 31.某二叉樹的線索鏈表存儲結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點的指針，圖(a)為結(jié)點結(jié)構(gòu)。 閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果； (2)簡述函數(shù)f的功能。 void f(BinThrTree t) while(t) printf(t->data); if(t->lchild) t=t->lchild; else t=t->rchild; 答案（1）ABDFCEGH (2) 先根遍歷32.下列函數(shù)FindCycle(G,i)的功能是，對一個采用鄰接表作存儲結(jié)構(gòu)的有向圖G，利用深度優(yōu)先搜索策略尋找一條經(jīng)過頂點vi的簡單回路。數(shù)組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=j(j0)表示在回路中頂點vk的下一個頂點是vj。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。 vertex firstedge 已知鄰接表的頂點表結(jié)點結(jié)構(gòu)為： adjvex next 邊表結(jié)點EdgeNode結(jié)構(gòu)為： int cycle_pathMaxNum; int FindCycle(ALGraph*G,int i) /若回路存在，則返回1，否則返回0 int j; for(j=0;j<G->n;j+)cycle_pathj=-1; return DFSPath(G,i,i); int DFSPath(ALGraph*G,int j,int i) EdgeNode *p; int cycled=0; for(p=G->adjlistj.firstedge;p&!cycled;p=p->next) cycle_pathj=p->adjvex; if( (1 ) )cycled=1;/已找到回路 else if(cycle_pathp->adjvex=-1)cycled= (2) ; return (3) (1) (2) (3) 32題答案： （1）p->adjvex=i (2)DFSpath(G,p->adjvex,i) (3)cycled33.閱讀下列函數(shù)algo,并回答問題。 (1)假設(shè)整型數(shù)組A1.8中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數(shù)調(diào)用algo(A,8)時，外層while的循環(huán)體執(zhí)行多少次?函數(shù)的返回值是多少? (2)簡述函數(shù)algo(L,n)的功能。 int algo(int L,intn) int i=0,j,s=1,t=n; while (i!=(n+1)/2) int x=Ls； i=s;j=t; while(i<j) while(i<j & Lj>=x)j-; Li=Lj; while(i<j & Li<=x)i+; Lj=Li; Li=x; if(i<(n+1)/2)s=i+1; else t=i-1; if(i=0)return 0; else return Li; (1) (2) (3) 33題答案： （1）外循環(huán)執(zhí)行4次，函數(shù)返回值為3。 （2）將A1至A8中不小于A1的元素進行遞增排序，如調(diào)用algo(A,8)時最終排序結(jié)果為2 1 3 4 6 7 8 9 五、算法設(shè)計題(本大題共10分) 34.假設(shè)以帶頭結(jié)點的單循環(huán)鏈表作非遞減有序線性表的存儲結(jié)構(gòu)。請設(shè)計一個時間復(fù)雜度為O(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點空間。例如： (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月全國數(shù)據(jù)結(jié)構(gòu)試題 （2006-7-25 2:07:00） 1.計算機識別、存儲和加工處理的對象被統(tǒng)稱為(b)A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型2.在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復(fù)雜度是(b)A.O(1)B.O(n)C.O(nlogn)D.O(n2)3.隊和棧的主要區(qū)別是(d)A.邏輯結(jié)構(gòu)不同B.存儲結(jié)構(gòu)不同C.所包含的運算個數(shù)不同D.限定插入和刪除的位置不同4.鏈棧與順序棧相比，比較明顯的優(yōu)點是(d)A.插入操作更加方便B.刪除操作更加方便C.不會出現(xiàn)下溢的情況D.不會出現(xiàn)上溢的情況5.采用兩類不同存儲結(jié)構(gòu)的字符串可分別簡稱為(b)A.主串和子串B.順序串和鏈串C.目標串和模式串D.變量串和常量串6.在目標串T0.n-1=xwxxyxy中，對模式串P0.m-1=xy進行子串定位操作的結(jié)果是(c)A.0B.2C.3D.57.已知廣義表的表頭為a，表尾為(b,c)，則此廣義表為(b)A.(a,(b,c)B.(a,b,c)C.(a),b,c)D.(a,b,c)8.二維數(shù)組A按行優(yōu)先順序存儲，其中每個元素占1個存儲單元。若A11的存儲地址為420，A33的存儲地址為446，則A55的存儲地址為(c)A.470B.471C.472D.4739.二叉樹中第5層上的結(jié)點個數(shù)最多為(d)A.8B.15C.16D.3210.下列編碼中屬前綴碼的是(a)A.1,01,000,001B.1,01,011,010C.0,10,110,11D.0,1,00,1111.如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是(d)A.有向完全圖B.連通圖C.強連通圖D.有向無環(huán)圖12.對n個關(guān)鍵字的序列進行快速排序，平均情況下的空間復(fù)雜度為(d)A.O(1)B.O(logn)C.O(n)D.O(nlogn)13.對表長為n的順序表進行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為(n/2)A.B.C.D.n14.對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是(d)A.35和41B.23和39C.15和44D.25和5115.稠密索引是在索引表中()A.為每個記錄建立一個索引項B.為每個頁塊建立一個索引項C.為每組記錄建立一個索引項D.為每個字段建立一個索引項二、填空題（每小題2分，若有兩個空格，每個空格1分，共20分）16.當(dāng)問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的_(_時間復(fù)雜度_)_。17.在鏈表的結(jié)點中，數(shù)據(jù)元素所占的存儲量和整個結(jié)點所占的存儲量之比稱作_(存儲密度)_。datenext18.已知鏈棧的結(jié)點結(jié)構(gòu)為棧頂指針為top，則實現(xiàn)將指針p所指結(jié)點插入棧頂?shù)恼Z句依次為_和_。19.空串的長度是_0_；空格串的長度是_(空格的數(shù)目_)_。20.假設(shè)一個6階的下三角矩陣B按列優(yōu)先順序壓縮存儲在一維數(shù)組A中，其中A0存儲矩陣的第一個元素b11,則A14存儲的元素是_b63_。21.在一棵度為3的樹中，度為2的結(jié)點個數(shù)是1，度為0的結(jié)點個數(shù)是6，則度為3的結(jié)點個數(shù)是_2_。22.如圖所示的有向無環(huán)圖可以排出_種不同的拓撲序列。 23.利用篩選法將關(guān)鍵字序列(37，66，48，29，31，75)建成的大根堆為(_75,66,48,29,31,37_)。24.對長度為20的有序表進行二分查找的判定樹的高度為_5_。25.在多重表文件中，次關(guān)鍵字索引的組織方式是將_的記錄鏈接成一個鏈表。26.對于單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結(jié)點的指針p，能否將p所指結(jié)點的數(shù)據(jù)元素與其確實存在的直接前驅(qū)交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。datenext單鏈表和單循環(huán)鏈表的結(jié)點結(jié)構(gòu)為priordatenext雙向鏈表的結(jié)點結(jié)構(gòu)為(1)單鏈表:(不可以,無法找到前驅(qū)接點)(2)單循環(huán)鏈表(可以:q=p-next;while(q-next!=p)q=q-next;q-datap-data;(3)雙向鏈表(可以:p-prior-datap-data;)27.假設(shè)通信電文使用的字符集為a,b,c,d,e,f,g，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。(1)請根據(jù)哈夫曼編碼畫出此哈夫曼樹，并在葉子結(jié)點中標注相應(yīng)字符；(2)若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權(quán)路徑長度。28.當(dāng)采用鄰接表作為圖的存儲結(jié)構(gòu)時，也可將鄰接表中的頂點表由順序結(jié)構(gòu)改為鏈表結(jié)構(gòu)。(1)請分別畫出這種鄰接表的頂點鏈表結(jié)點和邊表結(jié)點，并說明結(jié)點中各個域的作用；(2)對如圖所示的有向圖畫出這種鄰接表。29.已知4階B-樹如圖所示。(1)分別畫出將關(guān)鍵字23和89相繼插入之后的B-樹。(2)畫出從插入之前的B-樹中刪除關(guān)鍵字51之后的B-樹。四、算法閱讀題(每小題5分，共20分)30.閱讀下列函數(shù)algo,并回答問題：(1)假設(shè)隊列q中的元素為(2,4,5,7,8),其中“2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊列q；(2)簡述算法algo的功能。voidalgo(Queue*Q)StackS;InitStack(&S);while(!QueueEmpty(Q)Push(&S,DeQueue(Q);while(!StackEmpty(&S)nQueue(Q,Pop(&S);(1)87542(2)隊列倒置31.閱讀下列函數(shù)F，并回答問題：(1)已知如圖所示的二叉樹以二叉鏈表作存儲結(jié)構(gòu)，rt為指向根結(jié)點的指針。寫出執(zhí)行函數(shù)調(diào)用F(rt)的輸出結(jié)果。(2)說明函數(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)(2)前序遍歷二叉數(shù)vertexfirstedge32.已知鄰接表的頂點表結(jié)點結(jié)構(gòu)為adjvexnext邊表結(jié)點EdgeNode的結(jié)構(gòu)為下列算法計算有向圖G中頂點vi的入度。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。intFindDegree(ALGraph*G,inti)/ALGraph為圖的鄰接表類型intdgree,j;EdgeNode*p;degree=(1);for(j=0;jn;j+)p=G-adjlistj.firstedge;while(2)if(3)degree+;break;p=p-next;returndegree;(1)degree=0;(2)p(3)p-adj=vidatanext33.已知單鏈表的結(jié)點結(jié)構(gòu)為下列算法對帶頭結(jié)點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。請在空缺處填入合適的內(nèi)容，使其成為完整的算法。voidSelectSort(LinkedListL)LinkedListp,q,min;DataTypercd;p=(1);while(p!=NULL)min=p;q=p-next;while(q!=NU