《數(shù)據(jù)結(jié)構(gòu)》2010期考試卷(A)1

《《數(shù)據(jù)結(jié)構(gòu)》2010期考試卷(A)1》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、教務(wù)處填寫：XXXX學(xué)院（全日制）課程考試試卷（A）2010——2011學(xué)年度上學(xué)期系別：信科系班級(jí)名稱09A網(wǎng)絡(luò)課程名稱：《數(shù)據(jù)結(jié)構(gòu)》.考試時(shí)間：120分鐘閉卷題號(hào)一二三四五六七八九十總分應(yīng)得分303040100實(shí)得分評(píng)卷人第1頁(yè)（共頁(yè)）20年月日考試用專業(yè)：學(xué)號(hào)：姓名：裝訂線（答題不得超過(guò)此線）一、選擇題:（本大題共10小題,每題3分，共30分）1.樹最適合用來(lái)表示()。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)2.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有()條邊才能

2、確保是一個(gè)連通圖。A.5B.6C.7D.83.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，需要的輔助存儲(chǔ)空間大致為（）A.O（1）　　B.O（n）　　C.O（1og2n）D.O（n2）4.算法的計(jì)算量的大小稱為計(jì)算的（）A．效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度5.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為(D).A．2k-1B.2K+1C.2K-1　　　D.2k-16．以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(D)A.隊(duì)列　　B.棧C.線性表　　D.二叉樹7．棧和隊(duì)列的共同特點(diǎn)是()。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D

3、.沒(méi)有共同點(diǎn)4若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為()A.1，2，3　　　B.9，5，2，3　　　C.9，5，3　　　D.9，4，2，39.計(jì)算機(jī)的算法是指（）A.計(jì)算方法B.排序方法C.解決問(wèn)題的步驟序列D.調(diào)度方法10.以下那個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（）A.棧B.哈希表C.線索表D.雙向鏈表二、填空題（每空1分，共30分）1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為、　、　、　　四種。2.函數(shù)重載要求、或有所不同。3．在帶附加表頭的循環(huán)雙

4、向鏈表中，表頭附加結(jié)點(diǎn)的指針域指向最后一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)。4．在以HL為表頭指針的帶附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為和。5．在由數(shù)組a中元素結(jié)點(diǎn)構(gòu)成的單鏈表中，刪除下標(biāo)為i的結(jié)點(diǎn)后，需要把該結(jié)點(diǎn)插入到空閑表的表頭，具體操作為、。6．在由數(shù)組a中元素結(jié)點(diǎn)構(gòu)成的單鏈表中，刪除下標(biāo)為i的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，并將被刪除的結(jié)點(diǎn)的下標(biāo)賦給i的時(shí)候，所進(jìn)行的操作（需要用一個(gè)臨時(shí)變量p）應(yīng)描述為和。7．在稀疏矩陣的十字鏈接存儲(chǔ)中，每個(gè)結(jié)點(diǎn)的down指針域指向相同的下一個(gè)結(jié)點(diǎn)，right指針域指

5、向相同的下一個(gè)結(jié)點(diǎn)。8．一個(gè)廣義表中的元素分為元素和元素兩類。9．廣義表A=((a,(b,(),c),((d),e)))的長(zhǎng)度為，深度為。10．向一個(gè)順序棧插入一個(gè)元素時(shí)，首先應(yīng)，然后再將待插入元素放入棧頂位置。11．對(duì)于隊(duì)列，應(yīng)在進(jìn)行插入，在進(jìn)行刪除。412．中綴表達(dá)式2+7/(4-1)所對(duì)應(yīng)的后綴表達(dá)式為。13．后綴表達(dá)式“10354-*-1+32+-”的值為。14.一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g))),則e結(jié)點(diǎn)的雙親結(jié)點(diǎn)為，孩子結(jié)點(diǎn)為，樹的深度為　。三、算法閱讀題（本大題共2小題，每

6、小題20分，共40分）1．下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為：??????????????comstr(s1,s2)=????請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。intcomstr(LinkStrings1,LinkStrings2){//s1和s2為兩個(gè)鏈串的頭指針??while(s1&&s2){??????if(s1－>datedate)return－1；??????if(s1－>date>s2－>date)return1；??????????①????；??????????②????；?????

7、?}??????????if(??③??)return－1；??????if(??④??)return1；????????????⑤??；????}答：①②③④⑤42.閱讀下面的算法??????LinkListmynote(LinkListL)??????{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針????????????if(L&&L->next){??????????????????q=L；L=L－>next；p=L；????????S1：??????while(p－>next)p=p－>next；????????S

8、2：??????p－>next=q；q－>next=NULL；??????????????}??????????????return??L；????????????}????請(qǐng)回答下列問(wèn)題：??（1）說(shuō)明語(yǔ)句S1的功能；????（2）說(shuō)明語(yǔ)句組S2的功能；??????（3）設(shè)鏈表表示的線性表為（a1,a2,…,an）,寫出算法執(zhí)行后的返回值所表示的線性表。答：4