數(shù)據(jù)結構模擬試題與答案3

1、數(shù)據(jù)結構模擬試題3、單項選擇題1.帶頭結點的單向鏈表為空的判斷條件是）（設頭指針為head ）。A . head = =NULLB.head!=NULLC. head->next= =head head-> next= =NULL2 .非空的單向循環(huán)鏈表的尾結點滿足）（設頭指針為 head ,指針p指向尾結點）。A . p->next=NULLB. p=NULLC. p= =headD. p->next=head3.算法的時間復雜度與）有關。A .所使用的計算機B.計算機的操作系統(tǒng)C.算法本身D.數(shù)據(jù)結構4.設有一個長度為n的順序表，要刪除第i個元素需移動元素的個數(shù)為）

2、。A. n-i+1B . n-iC. n-i-15 .在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執(zhí)行）。A . p=s nextB. pn ext=snext;C . s n ext=pn ext; pn ext=s;D . pn ext= s; sn ext= pn ext6 .在一個鏈隊中,假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為）。A . r=f n ext;B . r=r n ext; C . f=fn ext;D . f=rn ext;7.元素 1, 3, 5,7按順序依次進棧，則該棧的不可能輸出序列是（）（進棧出棧可以交替進行）。B. 7, 5, 1 ,

3、3C. 3, 1, 7, 5&在C語言中，順序存儲長度為3的字符串，需要占用（）個字節(jié)。B. 3C. 6D. 12()。9.在一棵二叉樹中，若編號為i的結點存在左孩子，則左孩子的順序編號為A. 2iB . 2i-1C . 2i+1D . 2i+210 . 一棵具有35個結點的完全二叉樹, 取后一層有 （）個結點。A. 4B . 6C . 16D . 811 .在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（）倍。A. 3B . 2C . 2.5D . 1.5,則可能得到的12 .已知如圖3所示的一個圖，若從頂點V1出發(fā)，按廣度優(yōu)先法進行遍歷一種頂點序列為 （）。A. V1V2V4VN5V

4、3V6V7B. V1V2V4V5V8V3V6V7C. V1V2V4V8V3V5V6V7D. V1V3V6V7V2V4V5V813 .對二叉排序樹進行 （）遍歷，可以使遍歷所得到的序列是有序序列B.后序C.中序D.前序m+1個元素，并且只經(jīng)過一次元14 .設已有m個元素有序，在未排好序的序列中挑選第素的交換就使第m+1個元素排序到位，該方法是 （）。A.折半排序B.冒泡排序C.歸并排序D.簡單選擇排序15 . 一組記錄的關鍵字序列為（47 ,80,57 , 39 , 41 ,46）,利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為）。B.A. 39 , 47, 46, 80, 41 , 57

5、39 , 41 , 46 , 80 , 47 , 57C. 41 , 39, 46, 47, 57, 80D. 39, 80, 46, 47, 41 , 57二. 填空題1 .算法的5個特征為2. 要求在n個數(shù)據(jù)元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數(shù)和算法的時間復雜度分別為 和 。3. 在一個單向鏈表中p所指結點之后插入一個s所指向的結點時，應執(zhí)行s->next=p->next;禾口的操作。4. 在一個單向鏈表中，要刪除p所指結點，已知q指向p所指結點的前驅結點。則可以用 操作。_5. 向一個棧頂指針為h的鏈棧中插入一個s所指結點時，可執(zhí)行s->ne

6、xt=h;和操作。（結點的指針域為next）6. 在一個鏈隊中，設f和r分別為隊頭和隊尾指針，貝U插入s所指結點的操作為r->next=s; 和 （結點的指針域為next）。7兩個串相等的充分必要條件是。&在二叉樹的鏈式存儲結構中，通常每個結點中設置三個域，它們是、。9. 一棵二叉樹中有2n-2條邊（結點間的連線）,其中每一個非葉結點的度數(shù)都為2,則該樹共有非葉結點。10 .如圖1所示的二叉樹，其中序遍歷序列為 圖1圖211 如圖1所示的二叉樹，其后序遍歷序列為 。12 哈希函數(shù)是記錄關鍵字值與該記錄存儲地址之間所構造的對應關系。13 n個元素進行冒泡法排序，通常需要進行 趟冒泡

7、，第j趟冒泡要進行 元素間的比較。三、綜合題1 已知序列11 , 19 , 5, 4, 7, 13 , 2, 10(1) 試給出用歸并排序法對該序列作升序排序時的每一趟的結果(2) 對上述序列用堆排序的方法建立初始堆(要求小根堆，以二叉樹描述建堆過程)。2 設查找表為(7,15,21,22,40,58,68,80,88,89,120),元素的下標依次為 1,2,3,11.(樹中結點用下標表示)(1 )畫出對上述查找表進行折半查找所對應的判定樹(2) 說明成功查找到元素 40需要經(jīng)過多少次比較？(3) 求在等概率條件下，成功查找的平均比較次數(shù)？(1)如果二叉樹中任一結點的值均大于其左孩子的值、小

8、于其右孩子的值，則該樹為叉排序樹，這種說法是否正確？若認為正確，則回答正確，若認為不正確，則舉例說明。(2)設有數(shù)據(jù)集合40 , 29 , 7 , 73 , 101 , 4, 55 , 2 , 81 , 92 , 39,依次取集合中各 數(shù)據(jù)，構造一棵二叉排序樹.4 (1) 一棵二叉樹若它的根結點的值大于左子樹所有結點的值，小于右子樹所有結點的值 ：則該樹一定是二叉排序樹”。該說法是否正確，若認為正確，則回答正確，若認為不正確則 說明理由？(2)設有查找表7, 16 , 4, 8 , 20, 9, 6,18 , 5,依次取表中數(shù)據(jù)構造一棵二叉排序樹 對上述二叉樹給出后序遍歷的結果5.( 1)對給

9、定權值2 , 1 , 3, 3 , 4, 5 ,構造哈夫曼樹。(2)同樣用上述權值構造另一棵哈夫曼樹,使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權路徑長度。四、程序填空題1.以下是用尾插法建立帶頭結點且有n個結點的單向鏈表的程序，結點中的數(shù)據(jù)域從前向后依次為1,2,3,；n,完成程序中空格部分。NODE *create (n)NODE *head , *p, *q;int i;p=(NODE*)malloc(sizeof(NODE);head= ;p next=NULL; /* 建立頭結點 */for(i=1; i<=n; i+) P= ;p_>data=i;p-> ne

10、xt=NULL;q->n ext= ;,return(head);2 .設線性表為(6 ,10 ,16 , 4),以下程序用說明結構變量的方法建立單向鏈表，并輸出鏈表中各結點中的數(shù)據(jù)。#defi ne NULL 0void mai n()NODE a,b,c,d,*head,*p;a. data=6;b. data=10;c. data=16;d. data=4; /*d 是尾結點 */head=;a. n ext=&b;b. n ext=&c;c. n ext=&d; /*以上結束建表過程*/p=head; /*p 為工作指針，準備輸出鏈表*/doprintf(

11、 %dn ”,);,while();3. 以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結構中左、右指針域分別為left和right ,數(shù)據(jù)域data為字符型，BT指向根結點)。void In order (struct BTreeNode *BT) if(BT!=NULL)4. 以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結點）。void In order (struct BTreeNode *BT)if(BT!=NULL)(1) ;(2) ;In order(BT->

12、right);利用上述程序對右圖進行遍歷，結果是綜合練習題答案一、單項選擇題1. D2 . D3 . C4. B5 . C6. C 7 . B 8 . A 9 . A 10 . A11 . B12 . A13. C14. D15 . B二、填空題1 .有窮性、確定性、可行性、零個或多個輸入、一個或多個輸入2 . n-1,0( n)3 . s->n ext=p->n ext;4 . q->n ext=p->n ext;5 . s->n ext=h;6 . r->n ext=s;7.串長度相等且對應位置的字符相等&值域、左指針、右指針9 . n-110

13、. dgbaechif11 . gdbeihfca12 .存儲地址13 . n-1, n-j三、綜合題1.(1)初始 11 , 19 , 5, 4, 7, 13, 2, 10第一趟11 , 194 , 57 , 132 , 10第二趟4, 5, 11 , 192 , 7, 10, 13第三趟2 , 4, 5, 7, 11 , 10 , 11 , 13(2) 4 次(3) ASL=(1+2*2+3*4+4*4)/11=34029395573101(1)不正確，二叉排序樹要求其子樹也是二叉排序樹后續(xù)遍歷5,6, 4, 9, 8, 18, 20, 16, 75.( 1)wpl 仁45wpl2=45四、程序填空題1 -Pq=P