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

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

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

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

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

2016年4月高等教育自學(xué)考試《數(shù)據(jù)結(jié)構(gòu)》試題課程代碼：02331一、單項(xiàng)選擇題1．下列選項(xiàng)中，屬于非線性數(shù)據(jù)結(jié)構(gòu)的是A．隊(duì)列B．棧C．二叉排序樹(shù)D．線性表2．瑞士計(jì)算機(jī)科學(xué)家沃思教授曾指出：算法+數(shù)據(jù)結(jié)構(gòu)=程序。這里的數(shù)據(jù)結(jié)構(gòu)指的是A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)B．?dāng)?shù)據(jù)的線性結(jié)構(gòu)和非線性結(jié)構(gòu)C．?dāng)?shù)據(jù)的緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D．?dāng)?shù)據(jù)的J頃序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)3．線性表順序存儲(chǔ)時(shí)，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素，其存儲(chǔ)地址A．一定相鄰B．一定不相鄰C．不一定相鄰D．可能不相鄰4．?dāng)?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]的存儲(chǔ)地址是4000，每個(gè)數(shù)據(jù)元素占5個(gè)存儲(chǔ)單元，則元素A[20]的起始存儲(chǔ)地址是A．4005B．4020C．4100D．41056.廣義表A=(a,(b,c,(e,f))),函數(shù)head(head(tail(A)))的運(yùn)算結(jié)果是A.aB.bC.cD.e7．設(shè)高度為h的二叉樹(shù)中，只有度為0和2的結(jié)點(diǎn)，則此類二叉樹(shù)包含的結(jié)點(diǎn)數(shù)至少是A．2hB．2h-1C．2h+1D．h+18．一棵非空二叉樹(shù)了的前序遍歷和后序遍歷序列正好相反，則了一定滿足A．所有結(jié)點(diǎn)均無(wú)左孩子B．所有結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是一棵滿二叉樹(shù)9．設(shè)圖的鄰接矩陣A如下所示。各頂點(diǎn)的度依次是A．1,2,1,2B．2,2,1,1C．3,4,2,3D．4,4,2,210．無(wú)向圖G如題10圖所示，從頂點(diǎn)a開(kāi)始進(jìn)行深度優(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)個(gè)頂點(diǎn)，下列關(guān)于G的最小生成樹(shù)T的敘述中，正確的是A．T中可能含有回路B．T中含有圖G的所有邊C．T是唯一的，且含有n-1條邊D．T可能不唯一，但權(quán)一定相等12．若要求對(duì)序列進(jìn)行穩(wěn)定的排序，則在下列選項(xiàng)中應(yīng)選擇A．希爾排序B．快速排序C．直接插入排序D．直接選擇排序13．下列排序算法中，空間復(fù)雜度最差的是A．歸并排序B．希爾排序C．冒泡排序D．堆排序14．下列排序算法中，初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而更多的算法是A．插入排序B．冒泡排序C．快速排序D．希爾排序15．對(duì)線性表上進(jìn)行二分查找時(shí)，要求上必須滿足A．以順序方式存儲(chǔ)B．以順序方式存儲(chǔ)，且數(shù)據(jù)元素有序C．以鏈接方式存儲(chǔ)D．以鏈接方式存儲(chǔ)，且數(shù)據(jù)元素有序二、填空題16．下面程序段的時(shí)間復(fù)雜度是。i=1；while(i<n)i=i*2；17．在單鏈表的p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是。18．只能在線性表的兩端進(jìn)行插入或刪除操作的兩種邏輯結(jié)構(gòu)分別是。19．廣義表A=(x,(y,z,(u,v,w)))的長(zhǎng)度是。20．一棵樹(shù)的后序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的序遍歷序列相同。21．在有向圖、無(wú)向圖中，其鄰接矩陣一定對(duì)稱的是。22．要計(jì)算圖中從某一頂點(diǎn)出發(fā)到其余各項(xiàng)點(diǎn)的最短路徑，可選用算法。23．設(shè)關(guān)鍵字序列為28,72,97,63,4,53,84，使用希爾排序法將其排成升序序列，若第一趟采用的間隔是3，則該趟排序的結(jié)果是。24．對(duì)具有15個(gè)關(guān)鍵字的關(guān)鍵字序列進(jìn)行順序查找時(shí)，查找成功的平均查找長(zhǎng)度為。25．在二叉排序樹(shù)的查找過(guò)程中，若當(dāng)前結(jié)點(diǎn)的關(guān)鍵字值大于待查找關(guān)鍵字，則應(yīng)在該結(jié)點(diǎn)的子樹(shù)上繼續(xù)查找。三、解答題26．設(shè)Q是有N個(gè)存儲(chǔ)空間的循環(huán)隊(duì)列，初始狀態(tài)front=rear=0，約定指針rear指向的單元始終為空。定義如下：#defineN100typedefstruct{chardata[N];intfront,rear;}CQ;GQ*Q;(1)寫出清空隊(duì)列的語(yǔ)句序列；(2)寫出判斷隊(duì)列為滿的表達(dá)式；(3)給出計(jì)算隊(duì)列長(zhǎng)度L的表達(dá)式。27．已知4×5稀疏矩陣M按行優(yōu)先順序存儲(chǔ)的三元組表如下：(1)寫出矩陣M(2)給出矩陣M的轉(zhuǎn)置矩陣T按行優(yōu)先順序存儲(chǔ)的三元組表。28．給定一組權(quán)值數(shù)據(jù){3,8,9,11,4}，回答下列問(wèn)題。(1)畫出基于所給數(shù)據(jù)的一棵哈夫曼樹(shù)；(2)計(jì)算所得哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度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是否存在拓?fù)渑判蛐蛄?，若不存在?qǐng)說(shuō)明理由：若存在請(qǐng)給出一個(gè)拓?fù)渑判蛐蛄小Ｋ?、算法閱讀題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)用語(yǔ)句為f30（A,5），f30的返回值是多少？（2）若主函數(shù)調(diào)用語(yǔ)句為f30（A,9），f30的返回值是多少？（3）給出算法f30的功能。31．已知棧的基本操作定義如下，請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，完成相應(yīng)的功能。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é)點(diǎn)的單鏈表初始為空。將從鍵盤讀入的每個(gè)字符作為一個(gè)結(jié)點(diǎn)加入該鏈表表尾，當(dāng)讀入回車符時(shí)結(jié)束并返回鏈表表頭指針。請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(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生成原二叉樹(shù)的鏡像樹(shù)，即將二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)互換。請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(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è)計(jì)題34.實(shí)現(xiàn)f34，對(duì)含有n個(gè)整數(shù)的數(shù)組A進(jìn)行選擇排序。函數(shù)原型如下。voidf34(intA[],intn)；／／對(duì)含有n個(gè)整數(shù)的數(shù)組A進(jìn)行選擇排序

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

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