計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)試題

計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)試題一、填空題（每小題2分）1、與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（）A存儲(chǔ)結(jié)構(gòu)B邏輯結(jié)構(gòu)C算法D操作2、鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是（）A插入操作更加方便B通常不會(huì)出現(xiàn)棧滿(mǎn)的情況C不會(huì)出現(xiàn)?？盏那闆rD刪除操作更加方便3、對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是（）A直接選擇排序B直接插入排序C快速排序D起泡排序4、若采用鄰接矩陣法存儲(chǔ)一個(gè)N個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè)（）A上三角矩陣B稀疏矩陣C對(duì)角矩陣D對(duì)稱(chēng)矩陣5、在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的（）A前一個(gè)位置B后一個(gè)位置C隊(duì)頭元素位置D隊(duì)尾元素的前一位置6、用鏈表表示線(xiàn)性表的優(yōu)點(diǎn)是（）A便于隨機(jī)存取B花費(fèi)的存儲(chǔ)空間比順序表少C便于插入與刪除D數(shù)據(jù)元素的物理順序與邏輯順序相同7、對(duì)5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最多需要進(jìn)行（）次比較。A8B10C15D258、下列存儲(chǔ)形式中，（）不是樹(shù)的存儲(chǔ)形式A雙親表示法B左子女右兄弟表示法C廣義表表示法D順序表示法9、在一棵具有5層的滿(mǎn)二叉樹(shù)中結(jié)點(diǎn)數(shù)為（）A31B32C33D1610、設(shè)有100個(gè)數(shù)據(jù)元素，采用折半搜索時(shí)，最大比較次數(shù)為（）A6B7C8D10二、判斷題（每小題1分）（）1、算法的運(yùn)行時(shí)間涉及加、減、乘、除、轉(zhuǎn)移、存、取、等基本運(yùn)算。要想準(zhǔn)確地計(jì)算總運(yùn)算時(shí)間是不可行的。（）2、二維數(shù)組是數(shù)組元素為一維數(shù)組的線(xiàn)性表，因此它是線(xiàn)性結(jié)構(gòu)。（）3、順序表用一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，因此順序表是一維數(shù)組。（）4、通常使用兩個(gè)類(lèi)來(lái)協(xié)同表示單鏈表，即鏈表的結(jié)點(diǎn)類(lèi)和鏈表類(lèi)。（）5、棧和隊(duì)列都是順序存取的的線(xiàn)性表，但它們對(duì)存取位置的限制不同。（）6、在使用后綴表表示實(shí)現(xiàn)計(jì)算器時(shí)用到一個(gè)棧的實(shí)例，其作用是暫存運(yùn)算對(duì)象。（）7、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為L(zhǎng)log2n^+1。（）8、為度量一個(gè)搜索算法的性能，需要在時(shí)間和空間方面進(jìn)行權(quán)衡。（）9、閉散列法通常比開(kāi)散列法時(shí)間效率更高。（）10、一棵m階B樹(shù)中每個(gè)結(jié)點(diǎn)最多有m個(gè)關(guān)鍵碼，最少有2個(gè)關(guān)鍵碼。三、閱讀理解題（10分）voidunknown(BinTreeNode*T,inta[],inti){if(T!=NULL){a[i]=T->data;unknown(T->leftChild,a,2*I+1);unknown(T->rightChild,a,2*I+2);}}主程序調(diào)用方式unknown（BT.root,a,0）;//將完全二叉樹(shù)所有結(jié)點(diǎn)從要開(kāi)始，自頂向下，同一層自左向右連續(xù)編號(hào)//根結(jié)點(diǎn)的編號(hào)為0。四、簡(jiǎn)答題（共35分）1、對(duì)下面的帶權(quán)無(wú)向圖采用prim算法從頂點(diǎn)①開(kāi)始構(gòu)造最小生成樹(shù)。（寫(xiě)出加入生成樹(shù)頂點(diǎn)集合S和選擇Edge的順序）（10分）S：頂點(diǎn)號(hào)Edge：（頂點(diǎn)，頂點(diǎn)，權(quán)值）①（，，）①（，，）①（，，）①（，，）①（，，）①2、某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下：012345678910111213141516171819EAFDHCGIB（1） 試畫(huà)出此二叉樹(shù)的圖形表示。（3分）（2） 寫(xiě)出結(jié)點(diǎn)D的雙親結(jié)點(diǎn)及左、右子女。（3分）（3） 將此二叉樹(shù)看作森林的二叉樹(shù)表示，試將它還原為森林。（3分）3、設(shè)待排序序列為｛10，18，4，3，6，12，1，9，15，8｝，請(qǐng)給出用希爾排序每一趟的結(jié)果。增量序列取為5，3，2，1。（每一趟2分，共8分）4、設(shè)散列表的長(zhǎng)度為13,散列函數(shù)為H(k)=k%13，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27。試畫(huà)出用線(xiàn)性探查法解決沖突時(shí)所構(gòu)成的散列表。(8分)0 1 2 3 4 5 6 7 8 9 10 11 12五、綜合算法題(每題5分，共15分)對(duì)于二維整數(shù)數(shù)組A[m][n],對(duì)下列三種情況，分別編寫(xiě)相應(yīng)的函數(shù)。求數(shù)組所有邊緣的和。(5分)intsuml(intA[M][N],intm,intn)〃M和N分別大于等于m和n{}求從A[0][0]開(kāi)始的互不相鄰的所有元素的和(5分)注：一個(gè)元素的八個(gè)方向上的第一個(gè)元素均為相鄰元素。intsum2(intA[M][N],intm,intn){}假定m=n，請(qǐng)分別計(jì)算正、反兩條對(duì)角線(xiàn)上的元素的和。(5分)intsum3(intA[M][N],intn){六、填空題(每題2分，共10分)已知一棵完全二叉樹(shù)存放于一個(gè)一維數(shù)組T[n]中，T[n]中存放的是各結(jié)點(diǎn)的值。下面的算法的功能是：從T[0]開(kāi)始順序讀出各結(jié)點(diǎn)的值，建立該二叉樹(shù)的二叉鏈表表示。此算法有5處缺失，請(qǐng)根據(jù)算法的功能補(bǔ)充之。(10分)#include<istream.h>typedefstructnode{intdata;stuctnodeleftChildri,ghtchild;}BintreeNode;typedefBintreeNode*BinaryTree;voidConstrucTree(intT[],intn,intI,BintreeNode*&ptr);intmain(void){Binarytreet;intn;Cout<<”pleaseenterthenumberofnode:\n”;cin>>n;Int*A=newint[n];For(intI=O;Ivn;I++)① ;從鍵盤(pán)輸入結(jié)點(diǎn)值For(intI=0;I<n;I++)cout<<A[i];Cout<<endl;ConstructTree(A,n,0,t);;〃刪除數(shù)組Areturn1;}voidConstrucTree(intT[],intn,intI,BintreeNode*&ptr){f