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

1、數(shù)據(jù)結(jié)構(gòu)習題一 4/9習題一一、   單選題1.     在一個帶有附加表頭結(jié)點的單鏈表hl中，若要向表頭插入一個由指針p指向的結(jié)點，則執(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.    若順序存儲的循環(huán)隊列的queuemaxsize=n,則該隊列最多可存儲（ b ）個元素. a. n b.n-1 c.

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

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

4、以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序c. 線性表以順序方式存儲，并且按關(guān)鍵碼值排好序d.線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序8.    對n個記錄進行堆排序，所需要的輔助存儲空為c a. o（1og2n） b. o（n） c. o（1） d. o（n2）9.    對于線性表（7，34，77，25，64，49，20，14）進行散列存儲時，若選用h（k）=k %7作為散列函數(shù)，則散列地址為0的元素有（ d ）個， 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ù)組存儲一棵完全二叉樹是有效的存儲方法二、   填空題1.         數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_ 集合結(jié)構(gòu)、_線性結(jié)構(gòu)、_樹結(jié)構(gòu)和_圖結(jié)構(gòu)四種。2.         一個算

6、法的時間復雜度為(3n3+2000nlog2n+90)/n2，其數(shù)量級表示為_ o(n)_。3.         對于一個長度為n的單鏈存儲的隊列，在表頭插入元素的時間復雜度為_ o(1)_，在表尾插入元素的時間復雜度為_ o(1)_。4.         假定一棵樹的廣義表表示為a（d（e，g），h（i，j），則樹中所含的結(jié)點數(shù)為_7_個，樹的深度為_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_個結(jié)點，最多含有_(25)-1_個結(jié)點。7.         在樹中，一個結(jié)點的直接后繼結(jié)點稱為該結(jié)點的_。一個結(jié)點的直接前趨結(jié)點稱為該結(jié)點的_。8.

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

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

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, 試畫出這棵二叉樹。        當前序序列為abkcdfghij，中序序列為kbcdafhigj時，逐步形成二叉樹的過程如下圖4所示：

11、 fhigjaabkfcdhigjabkfcdgjhiabkfcdgjh     ikbcd圖43    已知一個圖的頂點集v為： v=1,2,3,4,5,6,7; 其共有10條邊。該圖用如下邊集數(shù)組存儲：起點1225522613終點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ù)據(jù)后堆的變化。         見圖5。424442255522884352834652834610513246108528344          圖5四、   閱讀算法1.    在下面的每個程序段中，假定線性表la的類型為list，元素類

13、型elemtype為int，并假定每個程序段是連續(xù)執(zhí)行的。試寫出每個程序段執(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); 前序遍歷鏈式存儲的二叉樹。五、   算法填空二分查找的遞歸算法。 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; /查找成功，返回元素的下標 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)習題二 4/9習題二一、                    

17、 單選題1.     對一個算法的評價，不包括如下（ ）方面的內(nèi)容。 a健壯性和可讀性 b并行性 c正確性 d時空復雜度2.     在帶有頭結(jié)點的單鏈表hl中，要向表頭插入一個由指針p指向的結(jié)點，則執(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)當采用鏈表

18、表示？( ) a.經(jīng)常需要隨機地存取元素 b.經(jīng)常需要進行插入和刪除操作 c.表中元素需要占據(jù)一片連續(xù)的存儲空間 d.表中元素的個數(shù)不變4.     一個棧的輸入序列為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.     采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。a低于鏈接法處理沖突 b. 高于鏈

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

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

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

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

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

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

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

26、，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：(1) 從頂點出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2) 從頂點出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4.         已知一個圖的頂點集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>若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。四、                     閱讀算法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)該算法的時間復雜度是多少？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; /查找成功，返回元素的下標 else if (k<mid.key) _; /在左子表上繼續(xù)查找 else _; /在右子表上繼續(xù)查找return -1; /查找失敗，返回-1六、                     編寫算法hl是單

31、鏈表的頭指針，試寫出刪除頭結(jié)點的算法。elemtype delefront(lnode * & hl)習題二參考答案一、                     單選題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.  &