數(shù)據(jù)結(jié)構(gòu)c語言章節(jié)練習題

1、數(shù)據(jù)結(jié)構(gòu)章節(jié)練習題第一章緒論一、單項選擇題1 .一個數(shù)組元素ai與的表示等價.A、*(a+i)B、a+iC、*a+iD、&a+i2 .下面程序段的時間復雜度為ofor(inti=0;i<m;i+)for(intj=0;j<n;j+)aij=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)3 .執(zhí)行下面程序段時,執(zhí)行S語句的次數(shù)為.for(inti=1;i<=n;i+)for(intj=1;j<=i;j+)S;n(n+1)/2A、n2B、n2/2C、n(n+1)D4 .下面算法的時間復雜度為ointf(unsignedintn)if(n=0|n

2、=1)return1;elsereturnA、O(1)B、O(n)C二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為n*f(n-1);、O(n2)D、O(n!)、和四種5 .數(shù)據(jù)的存儲結(jié)構(gòu)被分為、和兩種6 .在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中,前驅(qū)和后繼結(jié)點之間分別存在著和的聯(lián)系.7 .一種抽象數(shù)據(jù)類型包括和兩個局部.8 .當一個形參類型的長度較大時,應最好說明為,以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間.9 .當需要用一個形參訪問對應的實參時,那么該形參應說明為o10 在函數(shù)中對引用形參的修改就是對相應的修改,又t形參的修改只局限在該函數(shù)的內(nèi)部,不會反映到對應的實參上.11 當需要進行標準I/O操作時,那么應

3、在程序文件中包含頭文件,當需要進行文件I/O操作時,那么應在程序文件中包含頭文件.12 在包含有頭文件的程序文件中,使用能夠產(chǎn)生出020之間的一個隨機整數(shù).13 .一個數(shù)組a所占有的存儲空間的大小即數(shù)組長度為,下標為i的元素ai的存儲地址為,或者為o14 .從一維數(shù)組an中順序查找出一個最大值元素的時間復雜度為,輸出一個二維數(shù)組bmn中所有元素值的時間復雜度為.15 .在下面程序段中,s=s+p語句的執(zhí)行次數(shù)為,p*=j語句的執(zhí)行次數(shù)為,該程序段的時間復雜度為Ointi=0,s=0;while(+i<=n)intp=1;for(intj=1;j<=i;j+)p*=j;s=s+p;)

4、16 .一個算法的時間復雜度為(3n2+2nlog2n+4n-7)/(5n),其數(shù)量級表示為第二章線性表、單項選擇題1 .在一個長度為n的順序存儲線性表中,向第i個元素(1<i<n+1)之前插入一個新元素時,需要從后向前依次后移個元素.A、n-iB、n-i+1C、n-i-1D、i2 .在一個長度為n的順序存儲線性表中,刪除第i個元素(1<i<n+1)時,需要從前向后依次前移元素.A、n-iB、n-i+1C、n-i-1D、i3 .在一個長度為n的線性表中順序查找值為x的元素時,查找時的平均查找長度(即x同元素的平均比擬次數(shù),假定查找每個元素的概率都相等)為.A、nB、n/

5、2C、(n+1)/2D、(n-1)/24 .在一個單鏈表HL中,假設要向表頭插入一個由指針p指向的結(jié)點,那么執(zhí)行A、HL=p;p->next=HL;B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->next=p;5 .在一個單鏈表HL中,假設要在指針q所指的結(jié)點的后面插入一個由指針p所指的結(jié)點,那么執(zhí)行.A、q->next=p->next;p->next=q;B、p->next=q->next;q=p;C、q->next=p->next;p->

6、next=q;D、p->next=q->next;q->next=p;6 .在一個單鏈表HL中,假設要刪除由指針q所指向結(jié)點的后繼結(jié)點,那么執(zhí)行.A、p=q->next;p->next=q->next;B、p=q->next;q->next=p;C、p=q->next;q->next=p->next;D、q->next=q->next->next;q->next=q;二、填空題1 .在線性表的單鏈式存儲結(jié)構(gòu)中,每個結(jié)點包含有兩個域,一個叫域,另一個叫域C2 .在下面數(shù)組a中鏈式存儲著一個線性表,表頭指針為

7、a0.next,那么該線性表為.3 .對于一個長度為n的順序存儲的線性表,在表頭插入元素的時間復雜度為,在表尾插入元素的時間復雜度為O4 .對于一個長度為n的單鏈式存儲的線性表,在表頭插入元素的時間復雜度為,在表尾插入元素的時間復雜度為o5 .在線性表的順序存儲中,假設一個元素的下標為i,那么它的前驅(qū)元素的下標為,后繼元素的下標為O6 .在線性表的單鏈式存儲中,假設一個元素所在結(jié)點的地址為p,那么其后繼結(jié)點的地址為假設假定p為一個數(shù)組a中的下標,那么其后繼結(jié)點的下標為o7 .在循環(huán)單鏈表中,最后一個結(jié)點的指針指向結(jié)點.8 .在雙向鏈表中每個結(jié)點包含有兩個指針域,一個指向其結(jié)點,另一個指向其結(jié)點

8、,9 .在循環(huán)雙向鏈表中表頭結(jié)點的左指針域指向結(jié)點,最后一個結(jié)點的右指針域指向結(jié)點,10 .在以HL為表頭指針的帶表頭結(jié)點的單鏈表和循環(huán)單鏈表中,鏈表為空的條件分別為和o三、應用題1.在下面的每個程序段中,假定線性表La的類型為List,元素類型ElemType為int,并假定每個程序段是連續(xù)執(zhí)行的,試寫出每個程序段執(zhí)行后所得到的線性表La.(1) InitList(La);inta尸48,26,57,34,62,79;for(i=0;i<6;i+)InsertFront(La,ai);TraverseList(La);(2) InitList(La);for(i=0;i<6;i+

9、)Insert(La,ai);TraverseList(La);(3) ClearList(La);for(i=0;i<6;i+)InsertRear(La,ai);Delete(La,a5);Sort(La);Insert(La,a5/2);TraverseList(La);3 .對于List類型的線性表,編寫出以下每個算法.(1)從線性表中刪除具有最小值的元素并由函數(shù)返回,空出的位置由最后一個元素填補,假設線性表為空那么顯示出錯信息并退出運行.(2)從線性表中刪除第i個元素并由函數(shù)返回.(3)向線性表中第i個元素位置插入一個元素.(4)從線性表中刪除具有給定值x的所有元素.4 .對于

10、結(jié)點類型為LNode的單鏈表,編寫出以下每個算法.(1)刪除單鏈表中的第i個結(jié)點.(2)在有序單鏈表中才t入一個元素x的結(jié)點.(3)從單鏈表中查找出所有元素的最大值,該值由函數(shù)返回,假設單鏈表為空,那么顯示出錯信息并停止運行.(4)統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù).一、單項選擇題1.棧的插入與刪除操作在A、棧頂B、棧底第三章棧和隊列進行.C、任意位置D、指定位置2.當利用大小為N的一維數(shù)組順序存儲一個棧時,假定用top=0表示?？?那么向這個棧插入一個元素時,需要執(zhí)行A、top+B語句修改top指針.、top-C、top=03 .假設讓元素1,2,3依次進棧,那么出棧次序不可能出現(xiàn)A

11、、3,2,1B>2,1,3C、3,1,4 .在一個循環(huán)順序隊列中,隊首指針指向隊首元素的A、前一個B、后一個C、當前、top種情況.、1,3,2位置.、后面5 .當利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時,該隊列的最大長度為.A、N-2B、N-1C、ND、N+16 .從一個循環(huán)順序隊列刪除元素時,首先需要.A、前移一位隊首指針B、后移一位隊首指針C、取出隊首指針所指位置上的元素D、取出隊尾指針所指位置上的元素7 .假定一個循環(huán)順序隊列的隊首和隊尾指針分別為f和r,那么判斷隊空的條件是.A、f+1=rB、r+1=fC、f=0D、f=r8 .假定一個鏈隊的隊首和隊尾指針分別為front和

12、rear,那么判斷隊空的條件是.A、front=rearB、front!=NULLC、rear!=NULLD、front=NULL二、填空題1 .隊列的插入操作在進行,刪除操作在進行.2 .棧又稱為表,隊列又稱為表.3 .向一個順序棧插入一個元素時,首先把待插入元素到這個位置上然后,使后移一個位置.4 .從一個棧中刪除元素時,首先前移一位,然后再取出o5 .在一個循環(huán)順序隊列Q中,判斷隊空的條件為,判斷隊滿的條件為o6 .在一個順序棧中,假設棧頂指針等于,那么為空棧；假設棧頂指針等于,那么為滿棧.7 .在一個鏈棧中,假設棧頂指針等于NULL.,那么為;在一個鏈隊中,假設隊首指針與隊尾指針的值相

13、同,那么表示該隊列為O8 .向一個鏈棧插入一個新結(jié)點時,首先把新結(jié)點的存儲位置賦給,然后把棧頂指針指向.9 .從一個鏈棧中刪除一個結(jié)點時,需要把棧頂結(jié)點的值賦給o10 .向一個順序隊列插入元素時,需要首先向插入新元素,然后再移動O11 .當用長度為N的一維數(shù)組順序存儲一個棧時,假定用top=0表示棧空,那么表示棧滿的條件為.12 .向一個棧頂指針為HS的鏈棧中插入一個新結(jié)點*P果,應執(zhí)行和操作.13 .從一個棧頂指針為HS的非空鏈棧中刪除結(jié)點并不需要返回棧頂結(jié)點的值和回收結(jié)點時,應執(zhí)行操作.14 .假定front和rear分別為一個鏈隊的隊首和隊尾指針,那么該鏈隊中只有一個結(jié)點的條件為三、應用

14、題執(zhí)行下面函數(shù)調(diào)用后得到的輸出結(jié)果是什么？voidAF(Queue&Q)InitQueue(Q);inta4=5,8,12,15;for(inti=0;i<4;i+)QInsert(Q,ai);QInsert(Q,QDelete(Q);QInsert(Q,30);QInsert(Q,QDelete(Q)+10);while(!QueueEmpty(Q)printf("%d,QDelete(Q);第四章稀疏矩陣和廣義表一、單項選擇題1 .在稀疏矩陣的帶行指針向量的鏈接存儲中,每個行單鏈表中的結(jié)點都具有相同的OA、行號B、列號C、元素值D、地址二、填空題2 .在一個稀疏矩陣

15、中,每個非零元素所對應的三元組包括該元素的、和三項.3 .在稀疏矩陣所對應的三元組線性表中,每個三元組元素按為主序、為輔序的次序排列.4 .在初始化一個稀疏矩陣的函數(shù)定義中,矩陣形參應說明為參數(shù).5 .在稀疏矩陣的順序存儲中,利用一個數(shù)組來存儲非零元素,該數(shù)組的長度應對應三元組線性表的長度.第五章樹和二叉樹(一)一、填空題1 .對于一棵具有n個結(jié)點的樹,該樹中所有結(jié)點的度數(shù)之和為o2 .假定一棵三叉樹的結(jié)點個數(shù)為50,那么它的最小深度為,最大深度為o3 .在一棵三叉樹中,度為3的結(jié)點數(shù)有2個,度為2的結(jié)點數(shù)有1個,度為1的結(jié)點數(shù)為2個,那么度為0的結(jié)點數(shù)有個4.一棵深度為5的滿二叉樹中的結(jié)點數(shù)

16、為個.個,一棵深度為3的滿三叉樹中的結(jié)點數(shù)為,那么樹中所含的結(jié)點數(shù)為個,那么度為3、2、1、0的結(jié)點數(shù)分別為,那么結(jié)點H的雙親結(jié)點為,5 .假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)樹的深度為,樹的度為O6 .假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)、和個.7 .假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)孩子結(jié)點為8 .在一棵二叉樹中,假定雙分支結(jié)點數(shù)為5個,單分支結(jié)點數(shù)為6個,那么葉子結(jié)點數(shù)為個.9 .對于一棵二叉樹,假設一個結(jié)點的編號為i,那么它的左孩子結(jié)點的編號為,右孩子結(jié)點的編號為,雙親結(jié)點的編號為o10 .在一

17、棵二叉樹中,第5層上的結(jié)點數(shù)最多為o11 .假定一棵二叉樹的結(jié)點數(shù)為18,那么它的最小深度為,最大深度為,那么e結(jié)點的雙親結(jié)點為,左孩子,它含有雙親結(jié)點個,單分支結(jié)點12 .一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)結(jié)點為,右孩子結(jié)點為.13 .一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)個,葉子結(jié)點個.14.假定一棵二叉樹順序存儲在一維數(shù)組a中,那么ai元素的左孩子元素為元素為,雙親元素(i>1)為15.假定一棵二叉樹順序存儲在一維數(shù)組a中,但讓編號為1的結(jié)點存入a0元素中,讓編號為2的結(jié)點存入a1元素中,其余類推,那么編號為i結(jié)點的左孩子結(jié)點對應的存儲位置為

18、,假設編號為i結(jié)點的存儲位置用j表示,那么其左孩子結(jié)點對應的存儲位置為16 .假設對一棵二叉樹從0開始進行結(jié)點編號,并按此編號把它順序存儲到一維數(shù)組a中,即編號為0的結(jié)點存儲到a0中,其余類推,那么ai元素的左孩子元素為,右孩子元素為,雙親元素(i>0)為.17 .對于一棵具有n個結(jié)點的二叉樹,對應二叉鏈表中指針總數(shù)為個,其中個用于指向孩子結(jié)點,個指針空閑著.18 .一棵二叉樹廣義表表示為a(b(d(,h),c(e,f(g,i(k),該樹的結(jié)點數(shù)為個,深度為O19 .假定一棵二叉樹廣義表表示為a(b(c),d(e,f),那么對它進行的先序遍歷結(jié)果為,中序遍歷結(jié)果為,后序遍歷結(jié)果為,按層遍

19、歷結(jié)果為20 .假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d),那么先根遍歷結(jié)果為,按層遍歷結(jié)果為o二、應用題1 .一棵具有n個結(jié)點的完全二叉樹被順序存儲于一維數(shù)組的A1An元素中,試編寫一個算法打印出編號為i的結(jié)點的雙親和所有孩子.2 .編寫一算法,求出一棵二叉樹中所有結(jié)點數(shù)和葉子結(jié)點數(shù),假定分別用變參C1和C2統(tǒng)計所有結(jié)點數(shù)和葉子結(jié)點數(shù),初值均為0.第六章二叉樹的應用(二)一、單項選擇題1 .從二叉搜索樹中查找一個元素時,其時間復雜度大致為OAO(n)B、O(1)C、O(log2n)D、O(n2)2 .向二叉搜索樹中插入一個元素時,其時間復雜度大致為oA、O(1

20、)B、O(log2n)C、O(n)D、O(nlog2n)3 .根據(jù)n個元素建立一棵二叉搜索樹時,其時間復雜度大致為oA、O(n)B、O(log2n)C、O(n2)D、O(nlog2n)4 .從堆中刪除一個元素的時間復雜度為oA、O(1)B、O(n)C、O(log2n)D、O(nlog2n)5 .向堆中插入一個元素的時間復雜度為oA、O(log2n)B、O(n)C、O(1)D、O(nlog2n)6 .由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹,它的帶權(quán)路徑長度為oA、24B、48C、72D、53二、填空題1 .在一棵二叉搜索樹中,每個分支結(jié)點的左子樹上所有結(jié)點的值一定該結(jié)點的值,右

21、子樹上所有結(jié)點的值一定該結(jié)點的值.2 .對一棵二叉搜索樹進行中序遍歷時,得到的結(jié)點序列是一個o3 .從一棵二叉搜索樹中查找一個元素時,假設元素的值等于根結(jié)點的值,那么說明,假設元素的值小于根結(jié)點的值,那么繼續(xù)向查找,假設元素的大于根結(jié)點的值,那么繼續(xù)向查找.4 .在一個堆的順序存儲中,假設一個元素的下標為i,那么它的左孩子元素的下標為,右孩子元素的下標為O5 .在一個小根堆中,堆頂結(jié)點的值是所有結(jié)點中的,在一個大根堆中,堆頂結(jié)點的值是所有結(jié)點中的O6 .當從一個小根堆中刪除一個元素時,需要把元素填補到位置,然后再按條件把它逐層調(diào)整.三、應用題1 .一組元素為(46,25,78,62,12,37

22、,70,29),畫出按元素排列順序輸入生成的一棵二叉搜索樹.2 .空堆開始依次向堆中插入線性表(38,64,52,15,73,40,48,55,26,12)中的每個元素,請以線性表的形式給出每插入一個元素后堆的狀態(tài).3 .一個堆為(12,15,40,38,26,52,48,64),假設需要從堆中依次刪除四個元素,請給出每刪除一個元素后堆的狀態(tài).4 .有七個帶權(quán)結(jié)點,其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹,并計算出帶權(quán)路徑長度WPL數(shù)據(jù)結(jié)構(gòu)期末復習練習題答案(僅供參考)第一章緒論一、單項選擇題1. A2.C3.B4.C5.D6.B二、填空題1 .集合結(jié)構(gòu)、

23、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu)2.順序、鏈式3.1:1、1:N、M:N4.數(shù)據(jù)定義、操作聲明5.引用形參(或指針形參)6.引用類型(或指針類型)7.實參、值、rand()%2110.sizeof(a)、a+i*sizeof(a0)、a+i11.參數(shù)類型、數(shù)量、次序12.2、用戶自定義13.=、ra、rb14.O(n)、O(m*n)15.nn(n+1)/2O(n2)16.O(n)第二章線性表一、單項選擇題1. B2.A3.C4.B5.D6.C二、填空題1 .元素值、指針2.(38,56,25,60,42,74)3.O(n)、O(1)4.(1)、O(n)、i+1p->next、ap.next7

24、.表頭8.前驅(qū)、后繼9.表尾、表頭10. HL->next=NULL、HL->next=HL三、應用題(1) 1)(79,62,34,57,26,48)(2) (26,34,48,57,62,79)(3) (26,34,39,48,57,62)2. 12,26,9,8,15,30,50)3. (1)ElemTypeDMValue(List&L)if(ListEmpty(L)A2.B二、填空題1.行號、列號、元素值2.行號、列號3.引用(或指針)4.等于5.4、56.列號、行號7.單、表8.括號9.310.元素值、子表指針11.true、NULL三、應用題1.(1)(1,2,

25、4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6)12234556247142644-3185-726(2)(3)(1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1)122444673152465284-7-356212.(1)A:長度:1深度:2(2)B:長度：3深度：1(3)C:長度：2深度：3(4)D:長度：2深度：2(5)E:長度：3深度：3(6)F:長度：1深度：4第四章棧和隊列一、單項選擇題1.A2,B3.C4.A5.B6.B7.D8,

26、D二、填空題1,隊尾、隊首2.后進先出(LIFO)、先進先出(FIFO)3.棧頂指針、存儲4.棧頂元素、棧頂指針5.front=rear、(rear+1)%QueueMaxSize=front6.-1、StackMaxSize-17.?？?、空隊、隊列只有一個元素8.新結(jié)點的指針域、棧頂指針9.指針域、棧頂指針10.隊尾指針、存儲=0>next=HS、HS=p13,HS=HS->next14.(front=rear)&&(front<>NULL)15.3425615+-/8*+16.(24+8)*3/(4*(10-7)、8三、應用題121553018四、編程題遞歸算法：longFib(intn)if(n=1|n=2)6、21、4、3、1、1、6、I和J