數據結構復習題一.單選題（共182題）1.

(單選題)算法的計算量的大小稱為計算的（）A.效率B.復雜性C.現實性D.難度正確答案:

B2.

(單選題)無向圖G=（V，E），其中：V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，以頂點a為源點，對該圖進行深度優先遍歷，得到的頂點序列正確的是（）A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b正確答案:

D3.

(單選題)設主串的長度為m，子串的長度為n，那么KMP模式匹配算法的時間復雜度為（）A.O（m）B.O（n）C.O（m*n）D.O（m+n）正確答案:

D4.

(單選題)用鏈接方式存儲的隊列，假設有頭結點，在進行刪除運算時（）A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改正確答案:

D5.

(單選題)數據的存儲結構是指（）A.數據所占的存儲空間B.數據的邏輯結構在計算機中的表示C.數據在計算機中的順序存儲方式D.存儲在外存中的數據正確答案:

B6.

(單選題)設有6個值，由它們組成一棵赫夫曼樹，則該赫夫曼樹中結點個數共有（）A.6B.11C.12D.13正確答案:

B7.

(單選題)下面算法的時間復雜度為（）x=n；//n>1y=0；while（x>=（y+1）*（y+1））y++；A.O（n）B.O（n2）C.O（2n）D.O（n1/2）正確答案:

D8.

(單選題)設順序循環隊列Q[0..M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素，尾指針R總是指向隊尾元素的下一位置，則該循環隊列中的元素個數為（）A.R-FB.F-RC.（R-F+M）％MD.（F-R+M）％M正確答案:

C9.

(單選題)下面說法錯誤的是（）A.算法原地工作的含義是指不需要任何額外的輔助空間B.在相同的規模n下，復雜度O（n）的算法在時間上總是優于復雜度O（2n）的算法C.所謂時間復雜度是指最壞情況下，估算算法執行時間的一個上界D.某算法的時間復雜度為O（n2），表明該算法的執行時間與成n2正比正確答案:

A10.

(單選題)下列關于圖的敘述中，正確的是（）I.回路是簡單路徑II.存儲稀疏圖，用鄰接矩陣與鄰接表更省空間III.若有向圖中存在拓撲序列，則該圖不存在回路A.僅IIB.僅I、IIC.僅IIID.僅I、III正確答案:

C11.

(單選題)若元素a、b、c、d、e、f依次進棧，允許進棧、退棧操作交替進行，但不允許連續三次進行退棧工作，則不可能得到的出棧序列是（）A.dcebfaB.cbdaefC.bcaefdD.afedcb正確答案:

D12.

(單選題)棧和隊列的共同點是（）A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點正確答案:

C13.

(單選題)算法的計算量的大小稱為算法的（）A.效率B.現實性C.難度D.復雜度正確答案:

D14.

(單選題)串的長度是指（）A.串中所含不同字母的個數B.串中所含字符的個數C.串中所含不同字符的個數D.串中所含非空格字符的個數正確答案:

B15.

(單選題)下列排序算法中，（）排序在每趟結束后不一定能選出一個元素放到其排好序的最終位置上。A.歸并B.冒泡C.選擇D.堆正確答案:

A16.

(單選題)表達式a*（b+c）-d的后綴表達式是（）A.abcd*+-B.abc*+d-C.abc+*d-D.-+*abcd正確答案:

C17.

(單選題)輸入序列為A，B，C，輸出變為C，B，A時，經過的棧操作為（）A.push，pop，push，pop，push.popB.push，push，push，pop，pop，popC.push，push，pop，pop，push，popD.push，pop，push，push，pop，pop正確答案:

B18.

(單選題)以下（）是一個線性表。A.由n個實數組成的集合B.由100個字符組成的序列C.所有整數組成的序列D.由100個整數組成的集合正確答案:

B19.

(單選題)對n個關鍵字做快速排序，在最壞的情況下，算法的時間復雜度是（）A.O（n）B.O（n2）C.O（nlog2n）D.O（n3）正確答案:

B20.

(單選題)在常用的描述二叉排序樹的存儲結構中，關鍵字值最大的結點（）A.左指針一定為空B.右指針一定為空C.左右指針均為空D.左右指針均不為空正確答案:

B21.

(單選題)某算法的時間復雜度為O（n2），表明該算法的（）A.問題規模是n2B.執行時間等于n2C.執行時間與n2成正比D.問題規模與n2成正比正確答案:

C22.

(單選題)若一棵完全二叉樹有768個結點，則該二叉樹中的葉子結點的個數是（）A.257B.258C.384D.385正確答案:

C23.

(單選題)串是一種特殊的線性表，其特殊性體現在（）A.可以順序存儲B.每個數據元素是一個字符C.可以鏈式存儲D.每個數據元素是多個字符正確答案:

B24.

(單選題)用鏈表表示線性表的優點是（）A.便于隨機存取B.花費的存儲空間較順序存儲少C.便于插入和刪除D.數據元素的物理順序與邏輯順序相同正確答案:

C25.

(單選題)線性表若采用順序存儲結構時，要求內存中可用存儲單元的地址（）A.必須是連續的B.部分地址必須是連續的C.一定是不連續的D.連續不連續都可以正確答案:

A26.

(單選題)下面算法的時間復雜度為（）for（i=0；iA.O（m）B.O（n）C.O（n*m）D.O（n+m）正確答案:

C27.

(單選題)由3個結點可以構造出（）種不同的二叉樹。A.2B.3C.4D.5正確答案:

D28.

(單選題)關鍵路徑是事件結點網絡中（）A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑C.最長回路D.最短回路正確答案:

A29.

(單選題)算法分析的兩個主要方面是（）A.數據復雜性和程序復雜性B.正確性和簡明性C.空間復雜度和時間復雜度D.可讀性和文檔性正確答案:

C30.

(單選題)利用二叉鏈表存儲樹，則根結點的右指針是（）節。A.指向最左孩子B.指向最右孩子C.空D.非空正確答案:

C31.

(單選題)以下說法正確的是（）A.數據元素是數據的最小單位B.數據項是數據的基本單位C.數據結構是帶有結構的各數據項的集合D.一些表面上很不相同的數據可以有相同的邏輯結構正確答案:

D32.

(單選題)用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的（）遍歷。A.中序遍歷B.先序遍歷C.后序遍歷D.層序遍歷正確答案:

D33.

(單選題)已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是（）A.O（n）B.O（m*n）C.O（min（m，n））D.O（max（m，n））正確答案:

D34.

(單選題)線性表（a1，a2，...，an）以鏈接方式存儲時，訪問第i位置上元素的時間復雜度為（）A.O（i）B.O（1）C.O（n）D.O（i-1）正確答案:

C35.

(單選題)棧和隊列都是（）A.順序存儲的線性結構B.鏈式存儲的非線性結構C.限制存取點的線性結構D.限制存取點的非線性結構正確答案:

C36.

(單選題)已知一個長度為16的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個存在的元素，則比較次數最多的（）次。A.4B.5C.6D.7正確答案:

B37.

(單選題)n個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有（）個非零元素。A.nB.2（n-1）C.n/2D.n2正確答案:

B38.

(單選題)從未排序序列中挑選元素，并將其依次放入已排序序列（初始時只有一個元素）的正確位置的方法，稱為（）A.歸并排序B.冒泡排序C.插入排序D.選擇排序正確答案:

C39.

(單選題)將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是（）A.nB.2n-1C.2nD.n-1正確答案:

A40.

(單選題)在決定選取何種存儲結構時，一般不考慮（）A.所用編程語言實現這種結構是否方便B.結點個數的多少C.對數據有哪些運算D.各結點的值如何正確答案:

D41.

(單選題)KMP算法的特點是在模式匹配時指示主串的指針（）A.不會變大B.不會變小C.都有可能D.無法判斷正確答案:

B42.

(單選題)算法具有的五個重要特性是：有窮性，（），可行性，輸入和輸出。A.確定性B.可讀性C.健壯性D.可維護性正確答案:

A43.

(單選題)含有n個頂點的連通有向圖，其邊的個數至多為（）A.nB.n（n+1）C.n（n-1）D.n（n-1）/2正確答案:

C44.

(單選題)設某棵二叉樹中只有度數為0和度數為2的結點且度數為0的結點數為n，則這棵二叉中共有（）個結點。A.2nB.n+1C.2n-1D.2n+1正確答案:

C45.

(單選題)堆是一種（）排序。A.插入B.選擇C.交換D.歸并正確答案:

B46.

(單選題)兩個串相等的充分必要條件是（）A.兩串長度相等B.兩串所包含的字符集合相等C.兩串長度相等且對應字符相等D.兩串長度相等且所包含的字符集合相等正確答案:

C47.

(單選題)表達式a*（b+c/d）的后綴表達式是（）A.abcd/+*B.abc+*d/C.abc*+d/D./+*abcd正確答案:

A48.

(單選題)鏈式存儲結構中數據元素之間的邏輯關系是由（）表示的。A.線性結構B.非線性結構C.存儲位置D.指針正確答案:

D49.

(單選題)對一棵折半查找的判定樹進行中序遍歷能得到（）A.任意序列B.遞增序列C.遞減序列D.遞增遞減交替序列正確答案:

B50.

(單選題)在有向圖中每個頂點的度等于該頂點的（）A.入度B.出度C.入度與出度之和D.入度與出度之差正確答案:

C51.

(單選題)設一組初始記錄關鍵字的長度為8，則最多經過（）趟插入排序可以得到有序序列。A.6B.7C.8D.9正確答案:

B52.

(單選題)向一個棧頂指針為top的鏈棧中插入一個p所指向的結點時，其操作步驟為（）A.top->next=p；B.p->next=top->next；top->next=p；C.p->next=top；top=p；D.p->next=top；top=top->next；正確答案:

C53.

(單選題)n（n>=2）個權值均不相同的字符構成赫夫曼樹，關于該樹的敘述中，錯誤的是（）A.該樹是一棵完全二叉樹B.樹中一定沒有度為1的結點C.樹中兩個權值最小的結點一定是兄弟結點D.樹中任一非葉子結點的權值一定不小于下一層任一結點的權值正確答案:

A54.

(單選題)數組Q[n]用來表示一個循環隊列，f為隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數小于n，計算隊列中元素個數的公式為（）A.r-fB.（n+f-r）%nC.n+r-fD.（n+r-f）%n正確答案:

D55.

(單選題)假定兩個集合中的元素個數分別為m和n，用線性表實現求兩個集合的交集的運算的時間復雜度為（）A.O（m+n）B.O（m-n）C.O（m*n）D.O（m2）正確答案:

C56.

(單選題)利用棧計算中綴表達式5*（8/2-3）+7時，當掃描到'）'時，OPTR棧中從棧底到棧頂的元素依次是（）A.#*（-B.#*（/-C.#（*/-D.#*/-正確答案:

A57.

(單選題)假設某電文僅有7個字母a，b，c，d，e，f，g組成，各個字母在電文中出現的頻率分別為22，5，3，6，10，17，37，該哈夫曼樹的帶權路徑長度為（）A.244B.246C.264D.276正確答案:

B58.

(單選題)一棵二叉樹的先序序列和中序序列分別如下，后序序列：DCEBGIJHFA中序序列：CDBEAGFIHJ其先序序列為（）A.ABCDEFGHIJB.ACBDEFGHIJC.ACBDEFHGIJD.ABCEDFGHIJ正確答案:

A59.

(單選題)下列關于AOE網的敘述中，不正確的是（）A.關鍵活動不按期完成就會影響整個工程的完成時間B.任何一個關鍵活動提前完成，那么整個工程將會提前完成C.所有的關鍵活動提前完成，那么整個工程將會提前完成D.某些關鍵活動提前完成，那么整個工程將會提前完成正確答案:

B60.

(單選題)廣義表（a，b，（c，d））的表尾是（）A.（c，d）B.（（c，d））C.b，（c，d）D.（b，（c，d））正確答案:

D61.

(單選題)以下算法的時間復雜度為（）voidfun（intn）{inti=1；while（i<=n）i=i*2；}A.O（n）B.O（n2）C.O（nlog2n）D.O（log2n）正確答案:

D62.

(單選題)基數排序的時間復雜度是（）A.O（n）B.O（n2）C.O（nlog2n）D.O（d（n+rd））正確答案:

D63.

(單選題)與單鏈表相比，雙向鏈表的優點之一是（）A.插入、刪除操作更方便B.可以進行隨機訪問C.可以省略表頭指針或表尾指針D.訪問前后相鄰結點更靈活正確答案:

D64.

(單選題)順序存儲結構中數據元素之間的邏輯關系是由（）表示的。A.線性結構B.非線性結構C.存儲位置D.指針正確答案:

C65.

(單選題)對于n階對稱矩陣壓縮存儲時，需要表長為（）的順序表。A.n/2B.n*n/2C.n（n+1）/2D.n（n-1）/2正確答案:

C66.

(單選題)在做退棧運算時，應先判斷棧是否（）A.空B.滿C.上溢D.下溢正確答案:

A67.

(單選題)線性表是（）A.一個有限序列，可以為空B.一個有限序列，不可以為空C.一個無限序列，可以為空D.一個無限序列，不可以為空正確答案:

A68.

(單選題)線性表L=（a1，a2，……an），下列說法正確的是（）A.每個元素都有一個直接前驅和一個直接后繼B.線性表中至少有一個元素C.表中諸元素的排列必須是由小到大或由大到小D.除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼正確答案:

D69.

(單選題)要連通具有n個頂點的有向圖，至少需要（）條邊。A.n-lB.nC.n+lD.2n正確答案:

B70.

(單選題)某算法的語句執行頻度為（3n+nlog2n+n2+8），其時間復雜度表示（）A.O（n）B.O（nlog2n）C.O（n2）D.O（log2n）正確答案:

C71.

(單選題)線性表的順序存儲結構是一種（）A.隨機存取的存儲結構B.順序存取的存儲結構C.索引存取的存儲結構D.散列存取的存儲結構正確答案:

A72.

(單選題)設有一順序棧S，元素a，b，c，d，e，f依次進棧，如果6個元素的出棧順序依次是b，d，c，f，e，a，則棧的容量至少是（）A.2B.3C.5D.6正確答案:

B73.

(單選題)下列程序段的時間復雜度是（）countt=0；for（k=1；k<=n；k*=2）for（j=1；j<=n；j++）count++；A.O（log2n）B.O（n）C.O（nlog2n）D.O（n2）正確答案:

C74.

(單選題)棧在（）中應用。A.遞歸調用B.子程序調用C.表達式求值D.A，B，C正確答案:

D75.

(單選題)設關鍵字序列為（Kl，K2，…，Kn），則用篩選法建初始堆必須從第（）個元素開始進行篩選。A.1B.nC.n/2D.n-1正確答案:

C76.

(單選題)在數據結構中，從邏輯上可以把數據結構分成（）A.線性結構和非線性結構B.內部結構和外部結構C.動態結構和靜態結構D.緊湊結構和非緊湊結構正確答案:

A77.

(單選題)若串S=“software”，其子串的數目是（）A.8B.37C.36D.9正確答案:

B78.

(單選題)和順序棧相比，鏈棧有一個比較明顯的優勢是（）A.通常不會出現棧滿的情況B.通常不會出現棧空的情況C.插入操作更容易實現D.刪除操作更容易實現正確答案:

A79.

(單選題)下述幾種排序方法中，（）是穩定的排序方法。A.希爾排序B.快速排序C.歸并排序D.堆排序正確答案:

C80.

(單選題)鏈表不具有的特點是（）A.插入、刪除不需要移動元素B.所需空間與線性長度成正比C.不必事先估計存儲空間D.可隨機訪問任一元素正確答案:

D81.

(單選題)鏈棧與順序棧相比較，明顯的優點是（）A.插入操作更加方便B.刪除操作更加方便C.通常不會出現棧滿的情況D.通常不會出現棧空的情況正確答案:

C82.

(單選題)帶頭結點的單鏈表h為空的判斷條件是（）A.h==NULLB.h->next==hC.h->next==NULLD.h!=NULL正確答案:

C83.

(單選題)數據結構中評價算法的兩個重要指標是（）A.效率、難度B.可行性、確定性C.正確性、穩定性D.時間復雜度、空間復雜度正確答案:

D84.

(單選題)以下數據結構中，（）是非線性結構。A.樹B.字符串C.隊列D.棧正確答案:

A85.

(單選題)在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在p和q之間插入結點s，則執行（）A.s->next=p->next；p->next=s；B.p->next=s->next；s->next=p；C.q->next=s；s->next=p；D.p->next=s；s->next=q；正確答案:

C86.

(單選題)下列各種排序算法中平均時間復雜度為O（n2）是（）A.快速排序B.堆排序C.歸并排序D.冒泡排序正確答案:

D87.

(單選題)按（）遍歷二叉排序樹得到的序列是一個有序序列。A.先序B.中序C.后序D.層次正確答案:

B88.

(單選題)設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）A.空或只有一個結點B.任一結點無左孩子C.任一結點無右孩子D.任一結點都無左孩子或者任一結點都無右孩子正確答案:

D89.

(單選題)連通分量是（）極大連通子圖。A.圖B.樹C.有向圖D.無向圖正確答案:

D90.

(單選題)具有2017個結點的二叉樹，其深度至少為（）A.9B.10C.11D.12正確答案:

C91.

(單選題)對于一個不帶頭結點的單鏈表head，判定空表的條件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL正確答案:

A92.

(單選題)設赫夫曼樹中有199個結點，則該赫夫曼樹中有（）個葉子結點。A.99B.100C.101D.102正確答案:

B93.

(單選題)設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（）A.O（n）B.O（nlogn）C.O（1）D.O（n2）正確答案:

C94.

(單選題)一個序列中有10000個元素，若只想得到其中前10個最小元素，最好采用（）方法。A.快速排序B.堆排序C.插入排序D.二路歸并排序正確答案:

B95.

(單選題)元素a，b，c，d，e依次進入初始為空的棧中，若元素進棧后可停留，可出棧，直到所有的元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數是（）A.3B.4C.5D.6正確答案:

B96.

(單選題)二維數組之所以有行優先順序和列優先順序兩種存儲方式是因為（）A.數據的元素處在行和列兩個關系中B.數組的元素必須從左到右順序排列C.數組的元素之間存在次序關系D.數組是多維結構，內存是一維結構正確答案:

D97.

(單選題)廣義表（a，（b，c），d，e）的表尾為（）A.（b，c），d，eB.（（b，c），d，e）C.eD.（e）正確答案:

B98.

(單選題)算法分析的目的是（）A.分析算法的易懂性和文檔性B.找出數據結構的合理性C.研究算法中的輸入和輸出的關系D.分析算法的效率以求改進正確答案:

D99.

(單選題)關鍵路徑是AOE網中（）A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑C.最長回路D.最短回路正確答案:

A100.

(單選題)廣義（a，（b，c），d，e）的表頭為（）A.aB.bC.dD.e正確答案:

A101.

(單選題)無向圖的鄰接矩陣（）A.一定是對稱的B.一定是不對稱的C.不一定是對稱的D.不一定是不對稱的正確答案:

A102.

(單選題)下列哪一種圖的鄰接矩陣是對稱矩陣（）A.AOV網B.AOE網C.有向圖D.無向圖正確答案:

D103.

(單選題)已知一棵完全二叉樹的第6層（設根為第1層）有8個葉子結點，則該完全二叉樹的結點個數最多是（）A.39B.52C.111D.119正確答案:

C104.

(單選題)有兩個串p和q，求q在p中首次出現的位置的運算稱為（）A.連接B.模式匹配C.求子串D.求串長正確答案:

B105.

(單選題)已知一個二叉樹的先序序列是ABCDEFG，中序序列是BDCAFEG，則后序序列是（）A.DCBFGEAB.BCDFGEAC.BCDFEGAD.BDCFEGA正確答案:

A106.

(單選題)下面（）方法可以判定一個有向圖是否有環。A.廣度優先遍歷B.拓撲排序C.求最短路徑D.求最小生成樹正確答案:

B107.

(單選題)以下算法中加下劃線的語句的執行次數為（）intm=0，i，j；for（i=1；i<=n；i++）for（j=1；j<=2*i；j++）（）m++；A.nB.n（n+1）C.n+1D.n2正確答案:

B108.

(單選題)一個棧的輸入序列為1，2，3，……，n，若輸出序列的第一個元素是n，則輸出序列的第i（1<=i<=n）個元素是（）A.不確定B.n-i+1C.iD.n-i正確答案:

B109.

(單選題)鏈接存儲的存儲結構所占存儲空間（）A.分兩部分，一部分存放結點值，另一部分存放表示結點關系的指針B.只有一部分，存放結點值C.只有一部分，存儲表示結點間關系的指針D.分兩部分，一部分存放結點值，另一部分存放結點所占單元數正確答案:

A110.

(單選題)單鏈表中，增加一個頭結點的目的是為了（）A.使單鏈表至少有一個結點B.標識表結點中首結點的位置C.方便運算的實現D.說明單鏈表是線性表的鏈式存儲正確答案:

C111.

(單選題)一個順序表所占用的存儲空間大小與（）無關。A.表的長度B.數據元素的存放順序C.數據元素的類型D.數據元素中各字段的類型正確答案:

B112.

(單選題)廣義表L=（a，（b，c）），進行Tail（L）操作后的結果為（）A.cB.b，cC.（b，c）D.（（b，c））正確答案:

D113.

(單選題)堆的形狀是一棵（）A.二叉排序樹B.滿二叉樹C.完全二叉樹D.平衡二叉樹正確答案:

C114.

(單選題)空格串是（①），其長度等于（②），正確選項是（）A.①空串②零B.①由一個或者多個空格組成的字符串②其包含的空格個數C.①空串②未定義D.①由一個或者多個空格組成的字符串②未定義正確答案:

B115.

(單選題)利用二叉鏈表存儲樹，則根結點的右指針是（）A.指向最左孩子B.指向最右孩子C.空D.非空正確答案:

C116.

(單選題)已知一個長度為16的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數最多的是（）A.4B.5C.6D.7正確答案:

B117.

(單選題)在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲（）A.數據的操作方法B.數據元素的類型C.數據元素之間的關系D.數據的存取方法正確答案:

C118.

(單選題)在下列存儲形式中，（）不是樹的存儲形式。A.雙親表示法B.孩子鏈表表示法C.孩子兄弟表示法D.順序存儲表示法正確答案:

D119.

(單選題)下述幾種排序方法中，要求輔助存儲空間最大的是（）A.希爾排序B.快速排序C.歸并排序D.堆排序正確答案:

C120.

(單選題)一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（）A.不確定B.iC.n-i+1D.n-i正確答案:

C121.

(單選題)下列敘述中正確的是（）A.一個算法的空間復雜度大，則其時間復雜度也必定大B.一個算法的空間復雜度大，則其時間復雜度必定小C.一個算法的時間復雜度大，則其空間復雜度必定小D.上述三種說法都不對正確答案:

D122.

(單選題)下列說法不正確的是（）A.圖的遍歷是從給定的頂點出發，每一個頂點僅被訪問一次B.圖的深度優先遍歷不適用于有向圖C.遍歷的基本方法有兩種：深度優先搜索遍歷和廣度優先搜索遍歷D.圖的深度優先遍歷是一個遞歸過程正確答案:

B123.

(單選題)下述關于排序的穩定性描述不正確的是（）A.歸并排序是穩定的B.簡單選擇排序是不穩定的C.堆排序是不穩定的D.快速排序是穩定的正確答案:

D124.

(單選題)分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態為有序的表，則最省時間的是（）算法。A.堆排序B.快速排序C.冒泡排序D.歸并排序正確答案:

C125.

(單選題)若長度為n的線性表采用順序存儲結構，刪除第i個數據元素時需要移動的數據元素個數為（）A.iB.n-iC.nD.n-i+1正確答案:

B126.

(單選題)在下列查找方法中，平均查找長度與結點個數n無關的查找方法是（）A.順序查找B.折半查找C.分塊查找D.散列查找正確答案:

D127.

(單選題)廣義表（a，（b，c），（d，e））的表頭為（）A.aB.（a）C.a，（b，c）D.（a，（b，c））正確答案:

A128.

(單選題)一個鏈表最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則選用（）最節省時間。A.不帶頭結點的單循環鏈表B.雙鏈表C.有尾指針的單循環鏈表D.單鏈表正確答案:

C129.

(單選題)設哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。A.99B.100C.101D.102正確答案:

B130.

(單選題)判斷帶頭結點的單鏈表head為空的條件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL正確答案:

B131.

(單選題)下面關于串的敘述中，（）是不正確的。A.串是字符的有限序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲正確答案:

B132.

(單選題)設主串的長度為m，子串的長度為n，那么簡單的模式匹配算法的時間復雜度為（）A.O（m）B.O（n）C.O（m*n）D.O（m+n）正確答案:

C133.

(單選題)抽象數據類型的三個組成部分分別為（）A.數據對象、數據關系和基本操作B.數據元素、邏輯結構和存儲結構C.數據項、數據元素和數據類型D.?數據元素、數據結構和數據類型正確答案:

A134.

(單選題)下列哪種算法是求單源點最短路徑的算法（）A.PrimB.CruscalC.FloydD.Dijkstra正確答案:

D135.

(單選題)從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（）A.希爾排序B.冒泡排序C.插入排序D.選擇排序正確答案:

C136.

(單選題)下述哪一條是順序存儲結構的優點（）A.存儲密度大B.插入運算方便C.刪除運算方便D.方便地運用于各種邏輯結構的存儲表示正確答案:

A137.

(單選題)若串S="software"，則字符其子串的數目是（），其中空串和S串本身這兩個字符串也算作S的子串。A.8B.36C.37D.16正確答案:

C138.

(單選題)與數據元素本身的形式、內容、相對位置、個數無關的是數據的（）A.存儲結構B.存儲實現C.邏輯結構D.運算實現正確答案:

C139.

(單選題)計算機算法指的是（）A.計算方法B.調度方法C.解決問題的有限運算序列D.排序方法正確答案:

C140.

(單選題)已知一棵二叉樹的先序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果為（）A．CBEFDAB．FEDCBAC．CBEDFAD．不定A.CBEFDAB.FEDCBAC.CBEDFAD.不定正確答案:

A141.

(單選題)數據結構在計算機內存中的表示是指（）A.數據的邏輯結構B.數據元素之間的關系C.數據的存儲結構D.數據關系正確答案:

C142.

(單選題)下面關于哈希（Hash，雜湊）查找的說法正確的是（）A.哈希函數構造的越復雜越好，因為這樣隨機性好，沖突小B.除留余數法是所有哈希函數中最好的C.不存在特別好與壞的哈希函數，要視情況而定D.若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可正確答案:

C143.

(單選題)下面說法不正確的是（）A.廣義表的表頭總是一個廣義表B.廣義表的表尾總是一個廣義表C.廣義表難以用順序結構存儲D.廣義表可以是一個多層次的結構正確答案:

A144.

(單選題)已知一個二叉樹的先序序列是ABCDEFG，后序序列是DCBFGEA，則中序序列是（）A.BDCAEFGB.BCDAFEGC.BDCAFEGD.BCDAFGE正確答案:

C145.

(單選題)具有2012個結點的二叉樹，其深度至少為（）A.9B.10C.11D.12正確答案:

C146.

(單選題)對于單鏈表表示法，以下說法錯誤的是（）A.數據域用于存儲線性表的一個數據元素B.指針域或鏈域用于存儲一個指向本結點的直接后繼結點的指針C.所有數據通過指針的鏈接而組織成單鏈表D.NULL稱為空指針，它不指向任何結點，只起標志作用正確答案:

C147.

(單選題)在帶頭結點的循環鏈表中，將頭指針改設為尾指針（rear）后，其首元結點和尾結點的存儲位置分別是（）A.rear和rear->next->nextB.rear->next和rearC.rear->next->next和rearD.rear和rear->next正確答案:

C148.

(單選題)關于線性表的下列說法正確的是（）A.每個元素都有一個直接前驅和一個直接后繼B.線性表中至少有一個元素C.表中諸元素的排列順序必須是由小到大或由大到小D.除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前驅和直接后繼正確答案:

D149.

(單選題)鏈式棧結點為（data，next），top指向棧頂，若想刪除棧頂結點，并將刪除結點的值保存到x中，則應執行的操作（）A.x=top->data；top=top->next；B.top=top->next；x=top->data；C.x=top；top=top->next；D.x=top->data；正確答案:

A150.

(單選題)棧操作數據的原則是（）A.先進先出B.后進先出C.后進后出D.不分順序正確答案:

B151.

(單選題)若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節省運算時間。A.單鏈表B.僅有頭指針的單循環鏈表C.雙向鏈表D.僅有尾指針的單循環鏈表正確答案:

D152.

(單選題)設有二維數組A[0..9，0..19]，其每個元素占兩個字節，第一個元素的存儲地址為100，若按行優先順序存儲，則元素A[6，6]存儲地址為（）A.232B.241C.352D.332正確答案:

C153.

(單選題)下面給出的四種排序方法中，排序過程中的比較次數與初始序列無關的是（）A.簡單選擇排序法B.插入排序法C.快速排序法D.堆排序法正確答案:

A154.

(單選題)棧在（）中有所應用。A.遞歸調用B.函數調用C.表達式求值D.前三個選項都有正確答案:

D155.

(單選題)（）不是棧的基本操作。A.判斷棧是否為空B.將棧置為空棧C.刪除棧頂元素D.刪除棧底元素正確答案:

D156.

(單選題)若一棵二叉樹有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（）A.9B.11C.15D.不確定正確答案:

B157.

(單選題)設棧S和隊列Q的初始狀態為空，元素1，2，3，4，5和6依次進入棧S，一個元素出棧后立即進入Q，若6個元素的出隊序列是2，4，3，6，5，1，則棧S的容量至少應用是（）A.2B.3C.4D.6正確答案:

B158.

(單選題)設棧S元素和隊列Q的初始狀態均為空，元素abcde依次通過棧S，若每個元素出棧后立即進入隊列Q，且5個元素的出隊順序是bdcae，則棧S的容量至少是（）A.6B.4C.3D.2正確答案:

C159.

(單選題)下面關于串的的敘述中，哪一個是不正確的（）A.串是字符的有限序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲正確答案:

B160.

(單選題)下列關于無向連通圖特性的敘述中，正確的是（）I.所有頂點的度數之和是偶數II.邊數大于頂點個數減1III.至少有一個頂點的度為1A.只有IB.只有IIC.I和IID.I和III正確答案:

A161.

(單選題)對于一個帶頭結點的單循環鏈表head，判定空表的條件是（）A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL正確答案:

C162.

(單選題)將一棵有200個結點的完全二叉樹從根這一層開始，每一層上從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的右孩子編號為（）A.97B.98C.99D.100正確答案:

C163.

(單選題)從邏輯上可以把數據結構分為（）兩大類。A.動態結構、靜態結構B.線性結構、非線性結構C.順序結構、鏈式結構D.初等結構、構造型結構正確答案:

B164.

(單選題)若森林F有15條邊，25個結點，則F包含的樹的個數是（）A.8B.9C.10D.11正確答案:

C165.

(單選題)線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）A.必須是連續的B.部分地址必須是連續的C.一定是不連續的D.連續或不連續都可以正確答案:

D166.

(單選題)若數據序列{11，12，13，7，8，9，23，4，5}是采用下列排序方法之一得到的第二趟排序后的結果，則該排序算法只能是（）A.冒泡排序B.插入排序C.選擇排序D.歸并排序正確答案:

B167.

(單選題)廣義表（（a，b），c，（d，e））的表頭為（）A.aB.（a，b）C.a，bD.（（a，b），c）正確答案:

B168.

(單選題)基數排序是（）A.利用多邏輯關鍵字排序的思想對單邏輯關鍵字進行排序B.利用多邏輯關鍵字排序的思想對多邏輯關鍵字進行排序C.利用單邏輯關鍵字排序的思想對多邏輯關鍵字進行排序D.利用單邏輯關鍵字排序的思想對單邏輯關鍵字進行排序正確答案:

A169.

(單選題)設赫夫曼編碼的長度不超過4，若已對兩個字符編碼為1和01，則還最多可對（）個字符編碼。A.2B.3C.4D.5正確答案:

C170.

(單選題)順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）A.O（n）B.O（n2）C.O（n1/2）D.O（1og2n）正確答案:

A171.

(單選題)一個廣義表為（a，（a，b），d，e，（（i，j），k）），則該廣義表的長度為（）A.不確定B.8C.5D.6正確答案:

C172.

(單選題)設計一個判別表達式中左、右括號是否配對出現的算法，采用（）數據結構最佳。A.線性表的順序存儲結構B.隊列C.線性表的鏈式存儲結構D.棧正確答案:

D173.

(單選題)有向圖的鄰接矩陣（）A.一定是對稱的B.一定是不對稱的C.有可能是對稱的D.以上答案都不對正確答案:

C174.

(單選題)在下述結論中，正確的是（）①只有一個結點的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④深度為K的完全二叉樹的結點個數小于或等于深度相同的滿二叉樹。A.①②③B.②③④C.②④D.①④正確答案:

D175.

(單選題)以下數據結構中，（）是非線性數據結構。A.字符串B.隊列C.樹D.棧正確答案:

C176.

(單選題)設哈希表長為14，哈希函數是H（key）=key%11，表中已有數據的關鍵字為15，38，61，84共四個，現要將關鍵字為49的結點加到表中，用二次探測再散列法解決沖突，則放入的位置是（）A.8B.3C.5D.9正確答案:

D177.

(單選題)線性表L在（）情況下適用于鏈式結構實現。A.需經常修改L中的結點值B.需不斷對L進行刪除插入C.L中含有大量的結點D.L中結點結構復雜正確答案:

B178.

(單選題)用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的（）遍歷。A.中序遍歷B.先序遍歷C.后序遍歷D.層序遍歷正確答案:

B179.

(單選題)當棧中元素為n個，做進棧運算時發生溢出，則說明棧的最大容量為（）A.nB.n-1C.n+1D.n/2正確答案:

A180.

(單選題)某內排序方法的穩定性是指（）A.該排序算法不允許有相同的關鍵字記錄B.該排序算法允許有相同的關鍵字記錄C.平均時間為0（nlogn）的排序方法D.以上都不對正確答案:

D181.

(單選題)線性表是具有n個（）的有限序列。A.表元素B.字符C.數據元素D.數據項正確答案:

C182.

(單選題)鏈式棧結點為（data，link），top指向棧頂，若想摘除棧頂結點，并將刪除的結點的值保存到x中，則應執行操作（）A.x=top->data；top=top->link；B.top=top->link；x=top->link；C.x=top；top=top->link；D.x=top->link；正確答案:

A二.多選題（共23題）1.

(多選題)以下哪些是圖的分類A.無向圖B.有向圖C.加權圖D.無權圖正確答案:

ABCD2.

(多選題)從邏輯上可以把數據結構分為（）A.動態結構B.線性結構C.鏈式結構D.非線性結構正確答案:

BD3.

(多選題)以下關于指針變量的敘述中，正確的有（）A.指針變量可賦值為0B.指針變量中存放的是地址值C.指針可以進行加、減等算術運算D.指針變量不占用存儲空間正確答案:

ABC4.

(多選題)線索二叉樹的作用包括（）A.方便遍歷B.節省存儲空間C.加快查找速度D.便于插入和刪除操作正確答案:

AC5.

(多選題)下面說法正確的是（）A.算法原地工作的含義是指不需要任何輔助空間B.在相同的規模n下，時間復雜度為O（n）的算法在執行時間上一定比時間復雜度為O（nlogn）的算法快C.最壞時間復雜度是指算法在最壞情況下執行時間的上界D.可讀性好的算法有助于人們對算法的理解和交流正確答案:

CD6.

(多選題)對于哈夫曼編碼，以下說法正確的是（）A.哈夫曼編碼是一種不等長編碼B.哈夫曼編碼是前綴編碼C.出現頻率高的字符編碼短D.可以通過構建哈夫曼樹來生成編碼正確答案:

ABCD7.

(多選題)線索二叉樹的線索化過程主要包括（）A.先序線索化B.中序線索化C.后序線索化D.層次線索化正確答案:

ABC8.

(多選題)關于二叉樹的說法，正確的是（）A.二叉樹可以為空樹。B.二叉樹中結點的度都為2C.二叉樹中結點的度可以為0，1，2D.二叉樹的高度是指二叉樹中結點的個數正確答案:

AC9.

(多選題)二叉樹的性質包括（）A.第i層最多有2^(i-1)個結點（i≥1）B.深度為k的二叉樹最多有2^k-1個結點（k≥1）C.對于任何一棵二叉樹，如果其葉結點數為n?，度為2的結點數為n?，則n?=n?+1D.具有n個結點的完全二叉樹的深度為?log?(n+1)?正確答案:

ABCD10.

(多選題)數據之間的運算包括（）A.插入B.刪除C.查找D.更新和排序正確答案:

ABCD11.

(多選題)如何將字符串轉換為數值A.先用數值的valueOf函數將字符串轉換為數值類對象，再利用該對象的intValue或doubleValue等函數將數值類對象轉換為數值B.利用數值類的parseInt，parseDouble等函數將字符串直接轉換為數值C.利用數值類的靜態函數valueOf將字符串轉換為數值D.利用數值類的靜態函數intValue將字符串轉換為數值正確答案:

AB12.

(多選題)以下有關結構體數組的說法中，正確的有（）A.結構體數組中的每個元素都是結構體類型B.結構體數組也可初始化C.指針可以指向結構體變量,但不可以指向結構體數組D.結構體數組在內存中是連續存放的正確答案:

ABD13.

(多選題)二叉樹的遍歷方式有（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷正確答案:

ABCD14.

(多選題)算法的特征包括（）A.無窮性B.確定性C.有效性D.有零個或多個輸入正確答案:

BCD15.

(多選題)（）屬于特殊矩陣A.對角矩陣B.上三角矩陣C.下三角矩陣D.稀疏矩陣正確答案:

ABC16.

(多選題)算法的基本特征有（）A.有窮性B.確定性C.可行性D.輸入和輸出正確答案:

ABCD17.

(多選題)算法的時間復雜度取決于（）A.問題的規模B.待處理數據的初始狀態C.內存的大小D.操作系統的選擇正確答案:

AB18.

(多選題)以下哪些屬于索引順序文件可能出現的問題A.索引需要占用額外的存儲空間B.數據更新時維護索引的開銷較大C.索引結構若不合理可能導致查找效率降低D.完全杜絕了數據丟失風險正確答案:

ABC19.

(多選題)下面不可以聲明字符串類型的是()A.boolB.floatC.stringD.int正確答案:

ABD20.

(多選題)非空二叉樹的基本組成單元包括（）A.根結點B.左子樹C.右子樹D.空指針正確答案:

ABC21.

(多選題)樹的存儲結構可以有（）A.雙親表示法B.孩子表示法C.孩子兄弟表示法D.順序存儲結構正確答案:

ABC22.

(多選題)以下數據結構中，（）是線性結構。A.樹B.字符串C.線性表D.棧正確答案:

BCD23.

(多選題)數據元素也稱為（）A.元素B.結點C.頂點D.記錄正確答案:

ABCD三.填空題（共15題）1.

(填空題)設有一個10階的對稱矩陣A[10][10]，采用壓縮存儲方式按行將矩陣中下三角部分的元素存入一維數組B[]中，A[0][0]存入B[0]中，則A[8][5]在B[]中的下標為（）正確答案:

(1)412.

(填空題)數據結構從邏輯上劃分為四種基本類型：線性結構、樹形結構、圖狀結構和（）正確答案:

(1)集合3.

(填空題)一個二維數組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數組元素用相鄰的6個字節存儲，存儲器按字節編址。這個數組的體積是（）個字節。正確答案:

(1)2884.

(填空題)平衡二叉樹上所有結點的平衡因子只可能是0，1和（）正確答案:

(1)-15.

(填空題)串‘science’的非空子串有（）個。正確答案:

(1)266.

(填空題)設某棵完全二叉樹中有100個結點，則該二叉樹中有（）個葉子結點。正確答案:

(1)507.

(填空題)已知一個長度為13的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數最多的是（）正確答案:

(1)48.

(填空題)設線性表中有n個數據元素，則在在鏈式存儲結構上實現順序查找的平均時間復雜度為（）正確答案:

(1)O（n）9.

(填空題)設數組a[0..10，1..8]的基地址為2000，每個元素占4個字節，若以行序為主序順序存儲，則元素a[4，6]的存儲地址為（）正確答案:

(1)214810.

(填空題)設有二維數組A[0..9，0..19]，其每個元素占兩個字節，第一個元素的存儲地址為100，若按列優先順序存儲，則元素A[6，6]存儲地址為（）正確答案:

(1)23211.

(填空題