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

1、1算法指的是（ d ） A計(jì)算機(jī)程序 B排序算法 C解決問題的計(jì)算方法 D解決問題的有限運(yùn)算序列2線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址（a ） A連續(xù)與否均可 B必須是不連續(xù)的 C和頭結(jié)點(diǎn)的存儲地址相連續(xù) D必須是連續(xù)的3設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲空間，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串的長度必須大于零5設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示( )。 A688 B678 C692 D6966設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ ）。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è)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A54地址與A00的地址之

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

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

5、單路徑數(shù) B與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù) C通過該頂點(diǎn)的回路數(shù) D與該頂點(diǎn)連通的頂點(diǎn)數(shù) 17用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時，序列的變化情況如下： 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對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個， 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下面程序段的時間復(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è)有兩個串T和P，求P在T中首次出現(xiàn)的位置的串運(yùn)算稱作( ) A聯(lián)接 B求子串 C字符定位 D子串定位26一棵含18個結(jié)點(diǎn)的二叉樹的高度至少為( ) A3 B4 C5 D6 27已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為( ) ADEBAFC BDEFBCA CDEBCFA DDEBFCA 28已知一個圖如下所示，從頂點(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，其中每相鄰兩個為有序子序列。對這些子序列進(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對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個， A. 1 B2 C3 D41. 數(shù)

9、據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 存儲 無關(guān)，是獨(dú)立于計(jì)算機(jī)的。2. 在一個帶頭結(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 個。5. 假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B0存儲矩陣中第1個元素a1,1,則B31中存放的元素是 a48 。6. 已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有 384 個葉子結(jié)點(diǎn)。7. 假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，

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

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

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

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

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

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

16、。int comstr(LinkString s1,LinkString s2) /s1和s2為兩個鏈串的頭指針 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； 請回答下列問題： （1）說明語句S1的功能；查詢鏈表的尾結(jié)點(diǎn) （2）說明語句組S2的功能；將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。 返回的線性表為（a2,a3,an,a1）9假設(shè)兩個隊(duì)列共享一個循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typedef struct DateType dataMaxSize；