數(shù)據(jù)結(jié)構(gòu)與算法考試樣卷

樣卷公開本樣卷僅對(duì)考試題型進(jìn)展說明，不代表最終考試內(nèi)容。請(qǐng)根據(jù)考試大綱全面復(fù)習(xí)。第20XX-20XX學(xué)年第X學(xué)期考試卷課程代碼：SS1005課程名稱：數(shù)據(jù)構(gòu)造與算法考試時(shí)間：90分鐘考試形式：閉卷試卷類型：A學(xué)分：4題次分?jǐn)?shù)評(píng)分一30二20三30四20總分100評(píng)卷人一、單項(xiàng)選擇題〔共15小題，每題2分，共30分〕在每題列出的選項(xiàng)中只有一個(gè)選項(xiàng)符合題目要求，將正確選項(xiàng)前的字母填寫在答題紙上。1.數(shù)據(jù)三種最主要的邏輯構(gòu)造是樹形構(gòu)造和〔〕。A.線性表、二叉樹C.線性表、圖B.線性構(gòu)造、圖狀構(gòu)造D.樹形構(gòu)造、堆2.以下數(shù)據(jù)構(gòu)造中，〔〕是線性數(shù)據(jù)構(gòu)造。A．樹B．圖C．堆D．棧3.下面關(guān)于線性表的表達(dá)中，錯(cuò)誤的選項(xiàng)是哪一個(gè)？〔〕A．假設(shè)線性表采用順序存儲(chǔ)構(gòu)造，那么必須占用一片連續(xù)的存儲(chǔ)單元。B．假設(shè)線性表采用順序存儲(chǔ)構(gòu)造，那么便于進(jìn)展插入和刪除操作。C．假設(shè)線性表采用鏈接存儲(chǔ)構(gòu)造，那么不必占用一片連續(xù)的存儲(chǔ)單元。D．假設(shè)線性表采用鏈接存儲(chǔ)構(gòu)造，那么便于插入和刪除操作。4.p是指向單鏈表頭結(jié)點(diǎn)的指針，假設(shè)該鏈表是空表，下面正確的說法是()。A.p==NULLB.p!=NULLC.p->next==NULLD.p->next==NULL5.在指針p指向單鏈表結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是：〔〕。A．p->next=s;B．s->next=p->next;p->next=s;C．s->next=p;D．s->next=p->next;6.存取數(shù)據(jù)時(shí)采用先進(jìn)先出的原那么的數(shù)據(jù)構(gòu)造是〔〕。A.隊(duì)列B.棧C.字符串D.線性表7.假定棧用單鏈表的存儲(chǔ)構(gòu)造表示，棧的棧頂指針為top，當(dāng)結(jié)點(diǎn)x入棧時(shí)執(zhí)行的操作為()。A.x->next=top;C.top=x;B.top->next=x;top=x;D.x->next=top;top=x;8.隊(duì)列的數(shù)據(jù)出隊(duì)操作在〔〕進(jìn)展。A.隊(duì)尾位置B.隊(duì)頭位置C.任意位置D.中間位置9.樹的度是指〔〕。A.樹的結(jié)點(diǎn)數(shù)B.樹的后繼個(gè)數(shù)C.樹中任一結(jié)點(diǎn)最大的后繼數(shù)D.以上都不是10.具有8個(gè)葉子結(jié)點(diǎn)的二叉樹中有〔〕個(gè)雙支結(jié)點(diǎn)。A．7B．8C．9D．1011.下面對(duì)完全二叉樹描述正確的選項(xiàng)是〔〕。A.所有層的結(jié)點(diǎn)數(shù)都必須是滿的B.除最后一層，其它層上的結(jié)點(diǎn)數(shù)都必須是滿的C.最后一層的結(jié)點(diǎn)數(shù)不能是滿的D.以上都不是12.將100個(gè)元素散列到10000個(gè)單元的散列表中，那么〔〕產(chǎn)生沖突。A.一定會(huì)B.一定不會(huì)C.仍可能會(huì)13.假定利用數(shù)組a表示一個(gè)棧，用top保存棧頂位置，top=-1表示?？?，棧中有數(shù)據(jù)，當(dāng)元素x進(jìn)棧時(shí)的操作為〔〕。A.a[--top]=x;B.a[top--]=x;C.a[++top]=x;D.a[top++]=x;14.n個(gè)頂點(diǎn)的無向圖，至多有〔〕條邊。A．n-lB．n(n-1)/2C．n(n+l)D．2n15.無向圖G=(V,E),其中：V={a,b,c,d},E={(a,b),(a,c),(b,d),(c,d)}，對(duì)該圖進(jìn)展廣度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的選項(xiàng)是〔〕。A．a(chǎn),c,b,dB．a(chǎn),d,c,bC．a(chǎn),c,d,bD．a(chǎn),b,d,c二、填空題〔每空2分，共20分〕答案寫在答題紙上1．?dāng)?shù)據(jù)三種最主要的邏輯構(gòu)造是線性構(gòu)造、樹形構(gòu)造、圖形構(gòu)造。2．在線性構(gòu)造中，第一個(gè)結(jié)點(diǎn)沒有直接前驅(qū)，最后一個(gè)結(jié)點(diǎn)沒有直接后繼3．在定義一個(gè)過程或函數(shù)時(shí)出現(xiàn)調(diào)用本過程或本函數(shù)的成分，稱之為遞歸。。4．分析下面程序段中帶下劃語句的執(zhí)行次數(shù)4。inti=0;s=0;n=300;do{i=i+1;s=s+10*i;}while(i<n&&s<n);5．采用順序存儲(chǔ)構(gòu)造的線性表中，表的長(zhǎng)度為n，刪除線性表中第i個(gè)元素〔1<=i<=n〕一個(gè)元素時(shí)，需向前移動(dòng)____n-i+1______個(gè)元素。6．在二分〔折半〕查找算法的前提條件是查找表中的數(shù)據(jù)必須是表中元素必須有序。7．表達(dá)式a/(b+c)*d對(duì)應(yīng)的后綴表達(dá)式是abc+*d-。8．寫出下面二叉樹的后序遍歷結(jié)果DBFGCA。三、簡(jiǎn)答題〔4小題，共30分〕將答案寫在答題紙上1．設(shè)對(duì)數(shù)據(jù)ABCD執(zhí)行一系列的進(jìn)出操作，假設(shè)數(shù)據(jù)出棧的順序是BACD，寫出相應(yīng)的數(shù)據(jù)進(jìn)出棧的操作順序?！?分〕2．一組數(shù)據(jù)的排序碼為：｛46，53，40，38，74，16，88｝，要求排序后數(shù)據(jù)從小到大升序排列，寫出利用簡(jiǎn)單項(xiàng)選擇擇排序的方法排序時(shí)經(jīng)過3趟排序后的結(jié)果?！?分〕3．畫出下面圖所對(duì)應(yīng)的鄰接矩陣〔8分〕4．設(shè)給定關(guān)鍵字輸入序列為〔48，27，61，95,38〕,散列表的存儲(chǔ)地址范圍是0～10，如采用開放地址法線性探查法解決沖突?！?分〕a.設(shè)計(jì)合理的散列函數(shù)；b.構(gòu)造出包含給定關(guān)鍵字的散列表。四、設(shè)計(jì)題〔共2小題，共20分〕將答案寫在答題紙上1．?dāng)?shù)組A和數(shù)組B中的數(shù)據(jù)分別是有序，編寫算法將數(shù)組A和B中的數(shù)據(jù)合并到數(shù)組C中，并保證C中的數(shù)據(jù)也是有序的，用文字描述算法執(zhí)行的步驟。(10分)2．設(shè)計(jì)函數(shù)Node*Get