華工數(shù)據(jù)結(jié)構(gòu)卷

一.選擇題1.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（）個元素。A．8B.63.5C.63D.72.設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每個元素占一個空間，則A[3][3]在（）位置，（10）表明用10進(jìn)數(shù)表示。！P113A．692（10）B.626（10）C.709（10）D.724（10）·3.一個有序順序表有255個對象，采用順序搜索查表，平均搜索長度為（）。？A．128B.127C.126D.255·4.含5個結(jié)點（元素值均不相同）的二叉樹搜索樹有（）種。A．54B.42C.36D.655．N個頂點的連通圖至少有（）條邊。A．N－1B.NC.N＋1D.0 6．對于兩個函數(shù)，若函數(shù)名相同，但只是（）不同則不是重載函數(shù)。A．參數(shù)類型B.參數(shù)個數(shù)C.函數(shù)類型D.函數(shù)個數(shù)7．若需要利用形參直接訪問實參，則應(yīng)把形參變量表明為（）參數(shù)。A．指針B.引用C.值D.地址·8．下面程序的時間復(fù)雜度為（）。！for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A．O(m2)B.O(n2)C.O(m*n)D.O(m+n)·9.下面算法的時間復(fù)雜度為（）。！intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A．O(1)B.O(n)C.O(n2)D.O(n!)10.設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為(data,link)。已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s,則應(yīng)執(zhí)行下列哪一個操作（）。！A．s->link=p->link;p->link=s;B.q->link=s;s->link=p;C.p->link=s->link;s->link=q;D.p->link=s;s->link=q;11.設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為(data,link)。若想摘除結(jié)點*p的直接后繼，則應(yīng)執(zhí)行下列哪一個操作（）。！A．p->link=p->link->link;B.p=p->link;p->link=p->link->linkC.p->link=p->link;D.p=p->link->link;12.棧的插入和刪除操作在（）進(jìn)行。！A．棧頂B.棧底C.任意位置D.指定位置13．若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)哪種情況（）。！A．3，2，1B.2，1，3C.3，1，2D.1，3，2#14．廣義表A(a),則表尾為（）。A．a(chǎn)B.(())C.空表D.（a）#15．下列廣義表是線性表的有（）。A．E(a,(b,c))B.E(a,E)C.E(a,b)D.E(a,L())16.折半搜索與二叉搜索樹（即二叉排序樹）的時間性能（）。A．相同B.完全不同C.有時不相同D.不確定17．采用折半搜索算法搜索長度為n的有序表時，元素的平均搜索長度為（）。！A．O(nlog2n)B.O(n)C.O(log2n)D.O(n)18.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）。！A．中序遍歷B.前序遍歷C.后序遍歷D.按層次遍歷19．每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做（）排序。！A．插入B.選擇C.交換D.外排序20．采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。A．中序遍歷B.前序遍歷C.后序遍歷D.按層次遍歷二.填空題1.算法是一個有窮的指令集，它為解決某一特定任務(wù)規(guī)定了一個運(yùn)算序列。它應(yīng)具有輸入、輸出、___確定性________、有窮性和可執(zhí)行性等特性。！·2.在一棵度為3的樹中，度為2的結(jié)點個數(shù)是1，度為0的結(jié)點個數(shù)是6，則度為3的結(jié)點個數(shù)是_______2____。！3.隊列的插入操作在______隊尾_____進(jìn)行，刪除操作在____隊頭_______進(jìn)行。4.當(dāng)用長度為n的數(shù)組順序存儲一個棧時，若用top==n表示?？?，則表示棧滿的條件為_____top==0______。！5.對序列(49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個元素為基準(zhǔn)元素得到的劃分結(jié)果是___[132738]45[50657697]_______________。！6.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為}2.刪去鏈表中除表頭結(jié)點外的所有其他結(jié)點template<classType>voidList<Type>::MakeEmpty(){ListNode<Type>*q;while(first→link!=NULL){

q=firstlink;firstlink=qlink;//將表頭結(jié)點后第一個結(jié)點從鏈中摘下deleteq;//釋放它}last=first;//修改表尾指針} 3.刪去鏈?zhǔn)疥狀^結(jié)點（隊頭指針為QueueNode<Type>*front），并返回隊頭元素的值template<classType>TypeQueue<Type>::DeQueue(){assert(!IsEmpty()); //判隊空的斷言

QueueNode<Type>*p=______front____________________; Typeretvalue=p→data;//保存隊頭的值

__front=frontlink__; //新隊頭deletep;returnretvalue; }#4.最小堆的向下調(diào)整算法（沒有）template<classType>voidMinHeap<Type>::FilterDown(intstart,intEndOfHeap){inti=start,j=2*i+1;//j是i的左子女Typetemp=heap[i];while(j<=EndOfHeap){if(j<EndOfHeap&&heap[j].key>heap[j+1].key)j++;//兩子女中選小者if(temp.key<=heap[j].key)break;else{heap[i]=heap[j];i=j;j=2*j+1____；} } __heap[i]=temp;____; }5．基于有序順序表的折半搜索遞歸算法（Element為有序順序表）！template<classType>intorderedList<Type>::BinarySearch(constType&x,constintlow,constinthigh)const{intmid=-1;if(low<=high){

____mid=(low+high)/2______;if(Element[mid].getKey()<x)

mid=BinarySearch(__x,mid+1,high_____);elseif(Element[mid].getKey()>x) mid=BinarySearch(x,low,mid-1);}returnmid;}6.直接插入排序的算法（按關(guān)鍵碼Key非遞減順序?qū)?shù)據(jù)表list進(jìn)行排序）（無）template<classType>voidInsertionSort(datalist<Type>&list){

for(inti=1;i<list.CurrentSize;i++)_______inter(list,i)_______;}

template<classType>viodInsert(datalist<Type>&list,inti){Element<Type>temp=list.Vector[i];intj=i;//從后向前順序比較while(j>0&&temp.getKey()<list.Vector[j-1].getKey()){ ______list.vector[j]=list.vector[j-1]______;j--;}list.Vector[j]=temp;}7.直接選擇排序的算法:（沒）template<classType>voidSelectSort(datalist<Type>&list){

for(inti=0;i<list.CurrentSize-1;i++)___SelectExchange(list,i)____;}

template<classType>viodSelectExchange(datalist<Type>&list,constinti){intk=i;for(intj=i+1;j<list.CurrentSize;j++)if(list.Vector[j].getKey()<list.Vector[k].getKey())____k=j_______;//當(dāng)前具有最小關(guān)鍵碼的對象if(k!=i)Swap(list.Vector[i],list.Vector[k]);//交換}#8.判斷一個帶表頭結(jié)點的雙向循環(huán)鏈表L是否對稱相等的算法如下所示：（無）intsymmetry(DblListDL){intsym=1;DblNode*p=DL->rLink,*q=DL->lLink;While(p!=q&&p->rLink!=q&&sym==1)if(p->data==q->data){____p=prLink_____;_______q=qlLink_________________;}elsesym=0;returnsym;}五、簡答題給定權(quán)值集合{15,03,14,02,06,09,16,17},構(gòu)造相應(yīng)的霍夫曼樹,并計算它的帶權(quán)外部路徑長度。！(Ⅰ)05171609061415F：17160906021415(Ⅰ)05171609061415F：17160906021415020303020303(Ⅱ)1716091415(Ⅱ)171609141520161415(Ⅲ)171120161415(Ⅲ)171109110605091106050203020306050605(Ⅴ)332029020329161720(Ⅳ)(Ⅴ)332029020329161720(Ⅳ)161711091514141109151617110915141411091505060506060506050203020302030203(Ⅰ)05171609061415F：17160906021415(Ⅰ)05171609061415F：17160906021415020303020303(Ⅱ)1716091415(Ⅱ)171609141520161415(Ⅲ)171120161415(Ⅲ)171109110605091106050203020306050605(Ⅴ)332029020329161720(Ⅳ)(Ⅴ)332029020329161720(Ⅳ)1617110915141411091516171109151414110915050605060605060502030203020302038282(Ⅶ)4933(Ⅵ)4933(Ⅶ)4933(Ⅵ)4933172920161716292017292016171629201411091511091514141109151109151406050605060506050302030203020302 此樹的帶權(quán)路徑長度WPL=229。線性表可用順序表或是鏈表存儲，此兩種存儲表示各有哪些特點，優(yōu)缺點？！P50設(shè)有一個輸入數(shù)據(jù)的序列是{46,25,78,62,12,37,70,29}，試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。按順序逐個輸入46/\2578/\/123762/\2970對于如右圖所示的有向圖，試寫出：！(1)從頂點①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2)從頂點②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；P178#5.用廣義表的帶表頭結(jié)點的存儲表示法表示下列集合。A=()B=(6,2) C=(‘a(chǎn)’,(5,3,‘x’))D=(B,C,A) E=(B,D)6.右圖所示為一有向圖，請給出該圖的下述要求：（1）給出每個頂點的入度和出度；130222312431521614（2）以結(jié)點3為起始結(jié)點，分別畫出該圖的一個深度優(yōu)先生成樹和一個寬度優(yōu)先生成樹；（3）給出該圖的鄰接矩陣；（4）給出該圖的鄰接表；（5）給出該圖的逆鄰接表；7.已知二叉樹的先序、中序和后序序列分別如下，但其中有一些已模糊不清，試構(gòu)造出該二叉樹。先序序列_BC_EF__中序序列BDE_AG_H后序序列e_DCb_GHf_A8.已某個不帶權(quán)的無向圖采用鄰接矩陣存儲方法依次將頂點的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為

01100000

10