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

復(fù)習(xí)題一、選擇題： 1、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址 。A必須是連續(xù)的 B一定是不連續(xù)的C部分地址必須是連續(xù)的 D連續(xù)與否均可以2、設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需用修改指針的操作為 。Apnext= pnext next； Bp= pnext；Cp= pnext next； Dpnext= p；3、設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳、B、C、D、E，下列 是不可能的出棧序列。AA、B、C、D、E BB、C、D、E、ACE、A、B、C、D DE、D、C、B、A4、在一個(gè)具有n個(gè)單元的順序存儲(chǔ)循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則判斷隊(duì)列為滿(mǎn)的條件是 。Arear%n=front B(front+1)%n=rear Crear%n -1 = front Drear%n+1=front5、串是一種特殊的線性表，其特殊性體現(xiàn)在 。A 可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符C可以鏈接存儲(chǔ) D數(shù)據(jù)元素可以是多個(gè)字符6、廣義表(a, b, c, d)的表頭是 ，表尾是 。Aa B( ) C( a, b ,c, d ) D( a, b, c, d )7、一棵高為K的完全二叉樹(shù)，至少有多少個(gè)結(jié)點(diǎn)？( ) A. 2k-1 B. 2k-1-1 C. 2k-1 D. 2k 8、若給定的關(guān)鍵字集合為20，15，14，18，21，36，40，10，一趟快速排序結(jié)束時(shí)，鍵值的排列為 。A10，15，14，18，20，36，40，21 B10，15，14，18，20，40，36，21 C10，15，14，20，18，40，36，21 D15，10，14，18，20，36，40，219、在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為 。An-1 B2n-1 Cn+1 D2n+110、帶權(quán)有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中 。A第i行非無(wú)窮元素之和 B第i列非無(wú)窮元素之和 C第i行非零且非無(wú)窮元素個(gè)數(shù) D第i列非零且非無(wú)窮元素個(gè)數(shù)二、填空題： 1下面程序段的時(shí)間復(fù)雜度是 。for (i=0;in;i+) for (j=0;jnext ) Q=L; L=L-next; P=L; While ( P-next ) P=P-next; P-next=Q; Q-next=NULL;return OK; /A2簡(jiǎn)述以下算法的功能。 status algo2 (Stack S，int e) Stack T； int d；InitStack (T)；while ( !StackEmpty (S) ) Pop ( S，d)； if (d!=e) Push (T，d )； while ( !StackEmpty (T) ) Pop ( T,d)； Push ( S，d)； 六、設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫(xiě)一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。(va.length 順序表現(xiàn)有元素個(gè)數(shù)，va.listsize 為順序表容量，va.elemi為數(shù)據(jù)元素)七、直接插入排序、冒泡排序、簡(jiǎn)單選擇排序、歸并排序、基數(shù)排序書(shū)上例子，要自己能寫(xiě)出每一趟的結(jié)果。八、根據(jù)圖的數(shù)組表示法或者鄰接矩陣表示法，畫(huà)出圖的結(jié)構(gòu)，且能夠根據(jù)表示結(jié)構(gòu)進(jìn)行深度/廣度遍歷。九、拓?fù)渑判?，huffman樹(shù)的構(gòu)造，WPL計(jì)算，根據(jù)樹(shù)進(jìn)行編解碼。十、哈希表，書(shū)上的