1.計算機(jī)算法指的是(A1.計算機(jī)算法指的是(A.程序C?調(diào)度方法C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)中原工學(xué)院信息商務(wù)學(xué)院2006?2007學(xué)年第二學(xué)期|重修標(biāo)識軟件、網(wǎng)絡(luò)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程期末試卷題號—一二三四五六七八九十總分、單項(xiàng)選擇題(本大題共10小題，每小題2分，共30分))。B.問題求解步驟的描述D.排序方法以下數(shù)據(jù)結(jié)構(gòu)中，()個是非線性數(shù)據(jù)結(jié)構(gòu)。A.樹 B.字符串 C?隊(duì)D.棧對于順序存儲的線性表，訪問元素和插入元素的時間復(fù)雜度分別為：()。A.O(n)O(n)B.O(n)O(1) C.O(1)O(n)D.O(1)O(1)在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是()。A.p->next=s;s->next=p->next B.s->next=p->next;p->next=sC.p->next=s;p->next=s->next D.p->next=s->next;p->next=sn個頂點(diǎn)的有向圖中，含有向邊的數(shù)目最多為()A.n-1 B.nC.n(n-1)/2 D.n(n-1)TOC\o"1-5"\h\z循環(huán)隊(duì)列存儲在數(shù)組A[0..m]中，則入隊(duì)時的操作為( )A.rear=rear+1 B.rear=(rear+1)mod(m-1)

\o"CurrentDocument"字符串’ababaabab’的next函數(shù)為( )A.011232232 B.012341234 C.011122334D.011234234若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)為( )A.9B.11 C.15 D.不確定設(shè)有數(shù)組A[i,j],數(shù)組的每個元素長度為3字節(jié)，i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)以列為主序存放時，元素A[5,8]的首地址為( )。A.BA+141B.BA+180C.BA+222 D.BA+225n個頂點(diǎn)的帶權(quán)無向連通圖的最小生成樹包含()個頂點(diǎn)A.n-1 B.nC.n/2 D.n+111,有關(guān)二叉樹的下列說法正確的是()A.二叉樹的度為2 B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個結(jié)點(diǎn)的度為2 D-二叉樹中任何一個結(jié)點(diǎn)的度都為212.關(guān)鍵路徑是AOE網(wǎng)中()。A.從源點(diǎn)到匯點(diǎn)的最長路徑 B.從源點(diǎn)到匯點(diǎn)的最短路徑C?最長回路 D.最短路徑.若查找每個記錄的概率相等，則在具有n個記錄的連續(xù)文件中采用順序查找查找一個記錄，其平均查找長度ASL為()。A.(n-1)/2 B.n/2 C.(n+1)/2 D.n.就平均性能而言，目前最好的內(nèi)部排序方法是()A.冒泡排序 B.希爾排序 C,堆排序 。?快速排序15.已知廣義表LS=((ab,c),(d,ef)),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是()。A.head(tail(LS)) B.tail(head(LS))C.head(tail(head(tail(LS))))D.head(tail(tail(head(LS))))二、填空題（本大題共10小題，每空2分，共20分）數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。帶頭結(jié)點(diǎn)的單循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是。在隊(duì)列中，允許進(jìn)行插入操作的一端稱為，允許進(jìn)行刪除操作的一端稱為。假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，其中結(jié)點(diǎn)結(jié)構(gòu)為（假設(shè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，其中結(jié)點(diǎn)結(jié)構(gòu)為（data，next），并且只設(shè)一個指針rear指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，請寫出相應(yīng)的入隊(duì):EnQueue（LinkList&rear,ElemTypex）和出隊(duì)DeQueue（LinkList&rear,ElemType&x算法。已知一棵二叉樹的前序遍歷的結(jié)果是ABDFCEGH，中序遍歷的結(jié)果是BFDAGEHC，（1） 畫出這棵二叉樹；（4分）（2） 畫出這顆二叉樹的后序線索樹；（3分）（3） 將這顆二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。（3分）串中所含字符個數(shù)稱為該串的。深度為h的完全二叉樹至少有個結(jié)點(diǎn)，至多有個結(jié)點(diǎn)。對關(guān)鍵字序列（52,80，63,44,48,91）進(jìn)行一趟快速排序之后得到的結(jié)果為有n個頂點(diǎn)的有向圖，至少需要 條弧才能保證是連通的。算法設(shè)計題（10分）四、應(yīng)用題1.設(shè)一數(shù)列輸入順序?yàn)?23456，若采用棧結(jié)構(gòu)，能否得到輸出順序?yàn)?25641和154623的序列，并說明為什么不能得到或者如何得到（即寫出以‘S’表示進(jìn)棧和以‘X’表示出棧的棧操作序列）。（8分）將如下所示的有向圖給出其存儲結(jié)構(gòu)的鄰接鏈表表示（注：這里頂點(diǎn)的鄰接點(diǎn)按升序排列），然后分別寫出對其鄰接表從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列的結(jié)果。（畫出鄰接鏈表4分，求出深度優(yōu)先序列和廣度優(yōu)先序列各3分，共10分）4.給定關(guān)鍵碼序列（26,25,20,33,21,24,45,204,42,38,29,31），要用哈希法進(jìn)行存儲，規(guī)定裝填因子a=0.6（1）請給出除留余數(shù)法的哈希函數(shù)；（4分）（2）用線性探測法解決沖突，請畫出插入所有的關(guān)鍵碼后得到的哈希表；（5分）（3）計算等概率情況下查找成功的平均查找長度。（3分）中原工學(xué)院信息商務(wù)學(xué)院2006?2007學(xué)年第2學(xué)期 d卷軟件、網(wǎng)絡(luò)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程期末試卷標(biāo)準(zhǔn)答案（即評分標(biāo)準(zhǔn)）、單選題（每小題2分，共30分）1.B2.A3.C4.B5.D6.D7.D8.B9.B10.B11.B12.A13.C14.D15.C二、填空題(每空2分，共20分)數(shù)據(jù)元素關(guān)系L->next->next==L隊(duì)尾隊(duì)頭長度2h-i 2h-1484452638091n三、算法設(shè)計題：(共10分)參考算法：voidEnQueue(LinkList&rear,ElemTypex){s=newLNode;//1分if(!s)exit(1);s->data=x;s->next=rear->next;//2分rear->next=s;rear=s;//2分}voidDeQueue(LinkList&rear,ElemType&x){if(rear->next==rear)exit(1);//1分s=rear->next->next;x=s->data;〃2分rear->next->next=s->next〃1分if(s==rear)rear=rear->next;//1分deletes;四、應(yīng)用題1、(共8分)能得到325641,(2分)S(1)S(2)S(3)X(3)X(2)S(4)S(5)X(5)S(6)X(6)X(4)X(1)(2分)不能得到154623(2分)S(1)X(1)S(2)S(3)S(4)S5)X(5)X(4)S(6)X(6),此時，棧中還有23，所以不會得到23,只能得到32(2分)2、（共10分）（1）（4分）3、供10分。其中：鄰接鏈表4分，深度和廣度優(yōu)先遍歷序列各3分）深度優(yōu)先遍歷序列：125967384廣度優(yōu)先遍歷序列：1234567894、供12分）（1） （4分）表長m=12/0.6=20，H（key）=keyMOD19（2） （5分）H（26）=7成功 H（25）=6成功 H（20）=1成功H（33）=14成功 H（21）=2成功 H（24）=5成功H（45）=7沖突H1（45）=8成功H（204）=14沖突H1（204）=15成功H（42）=4