數(shù)據(jù)結(jié)構(gòu)習(xí)題題型

1、三、填空題1數(shù)據(jù)的物理結(jié)構(gòu)包括 數(shù)據(jù)元素 的表示和 數(shù)據(jù)元素間關(guān)系 的表示。2. 對(duì)于給定的 n 個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 線性結(jié)構(gòu) 、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)、集合四種。 3數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。4一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中表示（又稱映像）稱為存儲(chǔ)結(jié)構(gòu)。 5抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部使用。 6數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是 時(shí)間復(fù)雜度 和 空間復(fù)雜度 。7. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的邏輯

2、結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的操作，設(shè)計(jì)出相應(yīng)的算法。 8 一個(gè)算法具有5個(gè)特性: 有窮性 、 確定性 、 可行性 ，有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是（log2n）i=1； WHILE i<n DO i=i*2; 12. 下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級(jí)是(nlog2n )。i=1；while (i<n) for(i=1;i<=n;i+) x=x+1；i=i*2； 15. 下面程序段的時(shí)間復(fù)雜度為 O(n) 。(n>1) sum=1； for (i=0；sum<n

3、；i+) sum+=1； 8對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般包括哪三個(gè)方面的討論？邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、操作（運(yùn)算）4在一個(gè)長(zhǎng)度為 n 的順序表中第 i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。 5在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 主要是使插入和刪除等操作統(tǒng)一，在第一個(gè)元素之前插入元素和刪除第一個(gè)結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。10鏈接存儲(chǔ)的特點(diǎn)是利用 指針 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。11.順序存儲(chǔ)結(jié)構(gòu)是通過 物理上相鄰 表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過 指針 表示元素之間的關(guān)系的。 12. 對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)

4、新結(jié)點(diǎn)需修改的指針共4 個(gè)，單鏈表為 2 個(gè)。 15. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 L 中只有一個(gè)元素結(jié)點(diǎn)的條件是： L->next->next=L 16. 在單鏈表 L 中，指針 p 所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是： p->next!=null 17.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 L 為空表的條件是： L->next=L && L->prior=L 。 18. 在單鏈表 p 結(jié)點(diǎn)之后插入 s 結(jié)點(diǎn)的操作是： s->next=p->next;p->next=s; 。 1棧是 操作受限 的線性表，其運(yùn)算遵循 后進(jìn)先出 的原則。 2 棧 是限定僅在表尾

5、進(jìn)行插入或刪除操作的線性表。3. 一個(gè)棧的輸入序列是：1，2，3 則不可能的棧輸出序列是 312 。4. 設(shè)有一個(gè)空棧，棧頂指針為 1000H(十六進(jìn)制)，現(xiàn)有輸入序列為 1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，輸出序列是 23 ，而棧頂指針值是 100C H。設(shè)棧為順序棧，每個(gè)元素占 4 個(gè)字節(jié)。 5. 當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組 stack(1,n)表示，兩棧頂指針為 top1與 top2，則當(dāng)棧1 空時(shí)，top1為 0 ，棧2 空時(shí) ，top2為 n+1 ，棧滿時(shí)為 top1+1=top2 。 6兩個(gè)棧共享空間時(shí)棧滿的條

6、件 兩棧頂指針值相減的絕對(duì)值為1（或兩棧頂指針相鄰） 。 8. 多個(gè)棧共存時(shí)，最好用 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 作為存儲(chǔ)結(jié)構(gòu)。 9用 S 表示入棧操作，X 表示出棧操作，若元素入棧的順序?yàn)?1234，為了得到 1342 出棧順序，相應(yīng)的 S和X 的操作串為 S×SS×S×× 。 10. 順序棧用 data1.n存儲(chǔ)數(shù)據(jù)，棧頂指針是 top,則值為 x 的元素入棧的操作是 data+top=x；。 11表達(dá)式23+(12*3-2)/4+34*5/7)+108/9 的后綴表達(dá)式是 23.12.3*2-4/34.5*7/+108.9/+（注：表達(dá)式中的點(diǎn)(.)表示將數(shù)隔開

7、，如23.12.3是三個(gè)數(shù)）12. 循環(huán)隊(duì)列的引入，目的是為了克服 假溢出時(shí)大量移動(dòng)數(shù)據(jù)元素 。 14 隊(duì)列 又稱作先進(jìn)先出表。 15. 隊(duì)列的特點(diǎn)是先進(jìn)先出 。 16隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是 先進(jìn)先出 。 17. 已知鏈隊(duì)列的頭尾指針分別是 f 和 r，則將值 x 入隊(duì)的操作序列是 s=(LinkedList)malloc(sizeof(LNode)； s->data=x;s->next=r->next；r->next=s；r=s； 。 18區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是 犧牲一個(gè)存儲(chǔ)單元 和 設(shè)標(biāo)記 。 21

8、表達(dá)式求值是 棧 應(yīng)用的一個(gè)典型例子。 22循環(huán)隊(duì)列用數(shù)組 A0.m-1存放其元素值，已知其頭尾指針分別是 front 和 rear ，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是（rear-front+m）% m 。 23設(shè) Q0.N-1為循環(huán)隊(duì)列，其頭、尾指針分別為 P 和 R，則隊(duì) Q 中當(dāng)前所含元素個(gè)數(shù)為（R-P+N）% N。1空格串是指 由空格字符（ASCII值32）所組成的字符串 ，其長(zhǎng)度等于 空格個(gè)數(shù) 。2組成串的數(shù)據(jù)元素只能是 字符 。 3一個(gè)字符串中 任意個(gè)連續(xù)的字符組成的子序列 稱為該串的子串 。4INDEX（DATASTRUCTURE，STR）= 5 。8設(shè) T 和 P 是兩個(gè)給定的串，在 T

9、 中尋找等于 P 的子串的過程稱為 模式匹配 ，又稱P 為 模式串 。 9串是一種特殊的線性表，其特殊性表現(xiàn)在 其數(shù)據(jù)元素都是字符 ；串的兩種最基本的存儲(chǔ)方式是 順序存儲(chǔ) 、 鏈?zhǔn)酱鎯?chǔ) ；兩個(gè)串相等的充分必要條件是 串的長(zhǎng)度相等且兩串中對(duì)應(yīng)位置的字符也相等 。10兩個(gè)字符串相等的充分必要條件是 兩串的長(zhǎng)度相等且兩串中對(duì)應(yīng)位置的字符也相等 。11知U=xyxyxyxxyxy；t=xxy；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1）；ASSIGN（m，ww）求REPLACE（S，V，m）=xyxyxywwy。1. 數(shù)組的存儲(chǔ)結(jié)構(gòu)采用 順序存儲(chǔ)

10、結(jié)構(gòu) 存儲(chǔ)方式。 3. 設(shè)數(shù)組 a1.50,1.80的基地址為2000，每個(gè)元素占 2 個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a45,68的存儲(chǔ)地址為 9174 ;若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素 a45,68的存儲(chǔ)地址為 8788 。4. 將整型數(shù)組 A1.8，1.8按行優(yōu)先次序存儲(chǔ)在起始地址為 1000 的連續(xù)的內(nèi)存單元中，則元素 A7，3的地址是： 1100 。 6. 設(shè)有二維數(shù)組 A0.9,0.19,其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為 100，若按列優(yōu)先順序存儲(chǔ)，則元素 A6,6存儲(chǔ)地址為 232 。 11設(shè)n 行n 列的下三角矩陣 A 已壓縮到一維數(shù)組 B1.n*（n+1

11、）/2中，若按行為主序存儲(chǔ)，則 Ai,j對(duì)應(yīng)的 B 中存儲(chǔ)位置為 i(i-1)/2+j (1<=i,j<=n) 。 14. 設(shè)有一個(gè) 10 階對(duì)稱矩陣 A 采用壓縮存儲(chǔ)方式（以行為主序存儲(chǔ)：a11=1），則 a85 的地址為 33 (k=i(i-1)/2+j) (1<=i,j<=n) 。 15. 所謂稀疏矩陣指的是 非零元很少(t<<m*n)且分布沒有規(guī)律 。16. 對(duì)矩陣壓縮是為了 節(jié)省存儲(chǔ)空間 。17. 上三角矩陣壓縮的下標(biāo)對(duì)應(yīng)關(guān)系為： 上三角矩陣中，主對(duì)角線上第r(1£r£n) 行有n-r+1個(gè)元素，aij所在行的元素?cái)?shù)是j-i+1

12、。所以，元素在一維數(shù)組的下標(biāo)k和二維數(shù)組下標(biāo)關(guān)系:k=(i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j (i£j)。18. 假設(shè)一個(gè) 15 階的上三角矩陣 A按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組 B 中， 則非零元素 A9,9在 B中的存儲(chǔ)位置k= 93 。 （注：矩陣元素下標(biāo)從 1 開始）如果按行序?yàn)橹餍驅(qū)⑾氯窃?Ai j (i,j)存儲(chǔ)在一個(gè)一維數(shù)組 B 1.n(n+1)/2中，對(duì)任一個(gè)三角矩陣元素 A ,它在數(shù)組B 中的下標(biāo)為 i(i-1)/2+j 。 8深度為k 的完全二叉樹至少有1個(gè)結(jié)點(diǎn)，至多有2個(gè)結(jié)點(diǎn)。42一個(gè)無序序列可以通過構(gòu)造一棵樹而變成

13、一個(gè)有序序列，構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。50線索二元樹的左線索指向其 ，右線索指向其 。53若以4，5，6，7，8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長(zhǎng)度是 。22. 已知一無向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a 開始遍歷圖，得到的序列為abecd，則采用的是 深度優(yōu)先 遍歷方法。28. Prim（普里姆）算法適用于求 邊稠密 的網(wǎng)的最小生成樹；29克魯斯卡爾算法的時(shí)間復(fù)雜度為 O(eloge）,它對(duì) 邊稀疏 圖較為適合。34. Dijkstra 最短路徑算法從源點(diǎn)到其

14、余各頂點(diǎn)的最短路徑的路徑長(zhǎng)度按 遞增 次序依次產(chǎn)生，該算法弧上的權(quán)出現(xiàn) 負(fù)值 情況時(shí)，不能正確產(chǎn)生最短路徑。12. 在哈希函數(shù)H（key）=key%p 中，p 值最好取 。49. 依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹。(1) 試畫出生成之后的二叉排序樹; (2) 對(duì)該二叉排序樹作中序遍歷，試寫出遍歷序列;1若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的 比較 和記錄的 移動(dòng) 。6直接插入排序用監(jiān)視哨的作用是 免去查找過程中每一步都要檢測(cè)整個(gè)表是否查找完畢，提高了查找效率。1. 文件可按其記錄的類型不

15、同而分成兩類，即 操作系統(tǒng)文件 和 數(shù)據(jù)庫(kù) 文件。7. 索引順序文件既可以順序存取，也可以 隨機(jī) 存取。8. 建立索引文件的目的是 提高查找速度 。9. 索引順序文件是最常用的文件組織之一，通常用 樹 結(jié)構(gòu)來組織索引。10. 倒排序文件的主要優(yōu)點(diǎn)在于 檢索記錄快 。13. VSAM 系統(tǒng)是由索引集、順序集、數(shù)據(jù)集構(gòu)成的。31. 廣義表A( ),(a,(b),c)，head(tail(head(tail(head(A)等于b32. 廣義表運(yùn)算式HEAD(TAIL(a,b,c),(x,y,z)的結(jié)果是 (x,y,z) 。33. 已知廣義表A=（a，b），（c），（d，e），head（tail（ta

16、il（head（A）的結(jié)果是 (d,e) 。4、 應(yīng)用題1線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問：如果有n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長(zhǎng)度（即表中元素個(gè)數(shù)）的影響，插入、刪除時(shí)間復(fù)雜度為O。選順序存儲(chǔ)結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O。2線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一般說克服了順序存儲(chǔ)結(jié)構(gòu)的三個(gè)弱點(diǎn)。首先，插入、刪除不需移動(dòng)元素，只修改指針，時(shí)間復(fù)雜度為O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要?jiǎng)討B(tài)申請(qǐng)空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允許時(shí)，就不能克服順序存儲(chǔ)的缺點(diǎn)。3若較頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除