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

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

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

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

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

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

7、況下，需要比較n(n-1)/2次，時間復雜性為O(n2)。但平均卻是O(n)。如果n個元素事先已存在單鏈表中，現在對其排序，則可采用類似“冒泡排序”或“簡單選擇排序”那樣的算法，時間復雜性為O(n2)。(12) 以下說法錯誤的是（ ）。A求表長、定位這兩種運算在采用順序存儲結構時實現的效率不比采用鏈式存儲結構時實現的效率低B順序存儲的線性表可以隨機存取C由于順序存儲要求連續的存儲區域，所以在存儲管理上不夠靈活D線性表的鏈式存儲結構優于順序存儲結構(13) 在單鏈表中，要將s所指結點插入到p所指結點之后，其語句應為（ ）。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) 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（ ）。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) 在雙向循環鏈表中，在p指針所指的結點后插入q所指向的新結點，其修改指針的操作是（ ）。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依次進棧，則出棧次序不可能出現（ ）的情況。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）數組用來表示一個循環隊列，為當前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數小于，計算隊列中元素個數的公式為（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n說明：當用數組表示循環隊列時，f、r是數組元素的下腳標。由于是循環的，所以有可能r<f。若r>f，則r-f即為隊列的元素個數；

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

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

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

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

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

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

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

19、ab”的nextval為（ ）。A B C D （5）串的長度是指（ ）。A串中所含不同字母的個數 B串中所含字符的個數C串中所含不同字符的個數 D串中所含非空格字符的個數（6）假設以行序為主序存儲二維數組A=array1.100,1.100，設每個數據元素占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是數組列數，L是每個元素占用的單元數。注意按此公式計算時，i、j必須是從1數起的。（7）設有數組Ai,j，數組的每個元素長度為3字節，i的值為1到8，j的值為1到10，數組從內存首地址BA開始順序存放，當用以列為主存放時，元素A5,8的存儲首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+225說明：按列序存儲，A5,8前面有7列，每列8個元素，所在的第8列上方有4個元素（因為在第5行），因此A58前面共有7*8+4=60個元素，每個元素3個字節，故存儲地址為BA+60*3=BA

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

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