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

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