數(shù)據(jù)結(jié)構(gòu)習(xí)題庫匯總

知識點：01．緒論02．順序表03．鏈表04．棧05．鏈隊列06．循環(huán)隊列07．串08．?dāng)?shù)組的順序表示09．稀疏矩陣10．廣義表11．二叉樹的基本概念12．二叉樹遍歷、二叉樹性質(zhì)13．樹、樹與二叉樹的轉(zhuǎn)換14．赫夫曼樹15．圖的定義、圖的存儲16．圖的遍歷17．圖的生成樹18．靜態(tài)查找（順序表的查找、有序表的查找）19．動態(tài)查找（二叉排序樹、平衡樹、B樹）20．哈希查找21．插入排序（直接插入、折半插入、2路插入、希爾排序）22．選擇排序（簡單選擇、樹形選擇、堆排序）23．快速排序、歸并排序

101A1（1）．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是（A）。A．?dāng)?shù)據(jù)的組織形式B．?dāng)?shù)據(jù)的存儲形式C．?dāng)?shù)據(jù)的表示形式D．?dāng)?shù)據(jù)的實現(xiàn)形式101A1（2）．組成數(shù)據(jù)的基本單位是（C）。A．?dāng)?shù)據(jù)項B．?dāng)?shù)據(jù)類型C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)變量101B1（3）．與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲密度（B）。A．大B．小C．相同D．以上都不對101B2（4）．對于存儲同樣一組數(shù)據(jù)元素而言，（D）。A．順序存儲結(jié)構(gòu)比鏈接結(jié)構(gòu)多占空間B．在順序結(jié)構(gòu)中查找元素的速度比在鏈接結(jié)構(gòu)中查找要快C．與鏈接結(jié)構(gòu)相比，順序結(jié)構(gòu)便于安排數(shù)據(jù)元素D．順序結(jié)構(gòu)占用整塊空間而鏈接結(jié)構(gòu)不要求整塊空間101B2（5）．下面程序的時間復(fù)雜度為（B）。x=0；for（i=1；i<n；i++）for（j=i+1；j<=n；j++）x++；A．O（）B．O（n2）C．O（1）D．O（n）101B2（6）．下面程序的時間復(fù)雜度為（C）。for（i=0；i<m；i++）for（j=0；j<n；j++）A[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（m+n）101C2（7）．下面程序段的執(zhí)行次數(shù)為（B）。for（i=0；i<n-1；i++）for（j=0；j>i；j++）state；A．n（n+1）/2B．（n-1）（n+2）/2C．n（n+1）/2D．（n-1）（n+2）101D3（8）．下面程序的時間復(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）102A1（9）．順序表的特點是（B）。A．表中元素的個數(shù)為表長B．按順序方式存儲數(shù)據(jù)元素C．邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰D．按表中元素的次序存儲102C2（10）．設(shè)順序表共有n個元素，用數(shù)組elem存儲，實現(xiàn)在第i個元素之前插入一個元素e的操作，其主要語句為（D）。A．FORj=nDOWNTOiDOelem[j]=elem[j+1]；elem[i]=e；B．FORj=iTOnDOelem[j]=elem[j+1]；elem[i]=e；C．FORj=iTOnDOelem[j+1]=elem[j]；elem[i]=e；D．FORj=nDOWNTOiDOelem[j+1]=elem[j]；elem[i]=e；102D2（11）．順序表有5個元素，設(shè)在任何位置上插入元素是等概率的，則在該表中插入一個元素時所需移動元素的平均次數(shù)為（C）。A．3B．2C．2．5D．5102D2（12）．設(shè)順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數(shù)為（C）。A．9B．4．5C．7D．6102D3（13）．設(shè)順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節(jié)，則第14個元素的存儲地址為（B）。A．236B．239C．242D．245102D2（14）．設(shè)順序表的第5個元素的存儲地址為200，且每個元素占一個存儲單元，則第14個元素的存儲地址為（B）。A．208B．209C．210D．214103D3（15）．設(shè)p為指向雙向循環(huán)鏈表中某個結(jié)點的指針，p所指向的結(jié)點的兩個鏈域分別用p->llink和p->rlink表示，則下列等式中（D）成立。A．p=p->llinkB．p=p->rlinkC．p=p->llink->llinkD．p=p->llink->rlink103A1（16）．線性表采用鏈?zhǔn)酱鎯r，其地址（D）。A．必須是連續(xù)的B．一定是不連續(xù)的C．部分地址必須是連續(xù)的D．連續(xù)與否均可以103B1（17）．線性表是（A）。A．一個有限序列，可以為空B．一個有限序列，不可以為空C．一個無限序列，可以為空D．一個無限序列，不可以為空103B1（18）．鏈?zhǔn)酱鎯Φ木€性表中的指針指向其（B）。A．前趨結(jié)點B．后繼結(jié)點C．物理前趨D．物理后繼103C2（19）．設(shè)在鏈?zhǔn)酱鎯Φ木€性表中，設(shè)結(jié)點結(jié)構(gòu)為datalink，欲在p結(jié)點后插入一個結(jié)點q的關(guān)鍵步驟為（A）。A．q->link=p->link；p->link=q；B．p->link=q->link；p->link=q；C．q->link=p->link；q->link=p；D．p->link=q->link；q->link=p；103C3（20）．設(shè)有指針head指向的帶表頭結(jié)點的單鏈表，現(xiàn)將指針p指向的結(jié)點插入表中，使之成為第一個結(jié)點，其操作是（A）（其中，p->next、head->next分別表示p、head所指結(jié)點的鏈域）。A．p->next=head->next；head->next=p；B．p->next=head->next；head=p；C．p->next=head；head=p；D．p->next=head；p=head；104A1（21）．在棧中，下列說法正確的是（A）。A．每次插入總是在棧頂，每次刪除也總是在棧頂。B．每次插入總是在棧頂，每次刪除總是在棧底。C．每次插入總是在棧底，每次刪除總是在棧頂。D．每次插入總是在棧底，每次刪除也總是在棧底。104B2（22）．設(shè)有一個棧，按A、B、C的順序進棧，則下列（C）為不可能的出棧序列。A．ABCB．CBAC．CABD．ACB104B2（23）．設(shè)有一個棧，按A、B、C、D的順序進棧，則下列（D）為可能的出棧序列。A．DCABB．CDABC．DBACD．ACDB104A2（24）．順序棧的上溢是指（B）。A．棧滿時作退棧運算B．棧滿時作進棧運算C．?？諘r作退棧運算D．?？諘r作進棧運算104D3（25）．順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進棧操作的主要語句為（D）。A．s．elem[top]=e；s．top=s．top+1；B．s．elem[top+1]=e；s．top=s．top+1；C．s．top=s．top+1；s．elem[top+1]=e；D．s．top=s．top+1；s．elem[top]=e；104C2（26）．設(shè)有5個元素A，B，C，D，E順序進棧（進棧過程中可以出棧），出棧后依出棧次序進入隊列，已知其出隊次序為D，C，E，B，A，則該棧容量必定不小于（C）。A．2B．3C．4D．5104B2（27）．設(shè)棧S的初始狀態(tài)為空，現(xiàn)有五個元素組成的序列1，2，3，4，5，對該序列在棧S上依次進行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出棧的元素序列是（C）。A．5，4，3，2，1B．2，1C．2，3D．3，4104B2（28）．在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top為棧頂指針，則當(dāng)做出棧處理時，top變化為（C）。A．top不變B．top=0C．top--D．top++104D3（29）．向一個棧頂指針為hs的鏈棧中插入一個*s結(jié)點時，應(yīng)執(zhí)行（B）。A．hs->next=s；B．s->next=hs；hs=s；C．s->next=hs->next；hs->next=s；D．s->next=hs；hs=hs->next；105A1（30）．在隊列中，下列說法正確的是（A）。A．每次插入總是在隊尾，每次刪除總是在隊頭。B．每次插入總是在隊尾，每次刪除也總是在隊尾。C．每次插入總是在隊頭，每次刪除也總是在隊頭。D．每次插入總是在隊頭，每次刪除總是在隊尾。105D3（31）．在帶頭結(jié)點的鏈隊列q中，用q．front表示隊頭指針，q．rear表示隊尾指針，結(jié)點結(jié)構(gòu)為datanext，刪除鏈隊列的隊頭結(jié)點的主要語句為（B）。A．s=q．front；q．front->next=s．next；B．s=q．front->next；q．front->next=s．next；C．s=q．front->next；q．front=s．next；D．s=q；q．front->next=s．next；106C3（32）．循環(huán)隊列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sq．front指示隊頭元素的前一個位置，sq．rear指示隊尾元素的當(dāng)前位置，隊列的最大容量為MAXSIZE，則隊列滿的條件為（D）。A．sq．front=sq．rearB．sq．front=sq．rear+1C．（sq．front+1）modMAXSIZE=sq．rearD．（sq．rear+1）modMAXSIZE=sq．front106C2（33）．循環(huán)隊列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sq．front指示隊頭元素的前一個位置，sq．rear指示隊尾元素的當(dāng)前位置，隊列的最大容量為MAXSIZE，則在隊列未滿時元素x入隊列的主要操作為（A）。A．sq．rear=（sq．rear+1）modMAXSIZE；sq．elem[sq．rear]=x；B．sq．elem[sq．rear]=x；sq．rear=（sq．rear+1）modMAXSIZE；C．sq．front=（sq．front+1）modMAXSIZE；sq．elem[sq．front]=x；D．sq．elem[sq．front]=x；sq．front=sq．front+1；106B2（34）．循環(huán)隊列sq中，用數(shù)組elem[0‥25]存放數(shù)據(jù)元素，sq．front指示隊頭元素的前一個位置，sq．rear指示隊尾元素的當(dāng)前位置，設(shè)當(dāng)前sq．front為20，sq．rear為12，則當(dāng)前隊列中的元素個數(shù)為（D）。A．8B．16C．17D．18106B2（35）．設(shè)循環(huán)隊列的元素存放在一維數(shù)組Q[0‥30]中，隊列非空時，front指示隊頭元素的前一個位置，rear指示隊尾元素。如果隊列中元素的個數(shù)為11，front的值為25，則rear應(yīng)指向（B）元素。A．Q[4]B．Q[5]C．Q[14]D．Q[15]105A1（36）．隊列操作的原則是（A）。A．先進先出B．后進先出C．只能進行插入D．只能進行刪除105B2（37）．一個隊列的入列序列是1234，則隊列的輸出序列是（B）。A．4321B．1234C．1432D．3241108C2（38）．設(shè)6行8列的二維數(shù)組A6×8=（aij）按行優(yōu)先順序存儲，若第一個元素的存儲位置為200，且每個元素占3個存儲單元，則元素a54的存儲位置為（B）。A．308B．305C．266D．269109C2（39）．設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1，每元素占1個地址空間，則a85的地址為（B）。A．13B．33C．18D．40108A1（40）．設(shè)二個數(shù)組為A[0‥7]、B[-5‥2，3‥8]，則這兩個數(shù)組分別能存放的字符的最大個數(shù)是（C）。A．7和35B．1和5C．8和48D．1和6108C3（41）．二維數(shù)組M[i，j]的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下列j的范圍從0到5。M按行存儲時元素M[3，5]的起始地址與M按列存儲時元素（B）的起始地址下同。A．M[2，4]B．M[3，4]C．M[3，5]D．M[4，4]108C2（42）．設(shè)二維數(shù)組為M[0‥8，0‥10]，每個元素占2L個存儲單元，以行序為主序存儲，第一個元素的存儲位置為P。存儲位置為P+50L的元素為（A）。A．M[2，3]B．M[2，2]C．M[3，3]D．M[3，4]108C2（43）．設(shè)二維數(shù)組A的維數(shù)界偶定義為[1‥8，0‥10]，起始地址為LOC，每個元素占2L個存儲單元，以行序為主序存儲方式下，某數(shù)據(jù)元素的地址為LOC+50L，則在列序為主序存儲方式下，該元素的存儲地址為（D）。A．LOC+28LB．LOC+36LC．LOC+50LD．LOC+52L109B2（44）．?dāng)?shù)組A[1‥40，1‥30]采用三元組表示，設(shè)數(shù)組元素與下標(biāo)均為整型，則在非零元素個數(shù)小于（D）時，才能節(jié)省存儲空間。A．1200B．401C．399D．400108A1（45）．一維數(shù)組通常采用順序存儲結(jié)構(gòu)，這是因為（C）。A．一維數(shù)組是一種線性數(shù)據(jù)結(jié)構(gòu)B．一維數(shù)組是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)C．一旦建立了數(shù)組，則數(shù)組中的數(shù)據(jù)元素之間的關(guān)系不再變動D．一維數(shù)組只能采用順序存儲結(jié)構(gòu)109A1（46）．對稀疏矩陣進行壓縮存儲的目的是（B）。A．方便存儲B．節(jié)省存儲空間C．方便運算D．節(jié)省運算時間108D3（47）．設(shè)二維數(shù)組a[0‥5，0‥6]按行存儲，每個元素占d個存儲單元，如果每個元素改為2d個存儲單元，起始地址不變，則元素a[2，6]的存儲地址將要增加（A）個存儲單元。A．20dB．21dC．38dD．39d108B2（48）．一維數(shù)組與線性表的區(qū)別是（A）。A．前者長度固定，后者長度可變B．后者長度固定，前者長度可變C．兩者長度均固定D．兩者長度均可變107A1（49）．下列關(guān)于串的敘述中，不正確的是（B）。A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?07B2（50）．以下論斷正確的是（A）。A．“”是空串，“”是空白串B．“BEIJING”是“BEIJING”的子串C．“something”<“Somethig”D．”BIT”=”BITE”107B2（51）．字符串“VARTYPEunsignedint”若采用動態(tài)分配的順序存儲方法需要（C）個字節(jié)（假設(shè)每種數(shù)據(jù)均占用2個字節(jié)）。A．38B．動態(tài)產(chǎn)生，視情況而定C．40D．42111A1（52）．由3個結(jié)點可以構(gòu)造出（A）種不同形態(tài)的有向樹。A．2B．3C．4D．5111A1（53）．下列樹的度為（B）。A．2B．3C．5D．8112C2（54）．含10個結(jié)點的二叉樹中，度為0的結(jié)點有4個，則度為2的結(jié)點有（A）個。A．3B．4C．5D．6111B2（55）．對一棵有100個結(jié)點的完全二叉樹按層編號，則編號為49的結(jié)點，它的左孩子的編號為（A）。A．98B．99C．97D．50112B2（56）．一棵深度為8（根的層次號為1）的滿二叉樹有（B）個結(jié)點。A．256B．255C．128D．127112C3（57）．設(shè)二叉樹根結(jié)點的層數(shù)為1，若一棵高（深）度為h的二叉樹只有度為0與度為2的結(jié)點，則其結(jié)點數(shù)至少為（B）。A．hB．2h-1C．2hD．2h+1112C2（58）．對下列二叉樹進行先根次序遍歷，所得次序為（A）。A．ABCDEFB．ADCBFEC．BCDAFED．DCBFEA112D3（59）．一棵二叉樹的前（先）序序列為ABCDEFG，則它的中序序列不可能為（C）。A．CBDAFEGB．DCBAEFGC．CDBAGEFD．BDCAFGE112A1（60）．若先序遍歷二叉樹的結(jié)果為結(jié)點序列A，B，C，則有（C）棵不同的二叉樹可以得到這一結(jié)果。A．3B．4C．5D．6111B2（61）．具有n個結(jié)點的二叉樹，有（B）條邊。A．nB．n-1C．n+1D．2n112C2（62）．在具有n個結(jié)點的二叉樹的二叉鏈表表示中，2n個孩子指針域中，只用到（B）個域。A．nB．n-1C．n+1D．2n114B2（63）．對哈夫曼樹，下列說法錯誤的是（B）。A．哈夫曼樹是一類帶樹路徑長度最短的樹。B．給出一組數(shù)，構(gòu)造的哈夫曼樹唯一。C．給出一組數(shù)，構(gòu)造的哈夫曼樹的帶樹路徑長度不變。D．哈夫曼樹的帶權(quán)路徑長度為每個葉子的路徑長度與該葉子權(quán)值乘積之和。111D3（64）．假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15個，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為（B）。A．15B．16C．17D．47113C3（65）．假定一棵三叉樹的結(jié)點數(shù)為50，則它的最小高度為（C）。A．3B．4C．5D．6114B2（66）．由帶權(quán)為9，2，5，7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（D）。A．23B．37C．46D．44112C2（67）．二叉樹的先序遍歷為EFHIGJK，中序遍歷為HFIEJKG，則該二叉樹根的右子樹的根是（C）。A．EB．FC．GD．H111A1（68）．在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒有（C）。A．左孩子結(jié)點B．右孩子結(jié)點C．左孩子和右孩子結(jié)點D．左孩子結(jié)點，右孩子結(jié)點和兄弟結(jié)點113B2（69）．（B）二叉樹，可以唯一地轉(zhuǎn)化成一棵一般樹。A．根結(jié)點無左孩子B．根結(jié)點無右孩子C．根據(jù)結(jié)點有兩個孩子D．沒有一棵111C2（70）．具有65個結(jié)點的完全二叉樹其深度為（B）。A．8B．7C．6D．5112C2（71）．某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（B）的二叉樹。A．空或只有一個結(jié)點B．高度等于其結(jié)點數(shù)C．任一結(jié)點無左孩子D．任一結(jié)點無右孩子113A1（72）．下面敘述中，不正確的是（C）。A．線性表中除第一個元素和最后一個元素外，其他每個元素都有且僅有一個直接前驅(qū)和一個直接后繼B．樹中有且僅有一個結(jié)點沒有前驅(qū)C．環(huán)形隊列中任何一個元素都有且僅有一個直接前驅(qū)和一個直接后繼D．在樹中，一個結(jié)點可以有多個直接后繼114B2（73）．有m個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)是（C）。A．2mB．2m+1C．2m-1D．2（m+1）115A1（74）．設(shè)圖的鄰接矩陣為，則該圖有（A）個頂點。A．3B．4C．6D．9115B2（75）．設(shè)圖的鄰接矩陣為，則該圖為（A）。A．有向圖B．無向圖C．強連通圖D．完全圖115B2（76）．設(shè)圖的鄰接鏈表如下圖所示，則該圖有（B）條邊。1V1234^2V2134^3V312^4V412^A．4B．5C．10D．20115C2（77）．設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（B）條邊才能確保是一個連通圖。A．5B．6C．7D．8116D3（78）．已知一有向圖的鄰接表存儲結(jié)構(gòu)如下，則根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點V1出發(fā)，不能得到的頂點序列是（C）。1324^2^345^4^524^A．V1V2V3V5V4B．V1V3V4V5V2C．V1V2V4V5V3D．V1V4V3V5V2119C3（79）．下列圖的深度優(yōu)先遍歷序列為（B）。ABCDEFGHA．ABCDEFGHABCDEFGH115B1（80）．對一個具有n個頂點的圖，采用鄰接矩陣表示則該矩陣的大小為（D）。A．nB．（n-1）2C．（n+1）2D．n2118B2（81）．對含n個記錄的順序表進行順序查找，在最壞情況下需要比較（B）次。A．n-1B．nC．（n+1）/2D．n（n-1）/2118B2（82）．對含n個記錄的有序表進行折半查找，設(shè)每個記錄的查找概率相等，則平均查找長度的數(shù)量級為（C）。A．O（n）B．O（n2）C．O（）D．O（1）119B2（83）．有一棵二叉樹如下圖，該樹是（B）。5020951030557085A．二叉平衡樹B．二叉排序樹C．堆的形狀D．以上都不是119C3（84）．已知10個數(shù)據(jù)元素（50，30，15，35，70，65，95，60，25，40），按照依次插入結(jié)點的方法生成一棵二叉排序樹后，在查找成功的情況下，查找每個元素的平均比較次數(shù)（又稱平均查找長度）為（C）。A．2.5B．3.2C．2.9D．2.7118C3（85）．在順序存儲的線性表R[0‥29]上進行分塊查找（設(shè)分為5塊）的平均查找長度為（D）。A．6B．11C．5D．6.5120D3（86）．已知一個線性表（38，25，74，63，52，48），假定采用h（k）=k%7計算散列地址進行散列存儲，若引用線性探測的開放定地址法解決沖突，則在該散列表上進行查找的平均查找長度為（C）。A．1.5B．1.7C．2D．2.3119A1（87）．在一個3階的B-樹上，每個結(jié)點包含的子樹相同，最多為（C）。A．1B．2C．3D．4120B2（88）．設(shè)散列地址空間為0~m-1，k為關(guān)鍵字，用P去除k，將余數(shù)作為k的散列地址，即：h（k）=k%P，為了減少發(fā)生沖突的可能性，一般取P為（B）。A．小于m的最大奇數(shù)B．小于m的最大素數(shù)C．小于m的最大偶數(shù)D．小于m的最大合數(shù)120C3（89）．設(shè)散列表表長m=14，散列函數(shù)為h（k）=k%11，表中已有4個記錄，如果用二次探測再散列處理沖突，關(guān)鍵字為49的記錄的存儲地址是（D）。01234567891011121315386184A．8B．3C．5D．9119C3（90）．已知8個元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點的方法生成一棵二叉排序樹，該樹的深度為（C）。A．4B．5C．6D．7121B1（91）．直接插入排序算法的時間復(fù)雜度為（B）。A．O（n）B．O（n2）C．O（）D．O（1）121B2（92）．設(shè)記錄關(guān)鍵字序列為（84，67，21，50，33，79），采用對半插入排序方法自小到大進行排序時，記錄的移動次數(shù)為（C）。A．9B．10C．19D．25123D3（93）．下列四個序列中，（D）不是快速排序第一趟的可能結(jié)果。A．[68，11，69，23，18，70，73]93B．11[68，69，23，18，70，73，93]C．[68，11，69，23，18]70[93，73]D．[18，11，23]93[68，70，69，73]122C3（94）．下列四個關(guān)鍵字序列中，（C）不是堆。A．{05，23，16，68，94，72，71，73}B．{05，16，23，68，94，72，71，73}C．{05，23，16，73，94，72，71，68}D．{05，23，16，68，73，71，72，94}123B2（95）．從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列中的正確位置上，此方法稱為（D）。A．歸并排序B．選擇排序C．交換排序D．插入排序123B2（96）．在所有排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無關(guān)的是（D）。A．Shell排序B．冒泡排序C．直接插入排序D．直接選擇排序123B2（97）．下列排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（B）。A．選擇B．插入C．冒泡D．快速123C2（98）．采用下列排序算法對n個元素進行排序，其排序趟數(shù)肯定為n-1趟的排序方法有（A）。A．選擇和插入B．冒泡和快速C．插入和快速D．選擇和冒泡123D3（99）．若用冒泡排序方法對序列{10，14，26，29，41，52}從大到小進行排序，需要進行（C）次比較。A．5B．10C．15D．25121C3（100）．用直接插入排序方法對下面四個序列進行排序（由小到大），元素比較次數(shù)最少的是（C）。A．94，32，40，90，80，46，21，69B．32，40，21，46，69，94，90，80C．21，32，46，40，80，69，90，94D．90，69，80，46，21，32，94，40

二、填空題101A1（1）．?dāng)?shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（線性結(jié)構(gòu)和非線性結(jié)構(gòu)）。101A1（2）．算法的計算量的大小稱為（計算的復(fù)雜度）。102B2（3）．順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作的時間代價基本上都是等效的。則插入一個元素大約要移動表中的（n/2）個元素。103A2（4）．順序表相對于鏈表的優(yōu)點有（節(jié)省存儲）和（隨機存?。?。103B2（5）．線性表的長度是（表中數(shù)據(jù)元素的個數(shù)）。103D3（6）在帶有頭結(jié)點的雙鏈表L中，指針p所指結(jié)點是第一個元素結(jié)點的條件是（p=L->next；或L->next=p；）。103C3（7）．某鏈表如下所示infolinkpABCDE^若要刪除值為C的結(jié)點，應(yīng)做操作（p->link=p->link->link）。104A1（8）．對于棧只能在（棧頂）插入和刪除元素。104C2（9）．設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，6，經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（2、3）。106B2（10）．有一個循環(huán)隊列如下圖，其隊滿條件是（front=(rear+1)%n），隊列空的條件是（rear=front）。front…隊頭指針rear隊尾指針109B2（11）．一個稀疏矩陣為，則對應(yīng)的三元組線性表為（（（0，2，2），（1，0，3），（2，2，-1），（2，3，5）））。108C2（12）．設(shè)有二維數(shù)組A[0‥9，0‥19]，其每個元素占兩個字節(jié)，數(shù)組按列優(yōu)先順序存儲，第一個元素的存儲地址為100，那么元素A[6，6]的存儲地址為（232）。112B1（13）．在一棵二叉排序樹上按（中序）遍歷得到的結(jié)點序列是一個有序序列。111C3（14）．對于一棵具有n個結(jié)點的二叉樹，當(dāng)進行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為2n個，其中（n-1）個用于鏈接孩子結(jié)點。112B2（15）．對于下面的二叉樹，按后序遍歷得到的結(jié)點序列為（4，2，5，6，3，1）。123456115B1（16）．設(shè)無向圖G的頂點數(shù)為n，圖G最少有（0）邊。117C3（17）．對下列圖162534它的生成樹有（6）棵。118C3（18）．假定在有序表R[0‥19]上進行二分查找，則比較三次查找成功的結(jié)點數(shù)為（4）。120D3（19）．設(shè)有兩個散列函數(shù)H1（K）=Kmod13和H2（K）=Kmod11+1，散列表為T[0‥12]，用雙重散列法（又稱二次散列法）解決沖突。函數(shù)H1用來計算散列地址，當(dāng)發(fā)生沖突時，H2作為計算下一個探測地址的地址增量。假定某一時刻散列表T的狀態(tài)為：0123456789101112T：805534下一個被插入的關(guān)鍵碼為42，其插入位置是（0）。122C3（20）．已知一棵二叉排序樹如下圖所示，則在查找成功的情況下查找每個元素的平均查找長度為（2.75）。80509040701006075

三、完形填空題102D2（1）．設(shè)順序存儲的線性表存儲結(jié)構(gòu)定義為：structsequnce{ELEMTPelem[MAXSIZE]；intlen；/*線性表長度域*/}將下列簡單插入算法補充完整。voidinsert（structsequnce*p，inti，ELEMTPx）{v=*p；if（i<1）||（i>v.len+1）printf（“Overflow“）；else{for（j=v.len；j>=i；j--）v.elem[j+1]=v.elem[j]；v.elem[i]=x；v.len=v.len+1；}}103D3（2）．設(shè)線性鏈表的存儲結(jié)構(gòu)如下：structnode{ELEMTPdata；/*數(shù)據(jù)域*/structnode*next；/*指針域*/}試完成下列在鏈表中值為x的結(jié)點前插入一個值為y的新結(jié)點。如果x值不存在，則把新結(jié)點插在表尾的算法。voidinserty（structnode*head，ELEMTPx，ELEMTPy）{s=（structnode*）malloc（sizeof（structnode））；s->data=y；if（head->data==x）{s->nexr=head；head=s；}else{q=head；p=q->next；while（p->dqta!=x&&p->next!=NULL）{q=p；p=p->next；}if（p->data==x）{q->next=s；s->next=p；}else{p->next=s；s->next=NULL；}}}103D3（3）．設(shè)線性鏈表的存儲結(jié)構(gòu)如下：structnode{ELEMTPdata；/*數(shù)據(jù)域*/structnode*next；/*指針域*/}試完成下列建立單鏈表的算法。creat（）{charvar；head=（structnode*）malloc（sizeof（structnode））；head->next=NULL；while（（var=getchar（））！=‘\n’）{ptr=（structnode*）malloc（sizeof（structnode））；ptr->data=var；ptr->next=head->next；head->next=ptr；}}103D3（4）．下列算法將單鏈表中值重復(fù)的結(jié)點刪除，使所得的結(jié)果表中各結(jié)點值均不相同，試完成該算法。voidDelSameNode（LinkListL）//L是帶頭結(jié)點的單鏈表，刪除其中的值重復(fù)的結(jié)點//{ListNode*p，*q，*r；p=L->next；//p初始指向開始結(jié)點//while（p）{//處理當(dāng)前結(jié)點p//q=p；r=q->next；do{//刪除與結(jié)點*p的值相同的結(jié)點//while（r&&r->data!=p->data）{q=r；r=r->next；}if（r）{//結(jié)點*r的值與*p的值相同，刪除*r//q->next=r->next；free（r）；r=q->next；}}while（r）；p=p->next；}}106D3（5）假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針R指向隊尾元素結(jié)點（注意不設(shè)頭指針），下列為出隊一個元素的算法。DeList（R，e）LinkList*R，p；ElemTypee；{p=R->next->next；e=p->data；R->next->next=p->next；if（p==R）R=R->next；free（p）；}105D3（6）．鏈隊列的存儲結(jié)構(gòu)為：structnodetype{ELEMTPdata；structnodetype*next；}structlinkqueue{structnodetype*front，*rear；}/*front和rear分別為隊列的頭指針和尾指針*/完成下列刪除隊頭元素的算法。delq（structlinkqueue*r，ELEMTP*x）{q=*r；if（q.front==q.rear）printf（“QUEUEISEMPTY\n“）；else{p=q.front->next；q.front->next=p->next；if（p->next==NULL）q.rear=q.front；*x=p->data；free（p）；}111D3（7）．下面算法實現(xiàn)，用一棵二叉樹中的結(jié)點建立一個按關(guān)鍵字值從小到大次序排列的帶表頭結(jié)點的雙向循環(huán)鏈表。二叉樹的結(jié)點結(jié)構(gòu)如下所示：leftkeyright其中，p是指向結(jié)點的指針；p->key表示結(jié)點的關(guān)鍵字域，p->left和p->right分別表示結(jié)點的左、右孩子的指針域。voidfromtreetolist（p，l）/*p，h是指向二叉樹中結(jié)點的指針，*//*l是指向雙向循環(huán)鏈表表頭結(jié)點的指針*/{if(p!=NULL){fromtreetolist（p->left，l）；fromtreetolist（p->right，l）；h=l；while（h->right!=l）&&（h->right->key<p->key）h=h->right；p->right=h->right；p->left=h；h->right->left=p；h->rihght=p；}}voidbuildlisttree（root，l）/*root是指向二叉樹根結(jié)點的指針，*//*l是指向雙向循環(huán)鏈表表頭結(jié)點的指針*/{l=（structnodetype*）malloc（sizeof（structnodetype））；l->left=l；l->right=l