數(shù)據(jù)結(jié)構(gòu)模擬練習(xí)題1-參考答案

1、數(shù)據(jù)結(jié)構(gòu)模擬練習(xí)題1 參考答案一、單項(xiàng)選擇題（每小題2分，共30分）1、 算法的計(jì)算量的大小稱為計(jì)算的（ B ）。A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度2、靜態(tài)鏈表中指針表示的是（B）.內(nèi)存地址 B.數(shù)組下標(biāo) C.下一元素地址 D.左、右孩子地址3、對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（C）.O(n)O(n) B. O(n) O(1) C. O(1)O(n) D. O(1) O(1)4、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（D ）。Ap->next=s;s->next=p->next; Bp->next=s->

2、;next;p->next=s; Cp->next=s;p->next=s->next; D s->next=p->next;p->next=s;5、設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2,s3,s4, s6 , s5,s1,則棧的容量至少應(yīng)該是（ B ）A.2 B. 3 C. 5 D.66、串是一種特殊的線性表，其特殊性體現(xiàn)在（B ）。A可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符C可以鏈接存儲(chǔ) D數(shù)據(jù)元素可以是多個(gè)字符7、若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ D ）

3、。A9 B11 C15 D不確定 8、列說(shuō)法中正確的是（ A ）。A任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2B任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2C任何一棵二叉樹(shù)中的度肯定等于2D任何一棵二叉樹(shù)中的度可以小于29、已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（ B ）。ACBEFDA B FEDCBA C CBEDFA D不定 10、下列哪一種圖的鄰接矩陣是對(duì)稱矩陣（ B ）。A有向圖 B無(wú)向圖 CAOV網(wǎng) DAOE網(wǎng)11、在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的 Prim 算法的時(shí)間復(fù)雜度為(A ）。A. O(n+e) B. O(n) C. O(n2)

4、D. O(n3)12、適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（ D ）。 A鏈接方式存儲(chǔ)，元素?zé)o序 B鏈接方式存儲(chǔ)，元素有序C順序方式存儲(chǔ)，元素?zé)o序 D順序方式存儲(chǔ)，元素有序13、下圖所示的4棵二叉樹(shù), （B ）是平衡二叉樹(shù)。 （A） （B） （C） （D）14、若用冒泡排序方法對(duì)序列10,14,26,29,41,52從大到小排序，需進(jìn)行（C ）次比較。 A. 3 B. 10 C. 15 D. 25 15、下列四個(gè)序列中，哪一個(gè)是堆（C ）。A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,

5、20,10 D. 75,45,65,10,25,30,20,15二、判斷題（在各題后填寫(xiě)“”或“×”，每小題1分，共10分）1、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。( ) 2、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( × )3、循環(huán)隊(duì)列中不存在隊(duì)列滿的問(wèn)題。 （×）4、完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。(× )5、哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。()6、一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)數(shù)可能不等。（ × ）7、含有n個(gè)頂點(diǎn)和n-1條邊的圖一定是連通圖。( × )8、當(dāng)待排序

6、記錄已經(jīng)從小到大排序或已經(jīng)從大到小排序時(shí)，快速排序的執(zhí)行時(shí)間最省。（ × ）9、用shell排序時(shí)，若關(guān)鍵字的排列雜亂無(wú)序，則效率最高。（ × ）10、平衡二叉樹(shù)是一種提高查找效率的二叉排序樹(shù)。()三、 填空題（每空分，共10分）1、在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由 頭指針 指示，首元素結(jié)點(diǎn)的存儲(chǔ)位置由 頭結(jié)點(diǎn)指針域 指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由 前驅(qū)結(jié)點(diǎn)指針域    指示。2、一個(gè)棧的輸入序列是：A、B、C，則不可能的棧輸出序列是_CAB_。3、以下運(yùn)算實(shí)現(xiàn)在鏈棧上的退棧，請(qǐng)?jiān)赺處用請(qǐng)適當(dāng)句子予以填充。Int Pop(

7、LstackTp *ls,DataType *x) LstackTp *p; if(ls!=NULL) p=ls; *x=_; p->data; ls=ls->next; _; free(p); return(1)； else return(0); 4、 直接定址 法構(gòu)造的哈希函數(shù)肯定不會(huì)發(fā)生沖突。5、已知N元整型數(shù)組a存放N個(gè)學(xué)生的成績(jī)，已按由大到小排序，以下算法是用對(duì)分（折半）查找方法統(tǒng)計(jì)成績(jī)大于或等于X分的學(xué)生人數(shù)，請(qǐng)?zhí)羁帐怪晟啤?#define N /*學(xué)生人數(shù)*/int uprx(int aN,int x ) /*函數(shù)返回大于等于X分的學(xué)生人數(shù)*/ int head=1

8、,mid,rear=N; do mid=(head+rear)/2;if(x<=amid) _(1) rear=mid-1 _ else _(2)_head=mid+1 _;while(_(3)_ head>rear _);if (ahead<x) return head-1;return head; 四、應(yīng)用題（每小題6分，共30分）1、在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任何一個(gè)結(jié)點(diǎn)?解答：在單鏈表中不能從當(dāng)前結(jié)點(diǎn)（若當(dāng)前結(jié)點(diǎn)不是第一結(jié)點(diǎn)）出發(fā)訪問(wèn)到任何一個(gè)結(jié)點(diǎn)，鏈表只能從頭指針開(kāi)始，訪問(wèn)到鏈表中每個(gè)結(jié)點(diǎn)。在雙鏈表中求前驅(qū)和后繼都容易，從當(dāng)前結(jié)點(diǎn)向前到第一結(jié)點(diǎn)，

9、向后到最后結(jié)點(diǎn)，可以訪問(wèn)到任何一個(gè)結(jié)點(diǎn)。2、HASH方法的平均查找路長(zhǎng)決定于什么？ 是否與結(jié)點(diǎn)個(gè)數(shù)N有關(guān)？ 處理沖突的方法主要有哪些？解答：解答：哈希方法的平均查找路長(zhǎng)主要取決于負(fù)載因子（表中實(shí)有元素?cái)?shù)與表長(zhǎng)之比），它反映了哈希表的裝滿程度，該值一般取0.650.9。散列表存儲(chǔ)中解決碰撞的基本方法： 開(kāi)放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表長(zhǎng)，di是增量。根據(jù)di取法不同，又分為三種：adi =1，2，m-1 稱為線性探測(cè)再散列，其特點(diǎn)是逐個(gè)探測(cè)表空間，只要散列表中有空閑空間，就可解決碰撞，缺點(diǎn)是容易造成“聚集”，即不是同義詞的關(guān)鍵字爭(zhēng)奪同一散列地址。b

10、di =12，-12，22，-22， ，±k2（km/2） 稱為二次探測(cè)再散列，它減少了聚集，但不容易探測(cè)到全部表空間，只有當(dāng)表長(zhǎng)為形如4j+3（j為整數(shù)）的素?cái)?shù)時(shí)才有可能。cdi =偽隨機(jī)數(shù)序列，稱為隨機(jī)探測(cè)再散列。 再散列法 Hi=RHi（key） i=1，2，k，是不同的散列函數(shù)，即在同義詞產(chǎn)生碰撞時(shí)，用另一散列函數(shù)計(jì)算散列地址，直到解決碰撞。該方法不易產(chǎn)生“聚集”，但增加了計(jì)算時(shí)間。 鏈地址法 將關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一鏈表中，散列表地址區(qū)間用H0.m-1表示，分量初始值為空指針。凡散列地址為i（0im-1）的記錄均插在以Hi為頭指針的鏈表中。這種解決方法中數(shù)據(jù)元素個(gè)數(shù)

11、不受表長(zhǎng)限制，插入和刪除操作方便，但增加了指針的空間開(kāi)銷。這種散列表常稱為開(kāi)散列表，而中的散列表稱閉散列表，含義是元素個(gè)數(shù)受表長(zhǎng)限制。 建立公共溢出區(qū) 設(shè)H0.m-1為基本表，凡關(guān)鍵字為同義詞的記錄，都填入溢出區(qū)O0.m-1。3、給出一個(gè)以下帶權(quán)圖的鄰接矩陣表示：（1）每項(xiàng)活動(dòng)ai的最早開(kāi)始時(shí)間e(ai)和最遲開(kāi)始時(shí)間l(ai)；（2）完成此項(xiàng)工程需要多少天（設(shè)弧上權(quán)值為天數(shù)）；（3）哪些是關(guān)鍵活動(dòng)；（4）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期？12345678910a15a26a33a74a53a94a63a815a10a11224a13a12a46解:(1)所有事件的最早發(fā)生

12、時(shí)間如下： ee(1)=0; ee(2)=5; ee(3)=6; ee(4)=maxee(2)+3, ee(3)+6=12; ee(5)=maxee(3)+3, ee(4)+3=15; ee(6)=ee(4)+4=16; ee(7)=ee(5)+1=16; ee(8)=ee(5)+4=19; ee(9)=maxee(7)+5,ee(8)+2=21; ee(10)=max(ee(6)+4,ee(9)+2=23.所有事件的最遲發(fā)生時(shí)間如下： le(10)=23; le(9)=le(10)-2=21; le(8)=le(9)-2=19; le(7)=le(9)-5=14; le(6)=le(10)-

13、4=19; le(5)=minle(7)-1,le(8)-4=15; le(4)=minle(6)-4,le(5)-3=12; le(3)=minle(4)-6,le(5)-3=6; le(2)=le(4)-3=9; le(1)= minle(2)-5,le(3)-6=0 (3) 求所有活動(dòng)的e(),l()和d()如下：活動(dòng)a1：e(1)=ee(1)=0; l(1)=le(2)-5=4, d(1)=4;活動(dòng)a2：e(2)=ee(1)=0; l(2)=le(3)-6=0, d(2)=0;活動(dòng)a3：e(3)=ee(2)=5; l(3)=le(4)-3=8, d(3)=3;活動(dòng)a4：e(4)=ee(

14、2)=6; l(4)=le(4)-6=6, d(4)=0;活動(dòng)a5：e(5)=ee(3)=6; l(5)=le(5)-3=12,d(5)=6;活動(dòng)a6：e(6)=ee(3)=12; l(6)=le(5)-3=12,d(6)=0;活動(dòng)a7：e(7)=ee(4)=12; l(7)=le(6)-4=15,d(7)=3;活動(dòng)a8：e(8)=ee(5)=15; l(8)=le(7)-1=15, d(8)=0;活動(dòng)a9：e(9)=ee(5)=15; l(9)=le(8)-4=15, d(9)=0;活動(dòng)a10：e(10)=ee(6)=16; l(10)=le(9)-5=16,d(10)=0;活動(dòng)a11：e(

15、11)=ee(7)=19; l(11)=le(9)-2=19,d(11)=0;活動(dòng)a12：e(12)=ee(8)=16; l(12)=le(10)-4=19,d(12)=3;活動(dòng)a13：e(13)=ee(8)=21; l(13)=le(10)-2=21,d(13)=0; （2）完成此項(xiàng)工程最少需要23天。 (3)從以上計(jì)算得出，關(guān)鍵活動(dòng)為a2,a4,a6,a8,a9,a10,a11,a13。這些活動(dòng)構(gòu)成了兩條關(guān)鍵路徑a2，a4，a6，a8，a10，a13和 a2，a4，a6,a9，a11，a13。（4）存在a2,a4,a6,a13活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期。4、已知序列17,18

16、,60,40,7,32,73,65,85，請(qǐng)給出采用冒泡排序法對(duì)該序列升序排序時(shí)的每一趟結(jié)果。解：初始：17 18 60 40 07 32 73 65 85第1趟：17 18 40 07 32 60 65 73 85第2趟：17 18 07 32 40 60 65 73 85第3趟： 17 07 18 32 40 60 65 73 85第4趟： 07 17 18 32 40 60 65 73 85第5趟： 07 17 18 32 40 60 65 73 85第5趟無(wú)元素交換，則排序結(jié)束。5、設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設(shè)計(jì)一套二進(jìn)制編碼，使得上述正文的

17、編碼最短。解：字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。其哈夫曼編碼如下A:1，B:000，C:01，D:0011359000111五、算法設(shè)計(jì)題（20分）1、試分別以順序表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫(xiě)一個(gè)實(shí)現(xiàn)線性表的就地(即使用盡可能少的附加空間)逆置的算法，在原表的存儲(chǔ)空間內(nèi)將線性表(a1，a2,. .,an)逆置為(an,. .,a2,a1)。解答：(1)順序表分析：將順序表的第一個(gè)元素與最后一個(gè)元素互換，第二個(gè)元素與倒數(shù)第二個(gè)元素互換。void  invert(SeqList  *L,  int  *num)    int&#

18、160; j;  ElemType  tmp;for(j=0;j<=(*num-1)/2;j+) tmp=Lj;Lj=L*num-j-1;L*num-j-1=tmp;(2)單鏈表void  invert(LinkList  L)  Node  *p, *q, *r;    if(L->next =NULL)  return;          /*鏈表為空*/   

19、 p=L->next;        q=p->next;               p->next=NULL;              /* 摘下第一個(gè)結(jié)點(diǎn)，生成初始逆置表 */while(q!=NULL)             /* 從第二個(gè)結(jié)點(diǎn)起依次頭插入當(dāng)前逆置表 */   r=q->next;q->next=L->next;L->next=q;q=r;  2、有一鏈棧，每個(gè)結(jié)點(diǎn)放一個(gè)字符。試編寫(xiě)一個(gè)程序，具有下列功能：（1） 從鍵盤(pán)上輸入一個(gè)字符串入棧，以“！”不入棧；（2） 遍歷及顯示棧中內(nèi)容；（3） 執(zhí)行退棧操作，使棧為空。#include<stdio.h>t