【文章內(nèi)容簡介】 ） A．棧頂 B．棧底 C．任意位置 D．指定位置 標(biāo)準(zhǔn)答案： A 5某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。（ ） A．空或只有一個(gè)結(jié)點(diǎn) B．高度等于其結(jié)點(diǎn)數(shù) C．任一結(jié)點(diǎn)無左 孩子 D．任一結(jié)點(diǎn)無右孩子 標(biāo)準(zhǔn)答案： B 5在用鄰接表表示圖的情況下，建立圖的算法的時(shí)間復(fù)雜度是（ ）。（ ） A． O(n+e) B． O(n2) C． O(n e) D． O(n3) 標(biāo)準(zhǔn)答案： A 5一個(gè)棧的入棧序列是 a,b,c,d,e,則棧的不可能的輸出序列是（ ）。（ ） A． edcba B． decba C． abcde D． dceab 標(biāo)準(zhǔn)答案： D 5線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（ ）。（ ） 第 11 頁 共 24 頁 A．必須是連續(xù)的 B．部分地址必須是連續(xù)的 C．一定是不連續(xù)的 D．連續(xù)與否均可以 標(biāo)準(zhǔn)答案： D 60、二叉樹第 i層上至多有（ ）結(jié)點(diǎn)。（ ） A． 2i B． 2i C． 2i1 D． 2i1 標(biāo)準(zhǔn)答案： C 6在一個(gè)循環(huán)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（ ）位置。（ ） A．前一個(gè) B．后一個(gè) C．當(dāng)前 D．后面 標(biāo)準(zhǔn)答案： A 6如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（ ）。（ ） A．必須判別棧是否滿 B．對棧不作任何判別 C．必須判別棧是否空 D．判別棧元素的類型 標(biāo)準(zhǔn)答案： C 6組成數(shù)據(jù)結(jié)構(gòu)的基本單位是（ ）。（ ） A．?dāng)?shù)據(jù)項(xiàng) B．?dāng)?shù)據(jù)類型 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)變量 標(biāo)準(zhǔn)答案： C 6設(shè)單鏈表中指針 p 指著結(jié)點(diǎn) A，若要?jiǎng)h除 A之后的結(jié)點(diǎn)（若存在），則需要修改指針操作為（ ）。（ ） A． pnext=pnextnext B． p=pnext C． p=pnextnext D． pnext=p 標(biāo)準(zhǔn)答案： A 6棧的插入與刪除操作在（ ）進(jìn)行。（ ） A．棧頂 第 12 頁 共 24 頁 B．棧底 C．任意位置 D．指定位置 標(biāo)準(zhǔn)答案： A 6廣義表（（ a）），其表頭是（ ）。（ ） A． a B．（ a） C．（） D．（（ a）） 標(biāo)準(zhǔn)答案： B 6線索化二叉樹中某結(jié)點(diǎn) D，沒有左孩子的主要條件是（ ）。（ ） A． DLchild=Null B． Dltag=1 C． DRchild=Null D． Dltag=0 標(biāo)準(zhǔn)答案： B 6在有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（ ）。（ ） A．不確定 B． 2n C． 2n+1 D． 2n1 標(biāo)準(zhǔn)答案： D 6從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí)，首先需要（ ）。（ ） A．前移一位隊(duì)首指針 B．后移一位隊(duì)首指針 C．取出隊(duì)首指針?biāo)肝恢蒙系脑? D．取出隊(duì)尾指針 所指位置上的元素 標(biāo)準(zhǔn)答案： B 70、 Substr(39。DATA STRUCTURE39。， 5， 9)=（ ）。（ ） A． STRUCTURE39。 B． 39。ASTUCTUR39。 C． 39。DATA STRUCTRUE39。 標(biāo)準(zhǔn)答案： A 7二分查找要求被查找的表是（ ）。（ ） A．鍵值有序的鏈接表 B．鏈接表但鍵值不一定有序 C．鍵值有序的順序表 D．順序表但鍵值不一定有序 第 13 頁 共 24 頁 標(biāo)準(zhǔn)答案： C 二、填空題（本大題共 48 小題，每小題 2 分，共 96 分） 7數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、 ___、散列結(jié)構(gòu)四種。 標(biāo)準(zhǔn)答案：索引結(jié)構(gòu) 7數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、 ___四種。 標(biāo)準(zhǔn)答案：散列結(jié)構(gòu) 7在雙向鏈表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)指針域，一個(gè)指向其 ___結(jié)點(diǎn)，另一個(gè)指向其 ___結(jié)點(diǎn)。 標(biāo)準(zhǔn)答案：前驅(qū) 。后繼 7在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 ___倍。 標(biāo)準(zhǔn)答案： 2 7對于一棵具有 n 個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為 ___。 標(biāo)準(zhǔn)答案： n1 7假定一棵樹的廣義表表示為 A(B(C(D,E),F,G(H,I,J)),K)，則度為 3 的結(jié)點(diǎn)數(shù)為 ___個(gè)。 標(biāo)準(zhǔn)答案： 2 7一個(gè)算法應(yīng)具備的 5 個(gè)特性為 ___、確定性、可行性、輸入、輸出。 標(biāo)準(zhǔn)答案：有窮性 7一個(gè)算法應(yīng)具備的 5 個(gè)特性為有窮性、 ___、可行性、輸入、輸出。 標(biāo)準(zhǔn)答案：確定性 80、以二分查找方法從長度為 12 的有序表中查找一個(gè)元素時(shí)，平均查找長度為 ___。 標(biāo)準(zhǔn)答案： 37/12 8對于線性表 (18,25,63,50,42,32,90)進(jìn)行散列存儲(chǔ)時(shí)，若選用 H(K)=K % 9 作為散列函數(shù)，則散列地址為 0 的元素有 ___個(gè)，散列地址為 5 的元素有 ___個(gè)。 標(biāo)準(zhǔn)答案： 3。2 8數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、 ___、索引結(jié)構(gòu)、散列結(jié)構(gòu)四種。 標(biāo)準(zhǔn)答案：鏈接結(jié)構(gòu) 8對于一個(gè)具有 n 個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為 ___。 標(biāo)準(zhǔn)答案： n*n 8在雙向循環(huán)鏈表中，在指針 p 所指的結(jié)點(diǎn)之后插入指針 f 所指的結(jié)點(diǎn)，其操作為 ___。 第 14 頁 共 24 頁 標(biāo)準(zhǔn)答案：（ 1） fnext=pnext； （ 2） pnextprior=f； （ 3） fprior=p； （ 4） pnext=f； 8對于一個(gè)長度為 n 的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ___，在表尾插入元素的時(shí)間復(fù)雜度為 ___。 標(biāo)準(zhǔn)答案： O(n)。O(1) 8中綴表達(dá)示 3+X*（ ）所對應(yīng)的后綴表達(dá)示為 ___。 標(biāo)準(zhǔn)答案： 3 x 5 ／ 6 － *＋ 8假定一棵樹的廣義表表示為 A(B(C(D,E),F,G(H,I,J)),K)，則度為 0 的結(jié)點(diǎn)數(shù)為 ___個(gè)。 標(biāo)準(zhǔn)答案： 7 8對于線性表（ 18， 25， 63， 50， 41， 32， 90， 66）進(jìn)行散列存儲(chǔ)時(shí)，若選 用 H（ K） =K%11作為散列函數(shù)，則散列地址為 3 的元素有 ___個(gè)，散列地址為 8 的元素有 ___個(gè)。 標(biāo)準(zhǔn)答案： 1。2 8中綴算術(shù)表達(dá)式 3+4/(25(6+15))*8 所對應(yīng)的后綴算術(shù)表達(dá)式為 ___。 標(biāo)準(zhǔn)答案： 3 4 25 6 15 + / 8 * + 90、快速排序在平均情況下的時(shí)間復(fù)雜度為 ___，在最壞情況下的時(shí)間復(fù)雜度為 ___。 標(biāo)準(zhǔn)答案： O(nlog2n)。O(n2) 9前序序列和中序序列相同的二叉樹為 ___。 標(biāo)準(zhǔn)答案：單右枝二叉樹或孤立結(jié)點(diǎn) 9每次從無序表中 順序取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做 ___排序。 標(biāo)準(zhǔn)答案：插入 9一個(gè) n*n 的對稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為 ___。 標(biāo)準(zhǔn)答案： n(n+1)/2 9后綴表達(dá)式“ 2 10 + 5 * 6 – 9 / ”的值為 ___。 標(biāo)準(zhǔn)答案： 6 9對于一棵二叉樹，若一個(gè)