數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案(12級(jí))-免費(fèi)閱讀
【正文】 x=’e’； { y=pop (p)； (p)。x= ‘c’；五、分析題。22. 簡(jiǎn)述公共溢出區(qū)法解決沖突的基本思想。20. 順序查找時(shí)間為O(n)，二分查找時(shí)間為O(log2n)，散列查找時(shí)間為O(1)，為什么有高效率的查找方法而不放棄低效率的方法?答：衡量算法的標(biāo)準(zhǔn)有很多，時(shí)間復(fù)雜度只是其中之一。答：（1）鄰接鏈表：（2）逆鄰接鏈表：（3） 頂點(diǎn) 入度 出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 318. 對(duì)應(yīng)圖G3，寫出從v1出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個(gè)。 (3) 先序序列與后序序列相同。串變量的名字與串變量的值:串變量的名字表示串值的標(biāo)識(shí)符。5. 如果進(jìn)棧的元素序列為1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出棧序列?并說明為什么不能得到或如何得到。 BADC。不同點(diǎn)：棧只在一端（棧頂）進(jìn)行插入，刪除操作；隊(duì)列在一端（top）刪除，一端(rear)插入。算法：是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。四、簡(jiǎn)答題。( √ )23. 在二叉排序樹上插入新的結(jié)點(diǎn)時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針， 由空變?yōu)榉强占纯伞? )15. 已知二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹，因?yàn)椴恢罉?的根結(jié)點(diǎn)是哪一個(gè)。( )7．鏈表的每個(gè)結(jié)點(diǎn)中，都恰好包含一個(gè)指針。(52) 設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對(duì)其仍按遞增順序進(jìn)行排序，則______冒泡排序_________最省時(shí)間，____快速排序________最費(fèi)時(shí)間。(45) 對(duì)一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為____8______，在整個(gè)排序過程中最多需要進(jìn)行_____8_____趟排序才可以完成。(37) 散列法存儲(chǔ)的基本思想是由________關(guān)鍵碼直接______________決定數(shù)據(jù)的存儲(chǔ)地址。(29) 對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為______ O(n)____；若采用折半法查找，則時(shí)間復(fù)雜度為______ O(log2n)____。(21) s=”this is the main string”,sub=”string”,strindex(s,sub)是：_______13_______。(14) 設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中___ ni+1____個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中___ ni ____個(gè)元素。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為________網(wǎng)狀結(jié)構(gòu)________。A. 堆排序 B．冒泡排序 C．快速排序 D． SHELL排序二、填空題。A. 插入 B. 堆 (71) 每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做___ B _____排序。A．順序表 B．有序的順序表C．鏈表 D．有序的鏈表(63) 如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用_____ D ____查找方法。(訪問標(biāo)志位數(shù)組空間)A. O(n) B. O(e) C. O(ne) D. O(n+e)(55) 請(qǐng)指出在順序表{11123452}中，用折半法查找關(guān)鍵碼12需做____ C ___次關(guān)鍵碼比較。A. 31 B. 32 C. 33 D. 16(47) 已知8個(gè)數(shù)據(jù)元素為(374125965)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點(diǎn)總數(shù)為____B____。B. 11C. “ASTRUCTUR” B. 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等C. 同時(shí)具備(A)和(B)兩個(gè)條件D. 串中不同數(shù)字的個(gè)數(shù) (37) 兩個(gè)字符串相等的充要條件是____ C ______。B. 串中不同字母的個(gè)數(shù)D. 只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相符時(shí)才相等(36)A. frontnext=s；front=s；C. 4和2C. topnext=top。C. 16D. abcde(27) 設(shè)輸入序列是……、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是____ C ______。B. B. n=i (16) 設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B之間插入結(jié)點(diǎn)X的操作序列為__ B ______。 (7) 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為___ C ____。一、選擇題。 (8) 在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為___ A ____。A. snext=pnext；pnext=s； B. qnext=s； snext=p；C. pnext=snext；snext=p； D. pnext=s；snext=q；(17) 設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為___ A _____。B. top D. D(26) 一個(gè)棧的輸入序列是a,b,c,d,e,則棧的不可能的輸出序列是____ C _____。A. ni 字符串的長(zhǎng)度是指___ C ______。A. 兩個(gè)字符串的長(zhǎng)度相等D. 數(shù)據(jù)元素可以是多個(gè)字符(39) 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作D. 求串長(zhǎng)(40) 設(shè)串sI=ABCDEFG,s2=PQRST,函數(shù)con(x,y)返回x和y串的連接串,subs(s,i,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2))的結(jié)果串是__ D ___。D. BCDEFEF (41) 函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為___ A ______。A. 1 B. 2 C. D. 4(48) 由分別帶權(quán)為7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為____C____。 (56) 對(duì)線性表進(jìn)行折半查找時(shí)，必須要求線性表 ____ C ____。A．分塊 B．順序 C．折半 D．散列(64) 散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)按___ C ______取其值域的每一個(gè)值。A. 插入 B. 堆 (72) 設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為____ C ____。(每空1分，共10分)(1) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 數(shù)據(jù) 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。當(dāng)結(jié)點(diǎn)之間存在1對(duì)N（1：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_____樹結(jié)構(gòu)__________。(15) 若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用_____鏈?zhǔn)絖________存儲(chǔ)結(jié)構(gòu)。(22) int a[10][10],已知a=1000,sizeof(int)=2,求a[3][3]地址：_______1066___________(30) 假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為____1_______，則比較二次查找成功的結(jié)點(diǎn)數(shù)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1