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

數(shù)據(jù)結構第1-4章選擇題(有答案)數(shù)據(jù)結構第1-4章選擇題(有答案)數(shù)據(jù)結構第1-4章選擇題(有答案)數(shù)據(jù)結構第1-4章選擇題(有答案)編制僅供參考審核批準生效日期地址：電話：傳真:郵編:第1章緒論5．選擇題（1）在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（）。A．動態(tài)結構和靜態(tài)結構B．緊湊結構和非緊湊結構C．線性結構和非線性結構D．內部結構和外部結構（2）與數(shù)據(jù)元素本身的形式、內容、相對位置、個數(shù)無關的是數(shù)據(jù)的（）。A．存儲結構B．存儲實現(xiàn)C．邏輯結構D．運算實現(xiàn)（3）通常要求同一邏輯結構中的所有數(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ù)的基本單位C．數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)項的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構說明：注意幾個概念：數(shù)據(jù)項是數(shù)據(jù)的最小單位而不是基本單位，數(shù)據(jù)元素才是數(shù)據(jù)的基本單位，數(shù)據(jù)結構是帶有結構的數(shù)據(jù)元素的集合而不是數(shù)據(jù)項的集合。（5）以下與數(shù)據(jù)的存儲結構無關的術語是（）。A．順序隊列B.鏈表C.有序表D.鏈棧說明：數(shù)據(jù)的存儲結構只有數(shù)組（或稱為順序存儲）和鏈表兩種。順序隊列是用數(shù)組存儲的隊列，鏈表和鏈棧都是用鏈表。（6）以下數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構A．樹B．字符串C．隊D．棧

第2章線性表1．選擇題（1）一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）。A．110B．108C．100說明：計算公式：A+(i-1)*L，A為起始地址，i是元素序號，L是元素長度。（2）在n個結點的順序表中，算法的時間復雜度是O(1)的操作是（）。A．訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）B．在第i個結點后插入一個新結點（1≤i≤n）C．刪除第i個結點（1≤i≤n）D．將n個結點從小到大排序（3）向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數(shù)為（）。A．8B．63.5C．63說明：n個元素的順序表共有n+1個插入位置（包括一頭一尾），在第i個位置插入元素需要移動n-i+1個元素，因此平均為(1+2+…+n)/(n+1)=n/2。（4）鏈接存儲的存儲結構所占存儲空間（）。A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B．只有一部分，存放結點值C．只有一部分，存儲表示結點間關系的指針D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)（5）線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以（6）線性表Ｌ在（）情況下適用于使用鏈式結構實現(xiàn)。A．需經常修改Ｌ中的結點值Ｂ．需不斷對Ｌ進行刪除插入C．Ｌ中含有大量的結點Ｄ．Ｌ中結點結構復雜（7）單鏈表的存儲密度（）。A．大于1B．等于1C．小于1說明：存儲密度的定義在課本p41表的末尾，它是小于或等于1的一個實數(shù)。（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（）。A．nB．2n-1C．2nD說明：合并兩個有序表的算法見課本算法和算法。當兩個表中的一個完全排在另一個表的前面時，比較的次數(shù)最少，此時只是后面表中的第一個元素與前面表中的元素逐一比較一次，然后就直接將兩個表連接起來。（9）在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（）個元素。A．n-iB．n-i+1C．n-i-1(10)線性表L=(a1，a2,……an)，下列說法正確的是（）。A．每個元素都有一個直接前驅和一個直接后繼B．線性表中至少有一個元素C．表中諸元素的排列必須是由小到大或由大到小D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼。(11)若指定有n個元素的向量，則建立一個有序單鏈表的時間復雜性的量級是（）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)說明：這道題其實有些問題。若題目的意思是，有n個元素，事先我們不知道元素的大小次序，我們依此將這些元素一個個插入單鏈表中并且使得單鏈表有序。注意這是單鏈表，第8章的一些快速排序算法在這里用不上。因為是單鏈表，每次插入一個元素，只能從表頭開始逐一比較，尋找插入的位置。在最壞的情況下，需要比較n(n-1)/2次，時間復雜性為O(n2)。但平均卻是O(n)。如果n個元素事先已存在單鏈表中，現(xiàn)在對其排序，則可采用類似“冒泡排序”或“簡單選擇排序”那樣的算法，時間復雜性為O(n2)。(12)以下說法錯誤的是（）。A．求表長、定位這兩種運算在采用順序存儲結構時實現(xiàn)的效率不比采用鏈式存儲結構時實現(xiàn)的效率低B．順序存儲的線性表可以隨機存取C．由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活D．線性表的鏈式存儲結構優(yōu)于順序存儲結構(13)在單鏈表中，要將s所指結點插入到p所指結點之后，其語句應為（）。A．s->next=p+1;p->next=s;B．(*p).next=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;(14)在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;(15)在雙向循環(huán)鏈表中，在p指針所指的結點后插入q所指向的新結點，其修改指針的操作是（）。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->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)（）的情況。A．5,4,3,2,1B．2,1,5,4,3C．4,3,1,2,5D．2,3,5,4,1（2）若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）。A．iB．n-iC．n-i+1D．不確定說明：p1=n表明全部元素入棧之后才出棧，因此出棧序列只能是n,n-1,…,2,1,第i個出棧的必為n-i+1。（3）數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素個數(shù)的公式為（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n說明：當用數(shù)組表示循環(huán)隊列時，f、r是數(shù)組元素的下腳標。由于是循環(huán)的，所以有可能r<f。若r>f，則r-f即為隊列的元素個數(shù)；當r<f時，必須按(n+r-f)%n計算。注意當r>f時，(n+r-f)%n=(r-f)%n=r-f。（4）鏈式棧結點為：(data,link)，top指向棧頂.若想摘除棧頂結點，并將刪除結點的值保存到x中,則應執(zhí)行操作（）。A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；說明：鏈棧是一個單鏈表，表頭為棧頂，見課本p47圖。（5）設有一個遞歸算法如下

intfact(intn){

3C0C（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改說明：題目的意思是，用單鏈表實現(xiàn)隊列，頭指針指向第一個元素結點（首元結點），不使用頭結點。不然的話，象課本p65圖的情形，刪除操作只可能修改頭結點中的指針，頭指針永遠不變。由于隊列是“先進先出”的，所以刪除的一定是隊列第一個元素，當隊列元素只剩一個時，刪除后需同時修改頭、尾指針。（12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)說明：數(shù)組長度是m+1而不是m。（13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front說明：題目指的是課本p63圖所示的循環(huán)隊列。（14）棧和隊列的共同點是（）。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點說明：棧的“端點”是棧頂，隊列的“端點”是隊頭。（15）一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分說明：“迭代”是循環(huán)的另一種說法。

第4章串、數(shù)組和廣義表1．選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A．可以順序存儲B．數(shù)據(jù)元素是一個字符C．可以鏈式存儲D．數(shù)據(jù)元素可以是多個字符（2）下面關于串的的敘述中，（）是不正確的A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲（3）串“ababaaababaa”的next數(shù)組為（）。A．0B．012121111212C．0D．（4）串“ababaabab”的nextval為（）。A．0B．010102101C．（5）串的長度是指（）。A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)（6）假設以行序為主序存儲二維數(shù)組A=array[1..100,1..100]，設每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5,5]=（）。A．808B．818C．說明：按行序存儲時，A[5,5]位于第5行第5列，之前有4行，每行100個元素，所在第5行前面有4個元素，因此在A[5,5]前面一共有4*100+4=404個元素。從基地址10開始存放，每個元素兩個單元，所以A[5,5]的存儲地址是10+404*2=818。一般的計算公式是：loc(i,j)=BA+[(i-1)*n+(j-1)]*L，其中BA是基地址，n是數(shù)組列數(shù)，L是每個元素占用的單元數(shù)。注意按此公式計算時，i、j必須是從1數(shù)起的。（7）設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5,8]的存儲首地址為（）。A．BA+141B．BA+180C．說明：按列序存儲，A[5,8]前面有7列，每列8個元素，所在的第8列上方有4個元素（因為在第5行），因此A[58]前面共有7*8+4=60個元素，每個元素3個字節(jié)，故存儲地址為BA+60*3=BA+180。（8）設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A．13B．32C．說明：這道題沒有說明按上三角還是下三角存儲。假設按下三角存儲，則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以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關系為（）。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(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按行先存儲，元素A[8,5]的起始地址與當A按列先存儲時的元素（）的起始地址相同。設每個字符占一個字節(jié)。A．A[8,5]B．A[3,10]C．A[5,8]D．A[0,9]說明：因為每個元素占用的單元數(shù)都相同，所以只要計算所存儲的元素個數(shù)即可。當按行優(yōu)先存儲時，A[8,5]前面有8行（行號從0數(shù)起），每行10個元素，所在的第8行前面有4個元素，因此存儲到A[8,5]之前共有8*10+4=84個元素。按列優(yōu)先存儲時，若要存儲在相同位置，則前面同樣必須有84個元素，因為每列有9個元素，所以列號一定要大于[84/9]=9，由此即知只有選擇項B符合要求。（11）設二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標為（）。A．(i-1)*n+j