數(shù)據(jù)結(jié)構(gòu)(第二版)-模擬試題自測卷AB卷帶答案2

試卷三一、單項(xiàng)選擇題(在下列每小題四個備選答案中選出一個正確答案，并將其字母標(biāo)號填入題干的括號內(nèi)。每小題2分，共30分)1．?dāng)?shù)據(jù)結(jié)構(gòu)可以形式化地定義為（S，△），其中S指某種邏輯結(jié)構(gòu)，△是指（）A.S上的算法 B.S的存儲結(jié)構(gòu)C.在S上的一個基本運(yùn)算集 D.在S上的所有數(shù)據(jù)元素2．下列說法正確的是（）A.線性表的邏輯順序與存儲順序總是一致的B.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，要求內(nèi)存中可用的存儲單元可以是連續(xù)的，也可以不連續(xù)C.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)D.每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運(yùn)算3．稀疏矩陣一般采用（）方法壓縮存儲。A.三維數(shù)組 B.單鏈表C.三元組表 D.散列表4.在一個單鏈表中，若p↑結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p↑之后插入s↑結(jié)點(diǎn)，則實(shí)行()。A.s↑.next:=p；p↑.next=s;B.s↑.next:=p↑.next;p↑.next:=s；C.s↑.next:=p↑.next;p:=s;D.p↑.next:=s;s↑.next=p;5.某個向量第一元素的存儲地址為100，每個元素的長度為2，則第五個元素的地址是()。A.110B.108C.100D.1206.下面的二叉樹中，()不是完全二叉樹。7.一組記錄的排序碼為(47、78、61、33、39、80)，則利用堆排序的方法建立的初始堆為()。A.78、47、61、33、39、80B.80、78、61、33、39、47C.80、78、61、47、39、33D.80、61、78、39、47、338.假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針域，現(xiàn)要把一個指針s所指的新結(jié)點(diǎn)作為非空雙鏈表中q所指地點(diǎn)(中間結(jié)點(diǎn))的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中，則下列算法段能正確完成上述要求的是()A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;D.以上都不對9.由下列三棵樹組成轉(zhuǎn)的森林換成一棵二叉樹為()10.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］；上列程序的時間復(fù)雜度為（）A.O（m+n×t） B.O（m+n+t）C.O（m×n×t） D.O（m×t+n）11.設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q［0‥30］中，隊(duì)列非空時，front指示隊(duì)頭元素的前一個位置，rear指示隊(duì)尾元素。如果隊(duì)列中元素的個數(shù)為11，front的值為25，則rear應(yīng)指向的元素是（）A.Q［4］ B.Q［5］ C.Q［14］ D.Q［15］12.定義二維數(shù)組A［1‥8，0‥10］，起始地址為LOC，每個元素占2L個存儲單元，在以行序?yàn)橹餍虻拇鎯Ψ绞较?，某?shù)據(jù)元素的地址為LOC+50L，則在以列序?yàn)橹餍虻拇鎯Ψ绞较拢撛氐拇鎯Φ刂窞椋ǎ〢.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L13.采用排序算法對n個元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（）A.插入和快速 B.冒泡和快速 C.選擇和插入 D.選擇和冒泡14.設(shè)h是指向非空帶表頭結(jié)點(diǎn)的循環(huán)鏈表的頭指針，p是輔助指針。執(zhí)行程序段p=h;while(p->next->next!=h)p=p->next;p->next=h;后（其中，p->next為p指向結(jié)點(diǎn)的指針域），則()A.p->next指針指向鏈尾結(jié)點(diǎn) B.h指向鏈尾結(jié)點(diǎn)C.刪除鏈尾前面的結(jié)點(diǎn) D.刪除鏈尾結(jié)點(diǎn)15.某二叉樹的先根遍歷序列和后根遍歷序列正好相反，則該二叉樹具有的特征是()A.高度等于其結(jié)點(diǎn)數(shù) B.任一結(jié)點(diǎn)無左孩子C.任一結(jié)點(diǎn)無右孩子 D.空或只有一個結(jié)點(diǎn)二、填空題(本大題共13小題，每小題2分，共26分)請?jiān)诿啃☆}的空格中填上正確答案。錯填、不填均無分。16.數(shù)據(jù)的邏輯結(jié)構(gòu)通常包括集合、線性結(jié)構(gòu)、____________和圖狀結(jié)構(gòu)。17．給定n個值構(gòu)造哈夫曼樹。根據(jù)哈夫曼算法，初始森林中共有n棵二叉樹，經(jīng)過次合并后才能使森林中的二叉樹的數(shù)目由n棵減少到只剩下一棵最終的哈夫曼樹。18．樹型結(jié)構(gòu)結(jié)點(diǎn)間通過“父子”關(guān)系相互關(guān)聯(lián)，這種相互關(guān)聯(lián)構(gòu)成了數(shù)據(jù)間的關(guān)系。19.在一個具有n個結(jié)點(diǎn)的單鏈表中查找值為m的某結(jié)點(diǎn)，若查找成功，則需平均比較的結(jié)點(diǎn)數(shù)為____________。20.數(shù)據(jù)表示和________________是程序設(shè)計(jì)者所要考慮的兩項(xiàng)基本任務(wù)。21.在循環(huán)隊(duì)列中，存儲空間為0~n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個空閑元素，隊(duì)尾指針指向隊(duì)尾元素，那么其隊(duì)空標(biāo)志為rear=front，隊(duì)滿標(biāo)志為_________。22.深度為k的二叉樹至多有_________個結(jié)點(diǎn)，最少有_________個結(jié)點(diǎn)。23．在堆排序和快速排序中，若原始記錄已基本有序，則較適合選用。24.在一棵二叉排序樹上按____________遍歷得到的結(jié)點(diǎn)序列是一個有序序列。25.實(shí)現(xiàn)二分查找的存儲結(jié)構(gòu)僅限于順序存儲結(jié)構(gòu)，且其中元素排列必須是____________的。26.三個結(jié)點(diǎn)可構(gòu)成________種不同形態(tài)的二叉樹。27.設(shè)需將一組數(shù)據(jù)按升序排序。在無序區(qū)中依次比較相鄰兩個元素ai和ai+1的值，若ai的值大于ai+1的值，則交換ai和ai+1。如此反復(fù)，直到某一趟中沒有記錄需要交換為止，該排序方法被稱為_________。28.對于一棵具有n個結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為2n個，其中________個用于鏈接孩子結(jié)點(diǎn)。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29.已知一棵二叉樹的前序序列是ABCDEFG，中序序列是CBDAEGF。請構(gòu)造出該二叉樹，并給出該二叉樹的后序序列。30．有一字符串序列為5*-x-y/x+2，利用棧的運(yùn)算將其輸出結(jié)果變?yōu)?x-*yx+/-2，試寫出該操作的入棧和出棧過程（采用push(a)表示a入棧，pop(a)表示a出棧）。31.已知某二叉樹的順序存儲結(jié)構(gòu)如圖所示，試畫出該二叉樹，并畫出其二叉鏈表表示。ABCDEFG32.已知一組鍵值序列為(38，64，73，52，40，37，56，43)，試采用快速排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。33.請按照數(shù)列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序樹。四、算法設(shè)計(jì)題(本大題共3小題，共14分)34.試編寫一算法，以完成在帶頭結(jié)點(diǎn)單鏈表L中第i個位置前插入元素X的操作。（4分）35.某帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說明如下：（6分）typedefstructnode1{intdata;structnode1*next}node；試設(shè)計(jì)一個算法intcopy(node*head1,node*head2)，將以head1為頭指針的單鏈表復(fù)制到一個不帶頭結(jié)點(diǎn)且以head2為頭指針的單鏈表中。36.若二叉樹存儲結(jié)構(gòu)采用二叉鏈表表示，試編寫一算法，計(jì)算一棵二叉樹的所有結(jié)點(diǎn)數(shù)。（4分）參考答案一、選擇題（本題共30分,每題2分）1、C2、B3、C4、B5、B6、C7、B8、C9、A10、C11、B12、D13、C14、D15、A二、填空題（本題共26分,每小題2分）16、樹狀結(jié)構(gòu)17、n-118、邏輯19、n/220、數(shù)據(jù)處理21、front==(rear+1)%n22、2k-1，k23、堆排序24、中序25、有序26、527、冒泡排序28、n-1三、應(yīng)用題（本題共30分，每小題6分）29、ABABCDGFEFE30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);ACACDEFG第1趟：[37]38[735240645643]第2趟：3738[4352406456]73第3趟：3738[40]43[526456]73第4趟：3738404352[6456]73第5趟：3738404352[56]6473第6趟：373840435256647331、BACBACDEFGAB∧NULL∧C∧ROOT∧DE∧F∧∧G∧33、282812452018335537四、算法設(shè)計(jì)題（本題共14分）34、(4分)typedefstructnode*pointer;structnode{datatypedata;pointernext;};typedefpointerlklist;voidinsert_lklist(lklisthead,datatypex,inti){pointer*p,*s;p=head;j=0;while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}if(j!=i-1){printf("不存在第i個位置");break();}else{s=malloc(size);s->data=x;s->next=p->next;p->next=s;}}35、(6分)intcopy(node*head1,node*head2){Node*p,*s;P=head1->next;If(p!=NULL){*r=malloc(size);r->data=p->data;head2=r;p=p->next;}

else{head2=NULL;Return(0);}While(p!=NULL){*s=malloc(size);s->data=p->data;r->next=s;r=s;p=p->next;}r->next=NULL;return(1);}36、（4分）typedefcharDataType;

typedefstructnode

{

DataTypedata;

structnode*lchild,*rchild;

}BinTNode;

typedefBinTNode*BinTree;

intnodes(BinTreeT)

{

intnum1,num2;

if(T==NULL)return(0);

elseif(T->lchild==NULL&&T->rchild==NULL)return(1);

else

{

num1=nodes(T->lchild);

num2=nodes(T->rchild);

return(num1+num2+1);

}

}試卷A一、選擇題（本題共20分，每小題1分）1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A．動態(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．線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址()。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以3．不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是()。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL4．在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行()。A.s-next=p-next;p-next=s;B.p->next=s->next;s-next=p;C.q->next=s;s->next=p;D.p-next=s;s->next=q;5．從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功的情況下，需平均比較()個結(jié)點(diǎn)。A.nB.n/2C.(n-1)/2D.(n+1)/26．一個棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是()。A.edcbaB.decbaC.dceabD.abcde7．判定一個循環(huán)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是()。A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%m0D.QU->front!=(QU->rear+1)%m08．棧和隊(duì)列的共同點(diǎn)是()。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)9．?dāng)?shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為()。A.SA+141B.SA+144C.SA+222D.SA+22510．廣義表((a，b)，c，d)的表尾是()。A.aB.bC.(a，b)D.(c，d)11．設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[1，n(n-1)/2]中，對下三角部分中任一元素ai,j(i≥j)，在一維數(shù)組B的下標(biāo)位置k的值是（）。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j13.已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（）。A.acbedB.decabC.deabcD.cedba12.如下圖所示的4棵二叉樹中，（）不是完全二叉樹。14.按照二叉樹的定義，具有3個結(jié)點(diǎn)的二叉樹有（）種。A.3B.4C.5D.615.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）。A.2hB.2h-1C.2h+1D.h+116．在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）倍。A.1/2B.1C.2D.417．在一個具有n個頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（）條邊。A.nB.n+1C.n-1D.n/218．已知一有向圖的鄰接表存儲結(jié)構(gòu)如下圖所示，根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（）。A.v1，v2，v3，v5，v4B.v1，v2，v3，v4，v5C.v1，v3，v4，v5，v2D.v1，v4，v3，v5，v219.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。A.nB.n/2C.(n+1)/2D.(n-1)/220．快速排序方法在（）情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個數(shù)為奇數(shù)二、填空題（本題共20分，每空1分）1．根據(jù)數(shù)據(jù)元素之間的不同特征，通常有四類基本結(jié)構(gòu)：_____、______、______和______。2．下面程序段的時間復(fù)雜度是：______。for(i=0；i<n；i++)for(j=0；j<m；j++)A[i][j]=0；3．向一個長度為n的線性表中的第i個元素（1≤i≤n）之前插入一個元素時，需向后移動______個元素。4．在一個單鏈表中的p所指結(jié)點(diǎn)之前插入一個s所指結(jié)點(diǎn)時，可執(zhí)行如下操作：（1）s->next=______;（2）p-next=s;（3）t=p->data;（4）p->data=______;（5）s->data=______;5.深度為k的完全二叉樹至少有個結(jié)點(diǎn)，至多有個結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號（從1開始），則編號最小的葉子結(jié)點(diǎn)的編號是。6.一個廣義表為（a，（a，b），d，e，（（i，j），k）），則該廣義表的深度為________。7.有一棵樹如下圖所示，回答下面的問題：結(jié)點(diǎn)k3的度是；這棵樹的度為；這棵樹的深度是。8．在對一組記錄(54，38，96，23，15，72，60，45，83)進(jìn)行直接插入排序時，當(dāng)把第七個記錄60插入到有序表時，為尋找插入位置需比較______次。9.隊(duì)列的插入操作在_______進(jìn)行，刪除操作在_______進(jìn)行。10.判定一個有向圖中是否存在回路，即是否含有環(huán)，可以使用_________方法。三、閱讀程序?qū)懡Y(jié)果（本題共20分，每小題5分）單鏈表中，指針p指向某結(jié)點(diǎn)，執(zhí)行以下操作后，請用一句話描述程序執(zhí)行的結(jié)果是什么？q=p->next;p->data=p->next->data;p->next=p->next->next;free(q);閱讀下面二分查找程序代碼，填充空白位置，使算法完整。intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(low<=high){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)____①____;else______②_____;}return0;}如下圖所示給出了圖G及對應(yīng)的鄰接表，根據(jù)給定的dfs算法，從頂點(diǎn)8出發(fā)，寫出其搜索序列。Adjlistgl;voiddfs(intv){structvexnode*p;printf("%d"，v);visited[v]=1;p=gl[v]->link;/*gl是該圖的鄰接表的表頭指針數(shù)組*/while(p!=NULL){if(visited[p->adjvex]==0)dfs(p->adjvex);p=p->next;}}二叉樹采用二叉鏈表存儲結(jié)構(gòu)，將第四題綜合題3中的二叉樹，運(yùn)行下面的遞歸算法，請寫出最后的返回結(jié)果是什么？intcount(btree*b){intnum1，num2;if(b==NULL)return(0);elseif(b->left==NULL&&b->right==NULL)return(1);else{num1=count(b->left);num2=count(b->right);return(num1+num2);}}四、綜合題（本題共30分，每小題5分）1.有一份電文中共使用五個字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為{4、7、5、2、9}，試畫出對應(yīng)的哈夫曼樹（注意：構(gòu)造哈夫曼樹過程中請按左子樹根結(jié)點(diǎn)的權(quán)值小于等于右子樹根結(jié)點(diǎn)的權(quán)值次序構(gòu)造），并求出每個字符的哈夫曼編碼。2.利用普里姆算法，從節(jié)點(diǎn)1出發(fā)構(gòu)造出如下圖所示的圖G的一棵最小生成樹。3.一棵二叉樹如下面的圖所示，要求：（1）寫出對此二叉樹進(jìn)行中序遍歷時得到的結(jié)點(diǎn)序列。（2）畫出由此二叉樹轉(zhuǎn)換得到的森林。4．請畫出，將元素3和元素6依次插入到下圖所示的平衡二叉樹中的結(jié)果，要求仍然保持為一棵平衡二叉樹。5.一組元素為（46，25，78，62，12，37，70，29），要求：（1）畫出按元素排列順序輸入生成的一棵二叉排序樹。（2）畫出在二叉排序樹中，刪除元素46后的結(jié)果6.設(shè)哈希表長度為11，哈希函數(shù)h(key)=key%11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫出用線性探查法解決沖突時所構(gòu)造的哈希表。并計(jì)算在查找成功時候的平均查找長度。五、算法題（本題共10分）假設(shè)線性表中包含n個數(shù)據(jù)元素，請寫出順序存儲方式下對n個元素的冒泡排序算法。具體存儲結(jié)構(gòu)如下：#defineMaxsize20TypedefintKeyType;Typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RedType;//記錄類型Typedefstruct{RedTyper[Maxsize+1];//r[0]閑置或者用做哨兵單元Intlength;//順序表長度}SqList;//順序表類型參考答案選擇題（本題共20分,每題1分）12345678910CDACDCCCCD11121314151617181920BDCCBBCCCC二、填空題（本題共20分，每空1分）1.集合、線性結(jié)構(gòu)、樹形