自考數據結構歷年試題及答案

1、第一部分 選擇題(30分)一、 單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內。1算法指的是（D ） A計算機程序 B解決問題的計算方法 C排序算法 D解決問題的有限運算序列2線性表采用鏈式存儲時，結點的存儲地址（ B ） A必須是不連續(xù)的 B連續(xù)與否均可 C必須是連續(xù)的 D和頭結點的存儲地址相連續(xù)3將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（C ） AO（1） BO（n） CO（m） DO（m+n）4由兩個棧共享一個向量空間的好處是：（ B ） A減少存取時間，降低下溢發(fā)生的

2、機率 B節(jié)省存儲空間，降低上溢發(fā)生的機率 C減少存取時間，降低上溢發(fā)生的機率 D節(jié)省存儲空間，降低下溢發(fā)生的機率5設數組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ D ） 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í)行模式匹配算法時，在最壞情況下的時間

3、復雜度是（ ） AO（） BO（n） CO（n2） DO（n3）8一個非空廣義表的表頭（ D ） A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子9假設以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對應的稀疏矩陣是（ ） 10在一棵度為3的樹中,度為3的結點個數為2,度為2 的結點個數為1,則度為0的結點個數為( C ) A4 B5 C6 D711在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數為( D ) Ae B2e Cn2e Dn22e12假設一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間復雜度是( ) AO(n) BO(

4、e) CO(n+e) DO(n*e)13用某種排序方法對關鍵字序列（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 則所采用的排序方法是（ ） A選擇排序 B希爾排序 C歸并排序 D快速排序14適于對動態(tài)查找表進行高效率查找的組織結構是（ C ）A有序表 B分塊有序表 C三叉排序樹 D線性鏈表15不定長文件是指（ B ）A文件的長度不固定 B記錄的長度不固定C字段的長度不固定 D關鍵字項的長度不

5、固定第二部分 非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內。錯填或不填均無分。16數據的邏輯結構是從邏輯關系上描述數據，它與數據的 存儲機構 無關，是獨立于計算機的。17在一個帶頭結點的單循環(huán)鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為head= p-nect-next 。18棧頂的位置是隨著 進棧出棧 操作而變化的。19在串S=“structure”中，以t為首字符的子串有 12 個。20假設一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數組B中，其中B0存儲矩陣中

6、第1個元素a1,1,則B31中存放的元素是 。21已知一棵完全二叉樹中共有768結點，則該樹中共有 個葉子結點。 22已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相 23在單鏈表上難以實現(xiàn)的排序方法有 和 。 24在有序表（12，24，36，48，60，72，84）中二分查找關鍵字72時所需進行的關鍵字比較次數為 2 。 25多重表文件和倒排文件都歸屬于 多關鍵字 文件。 三、解答題（本大題共4小題，每小題5分，共20分）26畫出下列廣義表的共享結構圖形表示 P=（z）,(x,y)）,(x,y),x),(z)）27請畫出與下列二叉樹對應的森林。 28已知一個無向圖的頂點集為a, b, c, d

7、, e ,其鄰接矩陣如下所示ab cde (1)畫出該圖的圖形； （2）根據鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。29已知一個散列表如下圖所示：3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key)%m =0,1,，m1其中 h1(key)=key%11+1回答下列問題：（1）對表中關鍵字35，20，33和48進行查找時，所需進行的比較次數各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？四、算法

8、閱讀題（本大題共4小題，每小題5分，共20分）30下列算法的功能是比較兩個鏈串的大小，其返回值為： comstr(s1,s2)= 請在空白處填入適當的內容。int comstr(LinkString s1,LinkString s2) /s1和s2為兩個鏈串的頭指針 while(s1&&s2) if(s1>date<s2>date)return1； if(s1>date>s2>date)return1； ； ； if( )return1； if( )return1； ； 31閱讀下面的算法 LinkList mynote(LinkList L

9、) /L是不帶頭結點的單鏈表的頭指針 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； return L； 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。32假設兩個隊列共享一個循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typedef struct DateType dataMaxSi

10、ze； 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(i<0|i>1)return 0； if(Q>reari=Q>front return0； Q>data =x； Q>reari= ; return1； 33已知二叉樹的存儲結構為二叉鏈表，閱讀下面算法。 typedef struct no

11、de DateType data； Struct node * next； ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) LinkList s； If(T) Inorder(T>lchild)； If (!T>lchild)&&(!T>rchild) s=(ListNode*)malloc(sizeof(ListNode)； s>data=T>data； s>next=Leafhead； Leafhead=s；

12、Inorder(T>rchild)； 對于如下所示的二叉樹 （1）畫出執(zhí)行上述算法后所建立的結構； （2）說明該算法的功能。五、算法設計題（本題共10分）34閱讀下列函數arrange() int arrange(int a,int 1,int h,int x) /1和h分別為數據區(qū)的下界和上界 int i,j,t； i=1；j=h； while(i<j) while(i<j && aj>=x)j-； while(i<j && aj>=x)i+； if(i<j) t=aj；aj=ai；ai=t； if(ai<x)

13、return i； else return i1； （1）寫出該函數的功能； （2）寫一個調用上述函數實現(xiàn)下列功能的算法：對一整型數組bn中的元素進行重新排列，將所有負數均調整到數組的低下標端，將所有正數均調整到數組的高下標端，若有零值，則置于兩者之間，并返回數組中零元素的個數。一、 單項選擇題（本大題共15小題，每小題2分，共30分） 1D，101112131415二、填空題（本大題共10小題，每小題2分，共20分）16存儲（或存儲結構）17.pnextnext18進棧和退棧191220a4,82138422abefcdg23快速排序、堆排序、希爾排序2425.多關鍵字三、解答題（本大題共4

14、小題，每小題5分，共20分）26 圖1 圖22728該圖的圖形為： 深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29（）對關鍵字35、20、33和48進行查找的比較次數為、； （）平均查找長度四、算法閱讀題（本大題共4小題，每小題5分，共20分）30 S1=S1>next s2=s2>next s2(或s2!=NULL或s2&&!s1) s1(或s1!=NULL或s1&&!s2) return 031.（1）查詢鏈表的尾結點 （2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點 （3）返回的線性表為（a2,a3,an,a1）32. (i

15、1)%2(或1i) Q>reari (Q>reari)%Maxsize33.(1)LeafheadFHGD （2）中序遍歷二叉樹，按遍歷序列中葉子結點數據域的值構建一個以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結點數據自右至左鏈接成一個鏈表）。五、算法設計題（本題共10分） 34（1）該函數的功能是：調整整數數組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

16、=arrange(b,0,n1,1)； q= arrange(b,p+1,n1,1)； q= arrange(b,0,p,0)； return qp； return pq； 2003.1數據結構試題 一、單項選擇題(本大題共15小題，每小題2分，共30分。在每小題的四個備選答案中，選出一個正確答案，并將正確答案的序號填在題干的括號內) 1.下面程序段的時間復雜度是( D ) for(i=0;i&lt;n;i+) for(j=1;j&lt;m;j+) Aij=0； A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n) 2.在單鏈表中，指針p指向元素為x的結點，實

17、現(xiàn)“刪除x的后繼”的語句是( B ) A.p=p-&gt;next; B.p-&gt;next=p-&gt;next-&gt;next;C.p-&gt;next=p; D.p=p-&gt;next-&gt;next; 3.在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結點，若p-&gt;next-&gt;next= head,則( D ) A.p指向頭結點 B.p指向尾結點 C.*p的直接后繼是頭結點 D.*P的直接后繼是尾結點4.判定“帶頭結點的鏈隊列為空”的條件是( C ) A.Q.front=NUL

18、L B.Q.rear=NULL C.Q.front=Q.rear D.Q.front!=Q.rear5.設有兩個串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個結點的二叉樹的高度至少為( C ) A.3 B.4 C.5 D.6 8.已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( D ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.無向圖中一個頂點的度是指圖中( B

19、 ) A.通過該頂點的簡單路徑數 B.與該頂點相鄰接的頂點數 C.通過該頂點的回路數 D.與該頂點連通的頂點數 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.基數排序 12.已知一組關鍵字為25,48,36,72,79,82,23,40,16,35，其中每相鄰兩個為有序子序列。對這些子序列進行一趟兩兩歸并的結果是( A )

20、 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.設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為( B ) A.21 B.23 C.41 D.62 14.索引非順序文件的特點是( A ) A.主文件無序，索引表有序 B.主文件有序，索引表無序 C.主文

21、件有序，索引表有序 D.主文件無序，索引表無序 15.倒排文件的主要優(yōu)點是( C ) A.便于進行插入和刪除運算 B.便于進行文件的恢復 C.便于進行多關鍵字查詢 D.節(jié)省存儲空間 二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分) 16.抽象數據類型的特點是將_數據_和_運算_封裝在一起，從而現(xiàn)實信息隱藏。 17.從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需_前移_一個位置。 18.在隊列中，允許進行插入操作的一端稱為_隊尾_，允許進行刪除操作的一端稱為_隊頭_。 19.如圖兩個棧共享一個向量空間，top1和top2分別為指向兩個棧頂元素的指針，則

22、“棧滿” 的判定條件是_top1=top2-1_。 20.設S1=&quot;good&quot;,S2=&quot; &quot;,S3=&quot;book&quot;，則S1，S2和S3依次聯(lián)接后的結果是_ good book_。 21.假設三維數組A1098按行優(yōu)先順序存儲，若每個元素占3個存儲單元，且首地址為100，則元素A987的存儲地址是_2257_。 22.已知在一棵含有n個結點的樹中，只有度為k的分支結點和度為0的葉子結點，則該樹中含有的葉子結點的數目為_（(n-1)/k）*(k-1)+1_或 n - (n-1)/k_。 23.

23、能夠成功完全拓撲排序的圖一定是一個_有向無環(huán)圖_。 24.如果在排序前，關鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用_堆排序_較為適當。 25.假設哈希表的表長為m，哈希函數為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達為_hi=(H(key)+I)/m_。 三、解答題(本大題共4小題，每小題5分，共20分) 26.假設通信電文使用的字符集為a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個字符設計哈夫曼編碼。請先畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值小于右孩子結點的權值)，然后分別寫出每個字符對應的

24、編碼。27.已知一個圖如下所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優(yōu)先遍歷時得到的頂點序列為acbefd，進行廣度優(yōu)先遍歷時得到的頂點序列為acbdfe。 答案： 28.已知兩個4×5的稀疏矩陣的三元組表分別如下： 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.從空樹起，依次插入關鍵字40，8，90，15，62，95，12，23，56，32，構造一棵二叉排

25、序樹。 (1)畫出該二叉排序樹 (2)畫出刪去該樹中元素值為90的結點之后的二叉排序樹。 四、算法閱讀題(本大題共4小題，每小題5分，共20分) 30.如圖所示，利用同一循環(huán)向量空間實現(xiàn)兩個隊列，其類型Queue2定義如下： typedef struct DataType dataMaxSize; int front2,length2; Queue2; 對于i=0或1,fronti和lengthi分別為第i個隊列的頭指針和長度域。請在空缺處填入合適的內容，實現(xiàn)第i個循環(huán)隊列的入隊操作。 int EnQueue(Queue2*Q,int i,DataType x) /若第i個隊列不滿，則元素x入

26、隊列，并返回1，否則返回0if(i&lt;0|i&gt;1)return 0; if( (1) ) return 0; Q-&gt;data (2) =x; Q-&gt;length (3) +; return 1; 解: (1) (Q-&gt;fronti+Q-&gt;lengthi%Maxsize=Q-&gt;front(i+1)%2 (2) (Q-&gt;fronti+-&gt;lengthi%Maxsize (3) I 31.某二叉樹的線索鏈表存儲結構如圖(b)所示，其中p為指向根結點的指針，圖(a)為結點結構。

27、閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數調用f(p)的輸出結果； (2)簡述函數f的功能。 void f(BinThrTree t) while(t) printf(t-&gt;data); if(t-&gt;lchild) t=t-&gt;lchild; else t=t-&gt;rchild; 答案（1）ABDFCEGH (2) 先根遍歷32.下列函數FindCycle(G,i)的功能是，對一個采用鄰接表作存儲結構的有向圖G，利用深度優(yōu)先搜索策略尋找一條經過頂點vi的簡單回路。數組cycle_path用于保存搜索過程中形成的回路，cycle_pathk=

28、j(j0)表示在回路中頂點vk的下一個頂點是vj。請在空缺處填入合適的內容，使其成為一個完整的算法。 vertex firstedge 已知鄰接表的頂點表結點結構為： adjvex next 邊表結點EdgeNode結構為： int cycle_pathMaxNum; int FindCycle(ALGraph*G,int i) /若回路存在，則返回1，否則返回0 int j; for(j=0;j&lt;G-&gt;n;j+)cycle_pathj=-1; return DFSPath(G,i,i); int DFSPath(ALGraph*G,int j,int i) Edg

29、eNode *p; int cycled=0; for(p=G-&gt;adjlistj.firstedge;p&&!cycled;p=p-&gt;next) cycle_pathj=p-&gt;adjvex; if( (1 ) )cycled=1;/已找到回路 else if(cycle_pathp-&gt;adjvex=-1)cycled= (2) ; return (3) (1) (2) (3) 32題答案： （1）p-&gt;adjvex=i (2)DFSpath(G,p-&gt;adjvex,i) (3)cycled33

30、.閱讀下列函數algo,并回答問題。 (1)假設整型數組A1.8中的元素依次為(3，8，9，1，7，4，2，6)。執(zhí)行函數調用algo(A,8)時，外層while的循環(huán)體執(zhí)行多少次?函數的返回值是多少? (2)簡述函數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&lt;j) while(i&lt;j && Lj&gt;=x)j-; Li=Lj; while(i&lt;j && L

31、i&lt;=x)i+; Lj=Li; Li=x; if(i&lt;(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次，函數返回值為3。 （2）將A1至A8中不小于A1的元素進行遞增排序，如調用algo(A,8)時最終排序結果為2 1 3 4 6 7 8 9 五、算法設計題(本大題共10分) 34.假設以帶頭結點的單循環(huán)鏈表作非遞減有序線性表的存儲結構。請設計一個時間復雜度為O(n)的算法，刪除表中所有數值相同的多余元素，并釋放結點空間。例如： (7，1

32、0，10，21，30，42，42，42，51，70) 經算法操作后變?yōu)?(7，10，21，30，42，51，70) 34題答案： Exam4(Linklist,L) listnode *p,*q; p=L-&gt;next; while(p!=L)q=p-&gt;next; while(q&&q-&gt;data=p-&gt;data) p-&gt;next=q-&gt;next; free(q); q=p-&gt;next; p-&gt;next; 2003年10月全國數據結構試題 （2006-7-25 2:07

33、:00） 1.計算機識別、存儲和加工處理的對象被統(tǒng)稱為(   b   )A.數據                            B.數據元素C.數據結構        &#

34、160;               D.數據類型2.在具有n個結點的有序單鏈表中插入一個新結點并使鏈表仍然有序的時間復雜度是(  b    )A.O(1)                   

35、60;        B.O(n)C.O(nlogn)                        D.O(n2)3.隊和棧的主要區(qū)別是(  d    )A.邏輯結構不同    

36、                        B.存儲結構不同C.所包含的運算個數不同                    D.限定插入和刪除的位置不同4.

37、鏈棧與順序棧相比，比較明顯的優(yōu)點是(  d    )A.插入操作更加方便                        B.刪除操作更加方便C.不會出現(xiàn)下溢的情況           

38、60;        D.不會出現(xiàn)上溢的情況5.采用兩類不同存儲結構的字符串可分別簡稱為(   b   )A.主串和子串                            B.

39、順序串和鏈串C.目標串和模式串                        D.變量串和常量串6.在目標串T0.n-1=xwxxyxy中，對模式串P0.m-1=xy進行子串定位操作的結果是(  c    )A.0       &

40、#160;                B.2C.3                        D.57.已知廣義表的表頭為a，表尾為(b,c)，則此廣義表為(  b

41、0;   )A.(a,(b,c)                        B.(a,b,c)C.(a),b,c)                 

42、0;      D.(a,b,c)8.二維數組A按行優(yōu)先順序存儲，其中每個元素占1個存儲單元。若A11的存儲地址為420，A33的存儲地址為446，則A55的存儲地址為(   c   )A.470                       

43、0;B.471C.472                        D.4739.二叉樹中第5層上的結點個數最多為(   d   )A.8             &

44、#160;           B.15C.16                        D.3210.下列編碼中屬前綴碼的是(  a    )A.1,01,000,001 

45、                       B.1,01,011,010C.0,10,110,11                      

46、60;  D.0,1,00,1111.如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是(    d  )A.有向完全圖                        B.連通圖C.強連通圖       

47、;                 D.有向無環(huán)圖12.對n個關鍵字的序列進行快速排序，平均情況下的空間復雜度為(    d  )A.O(1)                   

48、     B.O(logn)C.O(n)                        D.O(n logn)13.對表長為n的順序表進行順序查找，在查找概率相等的情況下，查找成功的平均查找長度為(   n/2   )A. 

49、60;                       B. C.                        D.n14

50、.對于哈希函數H(key)=key%13,被稱為同義詞的關鍵字是(  d    )A.35和41                        B.23和39C.15和44          

51、0;             D.25和5115.稠密索引是在索引表中(      )A.為每個記錄建立一個索引項           B.為每個頁塊建立一個索引項C.為每組記錄建立一個索引項         

52、  D.為每個字段建立一個索引項二、填空題（每小題2分，若有兩個空格，每個空格1分，共20分）16.當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數量級被稱為算法的_(_時間復雜度_)_。17.在鏈表的結點中，數據元素所占的存儲量和整個結點所占的存儲量之比稱作_(存儲密度)_。date next18.已知鏈棧的結點結構為             棧頂指針為top，則實現(xiàn)將指針p所指結點插入棧頂的語句依次為_和_。19.空串的長度是_

53、0_；空格串的長度是_(空格的數目_)_。20.假設一個6階的下三角矩陣B按列優(yōu)先順序壓縮存儲在一維數組A中，其中A0存儲矩陣的第一個元素b11,則A14存儲的元素是_b63_。21.在一棵度為3的樹中，度為2的結點個數是1，度為0的結點個數是6，則度為3的結點個數是_2_。22.如圖所示的有向無環(huán)圖可以排出_種不同的拓撲序列。 23.利用篩選法將關鍵字序列(37，66，48，29，31，75)建成的大根堆為(_75,66,48,29,31,37_)。24.對長度為20的有序表進行二分查找的判定樹的高度為_5_。25.在多重表文件中，次關鍵字索引的組織方式是將_的記錄鏈接成一個鏈表。26.對于

54、單鏈表、單循環(huán)鏈表和雙向鏈表，如果僅僅知道一個指向鏈表中某結點的指針p，能否將p所指結點的數據元素與其確實存在的直接前驅交換?請對每一種鏈表作出判斷，若可以，寫出程序段；否則說明理由。 date next單鏈表和單循環(huán)鏈表的結點結構為prior date next雙向鏈表的結點結構為 (1)單鏈表: (不可以,無法找到前驅接點)(2)單循環(huán)鏈表(可以:q=p->next;while(q->next!=p)q=q->next;q->data<->p->data;(3)雙向鏈表(可以:p->

55、prior->data<->p->data;)27.假設通信電文使用的字符集為a,b,c,d,e,f,g，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。(1)請根據哈夫曼編碼畫出此哈夫曼樹，并在葉子結點中標注相應字符；(2)若這些字符在電文中出現(xiàn)的頻度分別為：3，35，13，15，20，5和9，求該哈夫曼樹的帶權路徑長度。28.當采用鄰接表作為圖的存儲結構時，也可將鄰接表中的頂點表由順序結構改為鏈表結構。(1)請分別畫出這種鄰接表的頂點鏈表結點和邊表結點，并說明結點中各個域的作用；(2)對如圖所示的有向圖畫出這種鄰接表。29.已知4階B

56、-樹如圖所示。(1)分別畫出將關鍵字23和89相繼插入之后的B-樹。(2)畫出從插入之前的B-樹中刪除關鍵字51之后的B-樹。四、算法閱讀題(每小題5分，共20分)30.閱讀下列函數algo,并回答問題：(1)假設隊列q中的元素為(2,4,5,7,8),其中“2”為隊頭元素。寫出執(zhí)行函數調用algo(&q)后的隊列q；(2)簡述算法algo的功能。void algo(Queue *Q)  Stack S;  InitStack(&S);  while (!QueueEmpty(Q

57、)    Push(&S, DeQueue(Q);  while (! StackEmpty(&S)    nQueue(Q,Pop(&S);(1)87542(2) 隊列倒置31.閱讀下列函數F，并回答問題：(1)已知如圖所示的二叉樹以二叉鏈表作存儲結構，rt為指向根結點的指針。寫出執(zhí)行函數調用F(rt)的輸出結果。(2)說明函數F的功能。void F(BinTree T)  Stack

58、60;S;  if(T)      InitStack(&S);    Push(&S,NULL);    while(T)          printf("%c", T->data);      if(T->rchil

59、d) Push(&S,T->rchild);      if(T->lchild)T=T->lchild;      else T=Pop(&S);      (1)(2)前序遍歷二叉數vertex firstedge32.已知鄰接表的頂點表結點結構為 adjvex next邊表結點EdgeNode的結構為下列算法計算有向圖G中頂點v

60、i的入度。請在空缺處填入合適的內容，使其成為一個完整的算法。int FindDegree(ALGraph *G,int i)/ALGraph為圖的鄰接表類型  int dgree, j;  EdgeNode *p;  degree=    (1)        for(j=0;j<G->n;j+)    &

61、#160; p=G->adjlistj. firstedge;    while (      (2)       )         if(     (3)     )   

62、;        degree+;      break;          p=p->next;        return degree;(1)degree=0;(2)p(3)p->adj=vidata next33.已知單鏈表的結點結構為下列

63、算法對帶頭結點的單鏈表L進行簡單選擇排序，使得L中的元素按值從小到大排列。請在空缺處填入合適的內容，使其成為完整的算法。void SelectSort(LinkedList L)  LinkedList p,q,min;  DataType rcd;  p=   (1)      while(p!=NULL)     min=p;  &#

64、160; q=p->next;    while(q!=NULL)      if(    (2)    )min=q;      q=q->next;        if(   (3)   

65、60; )      rcd=p->data;      p->data=min->data;      min->data=rcd;           (4)      (1)L->next(2)q->

66、;data<min->data(3)p!=min(4)p=p->next五、算法設計題(本題10分)34.設線性表A=(a1,a2,a3,an)以帶頭結點的單鏈表作為存儲結構。編寫一個函數，對A進行調整，使得當n為奇數時A=(a2,a4,an-1,a1,a3,an)，當n為偶數時A=(a2,a4,an,a1,a3,an-1)。typedef struct node int x; struct node *next; NODE; typedef NODE * LinkL

67、ist;void adjust( LinkList header ) NODE *pTmp = header;   /用來保存偶數鏈表尾指針 NODE *pCur = header->next; /鏈表遍歷指針 NODE *pOddHdr = header->next;/奇數鏈表頭指針 NODE *pOddTail = header->next;/奇數鏈表尾指針 int bIsOdd = true; /奇數結點標志，第一個結點是奇數結點