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