




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
數據結構典型習題知博書店1、下面程序段的時間復雜度為()
for(inti=0;i<m;i++)
for(intj=0;j<n;j++)
a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)答案:C設n為正整數,分析下列各程序段中加下劃線的語句的程序步數。for(inti=1;i<=n;i++) for(intj=1;j<=n;j++){
c[i][j]=0.0; for(intk=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];
}(2)x=0;y=0; for(inti=1;i<=n;i++)for(intj=1;j<=i;j++) for(intk=1;k<=j;k++)
x=x+y;
(3)inti=1,j=1; while(i<=n&&j<=n){
i=i+1;j=j+i; }
i=1時,i=2,j=j+i=1+2=2+1,i=2時,i=3,j=j+i=(2+1)+3=3+1+2,i=3時,i=4,j=j+i=(3+1+2)+4=4+1+2+3,i=4時,i=5,j=j+i=(4+1+2+3)+5=5+1+2+3+4,……
i=k時,i=k+1,j=j+i=(k+1)+(1+2+3+4+…+k),2、下面算法的時間復雜度為()
int
f(unsigned
intn){
if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.On!)答案:B棧是一種線性表,它的特點是
A。設用一維數組A[1,…,n]來表示一個棧,A[n]為棧底,用整型變量T指示當前棧頂位置,A[T]為棧頂元素。往棧中推入(PUSH)一個新元素時,變量T的值
B;從棧中彈出(POP)一個元素時,變量T的值
C。設棧空時,有輸入序列a,b,c,經過PUSH,POP,PUSH,PUSH,POP操作后,從棧中彈出的元素的序列是
D,變量T的值是
E。供選擇的答案:A:①先進先出②后進先出 ③進優于出 ④出優于進 ⑤隨機進出B,C: ①加1②減1③不變 ④清0⑤加2⑥減2D:①a,b②b,c ③c,a ④b,a⑤c,b⑥a,cE:①n+1②n+2③n ④n-1⑤n-2ABCDE=2,2,1,6,4
在做進棧運算時,應先判別棧是否
A;在做退棧運算時,應先判別棧是否
B。當棧中元素為n個,做進棧運算時發生上溢,則說明該棧的最大容量為
C。為了增加內存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續的內存空間時,應將兩棧的
D分別設在這片內存空間的兩端,這樣,只有當
E時,才產生上溢。供選擇的答案:A,B:①空②滿③上溢④下溢C: ①n-1②n③n+1④n/2D:①長度②深度③棧頂④棧底E:①兩個棧的棧頂同時到達棧空間的中心點②其中一個棧的棧頂到達棧空間的中心點③兩個棧的棧頂在達棧空間的某一位置相遇④兩個棧均不空,且一個棧的棧頂到達另一個棧的棧底ABCDE=2,1,2,4,3
從一維數組a[n]中順序查找出一最大值元素的時間復雜度為(),輸出一個二維數組b[m][n]中所有元素的時間復雜度為()在順序表中插入和刪除一個結點需平均移動多少個結點?具體的移動次數取決于哪兩個因素?答:在等概率情況下,順序表中插入一個結點需平均移動n/2個結點。刪除一個結點需平均移動(n-1)/2個結點。具體的移動次數取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動的結點數越少。O(n)O(m*n)何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜?答:1.基于空間的考慮。當要求存儲的線性表長度變化不大,易于事先確定其大小時,為了節約存儲空間,宜采用順序表;反之,當線性表長度變化大,難以估計其存儲規模時,采用動態鏈表作為存儲結構為好。
2.基于時間的考慮。若線性表的操作主要是進行查找,很少做插入和刪除操作時,采用順序表做存儲結構為宜;反之,若需要對線性表進行頻繁地插入或刪除等的操作時,宜采用鏈表做存儲結構。并且,若鏈表的插入和刪除主要發生在表的首尾兩端,則采用尾指針表示的單循環鏈表為宜。為什么在單循環鏈表中設置尾指針比設置頭指針更好?答:尾指針是指向終端結點的指針,用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便,設一帶頭結點的單循環鏈表,其尾指針為rear,則開始結點和終端結點的位置分別是rear->next->next和rear,查找時間都是O(1)。
若用頭指針來表示該鏈表,則查找終端結點的時間為O(n)。
在單鏈表、雙鏈表和單循環鏈表中,若僅知道指針p指向某結點,不知道頭指針,能否將結點*p從相應的鏈表中刪去?若可以,其時間復雜度各為多少?答:我們分別討論三種鏈表的情況。
1.單鏈表。當我們知道指針p指向某結點時,能夠根據該指針找到其直接后繼,但是由于不知道其頭指針,所以無法訪問到p指針指向的結點的直接前趨。因此無法刪去該結點。
2.雙鏈表。由于這樣的鏈表提供雙向鏈接,因此根據已知結點可以查找到其直接前趨和直接后繼,從而可以刪除該結點。其時間復雜度為O(1)。
3.單循環鏈表。根據已知結點位置,我們可以直接得到其后相鄰的結點位置(直接后繼),又因為是循環鏈表,所以我們可以通過查找,得到p結點的直接前趨。因此可以刪去p所指結點。其時間復雜度應為O(n)。
下述算法的功能是什么?
LinkList
Demo(LinkListL){//L是無頭結點單鏈表
ListNode*Q,*P;
if(L&&L->next){
Q=L;L=L->next;P=L;
while(P->next)P=P->next;
P->next=Q;
Q->next=NULL;
}
returnL;
}//Demo答:將開始結點摘下鏈接到終端結點之后成為新的終端結點,而原來的第二個結點成為新的開始結點,返回新鏈表的頭指針。
鏈棧中為何不設置頭結點?
答:鏈棧不需要在頭部附加頭結點,因為棧都是在尾部進行操作的,如果加了頭結點,等于要對頭結點之后的結點進行操作,反而使算法更復雜,所以只要有鏈表的頭指針就可以了。
循環隊列的優點是什么?如何判別它的空和滿?答:循環隊列的優點是:它可以克服順序隊列的“假溢出”現象,能夠使存儲隊列的向量空間得到充分的利用。判別循環隊列的“空”或“滿”不能以頭尾指針是否相等來確定,一般是通過以下幾種方法:一是另設一變量來區別隊列的空和滿。二是少用一個元素的空間。每次入隊前測試入隊后頭尾指針是否會重合,如果會重合就認為隊列已滿。三是設置一計數器記錄隊列中元素總數,不僅可判別空或滿,還可以得到隊列中元素的個數。
設數組data[m]作為循環隊列SQ的存儲空間,front為隊頭指針,rear為隊尾指針,則執行出隊操作后其頭指針front值為(
)
A.front=front+1
B.front=(front+1)%(m-1)
C.front=(front-1)%m
D.front=(front+1)%mD設長度為n的鏈隊用單循環鏈表表示,若設頭指針,則入隊出隊操作的時間為何?若只設尾指針呢?答:當只設頭指針時,出隊的時間為1,而入隊的時間需要n,因為每次入隊均需從頭指針開始查找,找到最后一個元素時方可進行入隊操作。若只設尾指針,則出入隊時間均為1。因為是循環鏈表,尾指針所指的下一個元素就是頭指針所指元素,所以出隊時不需要遍歷整個隊列。
在一個帶頭結點的單循環鏈表中,p指向尾結點的直接前驅,則指向頭結點的指針head可用p表示為head=_____。p->next->next數組Q[n]用來表示一個循環隊列,f為當前隊列頭元素的前一位置,r為隊尾元素的位置,假定隊列中元素的個數小于n,計算隊列中元素的公式為(A)r-f;(B)(n+f-r)%n;(C)n+r-f;(D)(n+r-f)%nD為了提高內存的利用效率,減少溢出機會,可以讓兩個棧共享一段連續內存空間,應如何設置兩個棧?棧底分別設在內存的兩端設有編號為1,2,3,4的四輛列車,順序進入一個棧式結構的車站,具體寫出這四輛列車開出車站的所有可能的順序。①全進之后再出情況,只有1種:4,3,2,1②進3個之后再出的情況,有3種,3,4,2,13,2,4,13,2,1,4③進2個之后再出的情況,有4種,2,4,3,12,3,4,12,1,3,42,1,4,3④進1個之后再出的情況,有5種,1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3設有一個順序棧S,元素s1,s2,s3,s4,s5,s6依次進棧,如果6個元素的出棧順序為s2,s3,s4,s6,s5,s1,則順序棧的容量至少應為多少?3指出下述程序段的功能是什么?voidDemo1(SeqStack*S){
inti;arr[64];n=0;
while(!StackEmpty(S))arr[n++]=Pop(S);
for(i=0,i<n;i++)Push(S,arr);
}答:程序段的功能是將一棧中的元素按反序重新排列,也就是原來在棧頂的元素放到棧底,棧底的元素放到棧頂。此棧中元素個數限制在64個以內。
SeqStackS1,S2,tmp;
DataTypex;
...//假設棧tmp和S2已做過初始化
while(!StackEmpty(&S1))
{
x=Pop(&S1);
Push(&tmp,x);
}
while(!StackEmpty(&tmp))
{
x=Pop(&tmp);
Push(&S1,x);
Push(&S2,x);
}
答:程序段的功能是利用tmp棧將一個非空棧的所有元素按原樣復制到一個空棧當中去。
voidDemo2(SeqStack*S,intm)
{
//設DataType
為int
型
SeqStackT;inti;
InitStack(&T);
while(!StackEmpty(S))
if((i=Pop(S))!=m)Push(&T,i);
while(!StackEmpty(&T))
{
i=Pop(&T);Push(S,i);
}
}
答:程序段的功能是將一個非空棧中值等于m的元素全部刪去。
voidDemo3(CirQueue*Q)
{
//設DataType
為int
型
intx;SeqStackS;
InitStack(&S);
while(!QueueEmpty(Q))
{x=DeQueue(Q);Push(&S,x);}
while(!StackEmpty(&s))
{x=Pop(&S);EnQueue(Q,x);}
}//Demo3
答:程序段的功能是將一個循環隊列反向排列,原來的隊頭變成隊尾,原來的隊尾變成隊頭。
CirQueueQ1,Q2;//設DataType
為int
型
intx,i,m=0;
...
//設Q1已有內容,Q2已初始化過
while(!QueueEmpty(&Q1))
{x=DeQueue(&Q1);EnQueue(&Q2,x);m++;}
for(i=0;i<m;i++)
{x=DeQueue(&Q2);
EnQueue(&Q1,x);EnQueue(&Q2,x);}
答:這段程序的功能是將隊列1的所有元素復制到隊列2中去,但其執行過程是先把隊列1的元素全部出隊,進入隊列2,然后再把隊列2的元素復制到隊列1中。
假設有如下的串說明:
chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;
(1)在執行如下的每個語句后p的值是什么?
p=index(s1,'t‘,2);p=index(s2,'9‘,1);p=index(s2,'6‘,1);
答:index(*s,*c,pos)函數的功能是查找在串s第pos個字符后第一次出現串c的位置,若找到,則返回該位置,否則返回NULL。因此:
執行p=index(s1,'t‘,1);后p的值是指向字符t的位置,也就是p=6。
執行p=index(s2,'9‘,1);后p的值是指向s2串中第一個9所在的位置,也就是p=10。
執行p=index(s2,'6‘,1);之后,p的返回值是0。
假設有如下的串說明:
chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;
在執行下列語句后,s3的值是什么?
strcpy(s3,s1);strcat(s3,",");strcat(s3,s2);
答:strcpy函數功能是串拷貝,strcat函數的功能是串聯接。所以:
在執行strcpy(s3,s1);后,s3的值是"Stocktom,CA"
在執行strcat(s3,",");后,s3的值變成"Stocktom,Ca,"
在執行完strcat(s3,s2);后,s3的值就成了"Stocktom,Ca,March5,1999"
假設有如下的串說明:
chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;
調用函數strcmp(s1,s2)的返回值是什么?
答:函數strcmp(串1,串2)的功能是串比較,按串的大小進行比較,返回大于0,等于0或小于0的值以表示串1比串2大,串1等于串2,串1小于串2。因此在調用函數strcmp(s1,s2)后,返回值是大于0的數(字符比較是以ascii碼值相比的)
假設有如下的串說明:
chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;
調用函數strcmp(&s1[5],"ton")的返回值是什么?
答:首先,我們要知道&s1[5]是一個地址,當放在函數strcmp中時,它就表示指向以它為首地址的一個字符串,所以在strcmp(&s1[5],"ton")中,前一個字符串值是"tom,CA",用它和"ton"比較,應該是后者更大,所以返回值是小于0的數。
假設有如下的串說明:
chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;
調用函數strlen(strcat(s1,s2))的返回值是什么?
答:strlen是求串長的函數,我們先將s1,s2聯接起來,值是"Stocktom,CAMarch5,1999",數一數有幾個字符,返回值是23。
若目標串的長度為n,模式串的長度為[n/3],則執行模式匹配算法時,在最壞情況下的時間復雜度是(
)
A.O(1)
B.O(n)
C.O(n2)
D.O(n3)C設串s1=’ABCDEFG’,s2=’PQRST’,函數con(x,y)返回x和y串的連接串,subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串,len(s)返回串s的長度,則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結果串是:A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEFD假設有二維數組A6×8,每個元素用相鄰的6個字節存儲,存儲器按字節編址。已知A的起始存儲位置(基地址)為1000,則數組A的體積(存儲量)為
;末尾元素A57的第一個字節地址為
;若按行存儲時,元素A14的第一個字節地址為
;若按列存儲時,元素A47的第一個字節地址為
。288B1282(8+4)×6+1000=1072(6×7+4)×6+1000)=1276設數組a[1…60,1…70]的基地址為2048,每個元素占2個存儲單元,若以列序為主序順序存儲,則元素a[32,58]的存儲地址為
___________________
三元數組表中的每個結點對應于稀疏矩陣的一個非零元素,它包含有三個數據項,分別表示該元素的
、
和
。
[(58-1)*60+(32-1)]*2+2048=8950行下標列下標元素值二維數組M的成員是6個字符(每個字符占一個存儲單元)組成的串,行下標i的范圍從0到8,列下標j的范圍從1到10,則存放M至少需要()個字節;M的第8列和第5行共占()個字節;若M按行優先方式存儲,元素M[8][5]的起始地址與當M按列優先方式存儲時的()元素的起始地址一致。A.90 B.180 C.240 D.540A.108 B.114 C.54 D.60A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]答案:DAB數組A中,每個元素A的長度為3個字節,行下標i從1到8,列下標j從1到10,從首地址SA開始連續存放在存儲器內,該數組按行存放時,元素A[8][5]的起始地址為()
A.SA+141 B.SA+144 C.SA+222 D.SA+225C稀疏矩陣一般的壓縮存儲方式有兩種,即()答案:三元組和十字鏈表有一個10階對稱矩陣A,采用壓縮存儲方式(以行序為主存儲,且A[0][0]=1),則A[8][5]的地址是()答案:42若采用三元組壓縮技術存儲稀疏矩陣,只要把每個元素的行下標和列下標互換,就完成了對該矩陣的轉置運算,這種觀點()A.正確 B.錯誤B1.廣義表((a),a)的表頭是(),表尾是().A.aB.bC.(a)D.((a))2.廣義表((a))的表頭是(),表尾是().A.aB.(a)C.()D.((a))3.廣義表((a,b),c,d)的表頭是(),表尾是().A.aB.bC.(a,b)D.(c,d)4.廣義表(a,b,c,d)的表頭是(),表尾是().A.aB.bC.(a,b)D.(b,c,d)5.廣義表((a,b,c,d))的表頭是(),表尾是().A.aB.()C.(a,b,c,d)D.((a,b,c,d))6.一個廣義表的表頭是一個廣義表,這個斷言是().A.正確的B.錯誤的7.一個廣義表的表尾是一個廣義表,這個斷言是().A.正確的B.錯誤的CCBCCDADCBBA利用廣義表的head和tail操作寫出函數表達式,把以下各題中的單元素banana從廣義表中分離出來:
(1)L1(apple,pear,banana,orange) (2)L2((apple,pear),(banana,orange)) (3)L3(((apple),(pear),(banana),(orange))) (4)L4((((apple))),((pear)),(banana),orange) (5)L5((((apple),pear),banana),orange) (6)L6(apple,(pear,(banana),orange))L1(apple,pear,banana,orange)T(L1)L(pear,banban,orange)T(L)L(banana,orange)H(L)bananaH(T(T(L1)))L2((apple,pear),(banana,orange))T(L2)L((banana,orange))H(L)L(banana,orage)H(L)bananaH(H(T(L2)))L3(((apple),(pear),(banana),(orange)))H(L3)L((apple),(pear),(banana),(orange))T(L)L((pear),(banana),(orange))T(L)L((banana),(orange))H(L)L(banana)H(L)bananaH(H(T(T(H(L3)))))L4((((apple))),((pear)),(banana),orange)T(L4)L(((pear)),(banana),orange)T(L)L((banana),orange)H(L)L(banana)H(L)bananaH(H(T(T(L4))))L5((((apple),pear),banana),orange)H(L5)L(((apple),pear),banana)T(L)L(banana)H(L)bananaH(T(H(L5)))(6)L6(apple,(pear,(banana),orange))T(L6)L((pear,(banana),orange))H(L)L(pear,(banana),orange)T(L)L((banana),orange)H(L)L(banana)H(L)bananaH(H(T(H(T()))))如圖的4棵樹二叉樹中,(
)不是完全二叉樹。
ABCDC在線索化二叉樹中,t所指結點沒有左子樹的充要條件是(
)A.t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不對二叉樹按某種順序線索化后,任意結點均有指向其前驅和后繼的線索,這種說法(
)A.正確B.錯誤
用二叉鏈表法存儲包含n個結點的二叉樹,結點的2n個指針區域中有n+1個為空指針。
A.正確B.錯誤BBA二叉樹的前序遍歷序列中,任意一個結點均處在其子女結點的前面,這種說法(
)
A.正確B.錯誤設深度為h的二叉樹上只有度為0和度為2的結點,則此類二叉樹中所包含的結點數至少為(
)
A.2hB.2h-1C2h+1Dh+1AB某二叉樹的前序遍歷節點訪問順序是abdgcefh,中序遍歷訪問順序是dgbaechf,則其后序遍歷的節點訪問順序是
AbdgcefhaBgdbecfhaCbdgaechfDgdbehfcaD按照二叉樹的定義,具有3個節點的二叉樹有
種A3B4C5D6一棵二叉樹如圖所示,其中序遍歷是
AabdgcefhBdgbaechfCgdbehfcaDabcdefghCdhabcegfB在一非空二叉樹的中序遍歷序列中,根節點的右邊
A只有右子樹上的所有節點B只有右子樹上的部分節點C只有左子樹的部分節點D只有左子樹上的所有節點任何一棵二叉樹的葉子節點在先序,中序和后序遍歷序列中的相對次序
A不發生改變B發生改變C不能確定D以上都不對AA如果某二叉樹的前序是stuwv,中序是uwtvs,那么后序為
AuwvtsBvwutsCwuvtsDwutsv設n,m為一棵二叉樹上的兩個節點,在中序遍歷是,n在m前面的條件是
An在m右方Bn是m祖先Cn在m左方Dn是m子孫CC.線索二叉樹是一種
結構。A邏輯B邏輯和存儲C物理D線性一棵度為2的樹與一棵二叉樹有何區別?
C在一個圖中,所有頂點的度數之和等于所有邊數的()倍。a.1/2b.1c.2d.4在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的()倍。a.1/2b.1c.2d.4CB一個有n個頂點的無向圖最多有()條邊。a.nb.n(n-1)c.n(n-1)/2d.2n在一個具有n個頂點的無向圖中,要連通全部頂點至少需要()條邊
a.nb.n+1c.n-1d.n-2CC對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大小是()a.nb.(n-1)2c.n-1d.n
2對于一個具有n個頂點和e條邊的無向圖,若采用鄰接表表示,則表頭向量的大小為(),所有鄰接表中的結點總數是()。1:a.nb.n+1c.n-1dn+e2:a.e/2b.ec.2ed.n+e
DAC已知一個圖如圖所示,若從頂點a出發按深度搜索法進行遍歷,則可能得到的一種頂點序列為()按廣度搜索法進行遍歷,則可能得到的一種頂點序列為()A.a,b,e,c,d,f
B.a,c,f,e,b,d
C.a,e,b,c,f,d
D.a,e,d,f,c,bAa,b,c,e,d,fB.a,b,c,e,f,d
C.a,e,b,c,f,d
D.a,c,f,d,e,bacefbdDB已知一有向圖的鄰接表存儲結構如圖所示。根據有向圖的深度優先遍歷算法,從頂點v1出發,所得到的頂點序列是()
a.v1,v2,v3,v5.v4b.v1,v2,v3,v4,v5c.v1,v3,v4,v5,v2d.v1,v4,v3,v5,v2123453244524C已知一有向圖的鄰接表存儲結構如圖所示。根據有向圖的廣度優先遍歷算法,從頂點v1出發,所得到的頂點序列是()a.v1,v2,v3,v4,v5b.v1,v3,v2,v4,v5c.v1,v2,v3,v5,v4dv1,v4,v3,v5,v2123453244524B采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的()a先序遍歷b中序遍歷c后序遍歷d按層遍歷采取鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的()a先序遍歷b中序遍歷c后續遍歷d按層遍歷
AD用鄰接表表示圖進行廣度優先遍歷時,通常是采用
來實現算法的。A.棧B.隊列C.樹D.圖
用鄰接表表示圖進行深度優先遍歷時,通常是采用
來實現算法的。A.棧B.隊列C.樹D.圖BA判定一個有向圖是否存在回路除了可以利用拓撲排序方法之外,還可以利用()a求關鍵路徑的方法b求最短路徑的dijkstra方法C廣度優先遍歷法d深度優先遍歷法任何一個無向連通圖的最小生成樹()A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在
DA在無權圖G的鄰接矩陣A中,若(vi,vj)或<vi,vj>屬于圖G的邊集合,則對應元素A[i][j]等于()否則等于()已知一個圖用鄰接矩陣表示,計算第i個結點的入度的方法是_____________刪除所有從第i個結點出發的邊的方法是___________10第i列非零元素之和
將矩陣第i行全部置為零
如果n個頂點的圖是一個環,則它有
____棵生成樹。n個頂點e條邊的圖,若采用鄰接矩陣存儲,則空間復雜度為_______。
n個頂點e條邊的圖,若采用鄰接表存儲,則空間復雜度為
。設有一稀疏圖G,則G采用
存儲較省空間。設有一稠密圖G,則G采用
存儲較省空間。
nO(n2)O(n+e)鄰接表鄰接矩陣用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度
的次序來得到最短路徑的。拓撲排序算法是通過重復選擇具有
個前驅頂點的過程來完成的
遞增0在數據的存放無規律而言的線性表中進行檢索的最佳方法是__________順序查找法適合于存儲結構為()的線性表
a散列存儲b順序存儲或鏈接存儲
c壓縮存儲d索引存儲對線性表進行二分查找時,要求線性表必須()a以順序方式存儲b以鏈接方式存儲c以順序方式存儲,且結點按關鍵字有序排序d以鏈接方式存儲,且結點按關鍵字有序排序順序查找
bC采用順序查找方法查找長度為n的線性表時,每個元素的平均查找長度為()a.nb.n/2c(n+1)/2d.(n-1)/2采用二分法查找長度為n的線性表時,每個元素的平均查找長度為()a.O(n2)bO(nlog2n)cO(n)dO(log2n)二分法查找和二叉排序樹的時間性能()a相同b不相同Cdb有一個有序表為(n=13){1,3,9,12,32,41,45,62,75,77,82,95,100},當二分查找值82為的結點時()次比較后查找成功a1b2c4d8設哈希表長m=14,哈希函數H(key)=key%11。表中已有4個結點:addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空,如用二次探測再散列處理沖突,關鍵字為49的結點的地址是()a8b3c5d9Cd有一個長度為12的有序表,按二分查找發對該表進行查找,在表內個元素等概率情況下查找成功所需的平均比較次數為()a35/12b37/12c39/12d43/12順序查找法的平均查找長度為();二分查找法的平均查找長度();分塊查找法(以順序查找確定塊)的平均查找長度();分塊查找法(以二分法查找確定塊)的平均查找長度()b(n+1)/2((n+1)*log2(n+1))/n-1(s+2s+n)/2slog(n/s+1)+s/2在各種查找方法中,平均查找長度與結點個數n無關的查找方法是在分塊查找法首先查找()再查找相應的()在散列函數H(key)=key%p中p應取()假設在有序線性表A[1.20]上進行二分查找,則比較一次查找成功的結點數為(),則比較二次查找成功的結點數為(),則比較三次查找成功的結點數為()則比較4次查找成功的結點數為()則比較5次查找成功的結點數為()平均查找長度為()哈希表查找法索引塊素數1個2個4個8個5個3.7在散列存儲中,裝填因子α的值越大則存取元素時發生沖突的可能性就()α值越小則()
折半查找有序表(4,6,10,12,20,30,50,70,88,100)(n=10)。若查找表中元素58,則它將依次與表中
比較大小,查找結果是失敗。A.20,70,30,50B.30,88,70,50C.20,50D.30,88,50
越大越小A要進行線性查找,則線性表
A;要進行二分查找,則線性表
B;要進行散列查找,則線性表
C。某順序存儲的表格,其中有90000個元素,已按關鍵項的值的上升順序排列。現假定對各個元素進行查找的概率是相同的,并且各個元素的關鍵項的值皆不相同。當用順序查找法查找時,平均比較次數約為
D,最大比較次數為
E。供選擇的答案:A~C:①必須以順序方式存儲②必須以鏈表方式存儲③必須以散列方式存儲④既可以以順序方式,也可以以鏈表方式存儲⑤必須以順序方式存儲且數據元素已按值遞增或遞減的次序排好⑥必須以鏈表方式存儲且數據元素已按值遞增或遞減的次序排好D,E:①25000②30000③45000④90000答案:A=④B=⑤C=③D=③E=④
在二叉排序樹中,每個結點的關鍵碼值
A
,
B一棵二叉排序,即可得到排序序列。同一個結點集合,可用不同的二叉排序樹表示,人們把平均檢索長度最短的二叉排序樹稱作最佳二叉排序,最佳二叉排序樹在結構上的特點是
C。供選擇的答案A:①比左子樹所有結點的關鍵碼值大,比右子樹所有結點的關鍵碼值小②比左子樹所有結點的關鍵碼值小,比右子樹所有結點的關鍵碼值大③比左右子樹的所有結點的關鍵碼值都大④與左子樹所有結點的關鍵碼值和右子樹所有結點的關鍵碼值無必然的大小關系B:①前序遍歷②中序(對稱)遍歷③后序遍歷④層次遍歷C:①除最下二層可以不滿外,其余都是充滿的②除最下一層可以不滿外,其余都是充滿的③每個結點的左右子樹的高度之差的絕對值不大于1④最下層的葉子必須在最左邊答案:A=①B=②C=②散列法存儲的基本思想是根據
A
來決定
B
,沖突指的是
C,處理沖突的兩類主要方法是
D
。供選擇的答案A,B:①存儲地址②元素的符號③元素個數④關鍵碼值⑤非碼屬性⑥平均檢索長度⑦負載因子⑧散列表空間C:①兩個元素具有相同序號②兩個元素的關鍵碼值不同,而非碼屬性相同③不同
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 裝修侵權和解協議書
- 車位打包購買協議書
- 食品供應免責協議書
- 長期外聘講師協議書
- 餐廳管理委托協議書
- 音響安裝合同協議書
- 部門車位分配協議書
- 超市供貨轉讓協議書
- 除塵設備技術協議書
- 車輛頂賬合同協議書
- 2025屆高三語文專題復習:文言文閱讀-實詞的五種類型
- 土木工程CAD-終結性考核-國開(SC)-參考資料
- 放射性皮膚損傷的護理-中華護理學會團體標準
- 帕金森病的護理教學查房
- 智能手環項目財務分析報告
- 廣東省2019年中考化學試卷(含答案)
- 2024年國家低壓電工證理論考試題庫(含答案)
- 甲狀腺手術甲狀旁腺保護
- HG20202-2014 脫脂工程施工及驗收規范
- OpenCV圖像處理技術(微課版)(全彩)電子教案
- 2024年江蘇省鎮江市潤州區中考第二次中考生物模擬試卷
評論
0/150
提交評論