數(shù)據(jù)結(jié)構(gòu)試題及答案修2

1、試卷一一、   單選題（每題 2 分，共20分）1.   對一個算法的評價，不包括如下（）方面的內(nèi)容。 A健壯性和可讀性 B并行性 C正確性 D時空復(fù)雜度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.   

2、對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( )A.經(jīng)常需要隨機(jī)地存取元素 B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間 D.表中元素的個數(shù)不變4.  一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( )A. 2 3 1B. 3 2 1 C. 3 1 2D. 1 2 35.   AOV網(wǎng)是一種（ ）。A有向圖 B無向圖 C無向無環(huán)圖 D有向無環(huán)圖7.   若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（ ）參數(shù)。A值 B函數(shù) C指針 D引用8.  

3、 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（ ）。A行號 B列號 C元素值 D非零元素個數(shù)二、 填空題（每空1分，共28分）1.     數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。當(dāng)結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_。2.     隊列的插入操作是在隊列的_尾_進(jìn)行，刪除操作是在隊列的_首_進(jìn)行。3.     當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示棧空，則表示棧滿的條件是_top=

4、0_。4.        對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為_，在表尾插入元素的時間復(fù)雜度為_。7.        二叉樹是指度為2的_樹。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是_。8.        對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點序列是一個_。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點序列是該算術(shù)表達(dá)式的_。9. 

5、;       對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_個，其中_個用于指向孩子，_個指針是空閑的。10.    若對一棵完全二叉樹從0開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A0中。其余類推，則A i 元素的左孩子元素為_,右孩子元素為_，雙親元素為_。11.    在線性表的散列存儲中，處理沖突的常用方法有_和_兩種。 三、      

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

7、;    對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：從頂點出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；從頂點出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 圖64.        已知一個圖的頂點集V和邊集E分別為： V=1,2,3,4,5,6,7;E=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<

8、5,7>,<6,1>,<6,2>,<6,5>若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。四、 閱讀算法（每題7分，共14分）1.        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;

9、 (1) 指出該算法的功能；(2)     該算法的時間復(fù)雜度是多少？2.  寫出下述算法的功能： void AJ(adjlist GL, int i, int n) Queue Q; InitQueue(Q); cout<<i<<' ' visitedi=true; QInsert(Q,i); while(!QueueEmpty(Q) int k=QDelete(Q); edgenode* p=GLk; while(p!=NULL) int j=p->adjvex; if(!visite

10、dj) cout<<j<<' ' visitedj=true; QInsert(Q,j); p=p->next; HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。ElemType DeleFront(LNode * & HL)參考答案一、單選題（每題2分，共20分）1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C二、 填空題（每空1分，共26分）1.         聯(lián)系 圖（或圖結(jié)構(gòu)）2.  

11、0;      尾 首3.         top=04.         O（1） O（n）5.         128 44 1086.         3 3 7.     

12、    65515132-145-2515637 圖7有序 n-18.         有序序列 后綴表達(dá)式（或逆波蘭式）9.         2n n-1 n+110.     2i+1 2i+2 (i-1)/211.     開放定址法 鏈接法12.     快速 歸并三、 

13、                    運算題（每題6分，共24分）1.         （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)圖8（2） 三元組線性表的順序存儲表示如圖7示。2.       &#

14、160; 如圖8所示。3.         DFS： BFS： 4.         拓樸排序為： 4 3 6 5 7 2 1 四、                      閱讀算法（每題7分，共14分）1. 

15、0;       (1) 判斷n是否是素數(shù)（或質(zhì)數(shù)）（2）O（）2.         功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 六、  編寫算法（8分）ElemType DeleFront(LNode * & HL)if (HL=NULL) cerr<<"空表"<<endl;exit(1);LNode* p=HL;HL=HL->next;ElemType te

16、mp=p->data;delete p;return temp; 試卷十三 一、選擇題(30分)1下列程序段的時間復(fù)雜度為（ ）。for(i=0； i<m； i+) for(j=0； j<t； j+) cij=0；for(i=0； i<m； i+) for(j=0； j<t； j+) for(k=0； k<n； k+) cij=cij+aik*bkj；(A) O(m*n*t)(B) O(m+n+t)(C) O(m+n*t)(D) O(m*t+n)2設(shè)順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動（ ）個元素。(A) n-i(B) n+l

17、-i(C) n-1-i(D) i3設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為（ ）。 (A) N1-1(B) N2-1(C) N2+N3(D) N1+N34利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為（ ）。 (A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(1og2n)5設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為（ ）。(A) p->right=s； s->left=p； p->

18、;right->left=s； s->right=p->right；(B) s->left=p；s->right=p->right；p->right=s； p->right->left=s；(C) p->right=s； p->right->left=s； s->left=p； s->right=p->right；(D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；7設(shè)輸入序列1、2、3、n經(jīng)過棧作用

19、后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（ ）。(A) n-i(B) n-1-i(C) n+l -i(D) 不能確定8設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。(A) 小于等于m的最大奇數(shù)(B) 小于等于m的最大素數(shù)(C) 小于等于m的最大偶數(shù)(D) 小于等于m的最大合數(shù)9設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有（ ）個。(A) 4(B) 5(C) 6(D) 710.設(shè)完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。 (A) n(n-1)/2(B

20、) n(n-1)(C) n(n+1)/2(D) (n-1)/214.設(shè)有向無環(huán)圖G中的有向邊集合E=<1，2>，<2，3>，<3，4>，<1，4>，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?）。(A) 1，2，3，4(B) 2，3，4，1(C) 1，4，2，3(D) 1，2，4，3二、填空題(30分)1 設(shè)指針p指向單鏈表中結(jié)點A，指針s指向被插入的結(jié)點X，則在結(jié)點A的前面插入結(jié)點X時的操作序列為：1）s->next=_；2) p->next=s；3) t=p->data；4) p->data=_；5) s-

21、>data=t；2設(shè)某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有_個葉子結(jié)點。3 設(shè)某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中最多存儲_隊列元素。6       設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_。7       設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序

22、序列為_。8       設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為_。 10   設(shè)無向圖G（如右圖所示），則其最小生成樹上所有邊的權(quán)值之和為_。 三、判斷題(20分)1    有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。( )2    對鏈表進(jìn)行插入和刪除操作時不必移動鏈表中結(jié)點。( )3   

23、; 子串“ABC”在主串“AABCABCD”中的位置為2。( )4    若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。( )6    用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。( )7    中序遍歷一棵二叉排序樹可以得到一個有序的序列。( )8    入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。( )9    順序表查找指的

24、是在順序存儲結(jié)構(gòu)上進(jìn)行查找。（ ）10堆是完全二叉樹，完全二叉樹不一定是堆。（ ）五、算法設(shè)計題(20分)1    設(shè)計計算二叉樹中所有結(jié)點值之和的算法。2    設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。3    設(shè)計判斷單鏈表中元素是否是遞增的算法。參考答案一、選擇題1A2A3A4C5D6D7C8B9C10A11C12C13D14A15A二、填空題1.         p->next，s->data 2. 

25、;        50 3.         m-1 4.         6，8 5.         快速，堆6.         19/77.     &

26、#160;   CBDA 8.         6 9.         (24，65，33，80，70，56，48) 10.     8三、判斷題1錯2對3對4對5錯6錯7對8對9錯10對四、算法設(shè)計題1設(shè)計計算二叉樹中所有結(jié)點值之和的算法。void sum(bitree *bt,int &s)if(bt!=0) s=s+bt->data; sum(bt->

27、;lchild,s); sum(bt->rchild,s);2   設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。void quickpass(int r, int s, int t)int i=s,j=t,x=rs;while(i<j)while (i<j && rj%2=0) j=j-1; if (i<j) ri=rj;i=i+1;while (i<j && ri%2=1) i=i+1; if (i<j) rj=ri;j=j-1;ri=x;3   設(shè)計判斷單鏈表中元素是否是遞增的算法。int

28、 isriselk(lklist *head)if(head=0|head->next=0) return(1);elsefor(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0);return(1); 試卷十四 一、選擇題(24分)1下列程序段的時間復(fù)雜度為（ ）。i=0，s=0； while (s<n) s=s+i；i+；(A) O(n1/2)(B) O(n1/3)(C) O(n)(D) O(n2)2設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素

29、，則選用下列（ ）存儲方式最節(jié)省運算時間。(A) 單向鏈表(B) 單向循環(huán)鏈表(C) 雙向鏈表(D) 雙向循環(huán)鏈表3設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為（ ）。(A) s->next=p->next；p->next=-s；(B) q->next=s； s->next=p；(C) p->next=s->next；s->next=p；(D) p->next=s；s->next=q；4設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的

30、輸出序列為（ ）。(A) 5，3，4，6，1，2(B) 3，2，5，6，4，1(C) 3，1，2，5，4，6(D) 1，5，4，6，2，35設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A54地址與A00的地址之差為（ ）。(A) 10(B) 19(C) 28(D) 556設(shè)一棵m叉樹中有N1個度數(shù)為1的結(jié)點，N2個度數(shù)為2的結(jié)點，Nm個度數(shù)為m的結(jié)點，則該樹中共有（ ）個葉子結(jié)點。(A) (B) (C) (D) 8. 設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)

31、造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（ ）。(A) 129(B) 219(C) 189(D) 2299. 設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（ ）次線性探測。(A) n2 (B) n(n+1)(C) n(n+1)/2(D) n(n-1)/210.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n，則這棵二叉中共有（ ）個結(jié)點。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 二、填空題(48分，其中最后兩小題各6分)1.       

32、  設(shè)需要對5個不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_次，至多需要比較_次。5.         設(shè)一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_個空指針域。6.         設(shè)指針變量p指向單鏈表中結(jié)點A，則刪除結(jié)點A的語句序列為：q=p->next；p->data=q->data；p->next=_；feee(q)；7.    

33、60;    數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：_、_和_。8.         設(shè)無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為_；用鄰接表作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為_。.12.     設(shè)有向圖G中的有向邊的集合E=<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，&

34、lt;6，5>，則該圖的一個拓?fù)湫蛄袨開。13.     下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。typedef struct nodeint data;struct node *lchild;_;bitree;void createbitree(bitree *&bt)scanf(“%c”,&ch);if(ch='#') _;else bt=(bitree*)malloc(sizeof(bitree); bt->data=ch; _;createbitree(bt->rchild)