數(shù)據(jù)結(jié)構(gòu)期末試卷及答案

PAGE2003-2004學(xué)年第二學(xué)期數(shù)據(jù)結(jié)構(gòu)期終試卷（A卷）（考試時(shí)間100分鐘）班級(jí)姓名學(xué)號(hào)得分單項(xiàng)選擇題（本大題共15小題，第小題2分，共30分）在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)符合題目要求，請(qǐng)將其代碼填在題后的括號(hào)內(nèi)。錯(cuò)選或未選均無分。1.算法必須具備輸入、輸出和[C]A.計(jì)算方法B.排序方法C．解決問題的有限運(yùn)算步驟D.程序設(shè)計(jì)方法2.有n個(gè)節(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是[A]訪問第i個(gè)節(jié)點(diǎn)（1≤i≤n）在第i個(gè)節(jié)點(diǎn)后插入一個(gè)新節(jié)點(diǎn)（1≤i≤n）刪除第i個(gè)節(jié)點(diǎn)（1≤i≤n）將n個(gè)節(jié)點(diǎn)從小到大排序3．單鏈表的存儲(chǔ)密度[C]A．大于1B.等于1C．小于1D.不能確定4．設(shè)將整數(shù)1,2,3,4,5依次進(jìn)棧，最后都出棧，出?？梢栽谌魏螘r(shí)刻（只要棧不空）進(jìn)行，則出棧序列不可能是[B]A．23415B.54132C．23145D.154325.循環(huán)隊(duì)列SQ的存儲(chǔ)空間是數(shù)組d[m]，隊(duì)頭、隊(duì)尾指針分別是front和rear，則執(zhí)行出隊(duì)后其頭指針front值是[D]A．front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m6.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是[B]A.O(1)B.O(n)C.O(n2)D.O(nlogn)7.設(shè)二維數(shù)組A[0..m-1][0..n-1]按行優(yōu)先順序存儲(chǔ)，則元素A[i][j]的地址為[B]A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)LOC(A[0][0])+[(i-1)*n+j-1]D.LOC(A[0][0])+[(i-1)*m+j-1]8.一個(gè)非空廣義表的表頭[D]A．一定是子表B.一定是原子C．不能是子表D.可以是原子，也可以是子表9．具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為[A]A．log2(n+1)-1B.log2n+1C.log2nD.log2n10.若要惟一地確定一棵二叉樹，只需知道該二叉樹的[D]A．前序序列B.中序序列C．前序和后序序列D.中序和后序序列11．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍[C]A．1/2B.1C.2D.412.拓?fù)渑判蜻\(yùn)算只能用于[C]A．帶權(quán)有向圖B.連通無向圖C．有向無環(huán)圖D.無向圖13．在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是[D]A．希爾排序B.冒泡排序C．插入排序D.選擇排序14．下列排序算法中時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n2)的是[C]A．堆排序B.冒泡排序C．直接選擇排序D.快速排序15．二分查找要求節(jié)點(diǎn)[A]A．有序、順序存儲(chǔ)B.有序、鏈接存儲(chǔ)C．無序、順序存儲(chǔ)D.無序、鏈接存儲(chǔ)填空題（本大題共10小題，每小題2分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯(cuò)填或不填均無分。16．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。17．在單鏈表中（假設(shè)結(jié)點(diǎn)指針域名稱為next），刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是p->next=p->next->next。18．已知循環(huán)隊(duì)列用數(shù)組data[n]存儲(chǔ)元素值，用front,rear分別作為頭尾指針，則當(dāng)前元素個(gè)數(shù)為(rear-front+n)%n。19．若n為主串長(zhǎng)，m為子串長(zhǎng)，則串的樸素匹配算法最壞的情況下需要比較字符的總次數(shù)為_______（n-m+1）×m__。20．廣義表((a),((b),j,(((d)))))的表尾是____(((b),j,(((d)))))________。21．已知二叉樹有61個(gè)葉子節(jié)點(diǎn)，且僅有一個(gè)孩子的節(jié)點(diǎn)數(shù)為45，則總節(jié)點(diǎn)數(shù)為____166__。22．解決計(jì)算機(jī)與打印機(jī)之間速度不匹配問題，須要設(shè)置一個(gè)數(shù)據(jù)緩沖區(qū)，應(yīng)是一個(gè)隊(duì)列結(jié)構(gòu)。23．n個(gè)頂點(diǎn)e條邊的圖采用鄰接表存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為_________O(n+e)___________。24．對(duì)于n個(gè)關(guān)鍵字的集合進(jìn)行冒泡排序，在最壞情況下所需要的時(shí)間為_____O（n2）________。25．在一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移n-i+1個(gè)元素。解答題（本大題共4小題，共25分）對(duì)于下面的稀疏矩陣，畫出其三元組法存儲(chǔ)表示(假設(shè)下標(biāo)從0開始)。（5分）00140000000-60700002400018000150000答案:021414-6207252433184115行號(hào)列號(hào)值行號(hào)列號(hào)值001234527.已知一棵二叉樹的中序序列和后序序列分別如下，請(qǐng)畫出該二叉樹。（5分）中序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA答案:AABCDEFHGJKIL28．設(shè)有一個(gè)關(guān)鍵碼的輸入序列｛55,31,11,37,46,73,63,02,07｝，（7分）從空樹開始構(gòu)造平衡二叉搜索樹，畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹的形態(tài)。若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)的類型及平衡旋轉(zhuǎn)的結(jié)果。(3分)計(jì)算該平衡二叉搜索樹在等概率下的搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。(4分)29．已知一個(gè)圖的鄰接表如下所示。（8分）畫出該圖的圖形；(4分)根據(jù)鄰接表分別畫出從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷所生成的生成樹。(4分)aabcdef12555243答案：CC算法閱讀題（本大題共3小題，每小題5分，共15分）30．設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為（a0,a1,…,an-1），在順序表上實(shí)現(xiàn)的插入和刪除算法如下，請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)內(nèi)容。(順序表的最大可容納項(xiàng)數(shù)為MaxSize)Template<classType>intSeqList<Type>::Insert(Type&x,inti){If(i<0||i>last+1||last==(1))return0;Else{Last++;For(intj=last;j>i;j--)data[j]=(2);(3);Return1;}}Template<classType>intseqList<Type>::Remove(Type&x){inti=Find(x);if(i>=0){last--;for(intj=(4);j<=last;j++)data[j]=(5);return1;}return0;}答案:(1)MaxSize-1(2)data[j-1](3)Data[i]=x(4)i(5)data[j+1]31．閱讀下面的算法，請(qǐng)回答下列問題：試說明算法的功能。當(dāng)執(zhí)行該程序時(shí)，輸入12345678-1，輸出什么結(jié)果？#defineStackSize200typedefintDataType;typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;voidPush(SeqStack*s,DataTypex){if(s->top!=StackSize-1)s->data[++s->top]=x;}DataTypePop(SeqStack*s){if(s->top!=-1)returns->data[s->top--];}voidmain(){DataTypei;SeqStacks;s.top=-1;scanf(“%d”,&i);while(i!=-1){push(&s,i);scanf(“%d”,&i);}while(s->top!=-1){i=Pop(&s);printf(“%6d”,i);}}答案:(1)程序的功能是把輸入的一串整數(shù)(用-1做結(jié)束標(biāo)記)，按照與輸入相反的次序輸出。用棧實(shí)現(xiàn)這一功能。（2）輸出結(jié)果87654321。32.已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。說明該算法的功能。Template<classType>intBinaryTree<Type>::height(BinTreeNode<Type>*t){if(t==NULL)return–1;inth1=height(t->leftChild);inthr=height(t->rightChild);return1+(h1>hr?h1:hr);}答案：該算法的功能是