#/9專升本《數(shù)據(jù)結(jié)構(gòu)》專升本《數(shù)據(jù)結(jié)構(gòu)》一、〔共75題,共150分〕.數(shù)據(jù)的邏輯結(jié)構(gòu)是由〔〕局部組成的?！?分〕A.2B.3C.4D.5標(biāo)準(zhǔn)答案：A.算法是對(duì)某一類問題求解步驟的有限序列，并具有〔〕個(gè)特性?！?分〕A.3B.4C.5D.6標(biāo)準(zhǔn)答案：C.隊(duì)列的入隊(duì)操作是在〔〕進(jìn)行的?！?分〕A.隊(duì)頭B.隊(duì)尾C.任意位置D.指定位置標(biāo)準(zhǔn)答案：B.隊(duì)列的出隊(duì)操作是在〔〕進(jìn)行的。〔2分〕A.隊(duì)頭B.隊(duì)尾C.任意位置D.指定位置標(biāo)準(zhǔn)答案：A.數(shù)組通常采用順序存儲(chǔ)的優(yōu)點(diǎn)是〔〕?！?分〕A.便于增加存儲(chǔ)空間B.便于依據(jù)下標(biāo)進(jìn)行隨機(jī)存取C.防止數(shù)據(jù)元素的移動(dòng)D.防止下標(biāo)溢出標(biāo)準(zhǔn)答案：B.以下給出的操作中，〔〕是允許對(duì)隊(duì)列進(jìn)行的操作?！?分〕A.刪除隊(duì)首元素B.取出最近進(jìn)隊(duì)的元素二按元素大小排序D.中間插入元素標(biāo)準(zhǔn)答案：A.采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)的線性表，假設(shè)表長(zhǎng)為n，在刪除第號(hào)元素時(shí)，需要移動(dòng)指針〔〕次?！?分〕A.k+1B.kC.k-1D.k-2標(biāo)準(zhǔn)答案：C.字符數(shù)組a[1..100]采用順序存儲(chǔ)，a[6]地址是517,那么a的首地址為1〕?！?分〕A.510B.512C.514D.516標(biāo)準(zhǔn)答案：B.深度為n的完全二叉樹最多有〔〕個(gè)結(jié)點(diǎn)?！?分〕A.2n+1B.2n-1C.2nD.2n-1標(biāo)準(zhǔn)答案：D.假設(shè)二叉樹對(duì)應(yīng)的二叉鏈表共有n個(gè)非空鏈域，那么該二叉樹有〔〕個(gè)結(jié)點(diǎn)的二叉樹。〔2分〕A.n-1B.nC.n+1D.2n標(biāo)準(zhǔn)答案：A.下面表達(dá)錯(cuò)誤的選項(xiàng)是〔〕?！?分〕A.借助于隊(duì)列可以實(shí)現(xiàn)對(duì)圖的廣度優(yōu)先遍歷B.三叉樹中序遍歷的序列是有序C.只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0D.空格串是指由1個(gè)或以上的空格符號(hào)組成的串標(biāo)準(zhǔn)答案：B.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是〔〕?！?分〕A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧標(biāo)準(zhǔn)答案：D.在一個(gè)長(zhǎng)度為n的鏈?zhǔn)綏Ｖ腥霔?shí)現(xiàn)算法的時(shí)間復(fù)雜度為〔〕?！?分〕A.O(1)B.O(logn)C.O(n)D.標(biāo)準(zhǔn)答案：A.在具有n個(gè)度數(shù)為2的二叉樹中，必有〔〕個(gè)葉子結(jié)點(diǎn)?！?分〕A.n+2B.n+1C.nD.n-1標(biāo)準(zhǔn)答案：B.在關(guān)鍵字序列〔10,15,20,25,30〕中采用折半法查找20，依次與〔〕關(guān)鍵字進(jìn)行了比擬。 〔2分〕A.30,20B.30,10,20C.40,20D.20標(biāo)準(zhǔn)答案：B.某二叉樹的前序遍歷序列和和中序遍歷序列分別為abc和bca，該二叉樹的后序遍歷序列是〔〕0A.cbaB.bcaC.abcD.acb標(biāo)準(zhǔn)答案：A.m個(gè)頂點(diǎn)的無向完全圖有〔〕個(gè)邊。〔2分〕A.m(mT)/2B.m(mT)C.m2D.2m標(biāo)準(zhǔn)答案：A.可以采用〔〕這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)圖的廣度優(yōu)先遍歷運(yùn)算?！?分〕A.隊(duì)列B.樹C.棧D.集合標(biāo)準(zhǔn)答案：A2分〕〔.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組元素A[0]至A[m]中，隊(duì)頭和隊(duì)尾下標(biāo)分別為front和rear,那么入隊(duì)時(shí)修改rear的操作為〔〕?！?分〕A.rear=rear+1B.rear=(rear+1)％(m-1)C.rear=(rear+1)％mD.rear=(rear+1)％(m+1)標(biāo)準(zhǔn)答案：A.空串的長(zhǎng)度是〔〕?！?分〕A.0B.1C.2D.3標(biāo)準(zhǔn)答案：A標(biāo)準(zhǔn)答案：C.隊(duì)列采用循環(huán)隊(duì)列存儲(chǔ)的優(yōu)點(diǎn)是〔〕?！?分〕A.便于增加隊(duì)列存儲(chǔ)空間B.便于隨機(jī)存取.序列〔21,19,37,5,2〕經(jīng)簡(jiǎn)單項(xiàng)選擇擇排序法由小到大排序，在第一趟后所得結(jié)果為〔〕。〔2分〕A.(19，21，5，2，37)B.(21，19，5，37，2)C.(21，19，2，5，37)D.(37，21，19，5，2)標(biāo)準(zhǔn)答案：C.算法具有的5個(gè)特性，〔〕均為算法的特性之一?！?分〕A.有窮性B.確定性C.可行性D.正確性標(biāo)準(zhǔn)答案：A,B,C.在以下數(shù)據(jù)結(jié)構(gòu)中，〔〕屬于非線性結(jié)構(gòu)。〔2分〕A.串B.棧C.樹D.圖標(biāo)準(zhǔn)答案：C,D.在以下排序方法中，〔〕的最壞時(shí)間復(fù)雜度為。其中，n為參加排序的元素個(gè)數(shù)。A.選擇排序B.快速排序C.歸并排序D.堆排序標(biāo)準(zhǔn)答案：C,D.假設(shè)一個(gè)棧的入棧序列是(1，2，3，4)，其不可能出棧序列為〔〕。〔2分〕A.(1，4，2，3)B.(3，4，1，2)C.(4，3，2，1)D.(2，3，4，1)標(biāo)準(zhǔn)答案：A,B.對(duì)一棵二叉排序樹1，用〔〕方法進(jìn)行遍歷，不一定得到各結(jié)點(diǎn)鍵值的有序序列?！?分〕A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷標(biāo)準(zhǔn)答案：A,C,D.物理結(jié)構(gòu)的在計(jì)算機(jī)內(nèi)部的根本存儲(chǔ)表示方法有〔〕種?！?分〕A.2B.3C.4D.5標(biāo)準(zhǔn)答案：A.以下時(shí)間復(fù)雜度中，〔〕表示的復(fù)雜度是最高的。〔2分〕A.O((bgn)3)B.O(n2)C.O(nlogn)D.O(n)標(biāo)準(zhǔn)答案：B.棧的插入和刪除操作是在〔〕進(jìn)行的?！?分〕A.棧頂B.棧底C.任意位置D.指定位置2分〕C.防止數(shù)據(jù)元素的移動(dòng)D.防止隊(duì)列溢出標(biāo)準(zhǔn)答案：C.串通常采用塊鏈存儲(chǔ)的優(yōu)點(diǎn)是〔〕。〔2分〕A.防止聯(lián)接操作溢出B.提高運(yùn)算效率C.防止數(shù)據(jù)元素的移動(dòng)D.提高存儲(chǔ)效率標(biāo)準(zhǔn)答案：D.采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)的線性表，假設(shè)表長(zhǎng)為n,在第k〔1WkWn+1〕號(hào)元素之前插入一個(gè)元素時(shí)，需要移動(dòng)指針〔〕次。 〔2分〕A.k+1B.kC.k-1D.k-2標(biāo)準(zhǔn)答案：C.數(shù)組a[1..10]采用順序存儲(chǔ)，a[1]和a[8]地址分別為128和149,那么每個(gè)元素占〔〕字節(jié)。 〔2分〕A.1B.2C.3D.4標(biāo)準(zhǔn)答案：C.深度為八的二叉樹至少有〔〕個(gè)結(jié)點(diǎn)?！?分〕A.hB.2h-1C.2h-1D.2h標(biāo)準(zhǔn)答案：A.m個(gè)結(jié)點(diǎn)的二叉樹，其對(duì)應(yīng)的二叉鏈表共有〔〕個(gè)非空鏈域?！?分〕A.mB.m+1C.2mD.2m+1標(biāo)準(zhǔn)答案：B.下面表達(dá)錯(cuò)誤的選項(xiàng)是〔〕?！?分〕A.借助于?？梢詫?shí)現(xiàn)對(duì)圖的深度優(yōu)先遍歷B.對(duì)矩陣進(jìn)行壓縮存儲(chǔ)后無法實(shí)現(xiàn)對(duì)其元素進(jìn)行隨機(jī)訪問C.樹的結(jié)點(diǎn)度是指結(jié)點(diǎn)的分支數(shù)上空串的長(zhǎng)度為零標(biāo)準(zhǔn)答案：B.以下〔〕術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)〔2分〕A.串B.哈希表C.線索樹D.單鏈表標(biāo)準(zhǔn)答案：A〔38.在一個(gè)長(zhǎng)度為n的順序表中插入一個(gè)元素的算法的時(shí)間復(fù)雜度為1〕。〔2分〕A.O(1)B.O(logn)C.O(n)D.O(n2)標(biāo)準(zhǔn)答案：C.在具有n個(gè)葉子的二叉樹中，必有〔〕個(gè)度數(shù)為2的結(jié)點(diǎn)?！?分〕A.n+1B.nC.n-1D.2n標(biāo)準(zhǔn)答案：C.在關(guān)鍵字序列〔10,15,20,25,30〕中，采用折半法查找10，關(guān)鍵字之間比擬需要〔〕次。〔2分〕A.1B.2C.3D.4標(biāo)準(zhǔn)答案：B.某二叉樹的后序遍歷序列和和中序遍歷序列分別為cba和bca,該二叉樹的前序遍歷序列是〔〕。〔2分〕A.cbaB.bcaC.abcD.acb標(biāo)準(zhǔn)答案：C.m個(gè)頂點(diǎn)的連通無向圖，至少有〔〕個(gè)邊?！?分〕A.m(m-1)/2B.m(m-I)C.mD.m-1標(biāo)準(zhǔn)答案：D.設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,假設(shè)要?jiǎng)h除A的直接后繼，那么所需修改指針的操作為〔〕?！?分〕A.p=p->nextB.p->next=p->next->nextC.p=p->next->nextD.p->next=p標(biāo)準(zhǔn)答案：B.序列〔21,19,37,5,2〕經(jīng)冒泡排序法由小到大排序，在第一次執(zhí)行交換后所得結(jié)果為〔〕?！?分〕A.（19，21，37，5，2）B.（21，19，5，37，2）C.（21，19，37，2，5）D.（2，21，19，37，5）標(biāo)準(zhǔn)答案：A.算法分析的內(nèi)容是對(duì)算法的〔〕分析?！?分〕A.時(shí)間效率8.空間效率C.可行性D.正確性標(biāo)準(zhǔn)答案：A,B.在以下數(shù)據(jù)結(jié)構(gòu)中，〔〕屬于非線性結(jié)構(gòu)?！?分〕A.串B.棧C.樹D.圖標(biāo)準(zhǔn)答案：C,D.假設(shè)一個(gè)棧的入棧序列是（1，2，3，4），其可能出棧序列為〔〕。〔2分〕A.（1，4，3，2）B.（3，4，1，2）C.（4，3，2，1）D.（2，3，4，1）標(biāo)準(zhǔn)答案：A,C,D.構(gòu)造哈希（Hash）函數(shù)的方法有〔〕等。〔2分〕A.除留余數(shù)法B.平方取中法C.折疊法D.開放尋址法標(biāo)準(zhǔn)答案：A,B,C.以下各項(xiàng)鍵值〔〕序列不是堆的。〔2分〕A.{5，23，16，68，94}B.{5，16，23，68，94}C.{5，23，16，94，68}D.{5，23，68，16，94}標(biāo)準(zhǔn)答案：D.以下各項(xiàng)鍵值〔〕序列是堆的?！?分〕A.{5，23，16，68，94}B.{5，23，68，16，94}C.{5，94，16，23，68}D.{5，16，23，68，94}標(biāo)準(zhǔn)答案：A,D.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)部存儲(chǔ)表示稱為為數(shù)據(jù)的〔〕?！?分〕A.數(shù)據(jù)結(jié)構(gòu)B.邏輯關(guān)系C.物理結(jié)構(gòu)D.數(shù)據(jù)元素的內(nèi)部結(jié)構(gòu)標(biāo)準(zhǔn)答案：C.數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，通常采用〔〕?！?分〕A.順序結(jié)構(gòu)B.鏈?zhǔn)浇Y(jié)構(gòu)C.順序和鏈?zhǔn)浇M合結(jié)構(gòu)D.散列結(jié)構(gòu)標(biāo)準(zhǔn)答案：A.棧和隊(duì)列的共同點(diǎn)是〔〕?！?分〕A.進(jìn)出原那么都是先進(jìn)先出B.進(jìn)出原那么都是后進(jìn)先出C.都是插入刪除操作受限的線性表D.不允許在任意端點(diǎn)處插入和刪除元素標(biāo)準(zhǔn)答案：C.以下邏輯結(jié)構(gòu)中，〔〕為線性結(jié)構(gòu)?！?分〕A.集合B.串C.二叉樹D.圖標(biāo)準(zhǔn)答案：B.線性表采用順序存儲(chǔ)的優(yōu)點(diǎn)是〔〕。〔2分〕A.便于插入B.便于隨機(jī)存取C.防止數(shù)據(jù)元素的移動(dòng)D.便于刪除標(biāo)準(zhǔn)答案：B.采用帶頭結(jié)點(diǎn)雙向鏈表存儲(chǔ)的線性表，在插入一個(gè)元素時(shí)，需要修改指針〔〕次。 〔2分〕A.1B.2C.3D.4標(biāo)準(zhǔn)答案：D.采用順序存儲(chǔ)的線性表，假設(shè)表長(zhǎng)為n,在刪除第m〔1WmWn〕號(hào)元素時(shí)，需要移動(dòng)〔〕個(gè)元素。A.mB.m+1C.n-mD.n-m+1分〕〔標(biāo)準(zhǔn)答案：CA.n(n-1)B.n(n-1)/2C.n2D.n.數(shù)組a[1..32]采用順序存儲(chǔ)，a的首地址為1024,每個(gè)元素占4字節(jié)，那么a[17]的地址是〔〕。〔2分〕標(biāo)準(zhǔn)答案：DA.1040B.1056C.1072D.1088標(biāo)準(zhǔn)答案：D.深度為h的完全二叉樹至少有。個(gè)結(jié)點(diǎn)?！?分〕A.2h-1B.2h-1-1C.2h—1D.2h+1標(biāo)準(zhǔn)答案：C.假設(shè)二叉樹對(duì)應(yīng)的二叉鏈表共有m個(gè)非空鏈域，那么該二叉樹有〔〕個(gè)結(jié)點(diǎn)的二叉樹?！?分〕A.2mB.m+1C.mD.m-1標(biāo)準(zhǔn)答案：D.下面表達(dá)錯(cuò)誤的選項(xiàng)是〔〕?！?分〕A.借助于隊(duì)列可以實(shí)現(xiàn)對(duì)二叉樹的層遍歷B.棧的特點(diǎn)是先進(jìn)后出C.對(duì)于單鏈表進(jìn)行插入操作過程中不會(huì)發(fā)生上溢現(xiàn)象D.在無向圖的鄰接矩陣中每行1的個(gè)數(shù)等于對(duì)應(yīng)的頂點(diǎn)度標(biāo)準(zhǔn)答案：C.以下數(shù)據(jù)結(jié)構(gòu)中，〔〕是線性結(jié)構(gòu)。〔2分〕A二維數(shù)組8.二叉樹C.特殊矩陣D.棧標(biāo)準(zhǔn)答案：D.在一個(gè)長(zhǎng)度為n的鏈?zhǔn)疥?duì)列中出隊(duì)實(shí)現(xiàn)算法的時(shí)間復(fù)雜度為〔〕?！?分〕A.O(1)B.O(logn)C.O(n)D.O(n2)標(biāo)準(zhǔn)答案：A.在具有n個(gè)度數(shù)為2的二叉樹中，必有〔〕個(gè)葉子結(jié)點(diǎn)?！?分〕A.n+1B.nC.n-1D.2n標(biāo)準(zhǔn)答案：A在關(guān)鍵字序列〔10,15,20,25,30〕中采用折半法查找10，依次與〔〕關(guān)鍵字進(jìn)行了比擬?！?分〕A.20,15,10B.20,10C.25,15，10D.10標(biāo)準(zhǔn)答案：B16某二叉樹的后序遍歷序列和和中序遍歷序列分別為cbda和bcad，該二叉樹的前序遍歷序列是〔〕。分〕A.cbdaB.dcbaC.abcdD.dcba標(biāo)準(zhǔn)答案：Cn個(gè)頂點(diǎn)的無向連通網(wǎng)的最小本錢樹，至少有〔〕個(gè)邊?！?分〕可以采用〔〕這種數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)判別的運(yùn)算。〔2分〕A.隊(duì)列B.樹C.棧D.集合標(biāo)準(zhǔn)答案：C帶頭結(jié)點(diǎn)鏈隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear,那么判斷隊(duì)空的條件為〔〕?！?分〕A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL標(biāo)準(zhǔn)答案：A序列〔21，19，37，5，2〕經(jīng)直接插入排序法由小到大排序，第一趟后所得結(jié)果為〔〕。〔2分〕A.（19，21，37，5，2）B.（19，21，5，2，37）C.（19,21，5，37，2）D.（19，21，2，5，37）標(biāo)準(zhǔn)答案：A單鏈表可作為〔〕的存儲(chǔ)結(jié)構(gòu)?！?分〕A.線性表B.棧C.隊(duì)列D.廣義表標(biāo)準(zhǔn)答案：A,B,C在n個(gè)數(shù)據(jù)元素中進(jìn)行查找，〔〕方法的平均時(shí)間復(fù)雜度為O（bgn）。[2