哈工大-數(shù)據(jù)結(jié)構(gòu)-2010春A卷-試題

班號(hào)學(xué)號(hào)姓名哈工大2023年春季學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法A試卷題號(hào)一二三四總分分值1515202070得分一、填空題〔每空1分，共15分〕注意行為標(biāo)準(zhǔn)遵守考場(chǎng)紀(jì)律1.在順序存儲(chǔ)的二叉樹(shù)中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是____________注意行為標(biāo)準(zhǔn)遵守考場(chǎng)紀(jì)律2．某二叉樹(shù)的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，那么其后序遍歷序列是_______________。3．在有n個(gè)葉子的哈夫曼樹(shù)中，分支結(jié)點(diǎn)總數(shù)為_(kāi)__________個(gè)。4．對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹(shù)的時(shí)間復(fù)雜度為_(kāi)__________。5.表達(dá)式a*(b+c)-d的后綴表達(dá)式是___________。6.假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18，那么它的最小深度為_(kāi)______，最大深度為_(kāi)_____。7.設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑亍舶▽?duì)角線(xiàn)上元素〕存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，那么A[i][j]與A[0][0]之間有_______個(gè)數(shù)據(jù)元素。8.設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，那么根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_(kāi)_______________________。9.磁盤(pán)文件的歸并技術(shù)有______________、____________、__________。10.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，那么該圖的一種拓?fù)湫蛄袨開(kāi)___________________。11.設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，那么用基數(shù)排序需要進(jìn)行________趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。主管領(lǐng)導(dǎo)簽字12.利用Dijkstra算法求從有向圖頂點(diǎn)v1到其他各頂點(diǎn)的最短路徑要求邊上權(quán)值_________。主管領(lǐng)導(dǎo)簽字二、選擇題〔每題1分，共15分〕1．假設(shè)某線(xiàn)性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，那么利用___________存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.

單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表02．在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端〔即下標(biāo)為0的單元〕作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為_(kāi)_____。A.不變B.top=0;C.top=top-1;D.top=top+1;3．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，那么以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為_(kāi)________。A、10，15，14，18，21，36，40，20B、10，15，14，18，20，40，36，21C、10，15，14，20，18，40，36，2lD、15，10，14，18，20，36，40，214．任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序________。A.肯定不發(fā)生改變 B.肯定發(fā)生改變C.不能確定 D.有時(shí)發(fā)生變化5．用有向無(wú)環(huán)圖描述表達(dá)式(A+B)*((A+B)/A)，至少需要頂點(diǎn)的數(shù)目為_(kāi)________。A.5

B.6

C.8

D.96.對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必須___________。A、以順序方式存儲(chǔ)B、以鏈接方式存儲(chǔ)C、以順序方式存儲(chǔ)，且數(shù)據(jù)元素有序D、以鏈接方式存儲(chǔ)，且數(shù)據(jù)方式有序7.設(shè)散列表表長(zhǎng)m=14，散列函數(shù)H(k)=kmod11。表中已有15、38、61、84四個(gè)元素，如果用線(xiàn)性探側(cè)法處理沖突，那么元素49的存儲(chǔ)地址是_________。A.8B.3C假設(shè)需在O(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，那么可選擇的排序方法是_________。A.快速排序B.堆排序C.歸并排序D.插入排序9.

下面關(guān)于m階B樹(shù)的說(shuō)法正確的選項(xiàng)是__________。①每個(gè)結(jié)點(diǎn)至少有兩株非空子樹(shù)②樹(shù)中每個(gè)結(jié)點(diǎn)至多有m-1個(gè)關(guān)鍵字③所有的葉子都在同一層上④當(dāng)插入一個(gè)記錄引起B(yǎng)樹(shù)分裂后，樹(shù)增高一層A.①②③B.②③

C.②③④D.①③10.一個(gè)有序表為〔12，18，24，35，47，50，62，83，90，115，134〕，當(dāng)折半查找值為90的元素時(shí)，經(jīng)過(guò)_______次比擬后查找成功。A.2 B.3C.4 D.511.能有效縮短關(guān)鍵路徑長(zhǎng)度的方法是_________。A．縮短任意一個(gè)活動(dòng)的持續(xù)時(shí)間B．縮短關(guān)鍵路徑上任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間C．縮短多條關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間D．縮短所有關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間12.在采用線(xiàn)性探測(cè)法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測(cè)多個(gè)位置，在查找成功的情況下，所探測(cè)的這些位置的關(guān)鍵字值________。A.一定都是同義詞 B.一定都不是同義詞C.不一定都是同義詞 D.都相同13.設(shè)哈夫曼編碼的長(zhǎng)度不超過(guò)4，假設(shè)已對(duì)兩個(gè)字符編碼為1和01，那么最多還可以對(duì)_______個(gè)字符編碼。A．2 B．3 C．4 D．514.圖的鄰接表如下所示，根據(jù)算法，那么從頂點(diǎn)0出發(fā)深度優(yōu)先遍歷的結(jié)點(diǎn)序列是____________。A.0132 B.0231 C.0321D.15.在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是_________。A.O(1) B.O(n) C.O(n2)D.O(nlog2n)三、簡(jiǎn)答題：每題10分，共20分.1．一個(gè)按數(shù)組元素有序的一維數(shù)組一定是堆嗎？請(qǐng)說(shuō)明理由。2.設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，可以構(gòu)造出一棵二叉排序樹(shù)，假設(shè)不是平衡樹(shù)那么調(diào)整平衡，并給出其前序遍歷該樹(shù)的序列，并寫(xiě)出右旋轉(zhuǎn)函數(shù)算法。四、算法設(shè)計(jì)：每題10分，共20分要求：⑴描述算法設(shè)計(jì)的根本思想⑵描述算法的詳細(xì)實(shí)現(xiàn)步驟⑶根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法〔使用C或C++或JAVA語(yǔ)言實(shí)〕，關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋?！矖?、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、根本操作可以直接引用〕1．對(duì)給定的序號(hào)j〔1＜j＜n〕，要求在無(wú)序記錄A[1]~A[n]中找到按關(guān)鍵碼從小到大排在第j位上的記錄，試?yán)每焖倥判虻膭澐炙枷朐O(shè)計(jì)算法實(shí)現(xiàn)上述查找。2．設(shè)計(jì)算法，判斷以鄰接表存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑〔i≠j〕。參考答案：一．填空：1.logi=logj2.CDBGFEA3.n-14.O(n2)5.abc+*d-6.5187.i(i+1)/2+j-18.1618192030229.多路歸并、I/O并行處理初始?xì)w并段產(chǎn)生10.1,4,2,311.312.非負(fù)二、單項(xiàng)選擇：1A2C3A4A5A6C三、簡(jiǎn)答：1.按數(shù)組元素有序的一維數(shù)組一定是堆。〔4分〕非升序數(shù)組一定是最小堆為例說(shuō)明如下：假設(shè)非升序數(shù)組為K1,K2,…,Kn，那么滿(mǎn)足K1≤K2,≤…≤Kn，那么一定滿(mǎn)足：Ki≤K2i且Ki≤K2i+1，即滿(mǎn)足最小堆的定義。同理可知，非降序數(shù)組一定是最大堆。因此，按數(shù)組元素有序的一維數(shù)組一定是堆?！?分〕2.二叉平衡樹(shù)為48，40，80，22，45，78〔3分〕前序：48，40，22，45，80，78〔3分〕右旋轉(zhuǎn)函數(shù)：voidR_Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;}四、算法1.1、本算法不要求將整個(gè)記錄進(jìn)行排序，而只進(jìn)行查找第j個(gè)記錄。(1)根本思想：改良劃分算法，是一次劃分將基準(zhǔn)元素定位于k，如果k==j，那么找到第j小的元素；否那么，遞歸地在k的左邊或右邊進(jìn)行劃分，直到k==j為止。(2)數(shù)據(jù)結(jié)構(gòu)：略(3)算法如下：intSearch(intA[],intn,intj){ s=1;t=n; k=Partition(A,s,t); while(k！=j) if(k<j)k=Partition(A,k+1，t); elsek=Partition(A,s，k-1); returnA[j];}intPartition(intA[],intlow,inthigh){ i=low;j=high;pivot=A[low];while(i<j){ while(A[j]>=pivot&&i<j)j--; if(i<j) A[i++]=A[j]; while(A[j]<pivot&&i<j)i++; if(i<j) A[j--]=A[i];}A[i]=pivot;returni;}2.intvisited[MAXSIZE];//指示頂點(diǎn)是否在當(dāng)前路徑上intexist_path_DFS(ALGraphG,inti,intj){if(i==j)return