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

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

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

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

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

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

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

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

9、 中尋找等于 P 的子串的過程稱為 模式匹配 ，又稱P 為 模式串 。 9串是一種特殊的線性表，其特殊性表現(xiàn)在 其數(shù)據(jù)元素都是字符 ；串的兩種最基本的存儲方式是 順序存儲 、 鏈式存儲 ；兩個串相等的充分必要條件是 串的長度相等且兩串中對應位置的字符也相等 。10兩個字符串相等的充分必要條件是 兩串的長度相等且兩串中對應位置的字符也相等 。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ù)組的存儲結構采用 順序存儲

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

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

12、。所以，元素在一維數(shù)組的下標k和二維數(shù)組下標關系:k=(i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j (i£j)。18. 假設一個 15 階的上三角矩陣 A按行優(yōu)先順序壓縮存儲在一維數(shù)組 B 中， 則非零元素 A9,9在 B中的存儲位置k= 93 。 （注：矩陣元素下標從 1 開始）如果按行序為主序將下三角元素 Ai j (i,j)存儲在一個一維數(shù)組 B 1.n(n+1)/2中，對任一個三角矩陣元素 A ,它在數(shù)組B 中的下標為 i(i-1)/2+j 。 8深度為k 的完全二叉樹至少有1個結點，至多有2個結點。42一個無序序列可以通過構造一棵樹而變成

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

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

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

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