青島大學(xué)910數(shù)據(jù)結(jié)構(gòu)

青島大學(xué)2017年碩士研究生入學(xué)考試試題科目代碼：910科目名稱：數(shù)據(jù)結(jié)構(gòu)（共5頁(yè)）請(qǐng)考生寫明題號(hào)，將答案全部答在答題紙上，答在試卷上無效一、單項(xiàng)選擇題（本大題共10道小題，每小題2分，共20分）1．計(jì)算機(jī)算法指的是（）。A.計(jì)算方法B.排序方法C.解決問題的步驟序列D.存儲(chǔ)結(jié)構(gòu)2．鏈表不具有的特點(diǎn)是（）。A.插入、刪除不需要移動(dòng)元素B.可隨機(jī)訪問任一元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性長(zhǎng)度成正比連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（）。A.—定連續(xù) B.—定不連續(xù)C.不一定連續(xù) D.部分連續(xù)，部分不連續(xù)一個(gè)遞歸算法必須包括（）。A.遞歸部分 B.終止條件和遞歸部分C.迭代部分 D.終止條件和迭代部分棧和隊(duì)列的共同點(diǎn)是（）。A.都是先進(jìn)先出 B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷中的相對(duì)次序（）。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)由帶權(quán)為｛8，2，5，7｝的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為（）。A.23 B.37 C.46 D43若從無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問圖中所有的頂點(diǎn)，則該圖一定是（）圖。A.非連通B.連通 C.強(qiáng)連通D.有向適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。A.鏈接方式存儲(chǔ)，元素?zé)o序B.鏈接方式存儲(chǔ)，元素有序C.順序方式存儲(chǔ)，元素?zé)o序D.順序方式存儲(chǔ)，元素有序10．對(duì)n個(gè)關(guān)鍵字作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是()。A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)二、簡(jiǎn)答題(本大題共6道小題，每題5分，共30分)1．如果有n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？2.有5個(gè)元素，其入棧次序?yàn)椋篈,B,C,D,E,在各種可能的出棧次序中，以元素C,D最先出棧(即C第一個(gè)且D第二個(gè)出棧)的次序有哪幾個(gè)？3．簡(jiǎn)述樹與二叉樹的轉(zhuǎn)化方法。試舉一個(gè)例子說明。4．簡(jiǎn)要說明圖的各種遍歷方法。5．簡(jiǎn)述順序查找和折半查找的優(yōu)缺點(diǎn)。6．簡(jiǎn)要說明歸并排序的基本思想。三、綜合應(yīng)用題(本大題共4道小題，每題12分，共48分)已知一棵二叉樹的中序遍歷序列為BCAFEC，后序遍歷序列為CBECFA,試畫出該二叉樹,并給出該二叉樹的先序序列。對(duì)于下圖所示的有向圖,試給出：(1)鄰接表；(2)從頂點(diǎn)v1出發(fā)的深度優(yōu)先遍歷序列；查找此平衡二叉樹排序中任一結(jié)點(diǎn)的平均查找長(zhǎng)度為多少？4.某設(shè)待排序的關(guān)鍵字集合為{12,2,16,30,28,10,16*,20,6,18},試分別回答下面的問題。給出希爾排序(增量選取5,3,1)的結(jié)果；寫出快速排序第一趟之后的狀態(tài)；把關(guān)鍵字集合調(diào)整成堆頂元素取最大值的堆。四、算法分析題(本大題共3道小題，每題10分，共30分)1．下面的算法是在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個(gè)元素，并由e返回其值，請(qǐng)?jiān)诳瞻滋幪钊胝_的語句。StatusListDelete(LinkList&L,inti,ElemType&e){TOC\o"1-5"\h\zLinkListp,q;p= ① ;intj=0;while(p->next&& ② ){p=p->next;++j;}if(!( ③ )||j>i-1)returnERROR;q=p->next;p->next= ④ ;e=q->data; ⑤ ;returnOK;}2．閱讀下面的代碼，試說明算法的功能。intUnknown(BiTNode*T,BiTNode*s){//s為指向二叉排序樹中某個(gè)結(jié)點(diǎn)的指針intk=0;BiTNode*p=T;if(T!=NULL){k++;while(p->data!=s->data){if(p->data<s->data)p=p->rchild;elsep=p->lchild;k++;}}returnk;}3．下面代碼是中序遍歷二叉樹T的非遞歸算法。請(qǐng)?jiān)诳瞻滋幪钊胝_的語句。StatusInOrderTraverse(BiTreeT){SqStackS;BiTreep;TOC\o"1-5"\h\z ① ;Push(S,T);while(! ② ){while(GetTop(S,p)&& ③ )Push(S,p->lchild);Pop(S,p);if(!StackEmpty(S)){ ④ ;printf("%c",T->data); ⑤ ;}}returnOK;}五、算法設(shè)計(jì)題(本大題共2道小題，每題11分，共22分)1．已知L1、L2分別為兩個(gè)循環(huán)單鏈表(帶頭結(jié)點(diǎn))的指針，m,n分別為L(zhǎng)I、L2表中數(shù)據(jù)元素個(gè)數(shù)。試設(shè)計(jì)一算法，用