13級(jí)數(shù)據(jù)結(jié)構(gòu)與算法期末試卷B

共10PAGE4*2頁第=PAGE4*2-17PAGE4*2-1頁 共10PAGE4*2頁第PAGE4*2PAGE4*2-1頁2013—2014學(xué)年第二學(xué)期閩江學(xué)院期末試卷考試課程：《數(shù)據(jù)結(jié)構(gòu)與算法》試卷類別：A卷□B卷t考試形式：閉卷t開卷□適用專業(yè)年級(jí)：13級(jí)金融服務(wù)、13級(jí)軟件服務(wù)裝訂線裝訂線題號(hào)一二三總分得分一、單項(xiàng)選擇題60%（請(qǐng)將答案填入答題卡相應(yīng)位置，30題，每題2分，共60分）得分1、計(jì)算機(jī)算法必須具備輸入、輸出和（）等5個(gè)特性。A．可行性、可移植性和可擴(kuò)充性B．可行性、確定性和有窮性C．確定性、有窮性和穩(wěn)定性D．易讀性、穩(wěn)定性和安全性2、設(shè)語句x++的時(shí)間是單位時(shí)間，則以下語句的時(shí)間復(fù)雜度為（）。for(i=1;i<=n;i++) x++;A．O(1)B．O(n2)C．O(n)D．O(n3)3、以下哪種邏輯結(jié)構(gòu)關(guān)系最松散（） A．集合B．線性C．樹D．圖4、以下哪種線性表的存儲(chǔ)地址一定是連續(xù)的（）A．有序表B．順序表C．單鏈表D．雙鏈表5、帶頭指針的循環(huán)鏈表在表尾插入，時(shí)間復(fù)雜性()A．O(1)B．O(n）C．O(n2)D．O(n3)6、設(shè)結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，L是帶頭結(jié)點(diǎn)和尾指針的單循環(huán)鏈表，L->last是表尾結(jié)點(diǎn)指針。若想刪除鏈表的首元結(jié)點(diǎn)，則應(yīng)執(zhí)行下列（）操作？A．s=L->last;L->last=L->last->next;free(s);B．L->last=L->last->next;free(L->last);C．L->last=L->last->next->next;free(L->last);D．s=L->last->next->next;L->last->next->next=s->next;free(s);7、帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是（）A．L->next==NULL;B．L!=NULL;C．L->next==L;D．L==NULL;8、設(shè)結(jié)點(diǎn)結(jié)構(gòu)為(prior,data,next)，L是不帶頭結(jié)點(diǎn)循環(huán)雙鏈表，L是表頭結(jié)點(diǎn)指針。若想刪除循環(huán)雙鏈表中p結(jié)點(diǎn)的后繼結(jié)點(diǎn)(假設(shè)存在)，則應(yīng)執(zhí)行下列（）操作？A．p->next=p->next->next;B．p->next=p->next->next;p->next->prior=p;C．p->next=p->next->next;p->next->next->prior=p;D．p->next->prior=p;p->next=p->next->next;9、若在線性表中經(jīng)常涉及插入刪除操作，則采用以下哪種表進(jìn)行元素存儲(chǔ)比較好（）？A．有序表B．順序表C．鏈表D．棧10、在一個(gè)長度為n的順序表中插入第i個(gè)元素(1<=i<=n+1)時(shí)，需向前移動(dòng)（）個(gè)元素。A．n-iB．n-i+1C．n-i-1D．i11、假定對(duì)元素序列（7,3,5,9,1,12）進(jìn)行堆排序，并且采用小根堆，則由初始數(shù)據(jù)構(gòu)成的初始堆為（）。A．1,3,5,7,9,12B．1,3,5,9,7,12C．1,5,3,7,9,12D．1,5,3,9,12,712、假定一個(gè)初始堆為(1,5,3,9,12,7,15,10)，則進(jìn)行第一趟堆排序后得到的結(jié)果為（）。A．3,5,7,9,12,10,15,1B.3,5,9,7,12,10,15,1C.3,7,5,9,12,10,15,1D.3,5,7,12,9,10,15,113、在平均情況下速度最快的排序方法為（）A．直接選擇排序B．歸并排序C．基數(shù)排序D．快速排序14、若一個(gè)元素序列基本有序，則選用（）方法較快。A．直接插入排序B．簡(jiǎn)單選擇排序C．歸并排序D．快速排序15、對(duì)1000個(gè)元素進(jìn)行排序，要求既快又省空間，則以下（）算法比較好。A．直接插入排序B．堆排序C．歸并排序D．快速排序16、設(shè)元素的進(jìn)棧次序?yàn)?,2,3，那么以下哪種是不可能的出棧序列。A．123B．132C．312D．31217、棧的插入和刪除操作在（）進(jìn)行。A．棧頂B．棧底C．中間D．任意位置18、隊(duì)列中元素的進(jìn)出原則為（）。A．先進(jìn)先出B．后進(jìn)先出C．大數(shù)先出D．小數(shù)先出19、對(duì)二叉排序樹進(jìn)行以下哪種遍歷會(huì)得到一個(gè)有序序列。A.先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷20、由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A.24 B.48 C.72 D.C.G->vertices[i].nextarcD.G->vertices[j].nextarc三、填空題30%（請(qǐng)將答案填入答題卡相應(yīng)位置，除第3題第一空為4分外，其余都為2分，共30分）得分1、已知記錄(46,74,53,14,26,38,86,65,27,34)，請(qǐng)給出歸并排序的第一趟排序結(jié)果(以第一個(gè)元素作為基準(zhǔn))：______2、從一棵二叉排序樹中查找一個(gè)元素時(shí)，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向______查找。3、假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請(qǐng)畫出該二叉樹______(4分)，并寫出該二叉樹的先序遍歷序列______。4、已知二叉樹的二叉鏈表表示法定義如下：typedefcharTElemType;typedefstructBiTnode{TElemTypedata;structBiTnode*lchild,*rchild;}BiTNode,*BiTree;請(qǐng)將下列二叉樹的查找算法補(bǔ)充完整：intLocateElem(BiTreeT,TElemTypee)//e為要查找的元素{ intfloor;//用于記錄層數(shù) if(T)//若樹不空 {if(___(1)___)//若在根處找到 return1; floor=LocateElem(___(2)___);//在左子樹查找 if(floor>0)//若在左子樹中找到 return___(3)___; floor=LocateElem(___(4)___); if(floor>0) return___(5)___; } return0;//若樹為空，則直接返回0，說明找不到}5、已知圖的鄰接表定義如第二題所示，下列程序段為圖的深度優(yōu)先搜索算法，請(qǐng)將算法中缺失的語句補(bǔ)充完整：voidDFS(ALGraphG,intv)//從編號(hào)為v的頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷{//假設(shè)所有變量、函數(shù)皆已定義visited[v]=true;//訪問標(biāo)志數(shù)組，true表示訪問過，false表示未被訪問過V