自考02331數(shù)據(jù)結(jié)構(gòu)（12-19）真題試卷

課程代碼：02331一、單項選擇題（本大題共15小題，每小題2份，共30分）1．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類。（B）A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2．下面關(guān)于線性表的敘述中，錯誤的是（B）A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B．線性表采用順序存儲，便于進行插入和刪除操作C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元D．線性表采用鏈接存儲，便于插入和刪除操作3．一個棧的輸入序列為1，2，3…，n，若輸出序列的第一個元素是n，輸出第i(1≤i≤n)個元素是（B）A．不確定B．n-i+lC．ID．n-i4．串的長度是指（B）A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)5．假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5，5]=。（B）A．808B．818C．1010D．10206．有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（D）A．不確定B．2nC．2n+lD．2n-17．要連通具有n個頂點的有向圖，至少需要條邊。（B）A．n-1B．nC．n+lD．2n8．具有12個關(guān)鍵字的有序表，折半查找的平均查找長度是（A）A．3．1B．4C．2．5D．59．下列排序算法中，其中是穩(wěn)定的。（B）A．堆排序，冒泡排序B．快速排序，堆排序C．直接選擇排序，歸并排序D．歸并排序，冒泡排序10．棧的插入和刪除操作在進行。（A）A．棧頂B．棧底C．任意位置D．指定位置11．圖中有關(guān)路徑的定義是（A）A．由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列．B．由不同頂點所形成的序列C．由不同邊所形成的序列D．上述定義都不是12．若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為（C）A．(n-1)／2B．n／2C．(n+1)／2D．n13．已知一算術(shù)表達式的中綴形式為A+B*C-D／E，后綴形式為ABC*+DE／-，其前綴形式為（D）A．-A+B*C／DEB．-A+B*CD／EC．-+*ABC／DED．-+A*BC／DE14．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（B）A．9B．11C．15D．不確定15．ISAM文件和VASM文件屬于（B）A.索引非順序文件B．索引順序文件C順序文件D．散列文件二、填空題(本大題共10tj、題，每小題2分，共20分)16．設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC,則其前序遍歷序列為CADB。17．數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是算法的時間復雜度和空間復雜度。18．鏈接存儲的特點是利用指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。19．設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為O（m+n）。20．所謂稀疏矩陣指的是非零元很少（t<<m*n）。21．在完全二叉樹中，編號為i和j的兩個結(jié)點處于同一層的條件是[log2i]=[log2i]。22．在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要N條弧。23．平衡二叉樹的定義是二叉樹中任意結(jié)點左子樹高度與右子樹高度差的絕對值小于等于1。24．堆排序的算法時間復雜度為O（nog2n）。25．高度為8的完全二叉樹至少有64個葉子結(jié)點。三、解答題(本大題共4小題，每小題5分，共20分)26．一個線性表為B：(12，23，45，57，20，03，78，31，15，36)，設(shè)散列表為HT[0..12]，散列函數(shù)為H(key)=key％13并用線性探查法解決沖突。請畫出散列表，并計算等概率情況下查找成功的平均查找長度。27．設(shè)給定一個權(quán)值集合恥氣3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。WPL=7828．已知一個無向圖如下圖所示，要求用Kruskal算法生成最小樹(假設(shè)以①為起點，要求畫出構(gòu)造過程)。29．設(shè)待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。用直接插入排序。試以排序碼序列的變化描述形式說明排序全過程(動態(tài)過程)，要求按遞減的順序排序。第一趟（3）[8,3]，2，5，9，1，6第二趟（2）[8，3，2]，5，9，1，6第三趟（5）[8，5，3，2]，9，1，6第四趟（9）[9，8，5，3，2]，1，6第五趟（1）[9，8，5，3，2，1]，6第六趟（6）[9，8，6，5，3，2，1]四、算法閱讀題(本大題共2小題，每小題10分，共20分)30．對單鏈表中元素按插入方淵晾的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，完成其功能。Typedefstructnode{Intdata;structnode*next;}linknode,*link;VoidInsertsort(linkL){Linkp,q,r,u;P=L->next;(1)While((2)){r=L;q=L->next;while((3)&&q->data<=p->data){r=q;q=q->next;}u=p->next;(4);(5);p=u;}}（1）l-.next=null(2)p!=null(3)q!=null(4)p->next=r->next(5)r->next=p31．下列算法實現(xiàn)求采用順序結(jié)構(gòu)存儲的串s和串t的一個最長公共子串，請補充完整。Voidmaxcomstr(orderstring*s,*t;intindes,length){IntI,j,k,length1,con;Index=0;length=0;i=1;While(i<=s.len){J=1;While(j<=t.len){K=1;Length1=1:Con=1;While(con)If(1){length1=length1+1;k=k+1;}else(2);if(length1>length){index=I;lenth=length1;}(3);}else(4);}(5);}}(1)i+k<=s.len&&j+k<=t.len&&s[i+k]==t[j+k](2)con=0(3)j+=k(4)j++(5)i++五、算法設(shè)計題（本大題10分）32.設(shè)二維數(shù)組a[1..m，1..n]含有m*n個整數(shù)。（1）寫出算法（pascal過程會c函數(shù)）：判斷a中算有元素是否互不相同？輸出相關(guān)信息：如果全不相同輸出yes，否則輸出no。（2）試分析算法的時間復雜度。二維數(shù)組中的每一個元素同其它元素都比較一次，數(shù)組中共m*n個元素，第1個元素同其它m,n-1個元素比較，第2個元素同其它m,n-2個元素比較，……，第m*n-1個元素同最后一個元素(m*n)比較一次，所以在元素互不相等時總的比較次數(shù)為(m*n-1)+(m*n-2)+....+2+1=(m*n)(m*n-1)／2。在有相同元素時，可能第一次比較就相同，也可能最后一次比較時相同，設(shè)在(m*n-1)個位置上均可能相同，這時的平均比較次數(shù)約為(m*n)(m*n—1)／4，總的時間復雜度是0(n4)。

課程代碼：02331一、單項選擇題（本大題共15小題，每小題2份，共30分）1．下列數(shù)據(jù)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是（C）A．棧B．隊列C．完全二叉樹D．堆2．下面關(guān)于算法說法正確的是（D）A．算法最終必須由計算機程序?qū)崿F(xiàn)B．為解決某問題的算法同為該問題編寫的程序含義是相同的C．算法的可行性是指指令不能有二義性D．以上幾個都是錯誤的3．下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點（A）A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結(jié)構(gòu)的存儲表示4．設(shè)A是n~n的對稱矩陣，將A的對角線及對角線下方的元素按行序存放在一維數(shù)組Brn(n+1)／2]中，對上述任一元素aijti習)，在一維數(shù)組B中的位置為（B）A．i(i-1)／2+jB．i(i十1)／2+jC．j(j-1)／2+i-1D．j(j+1)／2+i-15．下述編碼中不是前綴碼的是(B)A．(00，01，10，11)B．(0，l，00，11)C．(0，10，110，111)D．(1，01，000，001)6．樹的后序遍歷序列等同于該樹對應的二叉樹的(B)A．先序序列B．中序序列C.后序序列D．以上均不是7．在有向圖G的拓撲序列中，若頂點Ⅵ在頂點Ⅵ之前，則下列情形不可能出現(xiàn)的是(D)A．G中有弧<Vi，vi>B．G中有一條從Ⅵ到Ⅵ的路徑C．G中沒有弧<Vi，Ⅵ>D．G中有一條從邯到Ⅵ的路徑8．若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是(C)A．快速排序B．堆排序C．歸并排序D．直接插入排序9．下面關(guān)于線性表的敘述中，錯誤的是(B)A．線性表采用J頓序存儲，必須占用一片連續(xù)的存儲單元B．線性表采用順序存儲，便于進行插入和刪除操作C．線性表采用鏈式存儲，刁；必占用一片連續(xù)的存儲單元D．線性表采用鏈式存儲，便于插入和刪除操作10．n個結(jié)點的完全有向圖含有邊的數(shù)目為(D)A．n×nB．n×(n+1)C．n／2D．n×(n-1)11．若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度(ASL)為(C)A．(n-1)／2B．n/2C．(n+1)／2D．n12．已知有向圖如下所示，其中頂點A到頂點C的最短路徑長度是(D)A.43B.40C.45D.3313．下面說法不正確的是(A)A．廣義表的表頭總是一個廣義表B．廣義表的表尾總是一個廣義表C．廣義表難以用順序存儲結(jié)構(gòu)D．廣義表可以是一個多層次的結(jié)構(gòu)14．在含有n個關(guān)鍵字的小根堆(堆頂元素最小)中，關(guān)鍵字最大的記錄有可能存儲在以下哪個位置上(D)A，『n/2』B．『n/2』-1C．1D．『n/2』+215．下面關(guān)于B和B+樹的敘述中，不正確的是(C)A．B樹和B+樹都是平衡的多叉樹B。B樹和B+樹都可用于文件的索引結(jié)構(gòu)C．B樹和B+樹都能有效地支持順序檢索D．B樹和B+樹都能有效地支持隨機檢索二、填空題(本大題共10小題，每小題2分，共20分)16．數(shù)據(jù)結(jié)構(gòu)一般包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)驗算三個方面的內(nèi)容。17．線性表L=(a1，a2，…,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是（n-1）/2。18．帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是L->next==L&&L->prior==L。19.棧是限定僅在表尾進行插入或刪除操作的線性表。20．設(shè)某廣義表H=(A，（a，b，c))，運用head函數(shù)和tail函數(shù)求出廣義表H中某元素b的運算式為head（tail（head（tail（H））））。21.深度為k的完全二叉樹至少有2k-1個結(jié)點。22．求圖的最小生成樹有兩種算法，克努斯卡爾（Kruskal）算法算法適合于求稀疏圖的最小生成樹。23．在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散列查找。24．利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為二叉樹。25．下面程序段的時間復雜度是O（1）。三、解答題（本大題共3小題，每小題5分，共15分）26.對于后序線索二叉樹，怎樣查找任意結(jié)點的直接后繼？對于中序線索二叉樹，怎樣查找任意結(jié)點的直接前驅(qū)？后序線索樹中結(jié)點的后繼(根結(jié)點無后繼)，要么是其右線索(當結(jié)點的rtag=l時)(1′)，要么是其雙親結(jié)點右子樹中最左下的葉子結(jié)點(門。對中序線索二叉樹某結(jié)點，若其左標記等于1，則左子女為線索，指向直接前驅(qū)C仇否則，其前驅(qū)是其左子樹上按中序遍歷的最后一個結(jié)點(1′)。27.已知A為稀疏矩陣，試從空間角度，比較采用兩種不同的存儲結(jié)構(gòu)（二維數(shù)組和三元組表）完成求運算的優(yōu)缺點。稀疏矩陣A采用二維數(shù)組存儲時，需要n*n個存儲單元，(門完成求∑aii(1<=i<=n)時，由于a[i][i]隨機存取，速度快(1′)但采用三元組表時，若非零元素個數(shù)為t，需3(t+1)”個存儲單元(第一個分量中存稀疏矩陣A的行數(shù)，列數(shù)和非零元素個數(shù)，以后t個分量存各非零元素的行值、列值、元素值)，比二維數(shù)組節(jié)省存儲單元(1′);但在求∑aii(1<=i<=n)時，要掃描整個三元組表，以便找到行列值相等的非零元素求和，其時間性能比采用二維數(shù)組時差(2′)。28．下面的鄰接表表示一個給定的無向圖G(1)給出從頂點v1開始，對圖G用深度優(yōu)先搜索法進行遍歷時的頂點序列；V1V2V3V4V5V6(2)給出從頂點vl開始，對圖G用廣度優(yōu)先搜索法進行遍歷時的頂點序列。V1V2V3V4V5V6四、算法閱讀題(本大題共3小題，每小題5分，共15分)29．試將下列遞歸過程改寫為非遞歸過程。參考算法：30．下面是用c語言編寫的對不帶頭結(jié)點的單鏈表進行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針。試在空缺處填入適當?shù)恼Z句。31．已知N元整型數(shù)組a存放N個學生的成績，已按由大到小排序，以下算法是用二分查找方法統(tǒng)計成績大于或等于X分的學生人數(shù)，請?zhí)羁帐怪晟啤?defineN/*學生人數(shù)*／五、算法設(shè)計題(本大題共2小題，每小題10分，共20分)32．已知順序表R和增量序列d10-L1]，編寫算法實現(xiàn)希爾排序，并用希爾排序?qū)?shù)組{503，087，512，061，908，170，897，275，653，426}進行排序，給出的步長(也稱增量序列)依次是5，3，1，寫出排序的過程。33．請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：PUSH(ST，X)：元素x入ST棧；POP(ST，X)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運算來實現(xiàn)該隊列的三個運算：①enqueue：插入一個元素入隊列；②dequeue：刪除一個元素出隊列；⑧queueempty：判隊列為空。

2015年4月高等教育自學考試《數(shù)據(jù)結(jié)構(gòu)》試題課程代碼：02331一、單項選擇題1．以下各階時間復雜度中，性能最優(yōu)的是（A）A．B．C．D．2．頭指針head指向帶頭結(jié)點的單循環(huán)鏈表。鏈表為空時下列選項為真的是（D）A．head!=NullB.head==NullC．head->next=NullD．head->next=head3．設(shè)棧的進棧序列為a,b,c,d,e，經(jīng)過合理的出入棧操作后，不能得到的出棧序列是（A）A．d,c,e,a,bB．d,e,c,b,aC．a(chǎn),b,c,d,eD．e,d,c,b,a4．使用大小為6的數(shù)組實現(xiàn)循環(huán)隊列，若當前rear=0，front=3。當從隊列中出隊一個元素，再入隊兩個元素后，rear和front的值分別是（C）A．1和5B．4和2C．2和4D．5和15．二維數(shù)組a[10][20]按行優(yōu)先順序存放在連續(xù)的存儲空間中，元素a[0][0]的存儲地址為200，若每個元素占1個存儲空間，則元素a[6][2]的存儲地址是（B）A．226B．322C．341D．3426．廣義表A=(a,(b,c,(e,f,g,h)))的深度是（B）A．2B．3C．4D．77．以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，在有n(n>0)個結(jié)點的二叉鏈表中，空指針域的個數(shù)是（B）A．n-1B．n+1C．2n-1D．2n+18．構(gòu)造一棵含n個葉結(jié)點的哈夫曼樹，樹中結(jié)點總數(shù)是（C）A．n-1B．n+1C．2n-1D．2n+19．若圖G的鄰接表中有奇數(shù)個表結(jié)點，下列選項中，正確的是（D）A．G中必有奇數(shù)個頂點B．G中必有偶數(shù)個頂點C．G為無向圖D．G為有向圖10．下列關(guān)于有向無環(huán)圖G的拓撲排序序列的敘述中，正確的是（C）A．存在且唯一B．存在且不唯一C．存在但可能不唯一D．無法確定是否存在11．對下圖進行廣度優(yōu)先搜索遍歷，不能得到的遍歷序列是（B）A．v1v2v4v5v3B．v1v2v5v3v4C．v2v5v1v3v4D．v2v1v5v4v312.下列排序方法中，效率較高且使用輔助空間最少的方法是（C）A．冒泡排序B．快速排序C．堆排序D．歸并排序13．下列排序方法中，平均比較次數(shù)最少的方法是（B）A．插入排序B．快速排序C．簡單選擇排序D．歸并排序14．對含有16個元素的有序表進行二分查找，關(guān)鍵字比較次數(shù)最多是（C）A．3B．4C．5D．615．下列敘述中，不符合m階B樹定義的是（D）A．根結(jié)點可以只有一個關(guān)鍵字B．所有葉結(jié)點都必須在同一層上C．每個結(jié)點內(nèi)最多有m棵子樹D．每個結(jié)點內(nèi)最多有m個關(guān)鍵字二、填空題16．算法必須滿足可行性等五個準則，其中確定性的含義是：算法中每條指令的含義都必須明確，無二義性。17．采用大表示法時，常數(shù)階算法的時間復雜度記為。18．一個線性表如果需要頻繁地增刪元素，則存儲結(jié)構(gòu)應該選擇鏈式存儲結(jié)構(gòu)。19．隊列Q中已有元素1，3，5，數(shù)據(jù)序列2，4，6，8，10依次入隊，再連續(xù)執(zhí)行6次出隊操作，得到的出隊序列是1，3，5，2，4，6。20.廣義表A=(a(b,c,(e,f,g,h)))，head(tail(A))=（b,c,(e,f,g,h)）。21.一棵右子樹為空的二叉樹在后序線索化后，其空指針域的個數(shù)為2。22.用矩陣作為圖的存儲結(jié)構(gòu)，該矩陣稱為圖的鄰接矩陣。23.普里姆（Prim）算法得到的是帶權(quán)連通圖的最小生成樹。24.希爾排序方法使用的增量序列中，最后一個增量必須是1。25.若待排序序列的關(guān)鍵字基本有序，采用快速排序或直接插入排序時，效率較高的是直接插入排序。三、解答題26．順序棧的類型定義如下：typedefstruct{DataTypedata[MaxSize];inttop;}SeqStack;SeqStackS;規(guī)定棧底位置在MaxSize-1，請回答下列問題。(1)若要求?？諘r條件為真，則判斷?？盏臈l件表達式是什么?(2)若要求棧滿時條件為真，則判斷棧滿的條件表達式是什么?(3)用語句表示將x入棧的操作。答：27.已知廣義表及結(jié)點類型結(jié)構(gòu)如下：ypedefenum{ATOM,LIST}NodeTag;//ATOM=O,表示原子;LIST=1,表示子表//ATOM=O,表示原子;LIST=1,表示子表typeclefstructGLNode{NodeTagtag;//區(qū)分原子結(jié)點和表結(jié)點union{DataTypedata;//存放原子結(jié)點的值OLNode*slink;//指向子表的指針};GLNode*next;//指向下一個表結(jié)點}*Glist;//廣義表類型請回答下列問題。(1)若廣義表A為空表，應如何表示?(2)若廣義表A二(a,(b,c))，畫出A的存儲結(jié)構(gòu)。答：28．己知散列函數(shù)為H(key)=key％11，現(xiàn)將關(guān)鍵字序列{23,27,34,56,58,10,18,120}散列到散列表HT[0…10]中，利用線性探查法解決沖突?；卮鹣铝袉栴}。(1)畫出最后的散列表；(2)求在等概率情況下查找成功時的平均查找長度。答：29．給定帶權(quán)圖G如題29圖所示，使用迪杰斯特拉(Dijkstra)算法，求頂點v1到其他各項點的最短路徑，列出每條路徑上的各頂點及路徑長度。答：四、算法閱讀題30．設(shè)下列程序段中的數(shù)據(jù)皆為int型，請指出該程序段的功能是什么。voidf30(CirQueue*Q){intx;SeqStackS;InitStack(&S);//初始化棧Swhile(!QueueEmpty(Q)){x=DeQueue(Q);Push(&S,x);}while(!StackEmpty(&S)){x=Pop(&S);EnQueue(Q,x);｝｝答：程序段的功能是：將隊列Q中的所有元素的排列次序反轉(zhuǎn)。31．下列函數(shù)的功能是在帶頭結(jié)點的單鏈表head中刪除所有數(shù)據(jù)域值為xr的結(jié)點，請在空白處填上適當?shù)恼Z句，使其完成指定功能。voidf31(LinkListhead,intx){LinkNode*p,*q,*s;p-head;q=p->next;while(q!=NULL)if(q->data==x){s=q;q=q->next;free(s);p->next=q;}else{p=q;q=q->next（或q=p->next）,｝｝32．下列函數(shù)的功能是：在帶頭結(jié)點的單鏈表上進行選擇排序。請在空白處填上適當內(nèi)容將函數(shù)補充完整，并說明該算法是否是穩(wěn)定的。typedefstructnode{KeyTypekey;stmctnode*next;}RecType,*LinkList;voidf32(LinkListH){LinkListp,q,r=H;while(r->next!=NULL){p=r;q=p->next;'while(q->next)//查找最小值結(jié)點{if(p->next->key>q->next->key)p=q;q=q->next;｝q=p->next;//將最小值結(jié)點取下p->next=q->next;q->next=r->next;//將最小值結(jié)點插入r->next=q;r=q;}｝該算法是穩(wěn)定的排序方法。33.閱讀程序，并回答下列問題。typedefintKeyType;typedefstmct{KeyTypekey;InfoTypeotherinfo;}RecType;typedefRecTypeSeqList[MAXSIZE+1];intf33(SeqListR,KeyTypeK,intIow,inthigh){intmid;while(low<high){mid=(low+high)/2;if(R[mid].key>=K)returnf33(R,K,low,mid);elsereturnf33(R,K,mid+l,high);｝if(R[low].key==K)returnlow;elsereturn0;｝假設(shè)順序表R的元素存入在下標為1~8的數(shù)組元素中，K=7，low=1，high=8。(1)R的關(guān)鍵字依次為{1,2,3,4,5,6,7,8}，函數(shù)f33的返回值是多少?答：函數(shù)的返回值為7(2)R的關(guān)鍵字依次為{7,7,7,7,7,7,7,7}，函數(shù)f33的返回值是多少?答：函數(shù)的返回值為1(3)簡述函數(shù)的功能。答：函數(shù)實現(xiàn)二分查找，返回值為查找目標在表中第一次出現(xiàn)的下標位置。五、算法設(shè)計題34.存儲二叉樹的二叉鏈表定義如下：typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;請編寫一個后序遍歷二叉樹的遞歸程序voidPostOrder(BinTreeroot)，并輸出遍歷序列。其中root指向二叉樹根結(jié)點。答：

2015年10月高等教育自學考試《數(shù)據(jù)結(jié)構(gòu)》試題課程代碼：02331一、單項選擇題1．下列選項中，不屬于線性結(jié)構(gòu)的是A．網(wǎng)B．棧C.隊列D．線性表2.長度為n的順序表，刪除位置i上的元素(0≤i≤n-1)，需要移動的元素個數(shù)為A.n-iB．n-i-1C．iD．i+l3．棧采用不同的存儲方式時，下列關(guān)于出棧過程的敘述中，正確的是A．順序棧需要判定?？眨湕Ｒ残枰卸˙．順序棧需要判定?？?，而鏈棧不需要判定C．順序棧不需要判定?？?，而鏈棧需要判定D．順序棧不需要判定?？?，鏈棧也不需要判定4.若一個棧以數(shù)組V[0..n-1]存儲，初始棧頂指針top為n，則x入棧的正確操作是A．top=top+1；V[top]=xB．V(top)=x；top=top+1C.top=top-1；V[top]=xD．V(top)=x；top=top-15.在二維數(shù)組a[9][10]中，每個數(shù)組元素占用3個存儲空間，從首地址SA開始按行優(yōu)先連續(xù)存放，則元素a[8][5]的起始地址是A．SA+141B.SA+144C.SA+222D．SA+2556.廣義表A=(x,((y),((a)),A))的深度是A．2B．3C．4D．7．一棵左子樹為空的二叉樹在前序線索化后，其空指針域個數(shù)為A.0B．1C．2D.不確定8．下列關(guān)于哈夫曼樹的敘述中，錯誤的是A．用n個結(jié)點構(gòu)造的哈夫曼樹是唯一的B．哈夫曼樹中只有度為0或度為2的結(jié)點C．樹中兩個權(quán)值最小的結(jié)點可能是兄弟結(jié)點D．同一結(jié)點集構(gòu)造的二叉樹中，哈夫曼樹的WPL最小9．6個頂點的強連通圖中，含有的邊數(shù)至少是A．4B．5C．6D．710．對題10圖進行深度優(yōu)先搜索遍歷，下列選項中，正確的遍歷序列是A．v3v4v5v1v2B．v3v5v2v1v4C．v4v5v2v3v1D．v5v1v2v4v311．下列選項中，能構(gòu)成題10圖中一條路徑的是A．v1v2v4v5v3B．v1v2v5v3v4C．v2v5v1v3v4D．v2v1v5v4v312．有向圖采用鄰接矩陣存儲，某一行中非零元素的個數(shù)等于A．對應頂點v的度B．對應頂點v的出度C．對應頂點v的入度D．依附于對應頂點v的邊數(shù)13．以下選項中，符合堆定義的是A．{102,24,55,60,89,93}B．{24,89,55,60,93,102}C．{102,93,55,60,89,24}D.{102,60,89,93,55,24}14．己知關(guān)鍵字序列為{66,82,25,51,98,108}，利用快速排序方法，以第一個元素為基準得到的一趟排序結(jié)果為A．{25,51,66,82,98,108}B．{25,51,66,98,82,108}C．{51,25,66,108,98,82}D．{51,25,66,82,98,108}15．下列選項中，其平均查找性能與基于二叉排序樹的查找相當?shù)氖茿．二分查找B．順序查找C．分塊查找D．索引順序查找二、填空題16．線性表(a1,a2,…,an)中，除外，每個元素都有唯一的直接前趨。17．指針p指向單鏈表中某個結(jié)點，在p所指結(jié)點后插入指針s所指的結(jié)點，正確的操作序列是18．設(shè)Push、Pop分別表示入棧和出棧操作，x=10，y=20，z=30。依次進行下列操作：Push(y)、Push(z)、Push(z)、x=Pop()、y=Pop()，x、y的值分別是。19．廣義表L=(a,(b,c,(e,f,g,h))),head(L)=。20．設(shè)樹T的度為3，其中度為1、2和3的結(jié)點個數(shù)分別為3、2和1，則T中葉子結(jié)點的個數(shù)為。21．由一棵二叉樹的后序遍歷序列和遍歷序列可以唯一確定該二叉樹。22．在有n個頂點的無向圖中，任一頂點的度不大于。23．借助于一個棧來實現(xiàn)的圖的遍歷算法是、。24．若有向圖中存在拓撲排序序列，則該圖一定不存在。25．已知關(guān)鍵字序列為{66,82,25,51,98,108)，一趟二路歸并排序的結(jié)果為。三、解答題26．已知n階對稱矩陣A的元素為aij(0≤i，j≤n-1)，采用“按行優(yōu)先”．將下三角部分的元素(含主對角線)保存在一維數(shù)組sa中，且約定元素a0,0保存在sa[0]中，元素aij(0≤i，j≤n-1)保存在sa(k)中，請給出由下標i,j計算下標k的計算公式。27．己知二叉樹T如題27圖所示。請問答下列問題：(1)畫出該二叉樹對應的森林。(2)寫出對森林進行前序遍歷的遍歷序列。28．題28圖所示為一棵含2個關(guān)鍵字的3階B樹T?，F(xiàn)將關(guān)鍵字序列{40,60,70,20,10}依次插入到T中，畫出每插入一個關(guān)鍵字后得到的樹型。29．給定無向帶權(quán)連通圖G如題29圖所示，從頂點v0開始，使用普里姆(Prim)算法，求G的最小生成樹T。請回答下列問題。(1)畫出最小生成樹T。(2)計算T中各邊權(quán)值之和。四、算法閱讀題30．請寫出下列程序段的輸出結(jié)果。#defineListSize100typedefstmct{intdata[ListSize];intlength;}SeqList;voidf30(SeqList.*list){inti,j,k;for(i=0;i<=list->length-2;i++){j=i+l;while(j<=list->length-1){if(list->data[i]==-list->data[j]){for(k=j;k<list->length-1;k++list->length--;}elsej++;}}}voidmain()SeqListlist={{0,3,7,3,3,3,4,O,3,7),10};inti;t30(&list);printf(',!en=%d\n",list.length);for(i=O;i<list.length;i++)prinff("%d,",list.data[i]);prinff("\n");31．已知存儲稀疏矩陣三元組表的類型定義如下：#defineMAX100typedefstmct{inti,j;//非零元素的行號、列號(下標)ihtv;}TriTupleNode;typedefstruct{TriTupleNodedata[MAX];//存儲三元組的數(shù)組intm,n,t;//矩陣的行數(shù)、列數(shù)和非零元素個數(shù)}TSMatrix;//稀疏矩陣類型函數(shù)f31的功能是將a所表示的矩陣轉(zhuǎn)置后保存在*b中。請在空白處填寫適當內(nèi)容，intf31(TSMatdxa,TSMatrix*b)//返回值:1表示出錯，0表示正確{//a和*b分別是矩陣M、T的三元組表，T為稀疏矩陣M的轉(zhuǎn)置.intp,q,col;b->m=a.n;b->n=a.m;b->t=a.t;if(b->t<0)return1;else{q=0;for(col=0;col<a.n;++col)for(p=0;p<(1);++p)if((2)==col){b->data[q].i=(3);b->data[q].j=(4);b->data[q].v=a.data[p].v;++q;)}return0;}(1)(2)(3)(4)32．已知二叉樹的二叉鏈表類型定義如下：typedefstructnode{chardata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;函數(shù)CopyBin的功能是完成二叉樹Bt的復制,程序如下:BinTreeCopyBin(BinTreeBt)//函數(shù)返回值為指向復制后的二叉樹根的指針{BinTreep;if(Bt==NULL)(1);else{p=(BinTNode*)malloc(sizeof(BinTNode));p->data=Bt->data;p->lchild=(2);p->rchild=(3);}}returnp;為完成指定功能，請在空白處填寫適當內(nèi)容，使其功能完整。33．函數(shù)f33的參數(shù)t指向題33圖所示的二叉排序樹的根，閱讀程序，回答下列問題。typedefihtKeyType;typedefstructnode{KeyTypekey;node*lchild,*rchild;}BSTNode,*BSTree;BSTreeF33(BSTreet,KeyTypeK){BSTreep;while(t!=NULL){if(t->key==K){prinff("查找成功\n");returnt;}p=t;if(t->key>K)t=t->lchild;elset=t->rchild;}printf("查找不成功\n");t=(BSTree)malloc(sizeof(BSTNode));t->key=K;t->lchild=NULL;t->rchild=NULL;if(p->key>K)p->lchild=t;elsep->rchild=t;returnNULL;(1)若連續(xù)3次調(diào)用函數(shù)03，參數(shù)K的值依次取10、25、10，寫出每次調(diào)用后函數(shù)的輸出結(jié)果；(2)說明函數(shù)f33的功能。五、算法設(shè)計題34．已知順序表SeqList定義如下：typedefstreet{KeyTypekey;InfoTypeotherinfo;}ReeType;typedefRecTypeSeqList[MAXSIZE+1];編寫函數(shù)，用冒泡排序法將n個元素的待排序列R按關(guān)鍵字降序排序。函數(shù)原型為：iht134(SeqListR,intn).

2016年4月高等教育自學考試《數(shù)據(jù)結(jié)構(gòu)》試題課程代碼：02331一、單項選擇題1．下列選項中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是A．隊列B．棧C．二叉排序樹D．線性表2．瑞士計算機科學家沃思教授曾指出：算法+數(shù)據(jù)結(jié)構(gòu)=程序。這里的數(shù)據(jù)結(jié)構(gòu)指的是A．數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)B．數(shù)據(jù)的線性結(jié)構(gòu)和非線性結(jié)構(gòu)C．數(shù)據(jù)的緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D．數(shù)據(jù)的J頃序結(jié)構(gòu)和鏈式結(jié)構(gòu)3．線性表順序存儲時，邏輯上相鄰的兩個數(shù)據(jù)元素，其存儲地址A．一定相鄰B．一定不相鄰C．不一定相鄰D．可能不相鄰4．數(shù)據(jù)元素1,2,3,4,5依次入棧，則不可能得到的出棧序列是A．4,5,3,2,1B．1,2,3,4,5C．4,3,5,1,2D．5,4,3,2,15．設(shè)順序表首元素A[0]的存儲地址是4000，每個數(shù)據(jù)元素占5個存儲單元，則元素A[20]的起始存儲地址是A．4005B．4020C．4100D．41056.廣義表A=(a,(b,c,(e,f))),函數(shù)head(head(tail(A)))的運算結(jié)果是A.aB.bC.cD.e7．設(shè)高度為h的二叉樹中，只有度為0和2的結(jié)點，則此類二叉樹包含的結(jié)點數(shù)至少是A．2hB．2h-1C．2h+1D．h+18．一棵非空二叉樹了的前序遍歷和后序遍歷序列正好相反，則了一定滿足A．所有結(jié)點均無左孩子B．所有結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是一棵滿二叉樹9．設(shè)圖的鄰接矩陣A如下所示。各頂點的度依次是A．1,2,1,2B．2,2,1,1C．3,4,2,3D．4,4,2,210．無向圖G如題10圖所示，從頂點a開始進行深度優(yōu)先遍歷，下列遍歷序列中，正確的是A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,d,bC．a(chǎn),c,b,e,f,dD．a(chǎn),e,d,f,c,b11．設(shè)帶權(quán)連通圖G中含有n(n>1)個頂點，下列關(guān)于G的最小生成樹T的敘述中，正確的是A．T中可能含有回路B．T中含有圖G的所有邊C．T是唯一的，且含有n-1條邊D．T可能不唯一，但權(quán)一定相等12．若要求對序列進行穩(wěn)定的排序，則在下列選項中應選擇A．希爾排序B．快速排序C．直接插入排序D．直接選擇排序13．下列排序算法中，空間復雜度最差的是A．歸并排序B．希爾排序C．冒泡排序D．堆排序14．下列排序算法中，初始數(shù)據(jù)有序時，花費的時間反而更多的算法是A．插入排序B．冒泡排序C．快速排序D．希爾排序15．對線性表上進行二分查找時，要求上必須滿足A．以順序方式存儲B．以順序方式存儲，且數(shù)據(jù)元素有序C．以鏈接方式存儲D．以鏈接方式存儲，且數(shù)據(jù)元素有序二、填空題16．下面程序段的時間復雜度是。i=1；while(i<n)i=i*2；17．在單鏈表的p結(jié)點之后插入s結(jié)點的操作是。18．只能在線性表的兩端進行插入或刪除操作的兩種邏輯結(jié)構(gòu)分別是。19．廣義表A=(x,(y,z,(u,v,w)))的長度是。20．一棵樹的后序遍歷序列與其對應的二叉樹的序遍歷序列相同。21．在有向圖、無向圖中，其鄰接矩陣一定對稱的是。22．要計算圖中從某一頂點出發(fā)到其余各項點的最短路徑，可選用算法。23．設(shè)關(guān)鍵字序列為28,72,97,63,4,53,84，使用希爾排序法將其排成升序序列，若第一趟采用的間隔是3，則該趟排序的結(jié)果是。24．對具有15個關(guān)鍵字的關(guān)鍵字序列進行順序查找時，查找成功的平均查找長度為。25．在二叉排序樹的查找過程中，若當前結(jié)點的關(guān)鍵字值大于待查找關(guān)鍵字，則應在該結(jié)點的子樹上繼續(xù)查找。三、解答題26．設(shè)Q是有N個存儲空間的循環(huán)隊列，初始狀態(tài)front=rear=0，約定指針rear指向的單元始終為空。定義如下：#defineN100typedefstruct{chardata[N];intfront,rear;}CQ;GQ*Q;(1)寫出清空隊列的語句序列；(2)寫出判斷隊列為滿的表達式；(3)給出計算隊列長度L的表達式。27．已知4×5稀疏矩陣M按行優(yōu)先順序存儲的三元組表如下：(1)寫出矩陣M(2)給出矩陣M的轉(zhuǎn)置矩陣T按行優(yōu)先順序存儲的三元組表。28．給定一組權(quán)值數(shù)據(jù){3,8,9,11,4}，回答下列問題。(1)畫出基于所給數(shù)據(jù)的一棵哈夫曼樹；(2)計算所得哈夫曼樹的帶權(quán)路徑長度WPL。29.已知有向圖G=(V,E),其中V={v1,v2,v3,v4,v5,v6,v7},E={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>}。(1)畫出有向圖G；(2)判斷圖G是否存在拓撲排序序列，若不存在請說明理由：若存在請給出一個拓撲排序序列。四、算法閱讀題30．閱讀程序f30(intA[],intn){intm;if(n<=0)return-1;if(n==l)return0;m=f30(A,n-1);if(A[m]>A[n-1])returnm;elsereturnn-1;}已知線性表A={25,34,256,9,38,47,128,256,64}。（1）若主函數(shù)調(diào)用語句為f30（A,5），f30的返回值是多少？（2）若主函數(shù)調(diào)用語句為f30（A,9），f30的返回值是多少？（3）給出算法f30的功能。31．已知棧的基本操作定義如下，請在空白處填寫適當內(nèi)容，完成相應的功能。typedefstruct{//棧定義chardata[StackSize];inttop;}SeqStack;SeqStacks;voidInitStack(SeqStack*s)//棧初始化{s->top=-1;}intStackEmpty(SeqStack*s)//判棧是否為{return(1);}intStackFull(SeqStack*s)//判棧是否為滿{returns->top--StackSize-1;}charpush(SeqStack*s,charc)//入棧操作{if(StackFull(s))remm'\0';//操作失敗else(2)=c;returnc;//操作成功}charpop(SeqStack*s)//出棧操作{if(StackEmpty(s))return'\0';//操作失敗elsereturn(3)//操作成功}32．設(shè)帶頭結(jié)點的單鏈表初始為空。將從鍵盤讀入的每個字符作為一個結(jié)點加入該鏈表表尾，當讀入回車符時結(jié)束并返回鏈表表頭指針。請在空白處填寫適當內(nèi)容，完成其功能。typedefstructnode{chardata;structnode*next;}ListNode;typedefListNode*LinkList;LinkListf32(){LinkListhead=NULL;ListNode*p,*rear;charch;head=(ListNode*)malloc(sizeof(ListNode));rear=head;while((ch=getchar())!='\n'){(1),p->data=ch;(2);rear=p;}rear->next=NULL;return(3);33．給出二叉鏈表定義如下。程序f33生成原二叉樹的鏡像樹，即將二叉樹中所有結(jié)點的左、右子樹互換。請在空白處填寫適當內(nèi)容，完成其功能。typedefcharDataType;typedefstructnode{DataTypedata;//data是數(shù)據(jù)域structnode*lchild,*rchild;//分別指向左右孩子}BinTNode;typedefBinTNode*BinTree;BinTreef33(BinTreeT){BinTreeNewT;if((1))returnNULL;(2)=(BinTree)malloc(sizeof(BinTNode));NewT->data=T->data;NewT->lchild=(3);NewT->rchild=(4);return(5);}五、算法設(shè)計題34.實現(xiàn)f34，對含有n個整數(shù)的數(shù)組A進行選擇排序。函數(shù)原型如下。voidf34(intA[],intn)；／／對含有n個整數(shù)的數(shù)組A進行選擇排序

2016年10月高等教育自學考試《數(shù)據(jù)結(jié)構(gòu)》試題課程代碼：02331一、單項選擇題1．下列選項中，不屬于線性結(jié)構(gòu)特征的是A．數(shù)據(jù)元素之間存在線性關(guān)系B．結(jié)構(gòu)中只有一個開始結(jié)點C．結(jié)構(gòu)中只有一個終端結(jié)點D．每個結(jié)點都僅有一個直接前趨2．設(shè)n個元素的順序表中，若將第i(1≤i<n)個元素e移動到第j(1<j≤n，i<j)個位置，不改變除e外其他元素之間的相對次序，則需移動的表中元素個數(shù)是A．j-i-1B．j-iC．j-i+1D．i-j3．若用一個大小為7的數(shù)組作為循環(huán)隊列的存儲結(jié)構(gòu)，且當前rear和front的值分別為2和4，在此之前的操作是從隊列中刪除了一個元素及加入兩個元素，請問這3個操作之前real'和front的值分別是A．0和1B．0和3C．3和6D．4和54．已知廣義表LS=(((a))，((b,(c))，(d,(e,f)))，())，LS的長度是A．2B．3C．4D．55．一棵完全二叉樹了的全部k個葉結(jié)點都在同一層中且每個分支結(jié)點都有兩個孩子結(jié)點。了中包含的結(jié)點數(shù)是-A．kB．2k-1C．k2D．2k-16．如果某二叉樹的前序遍歷序列為abced，中序遍歷序列為cebda，則該二叉樹的后序遍歷序列是A．cedbaB．decbaC．ecdbaD．ecbad7．一個森林有陰棵樹，頂點總數(shù)為，2，則森林中含有的總邊數(shù)是A．mB．n-1C．n-mD．n+m8．設(shè)圖的鄰接矩陣A如下所示。各頂點的度依次是A．1,2,1,2B．2,2,1,1C．3,4,2,3D．4,4,2,29．若對下面無向圖進行深度優(yōu)先遍歷，得到的正確遍歷序列是A.h,c,a,b,d,e,g,fB.e,a,f,g,b,h,c,dC.d,b,c,a,h,e,f,gD.a,b,c,d,h,e,f,g10．已知有向圖G如下所示，G的拓撲序列是A.a,b,e,c,d,f,gB.a,c,b,f,d,e,gC.a,c,d,e,b,f,gD.a,c,d,f,b,e,g11．下列排序算法中，在每一趟都能選出一個元素放到其最終位置上的是A．插入排序B．希爾排序C．歸并排序D．直接選擇排序12．對一組數(shù)據(jù)(2,12,16,88,5,10)進行排序，若前3趟排序結(jié)果如下：第一趟：2,12,16,5,10,88第二趟：2,12,5,10,16,88第三趟：2,5,10,12,16,88則采用的排序方法是A．冒泡排序B．希爾排序C．歸并排序D．基數(shù)排序13．設(shè)有序表為{9,12,21,32,41,45,52}，當二分查找值為52的結(jié)點時，元素之間的比較次數(shù)是A．1B．2C．3D．414．下列選項中，既能在順序存儲結(jié)構(gòu)也能在鏈式存儲結(jié)構(gòu)上進行查找的方法是A．散列查找B．順序查找C．二分查找D．以上選項均不能15．在一棵5階B樹中，每個非根結(jié)點中所含關(guān)鍵字的個數(shù)最少是A．1B．2C．3D．4二、填空題16．兩個棧S1和S2共用含100個元素的數(shù)組S[0..99]，為充分利用存儲空間，若S2的棧底元素保存在S[99]中，則S1的棧底元素保存在中。17．在一個單鏈表中，已知指針變量q所指結(jié)點不是表尾結(jié)點，若在q所指結(jié)點之后插入指針變量s所指結(jié)點，則正確的執(zhí)行語句是。18．設(shè)順序表第1個元素的存儲地址是1000，每個數(shù)據(jù)元素占6個地址單元，則第11個元素的存儲地址是。19．二叉樹采用順序存儲方式保存，結(jié)點X保存在數(shù)組A[7]中，若X有右孩子結(jié)點Y，則Y保存在中。20．一棵二叉樹中，度數(shù)為1的結(jié)點個數(shù)為n1，度數(shù)為2的結(jié)點個數(shù)為n2，則葉結(jié)點的個數(shù)為。21．已知廣義表LS=((a,b)，c,d)，head(LS)是。22．在無向圖G的鄰接矩陣A中，若A[i,j]=1，則A[j,i]=。23．已知大根堆中的所有關(guān)鍵字均不相同，最大元素在堆頂，第2大元素可能存在的位置有2個，第3大元素可能存在的位置有個。24．在有n個元素組成的順序表上進行順序查找。若查找每個元素的概率相等，則查找成功時平均查找長度是。25．線性探查法和拉鏈法解決的是散列存儲中的問題。三、解答題26．對題26圖中所給的二叉排序樹T，回答下列問題。(1)給出能生成了的2種關(guān)鍵字插入序列；(2)給出了的前序遍歷序列。27．對題27圖所示的無向帶權(quán)圖G，回答下列問題。(1)給出圖G的鄰接矩陣；(2)給出圖G的一棵最小生成樹。28．現(xiàn)有5個權(quán)值分別是20、31、16、7和15的葉結(jié)點，用它們構(gòu)造一棵哈夫曼樹，畫出該樹。29．對于給定的一組關(guān)鍵字序列{26,18,60,65,45,13,32}，寫出使用直接選擇排序方法將其排成升序序列的過程。四、算法閱讀題30．設(shè)非空雙向循環(huán)鏈表L的頭指針為head，表結(jié)點類型為DLNode，定義如下。typedefhatDataType;typedefstmctdlnode{DataTypedata;//data是數(shù)據(jù)域stmctdlnode*prior,*next;//prior指向前趨結(jié)點，next指向后繼結(jié)點}DLNode;typedefDLNode*DLinkList;初始時，L中所有結(jié)點的prior域均為空(NULL)，next域和data域中已經(jīng)正確賦值。如題30圖a所示。函數(shù)f30完成的功能是：將L中各結(jié)點的prior域正確賦值，使L成為雙向循環(huán)鏈表。如題30圖b所示。請在空白處填上適當內(nèi)容將算法補充完整。voidf30(DLinkListhead){DLNode*p;p=head;while(p->next!=(1)){(2)=p;p=p->next;}(3)=p;}31．已知二叉樹的二叉鏈表類型定義如下，閱讀程序，并回答問題。typedefcharDataType;typedefstmctnode{DataTypedata;//data是數(shù)據(jù)域stmctnode*lchild,*rchild;//分別指向左、右孩子結(jié)點}BinTNode;typedefBinTNode*BinTree;voidf31(BinTreebt){if(bt!=NULL){printf("%c",bt->data);f31(bt->lchild);printf("%c",bt->data);}}若二叉樹了如下所示，寫出調(diào)用f31(T)的輸出結(jié)果。32．閱讀下列程序，寫出f32的輸出結(jié)果。voidf32(){SeqStack*S;charx,y;InitStack(S);x='h';y='t';Push(S,x);Push(S,'c');x=Pop(S);Push(S,x);Push(S,y);Push(S,'a');Push(S,x);while(!StackEmpty(S)){y=Pop(S);pfintf("%c",y);}pfintf("%c\n",'!');}33．閱讀程序，回答下列問題。intf33(NodeTypeR[],KeyTypek,intn){inti=n-1,count=1;R[0].key=k;while(R[i].key!=k){i--;count++;}if(i==0)return-1;elsereturncount;}(1)變量count的含義是什么?(2)f33的功能是什么?五、算法計算題34．已知單鏈表類型定義如下：typedefstructnode{intdata;streetnode*next;}ListNode;typedefListNode*List_ptr;單鏈表L中結(jié)點數(shù)不少于2。設(shè)計算法判斷L中存儲的全部n個數(shù)據(jù)是否是斐波那契序列的前n項。如果是，則函數(shù)返回1，否則返回0。函數(shù)原型如下：intIsF(List_ptrhead)；//判定是否是斐波那契序列注：斐波那契序列的定義為：f0=0，f1=1，fn=fn-1+fn-2(n≥2)

2017年4月高等教育自學考試《數(shù)據(jù)結(jié)構(gòu)》試題課程代碼：02331一、單項選擇題(本大題共]5d、題，每小題2分，共30分)1．下列敘述中，不正確的是A．算法解決的只能是數(shù)值計算問題B．同一問題可以有多種不同算法C．算法的每一步操作都必須明確無歧義D．算法必須在執(zhí)行有限步后結(jié)束2．下列關(guān)于棧中邏輯上相鄰的兩個數(shù)據(jù)元素的敘述中，正確的是A．順序存儲時不一定相鄰，鏈式存儲時一定相鄰B．順序存儲時不一定相鄰，鏈式存儲時也不一定相鄰C．順序存儲時一定相鄰，鏈式存儲時也一定相鄰D．順序存儲時一定相鄰，鏈式存儲時不一定相鄰3．對帶頭結(jié)點的單循環(huán)鏈表從頭結(jié)點開始遍歷(head為頭指針，p=head->next)。若指針p指向當前被遍歷結(jié)點，則判定遍歷過程結(jié)束的條件是A．p==NULLB．head==NULLC．p==headD．head!=p4．設(shè)棧的入棧序列為1,2,3,4,5，經(jīng)過入、出棧操作后，，可能得到的出棧序列是A．2,3,5,1,4B．4,2,1,3,5C．3,4,1,2,5D．3,4,2,1,55．數(shù)組A[2][3]按行優(yōu)先順序存放，A的首地址為10。若A中每個元素占用一個存儲單元，則元素A[1][2]的存儲地址是A．10B．12C．14D．156．廣義表((a，b)，(c，d))的表尾是A．bB．dC．(c，d)D．(