c語言版數(shù)據(jù)結(jié)構(gòu)試題及答案

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題一 4/9習(xí)題一一、   單選題1.     在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表hl中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( b )。 a. hl=p; p->next=hl; b. p->next=hl->next; hl->next=p; c. p->next=hl; p=hl; d. p->next=hl; hl=p; 2.    若順序存儲(chǔ)的循環(huán)隊(duì)列的queuemaxsize=n,則該隊(duì)列最多可存儲(chǔ)（ b ）個(gè)元素. a. n b.n-1 c.

2、 n+1 d.不確定3.    下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（a ） a存儲(chǔ)密度大 b.插入和刪除運(yùn)算方便 c. 獲取符合某種條件的元素方便 d.查找運(yùn)算速度快4.     設(shè)有一個(gè)二維數(shù)組amn，假設(shè)a00存放位置在600(10)，a33存放位置在678(10)，每個(gè)元素占一個(gè)空間，問a23(10)存放在什么位置？(腳注(10)表示用10進(jìn)制表示,m>3)d a658 b648 c633 d6535.    下列關(guān)于二叉樹遍歷的敘述中，正確的是( ad ) 。a. 若一個(gè)樹葉是某二叉

3、樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)b若一個(gè)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn) c若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個(gè)結(jié)點(diǎn) d若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)結(jié)點(diǎn)6.    k層二叉樹的結(jié)點(diǎn)總數(shù)最多為( a ). a2k-1 b.2k+1 c.2k-1 d. 2k-17.    對線性表進(jìn)行二分法查找，其前提條件是( b ).a.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序 b.線性表

4、以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序c. 線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序d.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序8.    對n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空為c a. o（1og2n） b. o（n） c. o（1） d. o（n2）9.    對于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用h（k）=k %7作為散列函數(shù)，則散列地址為0的元素有（ d ）個(gè)， a1 b2 c3 d410.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是( d ).a. 

5、0;  數(shù)組是不同類型值的集合 b.    遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉c.    樹是一種線性結(jié)構(gòu)d.    用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法二、   填空題1.         數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_ 集合結(jié)構(gòu)、_線性結(jié)構(gòu)、_樹結(jié)構(gòu)和_圖結(jié)構(gòu)四種。2.         一個(gè)算

6、法的時(shí)間復(fù)雜度為(3n3+2000nlog2n+90)/n2，其數(shù)量級表示為_ o(n)_。3.         對于一個(gè)長度為n的單鏈存儲(chǔ)的隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為_ o(1)_，在表尾插入元素的時(shí)間復(fù)雜度為_ o(1)_。4.         假定一棵樹的廣義表表示為a（d（e，g），h（i，j），則樹中所含的結(jié)點(diǎn)數(shù)為_7_個(gè)，樹的深度為_2_，樹的度為_2_。5.     

7、;    后綴算式79 2 30 + - 4 2 / *的值為_94_。中綴算式（3+x*y）-2y/3對應(yīng)的后綴算式為_3 x y * + 2 y * 3 / -_。6.         在一棵高度為5的理想平衡樹中，最少含有_(2(5-1)-1+1_個(gè)結(jié)點(diǎn)，最多含有_(25)-1_個(gè)結(jié)點(diǎn)。7.         在樹中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的_。一個(gè)結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的_。8.

8、60;        在一個(gè)具有10個(gè)頂點(diǎn)的無向完全圖中，包含有_(10*(10-1)/2_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_n*(n-1)_條邊。9.         假定一個(gè)線性表為(12,17,74,5,63,49,82,36)，若按key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_（12，36）_、_（17,5,49）_、_（74，82）_和_（63）_。10.  

9、60;  對一棵b_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹的高度比原樹的高度_減少1（或減少_。11.     在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_ o(log2n)_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_ o(nlog2n)_。12.     在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于_n/m_。三、  運(yùn)算題1    在如下數(shù)組a中鏈接存儲(chǔ)了一個(gè)線性表，表頭

10、指針存放在a 0.next，試寫出該線性表。 a 0 1 2 3 4 5 6 7 data 6050789034 40next405271 3       線性表為：（90，40，78，50，34，60）2 已知一棵二叉樹的前序遍歷的結(jié)果是abkcdfghij, 中序遍歷的結(jié)果是kbcdafhigj, 試畫出這棵二叉樹。        當(dāng)前序序列為abkcdfghij，中序序列為kbcdafhigj時(shí)，逐步形成二叉樹的過程如下圖4所示：

11、 fhigjaabkfcdhigjabkfcdgjhiabkfcdgjh     ikbcd圖43    已知一個(gè)圖的頂點(diǎn)集v為： v=1,2,3,4,5,6,7; 其共有10條邊。該圖用如下邊集數(shù)組存儲(chǔ)：起點(diǎn)1225522613終點(diǎn)6454767775權(quán)1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。        用克魯斯卡爾算法得到的最小生成樹為： (1,6)1, (2,4)1, (2,5)2, (5,

12、7)2, (2,6)3, (3,5)74 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。         見圖5。424442255522884352834652834610513246108528344          圖5四、   閱讀算法1.    在下面的每個(gè)程序段中，假定線性表la的類型為list，元素類

13、型elemtype為int，并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫出每個(gè)程序段執(zhí)行后所得到的線性表la。（1）initlist(la); int a=100,26,57,34,79; for (i=0;i<5;i+) insert(la,ai); traverselist(la);（2）deletefront(la);insertrear(la, deletefront(la); traverselist(la);（3）clearlist(la); for (i=0;i<5;i+) insertfront(la,ai); traverselist(la);   (1

14、) la=(26,34,57,79,100) (2)la=(57,79,100,34) (3)la=(79,34,57,26,100) 2.     現(xiàn)面算法的功能是什么？void abc(btnode * bt) if bt cout<<bt->data<<' ' abc(bt->left); abc(bt->right); 前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。五、   算法填空二分查找的遞歸算法。 int binsch(elemtype a,int low,int high,keyt

15、ype k) if _(low<=high) _ int mid=(low+high)/2; if (_ k=amid.key_) return mid; /查找成功，返回元素的下標(biāo) else if (k<amid.key) return binsch(a,low,mid-1,k); /在左子表上繼續(xù)查找 else return_binsch(a,mid+1,hight,k)_； /在右子表上繼續(xù)查找 else _ return -1_； /查找失敗，返回-1 六、   編寫算法hl為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。bool

16、 find(lnode* hl, elemtype &item)bool find(lnode* hl, elemtype &item) lnode* p=hl; while p if (p->data=item) return true; else p=p->next; return false;數(shù)據(jù)結(jié)構(gòu)習(xí)題二 4/9習(xí)題二一、                    

17、 單選題1.     對一個(gè)算法的評價(jià)，不包括如下（ ）方面的內(nèi)容。 a健壯性和可讀性 b并行性 c正確性 d時(shí)空復(fù)雜度2.     在帶有頭結(jié)點(diǎn)的單鏈表hl中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 a. p->next=hl->next; hl->next=p; b. p->next=hl; hl=p; c. p->next=hl; p=hl; d. hl=p; p->next=hl;3.    對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表

18、表示？( ) a.經(jīng)常需要隨機(jī)地存取元素 b.經(jīng)常需要進(jìn)行插入和刪除操作 c.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間 d.表中元素的個(gè)數(shù)不變4.     一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( ) a. 2 3 1b. 3 2 1 c. 3 1 2 d. 1 2 35.     aov網(wǎng)是一種（ ）。 a有向圖 b無向圖 c無向無環(huán)圖 d有向無環(huán)圖6.     采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（ ）。a低于鏈接法處理沖突 b. 高于鏈

19、接法處理沖突 c與鏈接法處理沖突相同 d高于二分查找7.     若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（ ）參數(shù)。a值 b函數(shù) c指針 d引用8.     在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。a行號(hào) b列號(hào) c元素值 d非零元素個(gè)數(shù)9.     快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。ao(log2n) bo(nlog2n) c0(n) d0(n2)10.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。 a. o(

20、n) b. o(1) c. o(log2n) d. o(n2)二、                     運(yùn)算題1.         數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。當(dāng)結(jié)點(diǎn)之間存在m對n（m：n）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_。2.       

21、60; 隊(duì)列的插入操作是在隊(duì)列的_進(jìn)行，刪除操作是在隊(duì)列的_進(jìn)行。3.         當(dāng)用長度為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=n表示?？?，則表示棧滿的條件是_。4.         對于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。5.         設(shè)w為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字

22、節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組w的數(shù)據(jù)元素共占用_個(gè)字節(jié)。w中第6 行的元素和第4 列的元素共占用_個(gè)字節(jié)。若按行順序存放二維數(shù)組w，其起始地址為100，則二維數(shù)組元素w6，3的起始地址為_。6.         廣義表a= (a,(a,b),(a,b),c),則它的深度為_，它的長度為_。7.         二叉樹是指度為2的_樹。一棵結(jié)點(diǎn)數(shù)為n的二叉樹，其所有結(jié)點(diǎn)的度的總和是_。8.  

23、       對一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)_。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的_。9.         對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_個(gè)，其中_個(gè)用于指向孩子，_個(gè)指針是空閑的。10.     若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組a中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到a0中。其余類推，則a

24、i 元素的左孩子元素為_,右孩子元素為_，雙親元素為_。11.     在線性表的散列存儲(chǔ)中，處理沖突的常用方法有_和_兩種。12.     當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時(shí)，宜采用_排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用_排序。三、                   

25、0; 運(yùn)算題1.         已知一個(gè)6´5稀疏矩陣如右所示，試：（1） 寫出它的三元組線性表；（2） 給出三元組線性表的順序存儲(chǔ)表示。2.         設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。3.         對于圖6所示的有向圖若存儲(chǔ)它采用鄰接表

26、，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4.         已知一個(gè)圖的頂點(diǎn)集v和邊集e分別為： 圖6 v=1,2,3,4,5,6,7;e=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<

27、6,2>,<6,5>若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。四、                     閱讀算法1.            

28、0;        int prime(int n) int i=1; int x=(int) sqrt(n); while (+i<=x) if (n%i=0) break; if (i>x) return 1; else return 0; (1)指出該算法的功能；(2)該算法的時(shí)間復(fù)雜度是多少？2.     寫出下述算法的功能： void aj(adjlist gl, int i, int n) queue q; initqueue(q); cout<<i

29、<<' ' visitedi=true; qinsert(q,i); while(!queueempty(q) int k=qdelete(q); edgenode* p=glk; while(p!=null) int j=p->adjvex; if(!visitedj) cout<<j<<' ' visitedj=true; qinsert(q,j); p=p->next; 五、 算法填空如下為二分查找的非遞歸算法，試將其填寫完整。int binsch(elemtype a ,int n,keytype k)in

30、t low=0;int high=n-1;while (low<=high)int mid=_；if (k=amid.key) return mid; /查找成功，返回元素的下標(biāo) else if (k<mid.key) _; /在左子表上繼續(xù)查找 else _; /在右子表上繼續(xù)查找return -1; /查找失敗，返回-1六、                     編寫算法hl是單

31、鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。elemtype delefront(lnode * & hl)習(xí)題二參考答案一、                     單選題1.b 2.a 3.b 4.c 5.d 6.b 7.d 8.a 9.d 10.c二、           

32、0;         填空題1.         聯(lián)系 圖（或圖結(jié)構(gòu)） 2.       尾 首 3.   top=0 4.   o（1） o（n）5.         128 44 108 6.         3 3 7.         65515132-145-2515637 圖7有序 n-18.  &