1、精選優(yōu)質(zhì)文檔-傾情為你奉上第1章 緒論5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（ ）。A存儲結(jié)構(gòu) B存儲實現(xiàn)C邏輯結(jié)構(gòu) D運算實現(xiàn)（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ）。 A數(shù)據(jù)具有同一特點B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等（4）以下說法正確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項是數(shù)據(jù)的基本單位

2、C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)說明：注意幾個概念：數(shù)據(jù)項是數(shù)據(jù)的最小單位而不是基本單位，數(shù)據(jù)元素才是數(shù)據(jù)的基本單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合而不是數(shù)據(jù)項的集合。（5）以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（ ）。A順序隊列 B. 鏈表 C. 有序表 D. 鏈棧說明：數(shù)據(jù)的存儲結(jié)構(gòu)只有數(shù)組（或稱為順序存儲）和鏈表兩種。順序隊列是用數(shù)組存儲的隊列，鏈表和鏈棧都是用鏈表。（6）以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊 D棧第2章 線性表1選擇題（1）一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是

3、（ ）。A110 B108 C100 D120說明：計算公式：A+(i-1)*L，A為起始地址，i是元素序號，L是元素長度。（2）在n個結(jié)點的順序表中，算法的時間復雜度是O(1)的操作是（ ）。A訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in） B在第i個結(jié)點后插入一個新結(jié)點（1in）C刪除第i個結(jié)點（1in）D將n個結(jié)點從小到大排序（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數(shù)為（ ）。A8 B63.5 C63 D7說明：n個元素的順序表共有n+1個插入位置（包括一頭一尾），在第i個位置插入元素需要移動n-i+1個元素，因此平均為(1+

4、2+n)/(n+1)=n/2。（4）鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（ ）。A分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B只有一部分，存放結(jié)點值C只有一部分，存儲表示結(jié)點間關(guān)系的指針D分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（5）線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以（6）線性表在（ ）情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。A需經(jīng)常修改中的結(jié)點值 需不斷對進行刪除插入 C中含有大量的結(jié)點 中結(jié)點結(jié)構(gòu)復雜（7）單鏈表的存儲密度（ ）。A大于1 B等于1 C小于1 D不能確定

5、說明：存儲密度的定義在課本p41表2.1的末尾，它是小于或等于1的一個實數(shù)。（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ ）。An B2n-1 C2n Dn-1說明：合并兩個有序表的算法見課本算法2.15和算法2.16。當兩個表中的一個完全排在另一個表的前面時，比較的次數(shù)最少，此時只是后面表中的第一個元素與前面表中的元素逐一比較一次，然后就直接將兩個表連接起來。（9）在一個長度為n的順序表中，在第i個元素（1in+1）之前插入一個新元素時須向后移動（ ）個元素。An-i Bn-i+1 Cn-i-1 Di(10) 線性表L=(a1，a2,an)，下列說法正確的是（ ）。

6、A每個元素都有一個直接前驅(qū)和一個直接后繼B線性表中至少有一個元素C表中諸元素的排列必須是由小到大或由大到小D除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。(11) 若指定有n個元素的向量，則建立一個有序單鏈表的時間復雜性的量級是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)說明：這道題其實有些問題。若題目的意思是，有n個元素，事先我們不知道元素的大小次序，我們依此將這些元素一個個插入單鏈表中并且使得單鏈表有序。注意這是單鏈表，第8章的一些快速排序算法在這里用不上。因為是單鏈表，每次插入一個元素，只能從表頭開始逐一比較，尋找插入的位置。在最壞的情

7、況下，需要比較n(n-1)/2次，時間復雜性為O(n2)。但平均卻是O(n)。如果n個元素事先已存在單鏈表中，現(xiàn)在對其排序，則可采用類似“冒泡排序”或“簡單選擇排序”那樣的算法，時間復雜性為O(n2)。(12) 以下說法錯誤的是（ ）。A求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈式存儲結(jié)構(gòu)時實現(xiàn)的效率低B順序存儲的線性表可以隨機存取C由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)(13) 在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應為（ ）。As->next=p+1; p->next=s;B(*p).n

8、ext=s; (*s).next=(*p).next;Cs->next=p->next; p->next=s->next;Ds->next=p->next; p->next=s; (14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ ）。Ap->next->prior=p->prior; p->prior->next=p->next;Bp->next=p->next->next; p->next->prior=p;Cp->prior->next=p; p->p

9、rior=p->prior->prior;Dp->prior=p->next->next; p->next=p->prior->prior;(15) 在雙向循環(huán)鏈表中，在p指針所指的結(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是（ ）。Ap->next=q; q->prior=p; p->next->prior=q; q->next=q;Bp->next=q; p->next->prior=q; q->prior=p; q->next=p->next;Cq->prior=p;

10、 q->next=p->next; p->next->prior=q; p->next=q;Dq->prior=p; q->next=p->next; p->next=q; p->next->prior=q;說明：對于（13）、（14）、（15）這類題，在草稿紙上畫一畫鏈表就明白了。要注意的是，按語句次序，一旦修改了某根指針，就要刪掉原來的指針。第3章 棧和隊列1選擇題（1）若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現(xiàn)（ ）的情況。A5,4,3,2,1 B2,1,5,4,3 C4,3,1,2,5 D2,3,5,4,1

11、（2）若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為（ ）。 Ai Bn-i Cn-i+1 D不確定說明：p1=n表明全部元素入棧之后才出棧，因此出棧序列只能是n,n-1,2,1,第i個出棧的必為n-i+1。（3）數(shù)組用來表示一個循環(huán)隊列，為當前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素個數(shù)的公式為（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n說明：當用數(shù)組表示循環(huán)隊列時，f、r是數(shù)組元素的下腳標。由于是循環(huán)的，所以有可能r<f。若r>f，則r-f即為隊列的元素個數(shù)；

12、當r<f時，必須按(n+r-f)%n計算。注意當r>f時，(n+r-f)%n=(r-f)%n=r-f。（4）鏈式棧結(jié)點為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x中,則應執(zhí)行操作（ ）。Ax=top->data;top=top->link； Btop=top->link;x=top->link； Cx=top;top=top->link； Dx=top->link；說明：鏈棧是一個單鏈表，表頭為棧頂，見課本p47圖3.3。（5）設(shè)有一個遞歸算法如下     

13、0;  int fact(int n)   /n大于等于0             if(n<=0) return 1;             else return n*fact(n-1);        則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。 A n+1&

14、#160;      B n-1      C n      D n+2說明：可觀察函數(shù)的參數(shù)，它將依次為n,n-1,1,0，共n+1個。（6）棧在 （ ）中有所應用。A遞歸調(diào)用 B函數(shù)調(diào)用 C表達式求值 D前三個選項都有必須指出，遞歸調(diào)用使用的是系統(tǒng)堆棧，不是應用程序設(shè)計的棧。（7）為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯

15、結(jié)構(gòu)應該是（ ）。A隊列 B棧 C 線性表 D有序表（8）設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應該是（）。A2 B3 C4 D 6說明：由于一個元素出棧后即進入隊列，而隊列是“先進先出”，所以出隊的序列就是出棧的序列。（9）在一個具有n個單元的順序棧中，假設(shè)以地址高端作為棧底，以top作為棧頂指針，則當作進棧處理時，top的變化為（）。 Atop不變 Btop=0 Ctop- Dtop+（10）設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）

16、數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B隊列 C. 線性表的鏈式存儲結(jié)構(gòu) D. 棧（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改說明：題目的意思是，用單鏈表實現(xiàn)隊列，頭指針指向第一個元素結(jié)點（首元結(jié)點），不使用頭結(jié)點。不然的話，象課本p65圖3.13的情形，刪除操作只可能修改頭結(jié)點中的指針，頭指針永遠不變。由于隊列是“先進先出”的，所以刪除的一定是隊列第一個元素，當隊列元素只剩一個時，刪除后需同時修改頭、尾指針。（12）循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（）。A. rear=rear+

17、1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 說明：數(shù)組長度是m+1而不是m。（13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front說明：題目指的是課本p63圖3.11所示的循環(huán)隊列。（14）棧和隊列的共同點是（）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點說明：棧的“端點”是棧頂，隊列的

18、“端點”是隊頭。（15）一個遞歸算法必須包括（）。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分說明：“迭代”是循環(huán)的另一種說法。第4章 串、數(shù)組和廣義表1選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A可以順序存儲 B數(shù)據(jù)元素是一個字符 C可以鏈式存儲 D數(shù)據(jù)元素可以是多個字符 （2）下面關(guān)于串的的敘述中，（ ）是不正確的？ A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈式存儲（3）串“ababaaababaa”的next數(shù)組為（ ）。A9 B2 C6 D45（4）串“ababaab

19、ab”的nextval為（ ）。A B C D （5）串的長度是指（ ）。A串中所含不同字母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù)（6）假設(shè)以行序為主序存儲二維數(shù)組A=array1.100,1.100，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC5,5=（ ）。A808 B818 C1010 D1020說明：按行序存儲時，A5,5位于第5行第5列，之前有4行，每行100個元素，所在第5行前面有4個元素，因此在A5,5前面一共有4*100+4=404個元素。從基地址10開始存放，每個元素兩個單元，所以A5,5的存儲地址是10+404*2=818。

20、一般的計算公式是：loc(i,j)=BA+(i-1)*n+(j-1)*L，其中BA是基地址，n是數(shù)組列數(shù)，L是每個元素占用的單元數(shù)。注意按此公式計算時，i、j必須是從1數(shù)起的。（7）設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當用以列為主存放時，元素A5,8的存儲首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+225說明：按列序存儲，A5,8前面有7列，每列8個元素，所在的第8列上方有4個元素（因為在第5行），因此A58前面共有7*8+4=60個元素，每個元素3個字節(jié)，故存儲地址為BA+60*3=BA

21、+180。（8）設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。A13 B32 C33 D40說明：這道題沒有說明按上三角還是下三角存儲。假設(shè)按下三角存儲，則a85前面有7行，第1行只有一個元素，第2行有2個元素，依次類推，前7行共有1+2+7=28個元素，a85所在的第8行前面有4個元素，于是前面共有28+4=32個元素，從地址1開始存儲，每個元素一個字節(jié)，因此存儲地址為1+32=33。若按上三角存儲，則存儲的是a85對稱的元素a58，其存儲地址為38。（9）若對n階對稱矩陣A以行序為主序方式將其

22、下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aij（i<j）的位置k的關(guān)系為（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i說明：此題計算的是aij在數(shù)組B中的下標而不是存儲地址，只要計算從數(shù)組第1個元素開始，到aij共有幾個元素。aij前面共有i-1行，第1行在B中只存儲一個元素，第2行存儲2個元素，依次類推，前i-1行共存儲了1+2+(i-1)=i*(i-1)/2個元素，aij位于第i行第j列，這一行到aij為止存儲了j個元素，因此B中到aij為止共有i*(i-1)/2+j個元素。（10）二維數(shù)組A的每個元素是由10個字符組成的串，其行下標i=0,1,8，列下標j=1,2,10。若A按行先存儲，元素A8,5的起始地址與當A按列先存儲時的元素（ ）的起始地址相同。設(shè)每個字符占一個字節(jié)。AA8,5 BA3,10 CA5,8 DA0,9說明：因為每個元素占用的單元數(shù)都相同，所以只要計算所存儲的元素個數(shù)即可。當按行優(yōu)先存儲時，A8,5前面有8行（行號從0數(shù)起），每行10個元素，所在的第8行前面有4個元素，因此存儲到A8,5