《數(shù)據(jù)結(jié)構(gòu)》(本)模擬試題一1

逵拉逵拉S氏下筆如有神《數(shù)據(jù)結(jié)構(gòu)》（本）模擬試題一一、填空題（每小題2分，共24分）1．一棵二叉樹沒(méi)有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹總共有個(gè)結(jié)點(diǎn)。.棧和隊(duì)列的操作特點(diǎn)分別是和。.設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹一共有個(gè)結(jié)點(diǎn)。.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為結(jié)構(gòu)。.按照二叉樹的遞歸定義，對(duì)二叉樹遍歷的常用算法有、、三種。.根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通?？煞譃榧?、線性、、四類基本結(jié)構(gòu)。．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為結(jié)構(gòu)。8.要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為和。9．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為結(jié)構(gòu)。10．在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行___和p->next=s;的操作。.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為結(jié)構(gòu)。.在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是值域、二、單項(xiàng)選擇題（每小題2分，共30分）i針對(duì)線性表，在存儲(chǔ)后如果最常用的操作是取第個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A單鏈表.雙鏈表.單循環(huán)鏈表.順序表2．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。.物理.存儲(chǔ).邏輯與物理D邏輯3．以下特征中，（）不是算法的特性。A有窮性.確定性.可行性.有個(gè)或多個(gè)輸出4設(shè)有一個(gè)長(zhǎng)度為的順序表，要在第個(gè)元素之前（也就是插入元素作為新表的第個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（）。.棧的插入刪除操作在（）進(jìn)行。.棧底.任意位置.指定位置.棧頂.以下說(shuō)法正確的是（）。.棧的特點(diǎn)是先進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)后出.棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出.棧和隊(duì)列的特點(diǎn)都是先進(jìn)先出.元素2，4，6，8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）。.設(shè)有一個(gè)階的對(duì)稱矩陣A采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組中（數(shù)組下標(biāo)從開始），則矩陣中元素在一維數(shù)組中的下標(biāo)是TOC\o"1-5"\h\z（）。A．42．13B．27C．32D9串函數(shù)（””,“”）的值為（）。．0A．1B．-1C．3Do在一棵二叉樹中，若編號(hào)為的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。．A2i．2i-1B．2i+2C．2i+1D.設(shè)一棵有個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2則該樹共有（）個(gè)指針域?yàn)榭?。A.2n.2n+1B.2n+2C.n+1D2E知如圖所示的一個(gè)圖，若從頂點(diǎn)出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。圖113.在有序表｛，13，8，13，33，42，46，6，37，678，8，697，10中0，｝用折半查找值86時(shí)，經(jīng)（）次比較后查找成功。1.4有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。15.一組記錄的關(guān)鍵字序列為（37，70，47，2，93，185），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）。三、綜合題.（1）利用篩選過(guò)程把序列｛42，82，67，102，16，32，57，52｝建成堆（小根堆），畫出該堆（不要求中間過(guò)程）。（2）寫出對(duì)上述堆對(duì)應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。.（1）以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹（要求每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2)一棵哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡(jiǎn)述理由？3．設(shè)查找表為(16,15,20,53,64,7),(1)用冒泡法對(duì)該表進(jìn)行排序(要求升序排列)，要求寫出每一趟的排序過(guò)程。(2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(3)求在等概率條件下,對(duì)上述有序表成功查找的平均查找長(zhǎng)度.四、程序填空題(每空2分，共16分)i以下冒泡法程序?qū)Υ娣旁冢?，……，中的序列進(jìn)行排序，完成程序中的空格部分，其中是元素個(gè)數(shù)，要求按升序排列。程序中的功能是()2．以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。voidPreorder(structBTreeNode*BT){if(BT!=NULL){(1)；(2);(3);

參考答案、填空題參考答案121234567后進(jìn)先出、先進(jìn)先出21圖狀（網(wǎng)狀）先序；中序；后序樹形圖狀樹形物理（存儲(chǔ)）1．線性2．左指針右指針、單項(xiàng)選擇題（每小題2分，共30分）1．D2．D3．D4．A5．D6．C7．D8．C9．B10．D11．D12．B13．D14．A15．A三、綜合應(yīng)用題1．（1）(1)（2）102，2．52，2：111011114：1107：008：019：102n-1個(gè)，因?yàn)榉侨~結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。(2)(3)平均查找長(zhǎng)度=(2)(3)平均查找長(zhǎng)度=(1*1+2*2+3*3)/6=14/63．(1)原序列1615205364715162053764151620753641516720536415