數(shù)據(jù)結(jié)構(gòu)試題庫

來源網(wǎng)絡(luò)來源網(wǎng)絡(luò)來源網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)試題庫單項(xiàng)選擇題下列程序段所代表的算法的時(shí)間復(fù)雜度為（D）。x=n;y=0;while(x>=(y+1)*(y+1))y++;(A)O(n)(B)O(n2)(C)O(log2n)(D)O()在一個(gè)長度為n的以順序結(jié)構(gòu)存儲的線性表中，假設(shè)在線性表的任何位置刪除元素的概率相等，則刪除一個(gè)元素時(shí)線性表所需移動元素的平均次數(shù)為（B）。(A)n2(B)(n-1)/2(C)(n+1)/2(D)n/2在一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行執(zhí)行操作為（C）。(A)HS->next=s;(B)s->next=HS->next;HS->next=s;(C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next;假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列Q，并且隊(duì)列只設(shè)一個(gè)頭指針front，不設(shè)隊(duì)列尾指針。若要進(jìn)隊(duì)一個(gè)元素*s，則在下列程序算法的空白處應(yīng)添加的操作語句是（A）。voidAddQueue(structlinkqueueQ){p=Q->front;while(p->next!=Q->front)p=p->next;}(A)p->next=s;s->next=Q->front;(B)Q->front->next=s;Q->front=s;(C)s->next=p;p->next=Q->front;(D)Q->front->next=s;s->next=p;設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（B）。(A)2h-1(B)2h-1+1(C)2h-1(D)2h-1-3現(xiàn)有數(shù)據(jù)集{53,30,37,12,45,24,96}，從空二叉樹逐個(gè)插入數(shù)據(jù)形成二叉排序樹，若希望查找此二叉樹中任一結(jié)點(diǎn)的平均查找長度最小，則應(yīng)選擇下面哪個(gè)序列輸入（C）。(A)45,24,53,12,37,96,30(B)30,24,12,37,45,96,53(C)37,24,12,30,53,45,96(D)12,24,30,37,45,53,96有一組數(shù)值{5,12,9,20,3}，用以構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度WPL值為（D）。(A)93(B)96(C)123(D)103已知一個(gè)有向圖G的頂點(diǎn)v={v1,v2,v3,v4,v5,v6}，其鄰接表如下圖所示，根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)遍歷序列是（B）。(A)v1,v2,v3,v6,v4,v5(B)v1,v2,v3,v6,v5,v4(C)v1,v2,v5,v6,v3,v4(D)v1,v2,v5,v3,v4,v6v3^v4^v5v5^v6^v3^v4^v5v5^v6^v1v2v2v2v3^v3v3v6^v6^v4^v5v4v4v6^設(shè)有m=2n-1個(gè)關(guān)鍵字，假設(shè)對每個(gè)關(guān)鍵字查找的概率相等，查找失敗的概率為0，若采用二分法查找一個(gè)關(guān)鍵字，則平均查找長度為（D）。(A)n-1(B)n-n/m(C)(n-1)-n/m(D)(n-1)+n/m已知一個(gè)待散列存儲的線性表{18,81,58,34,26,75,67,49,93}，散列函數(shù)為h(k)=k%11，散列地址空間為0~10。若采用線性探查法解決沖突，則平均查找長度為（A）。(A)5/3(B)13/9(C)16/9(D)3/2下列程序段所代表的算法的時(shí)間復(fù)雜度為（C）。y=n;x=1;while(x<=y)x*=2;(A)O(n)(B)O(n2)(C)O(log2n)(D)O()在一個(gè)長度為n的以順序結(jié)構(gòu)存儲的線性表中，假設(shè)在線性表的任何位置插入元素的概率相等，則插入一個(gè)元素時(shí)線性表所需移動元素的平均次數(shù)為（B）。(A)n2(B)(n+1)/2(C)(n-1)/2(D)n/2若對一個(gè)已有序的線性表最頻繁的操作是查找值為x的元素(假設(shè)存在的話)，則采用（D）存儲方式實(shí)現(xiàn)查找，其算法的時(shí)間復(fù)雜度為最小。(A)單鏈表(B)雙鏈表(C)單循環(huán)鏈表(D)順序表一個(gè)帶頭結(jié)點(diǎn)head的循環(huán)單鏈表為空的判斷條件是（C）。(A)head==NULL(B)head->next==NULL(C)head->next==head(D)head!=NULL若鏈隊(duì)列HQ中只有一個(gè)結(jié)點(diǎn)，則隊(duì)列的頭指針和尾指針滿足下列條件（D）。(A)HQ->rear->next==HQ->front(B)HQ->front->next==HQ->rear->next(C)HQ->front==HQ->rear(D)HQ->front->next==HQ->rear從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除結(jié)點(diǎn)的值，則應(yīng)執(zhí)行操作為（A）。(A)x=HS->data;HS=HS->next;(B)x=HS->data;HS->NEXT=NULL;(C)HS=HS->next;x=HS->data;(D)x=HS->data;HS=NULL;一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹，有m個(gè)葉子結(jié)點(diǎn)，深度為h，那么n、m和h滿足條件（D）。(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-1一棵左、右子樹均不為空的二叉樹在先序線索化后，其空指針域數(shù)為（B）。(A)0(B)1(C)2(D)不確定有一組數(shù)值{5,12,9,20,3}，用以構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度WPL值為（C）。(A)49(B)96(C)103(D)125在一個(gè)n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)關(guān)鍵字，進(jìn)行關(guān)鍵字比較次數(shù)最大值為（A）。(A)n(B)n/2(C)log2n(D)n*log2n已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，則下列邊集合E中（A）所對應(yīng)的有向圖沒有拓?fù)湫蛄?。E={<v2,v1>,<v6,v2>,<v1,v3>,<v2,v3>,<v5,v3>,<v3,v4>,<v4,v6>,<v5,v6>}E={<v1,v2>,<v1,v3>,<v1,v4>,<v3,v5>,<v3,v2>,<v4,v5>,<v6,v5>,<v6,v4>}E={<v1,v3>,<v1,v4>,<v1,v5>,<v2,v3>,<v2,v2>,<v3,v5>,<v3,v6>,<v4,v5>,<v4,v6>,<v5,v6>}E={<v1,v2>,<v1,v3>,<v2,v3>,<v1,v4>,<v2,v5>,<v3,v6>,<v4,v6>,<v5,v6>}冒泡排序算法在最好情況下的時(shí)間復(fù)雜度為（B）。(A)O(log2n)(B)O(n)(C)O(1)(D)O(n2)在下列內(nèi)部排序方法中，排序時(shí)不穩(wěn)定的，而且關(guān)鍵字的比較次數(shù)與記錄的初始排列次序無關(guān)的是（D）。(A)快速排序(B)冒泡排序(C)歸并排序(D)堆排序已知一個(gè)待散列存儲的線性表{18,81,58,34,26,75,67,49,93}，散列函數(shù)為h(k)=k%11，散列地址空間為0~10。若采用線性探查法解決沖突，則平均查找長度為（C）。(A)5/3(B)13/9(C)16/9(D)3/2下列程序段所代表的算法的時(shí)間復(fù)雜度為（D）。i=1;j=0;while(i<=n){i+=j;j++;}(A)O(n)(B)O(n2)(C)O(log2n)(D)O()將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，在最壞的情況下，其比較次數(shù)是（A）。(A)2n-1?(B)n???(C)n+1?(D)n-1若某鏈表中最常用的操作是在最后的一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用（D）存儲方式最節(jié)省運(yùn)行時(shí)間。(A)單鏈表(B)單循環(huán)鏈表(C)無頭雙向鏈表(D)帶頭雙向鏈表已知head是一個(gè)非空單鏈表的頭指針，指針p指向單鏈表的最后一個(gè)結(jié)點(diǎn)，若要在p之后插入一個(gè)新結(jié)點(diǎn)*s，并將單鏈表變?yōu)檠h(huán)單鏈表，則應(yīng)執(zhí)行的操作是（B）。(A)s->next=p->next;p->next=s;(B)s->next=head;p->next=s;(C)s->next=p->next;p->next=head;(D)s->next=p->next;s->next=p;已知用循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)一個(gè)元素的時(shí)間復(fù)雜度分別是（B）。(A)O(1)和O(1)(B)O(1)和O(n)(C)O(n)和O(1)(D)O(n)和O(n)設(shè)鏈隊(duì)列Q的頭指針和尾指針分別為front和rear，初始時(shí)隊(duì)列為空，若向隊(duì)列插入一個(gè)元素*s，則應(yīng)執(zhí)行的指針操作為（C）。(A)Q->front->next=s;s->next=Q->rear;Q->rear=NULL;(B)s->next=Q->front;Q->rear->next=s;Q->rear=NULL;(C)Q->rear->next=s;Q->rear=s;s->next=NULL;(D)Q->front->next=s;Q->rear=s;s->next=NULL;已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別為：V={1,2,3,4,5,6,7,8};E={(3,1)6，(3,4)7，(3,7)5，(1,2)3，(1,4)4，(4,7)8，(4,5)4，(7,8)5，(2,6)3，(2,5)5,(5,8)8,(5,6)5,(8,6)6},則該圖的最小生成樹的權(quán)值為（C）。(A)24(B)29(C)30(D)31當(dāng)待排序的關(guān)鍵字個(gè)數(shù)n很小，且初始排列為逆序時(shí)，采用下列排序方法中的（D），算法的時(shí)間復(fù)雜度最小。(A)直接插入排序(B)簡單選擇排序(C)冒泡排序(D)快速排序?qū)Χ媾判驑溥M(jìn)行（C）遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的排序序列。(A)層次???(B)前序???(C)中序???(D)后序已知一個(gè)長度為12的線性表（8，2，5，7，12，3，10，4，1，6，9，11），并將線性表中的元素依次插入到一個(gè)原先為空的二叉排序樹中去。假設(shè)查找每一個(gè)元素的概率相同，則查找該二叉樹中任一結(jié)點(diǎn)的平均查找長度為（A）。(A)10/3(B)13/3(C)37/12(D)13/2一組關(guān)鍵字序列{15，92，124，5，27，28，18，6，36，34，30，26，32，259}，將它們用散列函數(shù)H(key)=keyMOD11按順序散列到HASH表HT（0:10）中，用鏈地址解決沖突。假設(shè)查找每一個(gè)元素的概率相同，則查找該HASH表中任一元素的平均查找長度為（C）。(A)3/2(B)10/7(C)11/7(D)9/7以數(shù)據(jù)集{4，5，6，7，12，18，10}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹，則其帶權(quán)路徑長度WPL為（A）。(A)165(B)203(C)124(D)187假定對線性表R[0…n-1]進(jìn)行分塊查找，若將表均勻地分為b塊，每塊含有n/b個(gè)記錄；又假定表中每個(gè)記錄的查找概率相等，并用順序查找確定所在的塊，若要使分塊查找的平均查找長度ASL最小，則分塊數(shù)b的值應(yīng)為（B）。(A)(B)+1(C)「log2n」(D)「log2n」+1對n個(gè)記錄進(jìn)行直接插入排序，所需的關(guān)鍵字比較次數(shù)的最大值和最小值分別是（C）。(A)n(n+1)/2和n(B)n(n-1)/2和n-1(C)n(n+1)/2-1和n-1(D)n2和n若在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序，則該操作的時(shí)間復(fù)雜度是（）。(A)O(1)(B)O(n2)(C)O(nlog2n)(D)O(n)在一個(gè)頭結(jié)點(diǎn)為head的空循環(huán)鏈表中插入一個(gè)結(jié)點(diǎn)s，則指針s應(yīng)執(zhí)行操作（）。(A)head->next=s;s->next=NULL;(B)s->next=head;head->next=NULL;(C)head->next=s;s->next=head->next;(D)s->next=head;head->next=s;設(shè)鏈隊(duì)列Q的頭指針和尾指針分別為front和rear，隊(duì)中元素個(gè)數(shù)為n(n>1)，指針*p指向隊(duì)首元素m。若刪除元素m，則應(yīng)進(jìn)行的指針操作為（）。(A)Q->front->next=p->next(B)Q->rear=Q->front(C)Q->front=p->rear(D)Q->rear=p->next假設(shè)二叉樹T中有n個(gè)葉子結(jié)點(diǎn)，且所有非葉子結(jié)點(diǎn)都有左、右子樹，那么二叉樹T共有（）個(gè)結(jié)點(diǎn)。(A)2n(B)2n-1(C)2n+1(D)2n+2已知有向圖G的鄰接矩陣如下所示，則下列序列中（）不可能是圖G的拓?fù)湫蛄小?A)v1,v6,v3,v4,v2,v5(B)v1,v6,v4,v3,v2,v5(C)v1,v3,v2,v4,v6,v5(D)v1,v3,v6,v4,v5,v2已知一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲結(jié)構(gòu)，數(shù)組內(nèi)容如下表所示，則該二叉樹的后序遍歷序列為（）。1123456789101112131415161718192021EAFDGCJIHB(A)ACBDJEFIGH(B)ABCDJEFHGI(C)BCJDAHIGFE(D)EADCBJFGIH若T為n個(gè)結(jié)點(diǎn)的完全二叉樹，則T的葉子結(jié)點(diǎn)數(shù)為（）。(A)n/2(B)(n-2)/2(C)(n-1)/2(D)(n+1)/2有一組數(shù)值14,21,32,15,28，用以構(gòu)造huffman樹，則其WPL值為（）。(A)267(B)189(C)110(D)294采用折半插入排序，關(guān)鍵字的比較次數(shù)與移動次數(shù)分別為（）。(A)O(n),O(log2n)(B)O(n2),O(log2n)(C)O(log2n),O(n2)(D)O(nlog2n),O(n2)假設(shè)結(jié)點(diǎn)序列為{60,30,90,50,95,70,40,80}，以此構(gòu)成一棵二叉排序樹，則在該二叉排序樹上查找一個(gè)結(jié)點(diǎn)的平均查找長度為（）。(A)23/8(B)11/4(C)9/2(D)4下面程序段的時(shí)間復(fù)雜性的量級為（D）。for(i=1;i＜＝n;i++)for(j=1;j＜＝m;j++){c[i][j]=0;for(k=1;k＜＝w;k++)c[i][j]+=a[i][k]*b[k][j]}(A)O(i*j*k)(B)O(n*m*k)(C)O(n*j*k)(D)O(n*m*w)在一個(gè)長度為n的線性表中，刪除值為x的元素時(shí)需要比較元素和移動元素的總次數(shù)為（C）。(A)（n+1）/2(B)n/2(C)n(D)n+1利用3，6，8，12，5，7這六個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹的深度為（B）。(A)3(B)4(C)5(D)6一棵二叉樹的廣義表表示為a(b(c,d),e(,f(g))),則得到的層次遍歷序列為（D）。(A)a,b,c,d,e,f,g(B)c,b,d,a,e,g,f(C)c,d,b,g,f,e,a(D)a,b,e,c,d,f,g若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）。(1≤i≤n+1)(A)O(0)???(B)O(1)???(C)O(n)???(D)O(n2)若在線性表中采用折半查找法查找元素，該線性表應(yīng)該（）。(A)元素按值有序???(B)采用順序存儲結(jié)構(gòu)(C)元素按值有序，且采用順序存儲結(jié)構(gòu)(D)元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)已知一算術(shù)表達(dá)式的中綴形式為A＋B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）。?(A)–A+B*C/DE???(B)–A+B*CD/E(C)-+*ABC/DE???(D)-+A*BC/DE若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位置，利用（）遍歷方法最合適。?(A)前序???(B)中序???(C)后序???(D)按層次對二叉排序樹進(jìn)行（）遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的排序序列。?(A)前序???(B)中序???(C)后序???(D)按層次具有n個(gè)頂點(diǎn)的有向圖最多有（）條邊。?(A)n???(B)n(n—1)???Cn(n+1)???(D)n2從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法。?(A)插入???(B)選擇???(C)shell???(D)二路歸并排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）排序法。?(A)插入???(B)選擇???(C)冒泡???(D)快速下面給出的四種排序法中（）排序法是不穩(wěn)定性排序法。(A)插入???(B)冒泡???(C)二路歸并???(D)堆一個(gè)對象序列的排序碼為{46，79，56，38，40，84}，采用快速排序以位于最左位置的對象為基準(zhǔn)而得到的第一次劃分結(jié)果為（）。(A){38，46，79，56，40，84}(B){38，79，56，46，40，84}(C){40，38，46，56，79，84}(D){38，46，56，79，40，84}線性鏈表不具有的特點(diǎn)是（）。(A)隨機(jī)訪問(B)不必事先估計(jì)所需存儲空間大小(C)插入與刪除時(shí)不必移動元素(D)所需空間與線性表長度成正比設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。(A)n-1(B)n(C)n+1(D)n+2具有65個(gè)結(jié)點(diǎn)的完全二叉樹的高度為（）。（根的層次號為0）(A)8(B)7(C)6(D)5若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用（）方法比較次數(shù)最少。(A)直接插入排序(B)快速排序(C)歸并排序(D)直接選擇排序在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。(A)3(B)2(C)1(D)1/2對有14個(gè)數(shù)據(jù)元素的有序表R[14]進(jìn)行折半搜索，搜索到R[3]的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為（）。(A)R[0]，R[1]，R[2]，R[3](B)R[0]，R[13]，R[2]，R[3](C)R[6]，R[2]，R[4]，R[3](D)R[6]，R[4]，R[2]，R[3]若度為m的哈夫曼樹中,其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為（）。(A)[(n+1)/(m+1)]-1(B)[n/m]-1(C)[(n-1)/(m-1)](D)[n/(m-1)]-1下面關(guān)于算法說法錯(cuò)誤的是（）。(A)算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)(B)為解決某問題的算法同為該問題編寫的程序含義是相同的(C)算法的可行性是指指令不能有二義性(D)以上幾個(gè)都是錯(cuò)誤的以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。(A)循環(huán)隊(duì)列(B)鏈表(C)哈希表(D)棧以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）。(A)廣義表(B)二叉樹(C)稀疏矩陣(D)串以下那一個(gè)術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（）(A)棧(B)哈希表(C)線索樹(D)雙向鏈表在下面的程序段中，對x的賦值語句的頻度為（）。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;(A)O(2n)(B)O(n)(C)O(n2)(D)O(log2n)以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（）。(A)棧(B)廣義表(C)有向圖(D)字符串連續(xù)存儲設(shè)計(jì)時(shí)，存儲單元的地址（）。(A)一定連續(xù)(B)一定不連續(xù)(C)不一定連續(xù)(D)部分連續(xù)，部分不連續(xù)?一棵左右子樹均不空的二叉樹在先序前驅(qū)和后序后繼線索化后，其空鏈域數(shù)為（A）。(A)0(B)1(C)2(D)不確定設(shè)圖G采用鄰接表存儲，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是（B）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n*e)下列排序算法中，時(shí)間復(fù)雜度為O(nlog2n)且占用額外空間最少的是（A）。(A)堆排序(B)冒泡排序(C)快速排序(D)SHELL排序已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，則采用（B）排序算法最節(jié)省時(shí)間。(A)堆排序(B)插入排序(C)快速排序(D)直接選擇排序串是（D）。(A)不少于一個(gè)字母的序列(B)任意個(gè)字母的序列(C)不少于一個(gè)字符的序列(D)有限個(gè)字符的序列一個(gè)棧的輸入序列為12345，則下列序列中是棧的輸出序列的是（A）。(A)23415(B)54132(C)31245(D)14253設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1~n，其頭尾指針分別為f和r，則其元素個(gè)數(shù)為（D）。(A)r-f(B)r-f+1(C)(r-f)modn+1(D)(r-f+n)modn二叉樹在線索化后，仍不能有效求解的問題是（D）。(A)先序線索二叉樹中求先序后繼(B)中序線索二叉樹中求中序后繼(C)中序線索二叉樹中求中序前驅(qū)(D)后序線索二叉樹中求后序后繼求最短路徑的FLOYD算法的時(shí)間復(fù)雜度為（D）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n3)一棵左右子樹不空的二叉樹在先序線索化后，其空指針域數(shù)為（B）。(A)0(B)1(C)2(D)不確定數(shù)組A[1..5,1..6]的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先順序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5,5]的地址為（A）。(A)1140(B)1145(C)1120(D)1125在下列排序算法中，在待排序的數(shù)據(jù)表已經(jīng)為有序時(shí)，花費(fèi)時(shí)間反而最多的是（A）。(A)快速排序(B)希爾排序(C)冒泡排序(D)堆排序?qū)τ?8個(gè)元素的有序表做折半查找，則查找A[3]的比較序列的下標(biāo)依次為（D）。(A)1-2-3(B)9-5-2-3(C)9-5-3(D)9-4-2-3下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是（D）。(A)堆排序(B)冒泡排序(C)快速排序(D)直接插入排序在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡點(diǎn)為A，并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則做（B）型調(diào)整以使其平衡。(A)LL(B)LR(C)RL(D)RR下列各式中，按增長率由小至大的順序正確排列的是（）。(A),n!,2n,n3/2(B)n3/2,2n,nlogn,2100(C)2n,logn,nlogn,n3/2(D)2100,logn,2n,nn若要在單鏈表中的結(jié)點(diǎn)*p之后插入一個(gè)結(jié)點(diǎn)*s，則應(yīng)執(zhí)行的語句是（）。(A)s-＞next=p-＞next;p-＞next=s;(B)p-＞next=s;s-＞next=p-＞next(C)p-＞next=s-＞next;s-＞next=p;(D)s-＞next=p;p-＞next=s-＞next;若要在O（1）的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分別指向（）。(A)各自的頭結(jié)點(diǎn)(B)各自的尾結(jié)點(diǎn)(C)各自的第一個(gè)元素結(jié)點(diǎn)(D)一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)點(diǎn)棧的兩種常用存儲結(jié)構(gòu)分別為（）。(A)順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)(B)順序存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)(C)鏈?zhǔn)酱鎯Y(jié)構(gòu)和索引存儲結(jié)構(gòu)(D)鏈?zhǔn)酱鎯Y(jié)構(gòu)和散列存儲結(jié)構(gòu)已知循環(huán)隊(duì)列的存儲空間為數(shù)組data[21]，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，則該隊(duì)的當(dāng)前長度為（）。(A)5(B)6(C)16(D)17已知在如下定義的鏈串結(jié)點(diǎn)中，每個(gè)字符占1個(gè)字節(jié)，指針占4個(gè)字節(jié)，則該鏈串的存儲密度為（）。typedefstructnode{chardate[8];structnode*next;}LinkStrNode;(A)1/4(B)1/2(C)2/3(D)3/4應(yīng)用簡單的匹配算法對主串s=“BDBABDABDAB”與子串t=“BDA”進(jìn)行模式匹配，在匹配成功時(shí)，進(jìn)行的字符比較總次數(shù)為（）。(A)7(B)9(C)10(D)12二維數(shù)組A[20][10]采用列優(yōu)先的存儲方法，若每個(gè)元素占2個(gè)存儲單元，且第1個(gè)元素的首地址為200，則元素A[8][9]的存儲地址為（）。(A)574(B)576(C)578(D)580對廣義表L=((a,b),c,d)進(jìn)行操作tail(head(L))的結(jié)果是（）。(A)(c,d)(B)(d)(C)b(D)(b)已知一棵樹的前序序列為ABCDEF，后序序列為CEDFBA，則對該樹進(jìn)行層次遍歷得到的序列為（）。(A)ABCDEF(B)ABCEFD(C)ABFCDE(D)ABCDFE一個(gè)含n個(gè)頂點(diǎn)和e條弧的有向圖以鄰接矩陣表示法為存儲結(jié)構(gòu)，則計(jì)算該有向圖中某個(gè)頂點(diǎn)出度的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(e)(C)O(n+e)(D)O(n2)在關(guān)鍵字序列（12，23，34，45，56，67，78，89，91）中二分查找關(guān)鍵字為45，89和12的結(jié)點(diǎn)時(shí)，所需進(jìn)行的比較次數(shù)分別為（）。(A)4，4，3(B)4，3，3(C)3，4，4(D)3，3，4下列排序方法中，最好與最壞時(shí)間復(fù)雜度不相同的排序方法是（）。(A)冒泡排序(B)直接選擇排序(C)堆排序(D)歸并排序已知含10個(gè)結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于（）。(A)1.0(B)2.9(C)3.4(D)5.5在下列各種文件中，不能進(jìn)行順序查找的文件是（）。(A)順序文件(B)索引文件(C)散列文件(D)多重表文件下面帶有@標(biāo)記的語句的頻度(n>10)是（）。 for(inti=0;i<n-1;i++) for(intj=i+1;j<n;j++) @cout<<i<<j<<endl;(A)n*(n-1)/2(B)n*n/2(C)n*(n+1)/2(D)不確定已知使用順序表存儲數(shù)據(jù)，表長為n，假設(shè)在表中的任意位置插入元素的概率相等，則插入一個(gè)元素，平均需要移動的元素個(gè)數(shù)（）。(A)(n-1)/2(B)n/2(C)(n+1)/2(D)不確定在雙向鏈表p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是（）。(A)p?right=s;s?left=p;p?right?left=s;s?right=p?right;(B)p?right=s;p?right?left=s;s?left=p;s?right=p?right;(C)s?left=p;s?right=p?right;p?right=s;p?right?left=s;(D)s?left=p;s?right=p?right;p?right?left=s;p?right=s;字符串相等的充分必要條件是（）。(A)串長度相等(B)串使用相同的存儲結(jié)構(gòu)(C)串相同位置對應(yīng)的字符相等(D)A和C將一個(gè)遞歸算法改為對應(yīng)的非遞歸算法時(shí)，通常需要使用（）。(A)數(shù)組 (B)棧 (C)隊(duì)列 (D)二叉樹一個(gè)棧的入棧序列1,2,3,4,5,則棧的不可能的輸出序列是（）。(A)12345(B)54321(C)32514(D)12354設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1~n，其頭尾指針分別為f和r，則其元素個(gè)數(shù)為（）。(A)r-f(B)r-f+1(C)(r-f)modn+1(D)(r-f+n)modn某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是ABDEFCGH,中序遍歷的結(jié)點(diǎn)訪問順序是DBFEAGHC,則其后序遍歷的結(jié)點(diǎn)訪問順序是（）。(A)DFEBHCGA(B)DFEBHGCA(C)DEFBHGCA(D)DFEHBGCA正則二叉樹是只有度為0和2的結(jié)點(diǎn)的二叉樹，已知正則二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)為n，則該二叉樹總得結(jié)點(diǎn)數(shù)為（）。(A)n+1(B)2*n(C)2*n+1(D)2*n-1下面關(guān)于排序的說法錯(cuò)誤的是（）。(A)快速排序、歸并排序都是一種不穩(wěn)定的排序方法(B)直接插入排序和折半插入排序移動元素的次數(shù)相同(C)簡單選擇排序移動元素的次數(shù)最少(D)根據(jù)排序需要的平均時(shí)間，快速排序是目前最好的一種內(nèi)部排序方法折半查找有序表（3，4，5，10，13，14，20，30），若查找元素3，則被比較的元素依次為（）。(A)10,20,30(B)10,14,30(C)13,3(D)10,4,3下面關(guān)于棧和隊(duì)列的說法正確的是（）。(A)棧是先進(jìn)先出的線性表，隊(duì)列是后進(jìn)先出的線性表(B)棧是先進(jìn)先出的線性表，隊(duì)列也是先進(jìn)先出的線性表(C)棧是后進(jìn)先出的線性表，隊(duì)列是先進(jìn)先出的線性表(D)棧是后進(jìn)先出的線性表，隊(duì)列也是后進(jìn)先出的線性表兩個(gè)各有n個(gè)元素的有序列表并成一個(gè)有序表，其最少的比較次數(shù)是（）。

(A)n(B)2n-1(C)2n(D)n-1設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是0~n-1，f表示隊(duì)首元素的前驅(qū)位置，r表示隊(duì)尾元素的位置，則隊(duì)列中元素個(gè)數(shù)為（）。

(A)r-f(B)r-f1(C)(r-f1)modn(D)(r-fn)modn一個(gè)5行6列的二維數(shù)組s采用從最后一行開始，每一行的元素從右至左的方式映射到一維數(shù)組a中，s和a的下標(biāo)均從0開始，則s[3][3]在a中的下標(biāo)是（）。

(A)7(B)8(C)9(D)10設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為1，則高度為n的二叉樹中所含葉子結(jié)點(diǎn)的個(gè)數(shù)最多為（）個(gè)。

(A)2n(B)n(C)2n-1(D)2n-1設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）個(gè)（設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為1）。

(A)2h(B)2h-1(C)2h+1(D)h+1對一棵二叉檢索樹進(jìn)行（）得到的結(jié)點(diǎn)序列是一個(gè)有序序列。

(A)前序周游(B)中序周游(C)后序周游(D)層次周游一棵前序序列為1，2，3，4的二叉樹，其中序序列不可能是（）。

(A)4,1,2,3(B)4,3,2,1(C)2,4,3,1(D)3,4,2,1在含n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）。

(A)e(B)2e(C)n2-e(D)n2-2e具有n個(gè)頂點(diǎn)和e條邊的圖的深度優(yōu)先搜索算法的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n3)(C)O(n2)(D)O(ne)如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有（）棵生成樹。

(A)n(B)nl(C)n-l(D)2n堆排序算法在平均情況下的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(nlogn)(C)O(n2)(D)O(logn)在待排序數(shù)據(jù)已基本有序的前提下，下述排序方法中效率最高的是（）。(A)直接插入排序(B)直接選擇排序(C)快速排序(D)歸并排序在理想情況下，散列表中查找元素所需的比較次數(shù)為（）。

(A)n(B)O(C)n／2(D)1在一棵m階B樹中，若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是（）。

(A)m(B)m+1(C)m-l(D)m／2設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（C）。 (A)R-F (B)F-R (C)(R-F+M)％M (D)(F-R+M)％M設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（A）。 (A)BADC (B)BCDA (C)CDAB (D)CBDA設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（A）條邊。 (A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-1設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（C）。 (A)9 (B)10 (C)11 (D)12設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（B）個(gè)表頭結(jié)點(diǎn)。 (A)n-1 (B)n (C)n+1 (D)2n-1設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（C）。 (A)2，3，5，8，6 (B)3，2，5，8，6 (C)3，2，5，6，8 (D)2，3，6，5，8設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（B）。 (A)線性結(jié)構(gòu) (B)樹型結(jié)構(gòu) (C)物理結(jié)構(gòu) (D)圖型結(jié)構(gòu)下面程序的時(shí)間復(fù)雜為（B）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；} (A)O(n) (B)O(n2) (C)O(n3) (D)O(n4)設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（A）。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)；設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（A）個(gè)輔助記錄單元。 (A)1 (B)n (C)nlog2n (D)n2設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為（A）。(A)10，15，14，18，20，36，40，21 (B)10，15，14，18，20，40，36，21 (C)10，15，14，20，18，40，36，2l (D)15，10，14，18，20，36，40，21設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（B）。 (A)O(1) (B)O(log2n) (C)log2n (D)O(n2)設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（D）。 (A)n，e (B)e，n (C)2n，e (D)n，2e設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（C）條邊。 (A)n(n-1) (B)n+1 (C)n (D)n(n+1)設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（B）方法可以達(dá)到此目的。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)插入排序下列四種排序中（D）的空間復(fù)雜度最大。 (A)插入排序 (B)冒泡排序 (C)堆排序 (D)歸并排序設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（C）。 (A)O(n) (B)O(nlog2n) (C)O(1) (D)O(n2)設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（D）個(gè)結(jié)點(diǎn)。 (A)2k-1 (B)2k (C)2k-1 (D)2k-1設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（D）。 (A)n (B)e (C)2n (D)2e在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（B）。 (A)O(1) (B)O(n) (C)O(log2n) (D)O(n2)設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（C）條有向邊。 (A)n (B)n-1 (C)m (D)m-1設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（A）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A)3 (B)4 (C)5 (D)8設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（B）。 (A)必須判別棧是否為滿 (B)必須判別棧是否為空 (C)判別棧元素的類型 (D)對棧不作任何判別下列四種排序中（A）的空間復(fù)雜度最大。 (A)快速排序 (B)冒泡排序 (C)希爾排序 (D)堆設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（C）。 (A)N0=N1+1 (B)N0=Nl+N2 (C)N0=N2+1 (D)N0=2N1+l設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（A）。 (A)log2n+1 (B)log2n-1 (C)log2n (D)log2(n+1)數(shù)據(jù)的最小單位是（A）。 (A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（B）。 (A)40，50，20，95 (B)15，40，60，20 (C)15，20，40，45 (D)45，40，15，20設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（A）。(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（D）。 (A)O(log2n) (B)O(1) (C)O(n2) (D)O(n)設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（B）。(A)Nl+N2+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（B）次。 (A)25 (B)10 (C)7 (D)1設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（B）。 (A)abedfc (B)acfebd (C)aebdfc (D)aedfcb設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（C）。 (A)n-i (B)n-1-i (C)n+1-i (D)不能確定設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（C）。 (A)40，42，45，55，80，83 (B)42，40，45，80，85，88 (C)42，40，45，55，80，85 (D)42，40，45，85，55，80設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（D）。 (A)20 (B)30 (C)40 (D)45執(zhí)行一趟快速排序能夠得到的序列是（A）。 (A)[41，12，34，45，27]55[72，63] (B)[45，34，12，41]55[72，63，27] (C)[63，12，34，45，27]55[41，72] (D)[12，27，45，41]55[34，63，72]設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（A）。(A)head==0 (B)head->next==0(C)head->next==head (D)head!=0時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（A）。 (A)堆排序 (B)冒泡排序 (C)希爾排序 (D)快速排序設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（D）。 (A)空或只有一個(gè)結(jié)點(diǎn) (B)高度等于其結(jié)點(diǎn)數(shù) (C)任一結(jié)點(diǎn)無左孩子 (D)任一結(jié)點(diǎn)無右孩子一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（D）。 (A)堆排序 (B)冒泡排序 (C)快速排序 (D)希爾排序設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為（B）。 (A)3 (B)4 (C)5 (D)6順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（A）。 (A)O(n) (B)O(n2) (C)O(n1/2) (D)O(1og2n)二路歸并排序的時(shí)間復(fù)雜度為（C）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(log2n)深度為k的完全二叉樹中最少有（B）個(gè)結(jié)點(diǎn)。 (A)2k-1-1 (B)2k-1 (C)2k-1+1 (D)2k-1設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（C）。 (A)front->next=s；front=s； (B)s->next=rear；rear=s； (C)rear->next=s；rear=s； (D)s->next=front；front=s；設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為（A）。 (A)O(n+e) (B)O(n2) (C)O(ne) (D)O(n3)設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（B）個(gè)葉子結(jié)點(diǎn)。 (A)99 (B)100 (C)101 (D)102設(shè)二叉排序樹上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（D）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(log2n)設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（B）。 (A)第i行非0元素的個(gè)數(shù)之和 (B)第i列非0元素的個(gè)數(shù)之和 (C)第i行0元素的個(gè)數(shù)之和 (D)第i列0元素的個(gè)數(shù)之和設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（B）個(gè)表頭結(jié)點(diǎn)。 (A)2n (B)n (C)n/2 (D)n(n-1)設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有（B）條邊。 (A)n (B)n-1 (C)2n (D)2n-1設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（C）。 (A)40，42，60，55，80，85 (B)42，45，55，60，85，80 (C)42，40，55，60，80，85 (D)42，40，60，85，55，80（B）二叉排序樹可以得到一個(gè)從小到大的有序序列。 (A)先序遍歷 (B)中序遍歷 (C)后序遍歷 (D)層次遍歷設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（B）。 (A)2i+1 (B)2i (C)i/2 (D)2i-1程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時(shí)間復(fù)雜度為（A）。 (A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(n3/2)設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（C）。 (A)head==0 (B)head->next==0 (C)head->next==head (D)head!=0設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（C）。 (A)20 (B)256 (C)512 (D)1024設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（B）。 (A)1 (B)2 (C)3 (D)4設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（D）。 (A)top=top+1; (B)top=top-1; (C)top->next=top; (D)top=top->next;建立一個(gè)長度為n的有序單鏈表的時(shí)間復(fù)雜度為（C） (A)O(n) (B)O(1) (C)O(n2) (D)O(log2n)設(shè)某散列表的長度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇（B）。 (A)99 (B)97 (C)91 (D)93在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（B）。 (A)O(n) (B)O(log2n) (C)O(log2n) (D)O(n2)設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)?C)。 (A)A[1]，A[2]，A[3]，A[4] (B)A[1]，A[14]，A[7]，A[4] (C)A[7]，A[3]，A[5]，A[4] (D)A[7]，A[5]，A[3]，A[4]設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（B）。 (A)8 (B)7 (C)6 (D)5設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（C）個(gè)度數(shù)為0的結(jié)點(diǎn)。 (A)5 (B)6 (C)7 (D)8設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（A）。 (A)aedfcb (B)acfebd (C)aebcfd (D)aedfbc下列程序段的時(shí)間復(fù)雜度為（A）。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A)O(m*n*t) (B)O(m+n+t) (C)O(m+n*t) (D)O(m*t+n)設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動（A）個(gè)元素。 (A)n-i (B)n+l-i (C)n-1-i (D)i設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（A）。(A)N1-1 (B)N2-1(C)N2+N3 (D)N1+N3利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（C）。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(log2n)設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（D）。 (A)p->right=s；s->left=p；p->right->left=s；s->right=p->right； (B)s->left=p；s->right=p->right；p->right=s；p->right->left=s； (C)p->right=s；p->right->left=s；s->left=p；s->right=p->right； (D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（D）。 (A)快速排序 (B)堆排序 (C)歸并排序 (D)冒泡排序設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（C）。 (A)n-i (B)n-1-i (C)n+l-i (D)不能確定設(shè)散列表中有m個(gè)存儲單元，散列函數(shù)H(key)=key%p，則p最好選擇（B）。 (A)小于等于m的最大奇數(shù) (B)小于等于m的最大素?cái)?shù) (C)小于等于m的最大偶數(shù) (D)小于等于m的最大合數(shù)設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（C）個(gè)。 (A)4 (B)5 (C)6 (D)7設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（A）條邊。(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)(n-1)/2設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為（C）。 (A)n (B)n/2 (C)(n+1)/2 (D)(n-1)/2設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（C）次比較。 (A)1 (B)2 (C)3 (D)4設(shè)順序線性表的長度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長度為（D）。 (A)6 (B)11 (C)5 (D)6.5設(shè)有向無環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ˋ）。 (A)1，2，3，4 (B)2，3，4，1 (C)1，4，2，3 (D)1，2，4，3設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（A）。 (A)4 (B)5 (C)6 (D)7下列程序段的時(shí)間復(fù)雜度為（A）。i=0，s=0；while(s<n){s=s+i；i++；} (A)O(n1/2) (B)O(n1/3) (C)O(n) (D)O(n2)設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（D）存儲方式最節(jié)省運(yùn)算時(shí)間。 (A)單向鏈表 (B)單向循環(huán)鏈表(C)雙向鏈表 (D)雙向循環(huán)鏈表設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為（B）。(A)s->next=p->next；p->next=-s； (B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p； (D)p->next=s；s->next=q；設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（B）。(A)5，3，4，6，1，2 (B)3，2，5，6，4，1(C)3，1，2，5，4，6 (D)1，5，4，6，2，3設(shè)有一個(gè)10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個(gè)存儲單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（B）。 (A)10 (B)19 (C)28 (D)55設(shè)一棵m叉樹中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，……，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹中共有（D）個(gè)葉子結(jié)點(diǎn)。 (A) (B) (C) (D)二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（A）根結(jié)點(diǎn)的值。 (A)< (B)> (C)= (D)!=設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（D）。 (A)129 (B)219 (C)189 (D)229設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（D）次線性探測。 (A)n2 (B)n(n+1) (C)n(n+1)/2 (D)n(n-1)/2設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（C）個(gè)結(jié)點(diǎn)。 (A)2n (B)n+l (C)2n-1 (D)2n+l設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過（B）趟插入排序可以得到有序序列。 (A)6 (B)7 (C)8 (D)9設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（D）。(A)F，H，C，D，P，A，M，Q，R，S，Y，X(B)P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C)A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D)H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。（C）(A)688(B)678(C)692(D)696若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為（D）。(A)1，2，3 (B)9，5，2，3(C)9，5，3 (D)9，4，2，3對n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為（C）。(A)O（1）(B)O（n）(C)O（1og2n）(D)O（n2）對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（D）個(gè)。(A)1(B)2(C)3(D)4設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（A）條邊才能確保是一個(gè)連通圖。(A)5(B)6(C)7(D)8設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（B）個(gè)空指針域。 (A)2m-1 (B)2m (C)2m+1 (D)4m二、判斷題數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。（）鏈表的每個(gè)結(jié)點(diǎn)都恰好有一個(gè)指針。（）同一組不重復(fù)輸入序列執(zhí)行不同的入棧出棧組合操作，所得結(jié)果也可能相同。（）改進(jìn)的KMP算法中，字符串”abaaaba”的nextval數(shù)組值是0101110。（）用六叉鏈表表示30個(gè)結(jié)點(diǎn)的六叉樹，則樹中共有151個(gè)空指針。（）數(shù)組是一種線性結(jié)構(gòu)，因此只能用來存儲線性表。（）若有向圖不存在回路，即使不用訪問標(biāo)志位同一結(jié)點(diǎn)也不會被訪問兩次。（）若裝填因子a為1，則向散列表中散列元素時(shí)一定會產(chǎn)生沖突。（）若把堆看成是一個(gè)完全二叉樹，則該樹一定是一棵排序二叉樹。（）外排中使用置換選擇排序的目的，是為了增加初始?xì)w并段的長度。（）抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。（Y）線性表的插入和刪除總是伴隨著大量數(shù)據(jù)的移動。（N）隊(duì)列在程序調(diào)用是必不可少，因此遞歸離不開隊(duì)列。（N）字符串’aababaaaba’(Y)二叉樹中有雙子女的父結(jié)點(diǎn)，在中序遍歷中后繼一定是其中一個(gè)子女結(jié)點(diǎn)。（N）不用遞歸就不能實(shí)現(xiàn)二叉樹的前序遍歷。（N）若有向圖有n個(gè)頂點(diǎn)，則其強(qiáng)連通分量最多有n個(gè)。(Y)平衡二叉樹一定是一棵完全二叉樹。（N）若某內(nèi)部排序算法不穩(wěn)定，則該算法沒有使用價(jià)值。（N）倒排文件的目的是為了多關(guān)鍵字查找。(Y)已知指針curr指向鏈表中的某結(jié)點(diǎn)，執(zhí)行語句curr=curr->next；不會刪除該鏈表中的結(jié)點(diǎn)。()若二叉樹的葉結(jié)點(diǎn)數(shù)為1，則其高度等于結(jié)點(diǎn)數(shù)(僅含根結(jié)點(diǎn)的二叉樹高度為1)。（）按中序周游二叉樹時(shí)，某個(gè)結(jié)點(diǎn)的直接后繼是它的右子樹中第一個(gè)被訪問的結(jié)點(diǎn)。()完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。()向二叉檢索樹中插入一個(gè)新結(jié)點(diǎn)，需要比較的次數(shù)不可能大于此二叉樹的高度。()對一個(gè)堆按層次周游，一定能得到一個(gè)有序序列。()一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。()將一棵樹轉(zhuǎn)換為二叉樹表示后，該二叉樹的根結(jié)點(diǎn)沒有右子樹。()任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)湫蛄?，而且拓?fù)湫蛄胁晃ㄒ弧?)快速排序在最差情況下的時(shí)間復(fù)雜度是0(n2)，此時(shí)它的性能并不比冒泡排序更好。()AVL樹的任何子樹都是AVL樹。（Y）用相鄰矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。（N）霍夫曼樹一定是滿二叉樹。（Y）棧是一種線性結(jié)構(gòu)。（Y）B＋樹既適于隨機(jī)檢索，也適于順序檢索。（N）記錄是數(shù)據(jù)處理的最小單位。（）數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。()算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(Y)算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實(shí)際上就是程序了。（）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲形式。(Y)數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。（）在順序存儲結(jié)構(gòu)中，有時(shí)也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（）順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。（）數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨(dú)立。(Y)數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲存結(jié)構(gòu).（）數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。(Y)線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。(Y)線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。()棧和隊(duì)列邏輯上都是線性表。(Y)單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。()設(shè)串S的長度為n,則S的子串個(gè)數(shù)為n(n+1)/2。(Y)一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。(Y)（101，88，46，70，34，39，45，58，66，10）是堆。......(Y)將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有左子樹。()用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷。(Y)即使對不含相同元素的同一輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。()哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離很較近。(Y)數(shù)據(jù)的基本單位是數(shù)據(jù)項(xiàng)。()帶權(quán)的無向連通圖的最小生成樹是唯一的。()數(shù)組元素之間的關(guān)系，既不是線性的，也不是樹形的。()對于有n個(gè)對象的待排序序列進(jìn)行歸并排序，所需平均時(shí)間為O（nlog2n）。(Y)用鄰接矩陣法存儲一個(gè)圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)。(Y)在霍夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對于這種情況應(yīng)當(dāng)特殊處理。()線性表采用順序存儲表示時(shí)，必須占用一片連續(xù)的存儲單元。(Y)由樹轉(zhuǎn)化成二叉樹，其根的右子女指針總是空的。(Y)直接選擇排序是一種穩(wěn)定的排序方法。()裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿程度。(Y)若一個(gè)棧的輸入序列為123…n，其輸出序列的第一個(gè)元素為n，則其輸出序列的每個(gè)元素ai一定滿足ai=n-i+1。(i=1,2,...,n)（Y）二叉樹中的葉子結(jié)點(diǎn)就是二叉樹中沒有左右子樹的結(jié)點(diǎn)。（N）一棵樹中的葉子結(jié)點(diǎn)數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)點(diǎn)數(shù)。（N）刪除二叉排序樹中的一個(gè)結(jié)點(diǎn)，再重新插入上去，一定能得到原來的二叉排序樹。（N）線性表就是順序表。（N）若一棵樹中某結(jié)點(diǎn)的度為1，則該結(jié)點(diǎn)僅有一棵子樹。（Y）所謂平衡二叉樹是指左右子樹的高度差的絕對值不大于1的二叉樹。（N）AOE網(wǎng)所表示的工程至少所需的時(shí)間等于從源點(diǎn)到匯點(diǎn)的最短路徑的長度。（N）若某二叉樹的葉子結(jié)點(diǎn)數(shù)為1，則其先序序列和后序序列一定相反。（Y）在采用線性探測法處理沖突的散列表中，所有的同義詞在表中相鄰。（N）對B-樹中任一非葉子結(jié)點(diǎn)中的某關(guān)鍵字K，比K小的最大關(guān)鍵字和比K大的最小關(guān)鍵字一定都在非葉結(jié)點(diǎn)的最下層。（Y）若一個(gè)連通無向圖的以頂點(diǎn)1為起點(diǎn)的深度遍歷序列唯一，則可唯一確定該圖。（Y）若一個(gè)有向圖的以頂點(diǎn)1為起點(diǎn)的深度遍歷序列唯一，則可唯一確定該圖。（N）在數(shù)據(jù)表基本有序時(shí)，冒泡排序算法的時(shí)間復(fù)雜度一定接近O(n)。（N）設(shè)指針p指向單鏈表中的一個(gè)結(jié)點(diǎn)，則語句序列u:=p^.next;u:=u^.next將刪除一個(gè)結(jié)點(diǎn)。（N）線性表的長度是線性表所占用的存儲空間的大小。（N）雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。（N）在對鏈隊(duì)列做出隊(duì)操作時(shí)，不會改變front指針的值。（N）如果兩個(gè)串含有相同的字符，則說它們相等。（N）如果二叉樹中某結(jié)點(diǎn)的度為1，則說該結(jié)點(diǎn)只有一棵子樹。（Y）已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。（N）圖G的一棵最小代價(jià)生成樹的代價(jià)未必小于G的其它任何一棵生成樹的代價(jià)。（Y）圖G的拓?fù)湫蛄形ㄒ?，則其弧數(shù)必為n-1（其中n為頂點(diǎn)數(shù)）。（N）9.對一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列。（Y）10.直接選擇排序算法滿足：其時(shí)間復(fù)雜度不受數(shù)據(jù)的初始特性影響，為O(n2)。（Y）如果兩個(gè)串含有相同的字符，則這兩個(gè)串相等。（N）數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對它進(jìn)行插入、刪除等運(yùn)算。（N）在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個(gè)數(shù)有關(guān)，而且與每一塊中元素個(gè)數(shù)有關(guān)。（Y）在順序表中取出第i個(gè)元素所花費(fèi)的時(shí)間與i成正比。（N）在棧滿情況下不能作進(jìn)棧運(yùn)算，否則產(chǎn)生“上溢”。(Y）二路歸并排序的核心操作是將兩上有序序列歸并為一個(gè)有序序列。（Y）對任意一個(gè)圖，從它的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個(gè)頂點(diǎn).（N）二叉排序樹或者是一棵空二叉樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值;若它的右子樹非空，則根結(jié)點(diǎn)的值小于其右孩子的值。（N）在執(zhí)行某個(gè)排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（N）一個(gè)有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)一定相等。（Y）算法與程序的主要區(qū)別是算法滿足有窮性??并且算法不一定用機(jī)器可執(zhí)行的程序設(shè)計(jì)語言書寫。（Y）某線性表采用順序存儲結(jié)構(gòu)??元素長度為4??首地址為100??則下標(biāo)為12的??第13個(gè)??元素的存儲地址為148。（Y）在任何一種線性鏈表上都無法進(jìn)行隨機(jī)訪問。（N）順序棧是一種規(guī)定了元素進(jìn)棧順序的棧。（N）循環(huán)列表中每一個(gè)元素都有后繼。（Y）樹的先根遍歷與該樹對應(yīng)二叉樹的前序遍歷結(jié)果不同。（N）任何有向網(wǎng)絡(luò)??AOV網(wǎng)絡(luò)??拓?fù)渑判虻慕Y(jié)果是唯一的。（N）無向圖中的連通分量定義為無向圖的極大連通子圖。（Y）刪除一個(gè)二叉樹中的一個(gè)結(jié)點(diǎn)??再重新插入上去??一定能得到原來的二叉排序樹。（N）數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)間的邏輯結(jié)構(gòu)??數(shù)據(jù)的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方面的內(nèi)容。（Y）在動態(tài)單向鏈表中??每個(gè)結(jié)點(diǎn)總是占用一片連續(xù)的內(nèi)存空間。（N）高級語言中通常利用“遞歸工作?！眮硖幚磉f歸。（Y）中綴表示式??a+b??*(c+d)的后綴形式為ab+cd+*。（Y）棧和隊(duì)列都不適合用散列存儲法存儲。（N）廣義表的深度與廣義表中含有多少個(gè)子表元素有關(guān)。（Y）如果樹用二叉樹鏈表表示??則判斷某個(gè)結(jié)點(diǎn)是不是樹葉的條件是該結(jié)點(diǎn)左??右兩個(gè)指針域的值都為空。（Y）一組關(guān)鍵碼已完全有序時(shí)??最快的排序方法是快速排序。（Y）n個(gè)結(jié)點(diǎn)的無向圖最多有n*(n-1)/2條邊。（Y）線性結(jié)構(gòu)中的結(jié)點(diǎn)按前驅(qū)??后繼關(guān)系可以排成一個(gè)線性序列。（Y）在動態(tài)單向鏈表中??每個(gè)結(jié)點(diǎn)總是占用一片連續(xù)的內(nèi)存空間。（N）算法的有窮性是指一個(gè)算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。（Y）后綴表達(dá)式ABC+*的中綴形式為A*??B+C??。（Y）對順序棧進(jìn)行插入??刪除操作??不涉及元素的前后移動問題。（N）廣義表的長度是廣義表中元素的個(gè)數(shù)。（Y）在任何一棵完全二叉樹中??葉結(jié)點(diǎn)的個(gè)數(shù)或者和分支結(jié)點(diǎn)一樣多，或者只比分支結(jié)點(diǎn)多一個(gè)。（Y）直接選擇排序是一種穩(wěn)定的排序方法。（N）n個(gè)頂點(diǎn)的生成樹中有n-1條邊。（Y）有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。(錯(cuò))對鏈表進(jìn)行插入和刪除操作時(shí)不必移動鏈表中結(jié)點(diǎn)。(對)子串“ABC”在主串“AABCABCD”中的位置為2。(對)若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。(對)希爾排序算法的時(shí)間復(fù)雜度為O(n2)。(錯(cuò))用鄰接矩陣作為圖的存儲結(jié)構(gòu)時(shí)，則其所占用的存儲空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。(錯(cuò))中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。(對)入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。(對)順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。（錯(cuò)）堆是完全二叉樹，完全二叉樹不一定是堆。（對）調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（錯(cuò)）分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（對）冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（對）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（對）設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（錯(cuò)）層次遍歷初始堆可以得到一個(gè)有序的序列。（錯(cuò)）設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（對）線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（錯(cuò)）中序遍歷二叉排序樹可以得到一個(gè)有序的序列。（對）快速排序是排序算法中平均性能最好的一種排序。（對）不論是入隊(duì)列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（對）當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（對）設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（對）完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（對）哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。（對）對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（對）先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。（對）由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（錯(cuò)）線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（錯(cuò)）帶權(quán)無向圖的最小生成樹是唯一的。（錯(cuò)）如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（對）設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（錯(cuò)）分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。（對）二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（錯(cuò)）向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（錯(cuò)）如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（對）非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（對）不論線性表采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（對）圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。（對）稀疏矩陣的壓縮存儲可以用一個(gè)