數(shù)據(jù)結(jié)構(gòu)--第1-4章選擇題(有-答案)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第1章 緒論5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A動(dòng)態(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)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（ ）。A存儲(chǔ)結(jié)構(gòu) B存儲(chǔ)實(shí)現(xiàn)C邏輯結(jié)構(gòu) D運(yùn)算實(shí)現(xiàn)（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ）。 A數(shù)據(jù)具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等（4）以下說(shuō)法正確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

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

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

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

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

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

7、況下，需要比較n(n-1)/2次，時(shí)間復(fù)雜性為O(n2)。但平均卻是O(n)。如果n個(gè)元素事先已存在單鏈表中，現(xiàn)在對(duì)其排序，則可采用類似“冒泡排序”或“簡(jiǎn)單選擇排序”那樣的算法，時(shí)間復(fù)雜性為O(n2)。(12) 以下說(shuō)法錯(cuò)誤的是（ ）。A求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低B順序存儲(chǔ)的線性表可以隨機(jī)存取C由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)(13) 在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為（ ）。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) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。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指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（ ）。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;說(shuō)明：對(duì)于（13）、（14）、（15）這類題，在草稿紙上畫(huà)一畫(huà)鏈表就明白了。要注意的是，按語(yǔ)句次序，一旦修改了某根指針，就要?jiǎng)h掉原來(lái)的指針。第3章 棧和隊(duì)列1選擇題（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)（ ）的情況。A5,4,3,2,1 B2,1,5,4,3 C4,3,1,2,5 D2,3,5,4,1

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

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

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

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

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

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

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

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

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

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

21、+180。（8）設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。A13 B32 C33 D40說(shuō)明：這道題沒(méi)有說(shuō)明按上三角還是下三角存儲(chǔ)。假設(shè)按下三角存儲(chǔ)，則a85前面有7行，第1行只有一個(gè)元素，第2行有2個(gè)元素，依次類推，前7行共有1+2+7=28個(gè)元素，a85所在的第8行前面有4個(gè)元素，于是前面共有28+4=32個(gè)元素，從地址1開(kāi)始存儲(chǔ)，每個(gè)元素一個(gè)字節(jié)，因此存儲(chǔ)地址為1+32=33。若按上三角存儲(chǔ)，則存儲(chǔ)的是a85對(duì)稱的元素a58，其存儲(chǔ)地址為38。（9）若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵?/p>

22、下三角形的元素(包括主對(duì)角線上所有元素)依次存放于一維數(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說(shuō)明：此題計(jì)算的是aij在數(shù)組B中的下標(biāo)而不是存儲(chǔ)地址，只要計(jì)算從數(shù)組第1個(gè)元素開(kāi)始，到aij共有幾個(gè)元素。aij前面共有i-1行，第1行在B中只存儲(chǔ)一個(gè)元素，第2行存儲(chǔ)2個(gè)元素，依次類推，前i-1行共存儲(chǔ)了1+2+(i-1)=i*(i-1)/2個(gè)元素，aij位于第i行第j列，這一行到aij為止存儲(chǔ)了j個(gè)元素，因此B中到aij為止共有i*(i-1)/2+j個(gè)元素。（10）二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,8，列下標(biāo)j=1,2,10。若A按行先存儲(chǔ)，元素A8,5的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。AA8,5 BA3,10 CA5,8 DA0,9說(shuō)明：因?yàn)槊總€(gè)元素占用的單元數(shù)都相同，所以只要計(jì)算所存儲(chǔ)的元素個(gè)數(shù)即可。當(dāng)按行優(yōu)先存儲(chǔ)時(shí)，A8,5前面有8行（行號(hào)從0數(shù)起），每行10個(gè)元素，所在的第8行前面有4個(gè)元素，因此存儲(chǔ)到A8,5