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

1、1算法指的是（ d ） A計(jì)算機(jī)程序 B排序算法 C解決問(wèn)題的計(jì)算方法 D解決問(wèn)題的有限運(yùn)算序列2線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（a ） A連續(xù)與否均可 B必須是不連續(xù)的 C和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù) D必須是連續(xù)的3設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ c ） Afront=(front+1)%(m-1) Bfront=front+1 Cfront=(front+1)%m D front=(front-1)%m4如下陳述中正確的是（c ） A串中元素只能是字母 B空串就是空白串 C串是一種特殊的線性

2、表 D串的長(zhǎng)度必須大于零5設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示( )。 A688 B678 C692 D6966設(shè)輸入序列為1、2、3、4、5、6，則通過(guò)棧的作用后可以得到的輸出序列為（ ）。A 5，3，4，6，1，2B 3，2，5，6，4，1C 3，1，2，5，4，6D 1，5，4，6，2，37設(shè)有一個(gè)10階的下三角矩陣A（包括對(duì)角線），按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A54地址與A00的地址之

3、差為（ ）。A 10B 19C 28D 558一個(gè)非空廣義表的表頭（ ） A不可能是子表 B只能是子表 C只能是原子 D可以是子表或原子 9在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p-next-next= head,則( ) Ap指向頭結(jié)點(diǎn) Bp指向尾結(jié)點(diǎn) C*p的直接后繼是頭結(jié)點(diǎn) D*P的直接后繼是尾結(jié)點(diǎn)10在一棵度為3的樹(shù)中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為( )A4 B5 C6 D711廣義表A=(a,(b),(),(c,d,e)的長(zhǎng)度為( ) A4 B5 C6 D7 12在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,零元素的

4、個(gè)數(shù)為( ) Ae B2e Cn2e Dn22e13設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有( 5 )條邊才能確保是一個(gè)連通圖。14設(shè)順序存儲(chǔ)的線性表共有123個(gè)元素，按分塊查找的要求等分成3塊。若對(duì)索引表采用順序查找來(lái)確定塊，并在確定的塊中進(jìn)行順序查找，則在查找概率相等的情況下，分塊查找成功時(shí)的平均查找長(zhǎng)度為( ) A21 B23 C41 D62 15若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( ) A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，316無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中( ) A通過(guò)該頂點(diǎn)的簡(jiǎn)

5、單路徑數(shù) B與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù) C通過(guò)該頂點(diǎn)的回路數(shù) D與該頂點(diǎn)連通的頂點(diǎn)數(shù) 17用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A選擇排序 B希爾排序 C歸并排序 D快速排序18對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)， A1 B2

6、C3 D419設(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的操作序列為（ ）。As-next=p-next；p-next=-s；B q-next=s； s-next=p；Cp-next=s-next；s-next=p；Dp-next=s；s-next=q；20下面程序段的時(shí)間復(fù)雜度是( ) for(i=0;i=n;i+) for(j=1;jnext; Bp-next=p-next-next;Cp->next=p; Dp=p->next->next; 24判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是( ) AQ

7、.front=NULL BQ.rear=NULL CQ.front=Qrear DQ.front!=Qrear25設(shè)有兩個(gè)串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱(chēng)作( ) A聯(lián)接 B求子串 C字符定位 D子串定位26一棵含18個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度至少為( ) A3 B4 C5 D6 27已知二叉樹(shù)的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( ) ADEBAFC BDEFBCA CDEBCFA DDEBFCA 28已知一個(gè)圖如下所示，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷可能得到的序列為( ) Aa c e f b d Ba c b d f e Ca c b d e f Da c

8、d b f e 29已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35，其中每相鄰兩個(gè)為有序子序列。對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是( ) A25,36,48,72,23,40,79,82,16,35 B25,36,48,72,16,23,40,79,82,35 C25,36,48,72,16,23,35,40,79,82 D16,23,25,35,36,40,48,72,79,82 30對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)， A. 1 B2 C3 D41. 數(shù)

9、據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 存儲(chǔ) 無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。2. 在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為 head= pnextnext 。3. 棧頂?shù)奈恢檬请S著 進(jìn)棧和退棧 操作而變化的。4. 在串S=“structure”中，以t為首字符的子串有 12 個(gè)。5. 假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B0存儲(chǔ)矩陣中第1個(gè)元素a1,1,則B31中存放的元素是 a48 。6. 已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有 384 個(gè)葉子結(jié)點(diǎn)。7. 假定一棵樹(shù)的廣義表表示為A（C，D（E，F(xiàn)，

10、G），H（I，J），則樹(shù)中所含的結(jié)點(diǎn)數(shù)為_(kāi)9_個(gè)，樹(shù)的深度為_(kāi)3_，樹(shù)的度為_(kāi)3_。8. 若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有_2n_個(gè)指針域，其中有_n-1_個(gè)指針域是存放了地址，有_n+1_個(gè)指針是空指針。9. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_e_個(gè)和_2e_個(gè)。10. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有_n(n-1)/2_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_n(n-1)_條邊。11. 向一棵B_樹(shù)插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂

11、，則新樹(shù)高度與原樹(shù)高度相比_增加1_。12. 在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為 2 。 13. 在快速排序、堆排序、歸并排序中，_ 歸并_排序是穩(wěn)定的。14. 從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需_向前移_一個(gè)位置。 15. 在隊(duì)列中，允許進(jìn)行插入操作的一端稱(chēng)為_(kāi)隊(duì)尾_，允許進(jìn)行刪除操作的一端稱(chēng)為_(kāi)隊(duì)頭_。 16. 假設(shè)三維數(shù)組A1098按行優(yōu)先順序存儲(chǔ)，若每個(gè)元素占3個(gè)存儲(chǔ)單元，且首地址為100，則元素A987的存儲(chǔ)地址是_2182_。 17. 已知在一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)中，只有度為k的分支結(jié)點(diǎn)和度為0

12、的葉子結(jié)點(diǎn)，則該樹(shù)中含有的葉子結(jié)點(diǎn)的數(shù)目為_(kāi)n-(n-1)/k_。 18. 能夠成功完全拓?fù)渑判虻膱D一定是一個(gè)_有向圖_。 19. 如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用_堆排序_較為適當(dāng)。 20. 假設(shè)哈希表的表長(zhǎng)為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的形式表達(dá)為_(kāi) Hi = （H(key)+di) MOD m (di為增量序列）_。 21. 已知指針p指向單鏈表中某個(gè)結(jié)點(diǎn)，則語(yǔ)句p-next=p-next-next的作用是_刪除p所指向的結(jié)點(diǎn)的直接后繼結(jié)點(diǎn) _。1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A 0.n

13、ext，試寫(xiě)出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572041 (78 7 40 60 34 90)2請(qǐng)先中序遍歷該二叉樹(shù)（2分），然后畫(huà)出與下列二叉樹(shù)對(duì)應(yīng)的森林（3分）。3已知一個(gè)無(wú)向圖的頂點(diǎn)集為a, b, c, d, e ,其鄰接矩陣如下所示 (1)畫(huà)出該圖的圖形；（1分） （2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷（各2分），寫(xiě)出相應(yīng)的遍歷序列。 深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc4、 設(shè)有無(wú)向圖G，要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。5設(shè)棧S1的入棧序列為1234（每個(gè)數(shù)字

14、為13個(gè)元素），則不可能得到出棧序列3142。但可通過(guò)增設(shè)棧S2來(lái)實(shí)現(xiàn)。例如，按下圖中的箭頭指示，依次經(jīng)過(guò)棧S1和S2，便可得到序列3142。如果用H1和H2分別表示棧S1和S2的進(jìn)棧操作，用P1和P2分別表示兩個(gè)棧的出棧操作，則得到3142的一個(gè)操作步驟為H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2請(qǐng)仿照上例寫(xiě)出利用兩個(gè)棧從1234得到4132的操作步驟。H1, H1, P1, H2, H1, P1, H2, H1, P1, H2, P2, P1,H2,P2,P2, P26已知樹(shù)如右圖所示， （1）寫(xiě)出該樹(shù)的后序序列；(2分)（2）畫(huà)出由該樹(shù)

15、轉(zhuǎn)換得到的二叉樹(shù)。(3分)26.假設(shè)通信電文使用的字符集為a,b,c,d,e,f，名字符在電文中出現(xiàn)的頻度分別為：34，5，12，23，8，18，試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫(huà)出你所構(gòu)造的哈夫曼樹(shù)(要求樹(shù)中左孩子結(jié)點(diǎn)的權(quán)值小于右孩子結(jié)點(diǎn)的權(quán)值)，然后分別寫(xiě)出每個(gè)字符對(duì)應(yīng)的編碼。7.已知一個(gè)圖如下所示，其頂點(diǎn)按a、b、c、d、e、f順序存放在鄰接表的頂點(diǎn)表中，請(qǐng)畫(huà)出該圖的鄰接表，使得按此鄰接表進(jìn)行深度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbefd，進(jìn)行廣度優(yōu)先遍歷時(shí)得到的頂點(diǎn)序列為acbdfe。下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為： comstr(s1,s2)= 請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容

16、。int comstr(LinkString s1,LinkString s2) /s1和s2為兩個(gè)鏈串的頭指針 while(s1&s2) if(s1datedate)return1； if(s1dates2date)return1； S1=S1next _ ； _ s2=s2next _ ； if( _ s2(或s2!=NULL或s2&!s1_ )return1； if( _ s1(或s1!=NULL或s1&!s2)_ )return1； return 0 _ ； 8閱讀下面的算法 LinkList mynote(LinkList L) /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 請(qǐng)回答下列問(wèn)題： （1）說(shuō)明語(yǔ)句S1的功能；查詢(xún)鏈表的尾結(jié)點(diǎn) （2）說(shuō)明語(yǔ)句組S2的功能；將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。 返回的線性表為（a2,a3,an,a1）9假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見(jiàn)右下圖）， 其類(lèi)型Queue2定義如下： typedef struct DateType dataMaxSize；