【正文】 《數(shù)據(jù)結(jié)構(gòu)》練習(xí)測(cè)試題 一．選擇題 1． 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ C ）。 A． 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B． 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C． 線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D． 內(nèi)部結(jié)構(gòu)和非內(nèi)部結(jié)構(gòu) 2． 若頻繁地對(duì)線(xiàn)性表進(jìn)行插入和刪除操作，該線(xiàn)性表應(yīng)該采用（ C ）存儲(chǔ)結(jié)構(gòu)。 A．散列 3． 若刪除非空線(xiàn)性鏈表中由 p 所指鏈結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的過(guò)程是依次執(zhí)行 (B ) A． r=pnext。 pnext=r。 call RET(r) B． r=pnext。 pnext=rnext。 call RET(r) C． r=pnext。 pnext=rnext。 call RET(p) D． pnext=pnextnext。 call RET(p) 4． 下面的說(shuō)法中，不正確的是（ D ）。 A．只須存放對(duì)稱(chēng)矩陣中包括主對(duì)角線(xiàn)元素在內(nèi)的下 (或上 )三角部分的元素即可 B．只須存放對(duì)角 矩陣中的非零元素即可 C．稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ) D．稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ) 5． 串的長(zhǎng)度是 ( D )。 A．串中不同字母的個(gè)數(shù) B．串中不同字符的個(gè)數(shù) C．串中所含字符的個(gè)數(shù)，且大于 0 D．串中所含字符的個(gè)數(shù) 6． 一個(gè)棧的人棧序列是 a， b， c， d， e，則棧的不可能的輸出序列是 ( C )。 A． edcba B． decba C． dceab D． abcde 7． 廣義表的長(zhǎng)度是指（ A ） A，廣義表中元素的個(gè)數(shù) B。廣義表中原子元素的個(gè)數(shù) C．廣義表中表元素的個(gè)數(shù) D．廣義表中括號(hào)嵌套的層數(shù) 8． 某非空二叉樹(shù)的前序序列和后序序列正好相反，則二叉樹(shù) 定是 ( B )的二叉樹(shù)。 B．高度等于其結(jié)點(diǎn)數(shù) D．任一結(jié)點(diǎn)無(wú)右孩子 9. 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為( A )。 A． n B． n+1 C． nl D． n 十 e 10． 在計(jì)算遞歸函數(shù)時(shí)，若不用遞歸則應(yīng)借助數(shù)據(jù)結(jié)構(gòu) ( D )。 A. 數(shù)組 B. 隊(duì)列 C. 鏈表 D. 棧 11． 算法分析的目的是（ C ）； Ａ . 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 研究算法中的輸入和輸出的關(guān)系 C. 分析算法的效率以求改進(jìn) D. 分析算法的易懂性和文檔性 12． 在一個(gè)長(zhǎng)度為 n 的順序表中，向第 i個(gè)元素（ 1≤ i≤ n＋１）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)（ C ）個(gè)元素。 +1 13． 在一個(gè)雙鏈表中結(jié)點(diǎn) p 之后插入一個(gè)結(jié)點(diǎn) s 的操作是 ( C )。 A. sright=p。sleft=pright。prightleft=s。pright=s B. sright=pright。prightleft=s。sright=p。pleft=s C. sright=pright。sleft=p。pleftleft=s。pright=s D. sright=p。pleftleft=s。pright=s。sright=pright 14． 若將 n 階對(duì)稱(chēng)矩陣 A 按照行序?yàn)橹餍蚍绞綄ㄖ鲗?duì)角線(xiàn)元素在內(nèi)的下三角形的所有元素依次存放在一個(gè)一維數(shù)組 B 中，則該對(duì)稱(chēng)矩陣在 B 中占用了 ( C )個(gè)數(shù)組元素。 A． n/2 B． n*(n1) C． n*(n+1)／ 2 D． n*(n1) 15． 設(shè)串 s=ABUBG,len(s)返 回串 s 的長(zhǎng)度，則 len(s)是 ( C )。 A． 2 B． 4 C． 5 D． 6 16． 向一個(gè)棧頂指針為 HS 的鏈棧中插入 — 個(gè) s 所指結(jié)點(diǎn)時(shí)，則執(zhí)行 ( C ) A． HSnext=S； B． Snext=HSnext； HSnext=S； C． Snext=HS； HS=S； D． Snext=HS； HS=HSnext； 17． 廣義表的深度是指 ( D ) A．廣義 表中元素的個(gè)數(shù) B．廣義表中原子元素甜個(gè)數(shù) C. 廣義表中表元素的個(gè)數(shù) D．廣義表中括號(hào)嵌套的層數(shù) 18． 非空二叉樹(shù)在線(xiàn)索化后，仍不能有效求解的問(wèn)題是 (D )。 A．前序線(xiàn)索二叉樹(shù)中求前序后繼 B．中序線(xiàn)索二叉樹(shù)中求中序后繼 D．后序線(xiàn)索二叉樹(shù)中求后序后繼 19. 一個(gè)具有 n 個(gè)頂點(diǎn)的有向圖最多有 ( B )條邊。 A． nx(n1)／ 2 B． nx(n1) C． nx(n+1)／ 2 D． nxn 20． 依次將待排序膨 0中的元素和有序子序列合并為一個(gè)新的有序子序列的是 ( A )。 A．插入排序 B．冒泡排序 D．堆排序 21． 算法分析的兩個(gè)主要方面是（ B ）。 A. 空間復(fù)雜度和時(shí)間復(fù)雜度 B. 正確性和簡(jiǎn)單性 C．可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 22． 若長(zhǎng)度為 n 的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在表的第 i個(gè)位置插入一個(gè)元素的算法的時(shí)間復(fù)雜度是（ A ） Ａ .O(n) (n*n) (nlog2n) (log2n) 23． 非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)（由 p 所指向）滿(mǎn)足（ C ）。 next=NULL。 =NULL。 next=head。 =head。 24． 若將對(duì)稱(chēng)矩陣 A 按照行序?yàn)橹餍蚍绞綄ㄖ鲗?duì)角線(xiàn)元素在內(nèi)的下三角形的所有元素依次存放在一個(gè)一維數(shù)組 B 中，那么， A中某元素 ai(i0)在 B 中的位置是 ( C )。 A． (i*(i1))／ 2+j B． (i*(i1))／ 2j C． (j*(j1))／ 2+i D． (j*(j1))/ 2i 25． 設(shè)串 sI=ABCDEFG,s2=PQRST,函數(shù) con(x,y)返回 x和 y 串的連接串 ,subs(s，山 )返回串 s 的從序號(hào) i 的字符開(kāi)始的 j 個(gè)字符組成的子串， len(s)返回串 s 的長(zhǎng)度，則con(subs(s1,2,1en(s2))， subs(sl,len(s2)， 2))的結(jié)果串是 ( D )。 A． BCDEF B． BCDEFG C． BCPQRST n。 BCDEFEF 26． 中綴表達(dá)式 A(B+C／ D)*E 的后綴形式是 ( B )。 A． ABC+D／ *E B． ABCD／ +E* C． ABC+D／ E* D． ABC+D/E* 27． 廣義表 A： )， (a)， b， c， d)))的長(zhǎng)度為 ( B ) A． 2 B． 3 C． 4 D． 5 28． 對(duì)于一組結(jié)點(diǎn)，從空樹(shù)開(kāi)始，把它們插入到二叉排序樹(shù)中，就建立了一棵二叉排序樹(shù)。這時(shí)，整個(gè)二叉排序樹(shù)的形狀取決于 ( A )。 A．結(jié)點(diǎn)的輸入順序 B．結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) D．計(jì)算機(jī)的硬件 29. 導(dǎo)致圖的遍歷序列不惟一的因素是 ( D ) A．出發(fā)點(diǎn)的不同、遍歷方法的不同 B．出發(fā)點(diǎn)的不同、存儲(chǔ)結(jié)構(gòu)的不同 C．遍歷方法的不同、存儲(chǔ)結(jié)構(gòu)的不同 D．出發(fā)點(diǎn)的不同、存儲(chǔ)結(jié)構(gòu)的不同、遍歷方法的不同 30．線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址 ( D )。 A. 必須是連續(xù)的； B. 部分地址必須是連續(xù)的； C. 一定是不連續(xù)的； D. 連續(xù)與否均可以。 31． 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ C ）。 A． 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B． 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C． 線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D． 內(nèi)部結(jié)構(gòu)和非內(nèi)部結(jié)構(gòu) 32． 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種（ B ）的存儲(chǔ)結(jié)構(gòu)。 A． 隨機(jī)存取 B． 順序存取 C． 索引存取 D． HASH 存取 33． 設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為 (date， link)且 rear 是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)指針。若想刪除鏈表的第一個(gè)結(jié)點(diǎn) ,則應(yīng)執(zhí)行下列哪一個(gè)操作 ?( B ) =rear。rear=rearlink。delete s。 B. rear=rearlink。delete rear。 =rearlinklink。delete rear。 D. s=rearlinklink。rearlinklink=slink。delete s。 34． 稀疏矩陣一般的壓縮存儲(chǔ)方法有 兩種，即 ( C )。 A．二維數(shù)組和三維數(shù)組 B．三元組和散列 C. 三元組和十字鏈表 D．散列和十字鏈表 35． 設(shè)串 sI=ABCDEFG,s2=PQRST,函數(shù) con(x,y)返回 x和 y 串的連接串 ,subs(s，山 )返回串 s 的從序號(hào) i 的字符開(kāi)始的 j 個(gè)字符組成的子串， len(s)返回串 s 的長(zhǎng)度，則con(subs(s1,2,1en(s2))， subs(sl,len(s2)， 2))的結(jié)果串是 ( D )。 A． BCDEF B． BCDEFG C． BCPQRST n。 BCDEFEF 36． 判定一個(gè)循環(huán)隊(duì)列 QU(最多元素為 m0)為滿(mǎn)隊(duì)列的條件是 ( C ) A． QUfront==QUrear B． QUfront!=QUrear C． QUfront==(QUrear+1)％ m0 D． QUfront!=(QUrear+1)％ m0 37． 廣義表 A=(()， (a)， (b， (c， d)))的深度為 ( B ) A． 2 B． 3 C． 4 D． 5 38． 已知某二叉樹(shù)的后序遍歷序列是 dabec,中序遍歷序列是 debac,它的前序遍歷序列是( D )。 A． acbed B． decab C． deabc D． cedba 39. 任何一個(gè)帶權(quán)無(wú)向連通圖的最小生成樹(shù) ( B )。 A．是唯一的 B．是不唯一的 C．有可能不惟一 D．有可能不存在 40． 快速排序在最好的情況下的時(shí)間復(fù)雜度是 ( B )。 A． O(n) B． 0(nlog2n) C． O(n2) D． 0(10g2n) 二． 判斷題 1. 線(xiàn)性表的邏輯順序與存儲(chǔ)順序總是一致的。 ( F ) 2. 當(dāng)字符集中的各字符使用頻率不均勻時(shí)，等長(zhǎng)編碼是最優(yōu)的前綴碼。 ( F ) 3. 一個(gè)棧的輸人序列是 1， 2， 3， 4， 5，則棧的輸出序列有可能式 4,3,5,1,2 。 ( F ) 4. 存儲(chǔ)無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，故只存儲(chǔ)鄰接矩陣的下 (或上 )三角部分即可。 ( T ) 5. 順序表的插入和刪除操作不需要付出很大的時(shí)間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲脑匦枰苿?dòng)。 （ F ） 6. 鄰接表法只用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。 ( F ) 7. 在二叉樹(shù)中插入結(jié)點(diǎn)則該二叉樹(shù)便不再是二叉樹(shù)。