數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題庫考前必備

1、第一章緒論一.選擇題1 .數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K,R）,其中K是_B_的有限集合，R是K上的_D_的有限集合。A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)A.操作B.映象C.存儲(chǔ)D.關(guān)系2 .算法分析的目的是C,算法分析的兩個(gè)主要方面是AoA.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性A.空間復(fù)雜性和時(shí)間復(fù)雜性B,正確性和簡明性C,可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3 .在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（B）A.邏輯結(jié)構(gòu)B.順序存儲(chǔ)結(jié)構(gòu)C.鏈表存儲(chǔ)結(jié)構(gòu)D.以上都不對4 .數(shù)據(jù)結(jié)構(gòu)中，在邏

2、輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：（C）。A.動(dòng)態(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)5 .以下屬于順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn)的是（A）。A.存儲(chǔ)密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D,可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示6 .數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是（D）。A.數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.建立在相應(yīng)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)上的算法D,包括以上三個(gè)方面7 .鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（A）A.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B,只有一部分，存放結(jié)點(diǎn)值C.只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)

3、所占單元數(shù)8 .一個(gè)正確的算法應(yīng)該具有5個(gè)特性，除輸入、輸出特性外，另外3個(gè)特性是（A）。A.確定性、可行性、有窮性B.易讀性、確定性、有效性C.有窮性、穩(wěn)定性、確定性D,可行性、易讀性、有窮性9 .以下關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中正確的是（A）。A.數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述B.數(shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式C.數(shù)據(jù)的邏輯結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)D.數(shù)據(jù)的邏輯結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)10 .算法分析的主要任務(wù)是（C）。A.探討算法的正確性和可讀性B.探討數(shù)據(jù)組織方式的合理性C.為給定問題尋找一種性能良好的解決方案D.研究數(shù)據(jù)之間的邏輯關(guān)系二.解答設(shè)有一數(shù)據(jù)的邏輯結(jié)構(gòu)為：

4、B=(D,S),其中：D=d1,d2,，d9S=<d1,d3>,<d1,d8>,<d2,d3>,<d2,d4>,<d2,d5>,<d3,d9>,<d4,d7>,<d4,d6>,<d5,d6>,<d8,d9>,<d9,d7>畫出這個(gè)邏輯結(jié)構(gòu)示意圖。d5d6第二章線性表一、選擇題1 .下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（A）A.存儲(chǔ)密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2 .下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（B）A.線性表采

5、用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3 .若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（A）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表4 .某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（D）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D,僅有尾指針的單循環(huán)鏈表5 .在一個(gè)長度為n的順序表中刪除第i個(gè)元素（0<=i

6、<=n）時(shí)，需向前移動(dòng)（A）個(gè)元素A.n-iB.n-i+lC.n-i-1D.i6 .從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較（C）個(gè)元素結(jié)點(diǎn)A.n/2B.nC.（n+1）/2D.（n-1）/27 .設(shè)單鏈表中指針p指向結(jié)點(diǎn)m,若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為（A）A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p;8 .在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行（B）A

7、. s->next=p->next;p->next=sB. q->next=s;s->next=pC. p->next=s->next;s->next=pD. p->next=s;s->next=q9 .線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（A）的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取二、填空1 .在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過物理位置相鄰決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過指針決定的。2 .在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向一.直接前驅(qū)結(jié)點(diǎn)，另一個(gè)指向直接后繼結(jié)點(diǎn)。3 .當(dāng)對一

8、個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用順序存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。、算法設(shè)計(jì)1,設(shè)有一個(gè)正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在）試編寫能實(shí)現(xiàn)下列功能的算法（要求用最少的時(shí)間和最小的空間）確定在序列中比正整數(shù)x大的數(shù)有幾個(gè)(相同的數(shù)只計(jì)算一次)將單鏈表中比正整數(shù)x小的偶數(shù)從單鏈表中刪除intcount(Linklisth,intx)(intnum=0;Linknode*p;p=h->next;while(p&&p->data<=x)/p指針向后移動(dòng)，直至p指向第

9、一個(gè)值大于x的結(jié)點(diǎn)p=p->next;while(p)if(p->next&&p->data=p->next->data)若p沒有指向鏈表中同一數(shù)值的最后一個(gè)結(jié)點(diǎn)，則向后移動(dòng)p=p->next;else/若p指向數(shù)值相同的結(jié)點(diǎn)中的最后一個(gè)，則num加1,p指針后移，繼續(xù)執(zhí)行while循環(huán)(num+;p=p->next;returnnum;voiddelevenl(Linklist&h,intx)(Linknode*p,*r;p=h->next;r=h;while(p&&p->data<x)(if

10、(p->data%2=0)(r->next=p->next;free(p);p=r->next;else(r=p;p=p->next;2. 設(shè)有一個(gè)表頭指針為h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)Op-Ahm丁丁丁h3. voidconverse(Linklist&h)(Linknode*p,*q;p=h->next;h->next=NULL;q=p->next;while(q)(p->next=h;h=p;p=q;q=q->

11、;next;p->next=h;h=p;3.設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C,其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點(diǎn))。4. voiddecompose(LinklistLa,Linklist&Lb,Linklist&Lc)(Linknode*p;Lc=(Linknode*)malloc(sizeof(Linknode);Lc->next=NULL;p=La->next;Lb=La;Lb->next=NULL;while(p)(La=p

12、->next;if(p->data>0)(p->next=Lc->next;Lc->next=p;)else(p->next=Lb->next;Lb->next=p;)P=La;)4.假設(shè)鏈表A、B分別表示一個(gè)集合，試設(shè)計(jì)算法以判斷集合A是否是集合B的子集，若是，則返回1,否則返回0,并分析算法的時(shí)間復(fù)雜度。5. intsubset(LinkListla,LinkListlb)LinkNode*pa,*pb;pa=la->next;while(pa)pb=lb->next;while(pb&&(pb->da

13、ta!=pa->data)pb=pb->next;if(!pb)return0;pa=pa->next;)return1;算法時(shí)間復(fù)雜度O(A.Length*B.Length)5.設(shè)有一單循環(huán)鏈表la,其結(jié)點(diǎn)有三個(gè)域：prior、data與next,其中data為數(shù)據(jù)域,next域指向直接后繼，prior域應(yīng)指向直接前驅(qū)，但目前空著。試寫一算法將此單循環(huán)鏈表改造為雙向循環(huán)鏈表。6. voidpriorset(DuLinkList&la)p=la;q=la->next;while(q!=la)q->prior=p;p=q;q=q->next;q->

14、;prior=p;第三章棧和隊(duì)列一、選擇題1 .已知棧的最大容量為4。若進(jìn)棧序列為1,2,3,4,5,6,且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為(C)A.5,4,3,2,1,6B.2,3,5,6,1,4C.325416D.146523設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列(C)A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A2 .在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端(即0單元)作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為（C）A. top不變B. top=0C. top-D.top+3 .

15、向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(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;4.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為（D）A.rear%n=frontB. (front+l)%n=rearC. rear%n-1=frontD.（rear+l）%n=front5 .在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear

16、分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為（C）A.C.rear%n=frontrear=frontB.front+l=rearD.(rear+l)%n=front6 .在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為（A）A.front=front->nextB.rear=rear->nextC.rear=front->nextD.front=rear->next7 .某堆棧的輸入序列為1,2,3,，n,輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素為（C）A.iB.n-iC.n-i+1D,哪個(gè)元素?zé)o所謂8 .用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)

17、隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（D）oA.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭，隊(duì)尾指針都可能要修改二、解答題1.一個(gè)雙向棧S是在同一向量空間內(nèi)實(shí)現(xiàn)的兩個(gè)棧，它們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè)計(jì)初始化InitStack（S）、入棧Push（S,i,x）和出棧Pop（S,i）等算法，其中i為0或1,用以表示棧號(hào)。1.雙棧一一.棧底1棧底2/雙向棧類型定義#defineSTACK_SIZE100;TypedefstructSElemType*base_one,*base_two;/棧底指針SElemType*t

18、op_one,*top_two;/棧頂指針intstacksize;SqStack;StatusInitStack(SqStack&S)初始化雙向棧S.base_one=S.top_one=(SElemType*)malloc(STACK_SIZE*sizeof(SElemType);/第個(gè)棧底和棧頂指向數(shù)組起點(diǎn)S.base_two=S.top_two=S.base_one+STACK_SIZE-1;/第二個(gè)棧底和棧頂指向數(shù)組終點(diǎn)S.stacksize=STACK_SIZE;returnOK;/InitStackStatusPush(SqStack&S,inti,SElemTy

19、pee)/入棧操作，i=0時(shí)將e存入前棧，i=1時(shí)將e存入后棧if(S.top_two<S.top_one)returnOVERFLOW;/棧滿，不考慮追加空間if(i=0)*S.top_one+=e;else*S.top_two-=e;returnOK;/PushSElemTypePop(SqStack&S,inti)出棧操作，i=0出前棧，i=1出后棧if(i=0)if(S.top_one=S.base_one)returnERROR;S.top_one-;e=*S.top_one;elseif(S.top_two=S.base_two)returnERROR;S.top_t

20、wo+;e=*S.top_two;returne;/Pop2. 利用兩個(gè)棧S1、S2模擬一個(gè)隊(duì)列時(shí)，如何使用棧的運(yùn)輸實(shí)現(xiàn)隊(duì)列的插入、刪除運(yùn)算。3. #defineM3structStackQelemtypedataM;inttop;structQueueStacks1;Stacks2;)；voidInitQueue(Queue&Q)/初始化隊(duì)列(Q.s1.top=0;Q.s2.top=0;)intIsEmpty(Queue&Q)/判斷隊(duì)列是否為空(if(Q.s1.top=0&&Q.s2.top=0)return1;if(Q.s2.top=0&&Q

21、.s1.top!=0)(while(Q.s1.top!=0)Q.s2.dataQ.s2.top+=Q.s1.data-Q.s1.top;)return0;)intIsFull(Queue&Q)(if(Q.s1.top=M&&Q.s2.top!=0)return1;if(Q.s1.top=M&&Q.s2.top=0)(while(Q.s1.top!=0)Q.s2.dataQ.s2.top+=Q.s1.data-Q.s1.top;return0;)if(Q.s1.top!=M)return0;)voidInQueue(Queue&Q,Qelemtyp

22、ee)(if(IsFull(Q)(cout<<"OVERFLOW"<<endl;return;)Q.s1.dataQ.s1.top+=e;voidDeQueue(Queue&Q,Qelemtype&e)(if(IsEmpty(Q)(cout<<"UNDERFLOW"<<endl;return;e=Q.s2.data-Q.s2.top;3.已知一個(gè)棧S的輸入序列為abcd,下面兩個(gè)序列能否通過棧的push和pop操作輸出？如果能，請寫出操作序列；如果不能，請寫明原因。(1)dbca(2)cbd

23、a4. (1)不能(2)可以原因略4.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法。5. structQueueNode(Qelemtypedata;QueueNode*next;structLinkQueue(QueueNode*rear;voidInitQueue(LinkQueue&Q)置空隊(duì)(Q.rear=newQueueNode;Q.rear->next=Q.rear;intEmptyQueue(LinkQueueQ)判隊(duì)空(returnQ.rear=Q.rear->next;v

24、oidEnQueue(LinkQueue&Q,Qelemtypee)/元素入隊(duì)(QueueNode*p;新建一個(gè)結(jié)點(diǎn)，并置其值為p=newQueueNode;p->data=e;/將結(jié)點(diǎn)插入隊(duì)列末尾p->next=Q.rear->next;Q.rear->next=p;修改隊(duì)尾指針Q.rear=p;)voidDeQueue(LinkQueue&Q,Qelemtype&e)元素出隊(duì)(QueueNode*p;if(EmptyQueue(Q)若隊(duì)中無元素，則無法執(zhí)行出隊(duì)操作(cout<<"error"<<en

25、dl;return;)p=Q.rear->next->next;讓p指向隊(duì)頭元素e=p->data;if(p=Q.rear)/如隊(duì)中只有一個(gè)元素，則要rear指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的next指針指向自身(Q.rear=Q.rear->next;Q.rear->next=Q.rear;)else若隊(duì)中不只一個(gè)元素，則刪除p所指向的結(jié)點(diǎn)。Q.rear->next->next=p->next;deletep;/釋放被刪除結(jié)點(diǎn)的存儲(chǔ)空間)5.假設(shè)以I和。表示入棧和出棧操作，棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列。稱可以操作的序

26、列為合法序列，否則稱為非法序列。(1)下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO(2)通過對問題的分析，寫出一個(gè)算法判定所給的操作序列是否合法。若合法返回TRUE,否則返回FALSE。(假定被判定的操作序列已經(jīng)存入一維數(shù)組中)6. typedefstruct(chardata10;inttop;stack;intdescion(char*str)(stacks;inti;s.top=0;for(i=0;stri;i+)(switch(stri)(caseT:s.datas.top+=stri;break;若為I,則如棧case

27、'O':if(s.top=0)return0;s.top-;若為O,則從棧中彈出一個(gè)Iif(s.top=0)return1;elsereturn0;第四章串一.選擇題1 .若用S='software',其子用的數(shù)目是(B)A.8B.37C.36D.92 .設(shè)有兩個(gè)用p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作(B)A.連接B.模式匹配C.求用長D.求子用3 .設(shè)字符串S1=ABCDEFQS2=PQRST,M運(yùn)算：S=CONCATSUBSTRS1,2,LEN(S2);SUBSTRS1,LEN(S2),2);后的申值為(D)A.ABCDEFB.BCDEFGC.BCDP

28、QRSTD.BCDEFEF4 .下面的說法中，只有(A)是正確的A.用是一種特殊的線性表B.用的長度必須大于零C.用中元素只能是字母D.空用就是空白用5 .兩個(gè)字符串相等的條件是(D)A.兩用的長度相等B.兩用包含的字符相同C.兩用的長度相等，并且兩用包含的字符相同D.兩用的長度相等，并且對應(yīng)位置上的字符相同二、填空題1 .令t1=aaab”,t2=abcabaa",t3=abcaabbabcabaacba",試分另U求出他們的nex函數(shù)值0123,0111232,01112231234532211。2 .空格用的長度為空格數(shù),空用的長度為0。3 .設(shè)用S='How

29、areyou",則用的長度為11。三、問答題回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個(gè)算法判定給定的字符變量是否為回文。StatusIsHuiwen(char*S)i=0;while(si!='0')i+;i=i-1;j=0;while(j<i)if(sj!=si)return0;elsej+;i-;return1;第五章數(shù)組和廣義表一.選擇題1 .設(shè)有數(shù)組Ai,j,數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首

30、地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A5,8的存儲(chǔ)首地址為(B)A.BA+141B.BA+180C.BA+222D.BA+2252 .假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array1.100,1.100,設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10,則LOC5,5=(B)A.808B.818C.1010D.10203對稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是(C)A.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間D.降低運(yùn)算的時(shí)間復(fù)雜度4 .廣義表A=(a,b,(c,d),(e,(f,g),則下面式子的值為(D)。Head(Tail(Head(Tail(Tail(A)A.(g)B.(d)C.cD.d

31、5 .設(shè)廣義表L=(a,b,c),則L的長度和深度分別為(B)A.1和1B.1C.1和2D.2和36.假設(shè)以三元組表表示稀疏矩陣,則與如圖所示三元組表對應(yīng)的4X5的稀疏矩A.C.7.陣是070-5007-5(注：矩陣的行列下標(biāo)均從1開始)(-8000-80000004600000007B.07-50-8000000460000300一個(gè)非空的廣義表的表尾(B)D.07-50-800000400040A.不能是子表B.只能是子表C.只能是原子D.是原子或子表8.如果將矩陣Anxn的每一列看成一個(gè)子表，整個(gè)矩陣看成是一個(gè)廣義表L,即L=(a11,a21,an1),(a12,a22,an2),，(a

32、1n,a2n,ann),并且可以通過求表頭head和求表尾tail的運(yùn)算求取矩陣中的每一個(gè)元素，則求得a21的運(yùn)算是(A)A.head(tail(head(L)B.head(head(head(L)C.tail(head(tail(L)D.head(head(tail(L).填空題1.己知三對角矩陣A1.9,1.9的元素逐行存儲(chǔ)在起始地址為的每個(gè)元素占2個(gè)單元，現(xiàn)將其三條對角線上1000的連續(xù)的內(nèi)存單元中，則元素A7,8的地址為_10382 .設(shè)廣義表L=(),(),則head(L)是_)；tail(L)是()_；L的長度是27深度是2>3 .廣義表A=(a,b),(c,d,e),試用求

33、表頭和表尾的操作Head()和Tail()取出A中的原子e的操作是：Head(Tail(Tail(Head(Tail(Head(A)_.解答下列各題1 .已知一個(gè)6行5列的稀疏矩陣中非零元的值分別為：-90,41,-76,28,-54,65,-8,它們在矩陣中的列號(hào)依次為：1,4,5,1,2,4,5。當(dāng)以帶行表的三元組表作存儲(chǔ)結(jié)構(gòu)時(shí)，其行表中的值依次為0,0,2,2,3,5(行列下標(biāo)均從1開始)寫出該稀疏矩陣。0000-9000410000000000-7628-540000065-8J2 .寫出廣義表B=(a,b),C=(a,(b,c,(d,e),D=(a,B,C),E=(a,b),E)的存

34、儲(chǔ)結(jié)構(gòu)(任一種存儲(chǔ)方法均可)第六章樹和二叉樹一.選擇題CDDACADDEDBCCBBCACCC1 .如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是()A.棧B.隊(duì)列C.樹D,圖2 .設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1則T中的葉子數(shù)為（）A.5B.6C.7D.83 .已知一棵含50個(gè)結(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn)，則該樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為（）A.0B.1C.48D.494 .樹的先根序列等同于與該樹對應(yīng)的二叉樹的（）A.先序序列B.中序序列C.后序序列D.層序序列5 .用二叉鏈表表示具有n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，值為空的指針域的個(gè)

35、數(shù)為（）A.n-1B.nC.n+lD.2n6 .設(shè)森林F對應(yīng)的二叉樹為B,它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（）A.m-nB.m-n-1C.n+1D.條件不足，無法確定7 .設(shè)樹T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1,則T中的葉子數(shù)為（）A.5B.6C.7D.88 .設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1,M2和M&與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）A.M1B,M1+M2C.M3D,M2+M39 .一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）A.250B.500C

36、.254D.505E.以上答案都不對10 .有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）A.不確定B.2nC,2n+1D.2n-111 .一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,則這棵二叉樹最少有（）結(jié)點(diǎn)A.2hB.2h-1C.2h+1D,h+112 .將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度（）A.4B.5C.6D.713 .若度為m的哈夫曼樹中，其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù)為（）A.n-1B|ln/m-1C.（n-1）/（m-1）D|n/（m-1）-1E.（n+1）/（m+1）-114 .若下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（）。A.0,10,1

37、10,1111B.11,10,001,101,0001C.00,010,0110,1000D.b,c,aa,ac,aba,abb,abc15 .一棵二叉樹的前序遍歷序列為ABCDEFG它的中序遍歷序列可能是（）A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG16 .線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯B.邏輯和存儲(chǔ)C.物理D.線性17 .引入二叉線索樹的目的是（）A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B.為了能在二叉樹中方便的進(jìn)行插入與刪除C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一18 .n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（）A.2nB.n-lC.n+lD.n19 .

38、若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為（）A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)20 .某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹A.空或只有一個(gè)結(jié)點(diǎn)B.任一結(jié)點(diǎn)無左子樹C.高度等于其結(jié)點(diǎn)數(shù).任一結(jié)點(diǎn)無右子樹二.填空題1 .假定一棵樹的嵌套括號(hào)表示法為A(B(E),C(F(H,I,J),G),D),則該樹的度為,樹的深度為,終端點(diǎn)的個(gè)數(shù)為，但分支結(jié)點(diǎn)的個(gè)數(shù)為,雙分支結(jié)點(diǎn)為,三分支結(jié)點(diǎn)的個(gè)數(shù)為,C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為,其孩子結(jié)點(diǎn)為和為結(jié)點(diǎn)。2 .一棵深度為K的滿二叉樹結(jié)點(diǎn)總數(shù)為,一棵深度為K的完全二

39、叉樹的結(jié)點(diǎn)總數(shù)的最小值為,最大值為。3 .由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有種不同的形態(tài)。4 .具有100個(gè)葉子結(jié)點(diǎn)的完全二叉樹的深度為5 .高為h(h>0)的滿二叉樹對應(yīng)森林的由棵樹構(gòu)成。三.已知一個(gè)二叉樹的中序序列為CBEDAHGIJF,后序序列為CEDBHJIGFA。1 .畫出該二叉樹。2 .畫出該二叉樹的先序線索二叉樹。四.試找出分別滿足下列條件的所有二叉樹：1 .先序序列和中序序列相同。2 .中序序列和后序序列相同。3 .先序序列和后序序列相同。五、設(shè)二叉樹用二叉鏈表表示，設(shè)計(jì)算法求二叉樹的高度。intDepth(BiTreet)(后序遍歷)if(!t)d=0;elsedl=Dept

40、h(t->lchild);dr=Depth(t->rchild);d=1+(dl>dr?dl:dr);returnd;六、設(shè)T是一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若給定二叉樹T的先序序列和中序序列，并假設(shè)T的先序序列和中序序列分別放在數(shù)組PreOrder1.n和InIrder1.n中，設(shè)計(jì)一個(gè)構(gòu)造二叉樹T的二叉鏈表存儲(chǔ)結(jié)構(gòu)的算法。六根據(jù)二叉樹的先序序列和中序序列創(chuàng)建二叉鏈表voidcreateBiTree(charpre,charin,intstart,intend,int&count,BiTree&T)/按先序次序創(chuàng)建二叉鏈表，pre為存放先序序列的字符數(shù)組，in為

41、存放中序序列的字符數(shù)組，/count為二叉樹的根結(jié)點(diǎn)在先序序列中的序號(hào)/start和end為以precount為根的二叉樹在中序序列中的起始位置和結(jié)束位置/T為二叉鏈表的根指針，if(start>end)T=0;elseT=(BiTNode*)malloc(sizeof(BiTNode);/新建根結(jié)點(diǎn)if(!T)exit(0);T->data=precount;T->lchild=T->rchild=0;for(inti=0;ini!='0'i+)查找根結(jié)點(diǎn)在中序序列in中的下標(biāo)if(ini=precount)break;count+;if(ini=&#

42、39;0')cout<<"inputerror"<<endl;elsecreateBiTree(pre,in,start,i-1,count,T->lchild);/根據(jù)先序序列和中序序列創(chuàng)建左子樹createBiTree(pre,in,i+1,end,count,T->rchild);/根據(jù)先序序列和中序序列創(chuàng)建右子樹七、設(shè)用于通信的電文由字符集a,b,c,d,e,f,g中的字母構(gòu)成，它們在電文中出現(xiàn)的頻率分別為0.31,0.16,0.10,0.08,0.11,0.20,0.04,回答下列問題：為這7個(gè)字母設(shè)計(jì)哈夫曼編碼若對這7

43、個(gè)字母進(jìn)行等長編碼，至少需要幾位二進(jìn)制數(shù)？、哈夫曼樹a:10b:110c:010d:1110e:011f:00g:1111等長編碼至少需要3位二進(jìn)制位。八.設(shè)計(jì)算法以輸出二叉樹中先序序列的前k(k>0)個(gè)結(jié)點(diǎn)的值。八voidpreintraverse(BiTreeT,int&n)if(T)n+;if(n<=k)cout<<T->data;intraverse(T->lchild,n);intraverse(T->rchild,n);九.編寫算法，對一棵二叉樹統(tǒng)計(jì)葉子的個(gè)數(shù)九、voidCountLeaf(BiTreet,int&count

44、)(先序遍歷)if(t)if(t->lchild=NULL)&&(t->rchild=NULL)count+;CountLeaf(t->lchild,&count);CountLeaf(t->rchild,&count);）第七章圖一.選擇題1 .n個(gè)頂點(diǎn)，e條邊的有向圖的鄰接矩陣中非零元素有C個(gè)。A.nB.2eC.eD.n+e2 .用鄰接表存儲(chǔ)圖所用的空間大小（A）A.與圖的頂點(diǎn)數(shù)和邊數(shù)都有關(guān)B.只與圖的邊數(shù)有關(guān)C.只與圖的頂點(diǎn)數(shù)有關(guān)D.與邊數(shù)的平方有關(guān)3 .有n條邊的無向圖的鄰接表存儲(chǔ)法中，鏈邊中結(jié)點(diǎn)的個(gè)數(shù)是（B）個(gè)。A.nB.2nC

45、.n/2D.n*n4 .一個(gè)帶權(quán)無向連通圖的最小生成樹（A）。A.有一棵或多棵.B.只有一棵C.一定有多棵D,可能不存在二.如下所示有向圖：1.請給出每個(gè)頂點(diǎn)的度，入度和出度。ABCD入度1121出度2111度32322.請畫出其鄰接矩陣、鄰接表、逆鄰接表、十字鏈表。飛1011001010000010鄰接矩陣鄰接表逆鄰接表十字鏈表三.試對下圖所示的AOE網(wǎng)絡(luò)，解答下列問題。1 .求每個(gè)事件的最早發(fā)生時(shí)間vei和最遲發(fā)生時(shí)間vli。2 .求每個(gè)活動(dòng)的最早開始時(shí)間ee(s)和最遲開始時(shí)間el(s)o3 .指出哪些活動(dòng)加速可使整個(gè)工程提前完成。事件ABCDEF最早發(fā)生時(shí)間vei032668最遲發(fā)生時(shí)

46、間vli042678活動(dòng)a1a2a3a4a5a6a7a8最早開始時(shí)間00332266最遲開始時(shí)間10442567關(guān)鍵活動(dòng)為a2a5a7,加速這些關(guān)鍵活動(dòng)可使整個(gè)工程提前完成。四.寫出下圖所示的AOV網(wǎng)的所有拓?fù)溆行蛐蛄小Ｋ?、拓?fù)溆行蛐蛄蠥BCDEFABCEDFACBDEFACBEDFACEBDF第九章查找一.填空題1 .采用二分法進(jìn)行查找的查找表，應(yīng)選擇順序方式的存儲(chǔ)結(jié)構(gòu)2 .設(shè)在有序表A09中進(jìn)行二分查找，比較一次查找成功的結(jié)點(diǎn)數(shù)為_1，比較二次查找成功的結(jié)點(diǎn)數(shù)為_2，比較三次查找成功的結(jié)點(diǎn)數(shù)為_4，比較四次查找成功的結(jié)點(diǎn)數(shù)為_3,比較五次查找成功的結(jié)點(diǎn)數(shù)為_0,平均查找長度為(1+2*2+3*4+4*3)/10=2.9。(3)設(shè)在線性表R059中進(jìn)行分塊查找，共分10塊，每塊長度為6,若利用順序查找法對索引表和子塊進(jìn)行查找，則查找每個(gè)元素的平均查找長度為9。二.選擇題1 .對線性表進(jìn)行二分查找時(shí)，要求線性表必須(B)A.鍵值有序的鏈接表B.鍵值有序的順序表C.鏈接表但鍵值不一定有序D.順序但鍵值不一定有序2 .有一個(gè)有序表1,4,6,10,18,35,42,53,67,71,78,84,9