計(jì)算機(jī)應(yīng)用專業(yè)(普專)數(shù)據(jù)結(jié)構(gòu)模擬試卷

1、計(jì)算機(jī)應(yīng)用專業(yè)（普專）數(shù)據(jù)結(jié)構(gòu)模擬試卷模擬試卷一一、 單選題（每題 2 分，共20分）1. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？( ) A. 有向圖 B. 隊(duì)列 C. 線索二叉樹 D. B樹2. 在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下( )語句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q;3. 以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？（ ） A. 在隊(duì)列第

2、i個(gè)元素之后插入一個(gè)元素 B. 從隊(duì)頭刪除一個(gè)元素 C. 判斷一個(gè)隊(duì)列是否為空 D.讀取隊(duì)頭元素的值4. 字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成( )個(gè)不同的字符串？ A.14 B.5 C.6 D.85. 由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為( )。EAGCBDF圖1A 11 B.35 C. 19 D. 53以下6-8題基于圖1。6. 該二叉樹結(jié)點(diǎn)的前序遍歷的序列為( )。A. E、G、F、A、C、D、B B. E、A、G、C、F、B、DC. E、A、C、B、D、G、F D. E、G、A、C、D、F、B7. 該二叉樹結(jié)點(diǎn)的中

3、序遍歷的序列為( )。A. A、B、C、D、E、G、FB. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E. B、D、C、A、F、G、E 8. 該二叉樹的按層遍歷的序列為( )。 AE、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B9. 下面關(guān)于圖的存儲(chǔ)的敘述中正確的是( )。 A用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān) B用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān) C. 用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān) D用鄰接矩陣

4、法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)10. 設(shè)有關(guān)鍵碼序列(q，g，m，z，a，n，p，x，h)，下面哪一個(gè)序列是從上述序列出發(fā)建堆的結(jié)果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z二、 填空題（每空1分，共26分）1. 數(shù)據(jù)的物理結(jié)構(gòu)被分為_、_、_和_四種。2. 對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。3. 向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是_;刪除

5、一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是_（假設(shè)棧不空而且無需回收被刪除結(jié)點(diǎn)）。4. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，一個(gè)結(jié)點(diǎn)的編號(hào)為i(1in)，若它有左孩子則左孩子結(jié)點(diǎn)的編號(hào)為_，若它有右孩子，則右孩子結(jié)點(diǎn)的編號(hào)為_，若它有雙親，則雙親結(jié)點(diǎn)的編號(hào)為_。5. 當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層_調(diào)整，直到被調(diào)整到_位置為止。6. 以二分查找方法從長(zhǎng)度為10的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_。7. 表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為_、_和_。8. 對(duì)于線性表（70，34，55，23，65，41，20）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素有_個(gè)，散列地

6、址為6的有_個(gè)。9. 在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為_，整個(gè)排序過程的時(shí)間復(fù)雜度為_，空間復(fù)雜度為_。10. 在一棵m階B_樹上，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為_個(gè)，最多為_個(gè)，其子樹數(shù)目最少為_，最多為_。三、 運(yùn)算題（每題 6 分，共24分）圖21. 寫出下列中綴表達(dá)式的后綴形式：（1） 3X/(Y-2)+1（2） 2+X*(Y+3)2. 試對(duì)圖2中的二叉樹畫出其：(1) 順序存儲(chǔ)表示的示意圖；(2) 二叉鏈表存儲(chǔ)表示的示意圖。3. 判斷以下序列是否是小根堆? 如果不是, 將它調(diào)整為小根堆。（1） 12,24,33,65,33,56,48,92,86,70 （2） 05, 23

7、, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 4. 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為： V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4, (4,7)20,(5,6)18,(6,7)25; 按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。四、 閱讀算法（每題7分，共14分）1. void AE(Stack& S) InitStack(S); Push(S,3); Push(S,4); int x=

8、Pop(S)+2*Pop(S); Push(S,x); int i,a5=1,5,8,12,15; for(i=0;i<5;i+) Push(S,2*ai); while(!StackEmpty(S) cout<<Pop(S)<<' ' 該算法被調(diào)用后得到的輸出結(jié)果為：2. void ABC (BTNode *BT,int &c1,int &c2) if (BT !=NULL ) ABC(BT->left,c1,c2); c1+; if (BT->left=NULL&&BT->right=NULL)

9、 c2+; ABC(BT->right,c1,c2); /if 該函數(shù)執(zhí)行的功能是什么？五、 算法填空（共8分）向單鏈表的末尾添加一個(gè)元素的算法。Void InsertRear(LNode*& HL,const ElemType& item)LNode* newptr;newptr=new LNode;If (_)cerr<<"Memory allocation failare!"<<endl;exit(1);_=item;newptr->next=NULL;if (HL=NULL) HL=_;elseLNode* P=H

10、L;While (P->next!=NULL) _;p->next=newptr; 六、 編寫算法（共8分）編寫從類型為L(zhǎng)ist的線性表L中將第i個(gè)元素刪除的算法，（假定不需要對(duì)i的值進(jìn)行有效性檢查,也不用判別L是否為空表。） void Delete(List& L, int i)模擬試卷一參考答案一、 單選題（每題2分，共20分）1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B二、 填空題（每空1分，共26分）1. 順序 鏈表 索引 散列2. O(n) O(1)圖33. p->next=HS;HS=p HS=HS->next4.

11、 2i 2i+1 ëi/2û（或i/2）5. 向上 根6. 2.97. 鄰接矩陣 鄰接表 邊集數(shù)組8. 1 49. O(n) O(nlog2n) O(n)10. ém/2ù-1 m-1 ém/2ù m 三、 運(yùn)算題（每題6分，共24分）1. (1) 3 X * Y 2 - / 1 + (2) 2 X Y 3 + * + 2. （1）（3分）012345678910111213141831123456789 （2）見圖3所示： 3. (1)不是小根堆。調(diào)整為：12,65,33,70,24,56,48,92,86,33 (2)是小根堆。

12、4. 普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹為：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20四、 閱讀算法（每題7分，共14分）1. 30 24 16 10 2 102. 該函數(shù)的功能是：統(tǒng)計(jì)出BT所指向的二叉樹的結(jié)點(diǎn)總數(shù)和葉子總數(shù) 五、 算法填空（共8分，每一空2分）newptr=NULL newptr->=data newptr p=p->next六、 編寫算法（8分） void Delete(List& L, int i) for(int j=i-1;j<L.size-1; j+) L.listj=L.listj

13、+1; /第i個(gè)元素的下標(biāo)為i-1 L.size-; 模擬試卷二一、 單選題（每題 2 分，共20分）1. 在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 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ǔ)（ ）個(gè)元素. A. n B.n-1 C. n+1 D.不確定3. 下述哪一條是順序存儲(chǔ)方式的優(yōu)

14、點(diǎn)？（ ） 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) A658 B648 C633 D6535. 下列關(guān)于二叉樹遍歷的敘述中，正確的是( ) 。A. 若一個(gè)樹葉是某二叉樹的中序遍歷的最后一個(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)是某二叉樹的中序遍歷

15、的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個(gè)結(jié)點(diǎn) D若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)結(jié)點(diǎn)6. k層二叉樹的結(jié)點(diǎn)總數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 對(duì)線性表進(jìn)行二分法查找，其前提條件是( ).A. 線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序 B. 線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C. 線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D. 線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序8. 對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為 A. O（1og2n） B. O（n） C. O（1）

16、D. O（n2）9. 對(duì)于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素有（ ）個(gè)， A1 B2 C3 D410. 下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是( ).A. 數(shù)組是不同類型值的集合 B. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C. 樹是一種線性結(jié)構(gòu)D. 用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法二、 填空題（每空1分，共26分）1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2. 一個(gè)算法的時(shí)間復(fù)雜度為(3n3+2000nlog2n+90)/n2，其數(shù)量級(jí)表示為_。3. 對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的

17、隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。4. 假定一棵樹的廣義表表示為A（D（E，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_，樹的度為_。5. 后綴算式79 2 30 + - 4 2 / *的值為_。中綴算式（3+X*Y）-2Y/3對(duì)應(yīng)的后綴算式為_。6. 在一棵高度為5的理想平衡樹中，最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(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. 在一個(gè)具有10個(gè)頂點(diǎn)的無向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。9. 假定一個(gè)線性表為(12,17,

18、74,5,63,49,82,36)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_、_、_和_。10. 對(duì)一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹的高度比原樹的高度_。11. 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。12. 在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于_。三、 運(yùn)算題（每題 6 分，共24分）1 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在A 0.next，試寫出該線性表。 A 0 1

19、2 3 4 5 6 7 data605078903440next40527132 已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ, 中序遍歷的結(jié)果是KBCDAFHIGJ, 試畫出這棵二叉樹。3 已知一個(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)值。4 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。四、 閱讀算法（每題7分，共14分）1. 在下面的每個(gè)程序段中

20、，假定線性表La的類型為L(zhǎng)ist，元素類型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); TraverseL

21、ist(La);2. 現(xiàn)面算法的功能是什么？void ABC(BTNode * BT) if BT cout<<BT->data<<' ' ABC(BT->left); ABC(BT->right); 五、 算法填空（共8分）二分查找的遞歸算法。 Int Binsch(ElemType A,int low,int high,KeyType K) if _ int mid=(low+high)/2; if (_) return mid; /查找成功，返回元素的下標(biāo) else if (K<Amid.key) return Binsch

22、(A,low,mid-1,K); /在左子表上繼續(xù)查找 else return_； /在右子表上繼續(xù)查找 else _； /查找失敗，返回-1 六、 編寫算法（共8分）HL為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。bool Find(LNode* HL, ElemType &item)模擬試卷二參考答案一、 單選題（每題2分，共20分）1.B 2.B 3.A 4.C 5.D 6.A 7.C 8.C 9.D 10.D二、 填空題（每空1分，共26分）1. 集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹結(jié)構(gòu) 圖結(jié)構(gòu)2. O(n)3. O(1) O(1)4. 7 3 25. 94 3

23、X Y * + 2 Y * 3 / -6. 16 317. 孩子（或子）結(jié)點(diǎn) 雙親（或父）結(jié)點(diǎn)8. 45 n(n-1)9. （12，36） （17,5,49） （74，82） （63）10. 減少1（或減少）11. O(log2n) O(nlog2n)12. n/m三、 運(yùn)算題（每題6分，共24分）1. 線性表為：（90，40，78，50，34，60）2. 當(dāng)前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時(shí)，逐步形成二叉樹的過程如下圖4所示： AAAAFBBFFBGKCGKCHIGJCDKFHIGJHDJHIJDIKBCD圖43. 用克魯斯卡爾算法得到的最小生成樹為： (1,6

24、)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)74. 見圖5。222444555244423881222253553351064310486484868圖5四、 閱讀算法（每題7分，共14分）1. (1) La=(26,34,57,79,100) (2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2. 前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。五、 算法填空（每空2分，共8 分）(low<=high) K=Amid.key Binsch(A,mid+1,hight,K) return -1六、 編寫算法（8分）bool Find

25、(LNode* HL, ElemType &item) LNode* p=HL; while p if (p->data=item) return true; else p=p->next; return false;模擬試卷三一、 單選題（每題 2 分，共20分）1. 對(duì)一個(gè)算法的評(píng)價(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

26、=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL;3. 對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) 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í)，其平均查找長(zhǎng)度（ ）。A低于鏈接法處理沖突 B. 高于

27、鏈接法處理沖突 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(n) B. O(1) C. O(log2n) D. O(n2)二、 運(yùn)算題（每題 6 分，共24分）1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。

28、當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_。2. 隊(duì)列的插入操作是在隊(duì)列的_進(jìn)行，刪除操作是在隊(duì)列的_進(jìn)行。3. 當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t表示棧滿的條件是_。4. 對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。5. 設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(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=

29、(a,(a,b),(a,b),c),則它的深度為_，它的長(zhǎng)度為_。7. 二叉樹是指度為2的_樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是_。8. 對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)_。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的_。9. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_個(gè)，其中_個(gè)用于指向孩子，_個(gè)指針是空閑的。10. 若對(duì)一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A0中。其余類推，則A i 元素的左孩子元素為_,右孩子元素為_，雙親元素為_。11. 在

30、線性表的散列存儲(chǔ)中，處理沖突的常用方法有_和_兩種。12. 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用_排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用_排序。三、 運(yùn)算題（每題6分，共24分）1. 已知一個(gè)6´5稀疏矩陣如右所示，試：（1） 寫出它的三元組線性表；（2） 給出三元組線性表的順序存儲(chǔ)表示。2. 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。3. 對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，

31、試寫出：(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>,<6,2>,<6,5>若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試

32、給出得到的拓樸排序的序列。四、 閱讀算法（每題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; (1) 指出該算法的功能；(2) 該算法的時(shí)間復(fù)雜度是多少？2. 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) Queue Q; InitQueue(Q); cout<<i<<' ' visitedi=true

33、; 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; 五、 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。Int Binsch(ElemType A ,int n,KeyType K)int low=0;int high=n-1;while (

34、low<=high)int mid=_；if (K=Amid.key) return mid; /查找成功，返回元素的下標(biāo) else if (K<mid.key) _; /在左子表上繼續(xù)查找 else _; /在右子表上繼續(xù)查找return -1; /查找失敗，返回-1六、 編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。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)系

35、 圖（或圖結(jié)構(gòu)）2. 尾 首3. top=04. O（1） O（n）5. 128 44 1086. 3 3 65515132-145-2515637 圖77. 有序 n-18. 有序序列 后綴表達(dá)式（或逆波蘭式）9. 2n n-1 n+110. 2i+1 2i+2 (i-1)/211. 開放定址法 鏈接法12. 快速 歸并三、 運(yùn)算題（每題6分，共24分）1. （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元組線性表的順序存儲(chǔ)表示如圖7示。圖82. 如圖8所示。3. DFS： BFS： 4. 拓樸排序?yàn)椋?4 3 6 5 7 2

36、1 四、 閱讀算法（每題7分，共14分）1. (1) 判斷n是否是素?cái)?shù)（或質(zhì)數(shù)） （2）O（）2. 功能為：從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。五、 算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、 編寫算法（8分）ElemType DeleFront(LNode * & HL)if (HL=NULL) cerr<<"空表"<<endl;exit(1);LNode* p=HL;HL=HL->next;ElemType temp=p->data;delete p;retur

37、n temp; 模擬試卷四一、 單選題（每題 2 分，共20分）1. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？( ) A. 有向圖 B. 棧 C. 二叉樹 D. B樹2. 若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。 A.單鏈表 B.雙鏈表 C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表3. 以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？（ ） A. 在隊(duì)列第i個(gè)元素之后插入一個(gè)元素 B. 從隊(duì)頭刪除一個(gè)元素 C. 判斷一個(gè)隊(duì)列是否為空 D.讀取隊(duì)頭元素的值4. 字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成( )個(gè)不同的字符串？

38、A.15 B.14 C.16 D.215. 由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為( )。A 11 B.37 C. 19 D. 53以下6-8題基于下面的敘述：若某二叉樹結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。6. 則該二叉樹結(jié)點(diǎn)的前序遍歷的序列為( ). A. E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B7. 該二叉樹有（ ）個(gè)葉子。 A3 B.2 C.5 D.48. 該二叉樹的按層遍歷的序列為( ) AE、G、F、A、C、D

39、、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B9. 下面的二叉樹中，( )不是完全二叉樹。10. 設(shè)有關(guān)鍵碼序列(q，g，m，z，a)，下面哪一個(gè)序列是從上述序列出發(fā)建的小根堆的結(jié)果?( ) A. a，g ，m，q， z B. a，g ，m，z,q C. g ，m，q，a，z D. g， m， a，q，z二、 填空題（每空1分，共26分）1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_。當(dāng)結(jié)點(diǎn)之間存在1對(duì)N（1：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_。2. 一個(gè)廣義表中的元素分為_元素和_元素兩類。3. 對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素

40、的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。4. 向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是_;刪除一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是_（假設(shè)棧不空而且無需回收被刪除結(jié)點(diǎn)）。5. 棧又稱為_表，隊(duì)列又稱為_表。6. 在稀疏矩陣所對(duì)應(yīng)的三元組線性表中，每個(gè)三元組元素按_為主序、_為輔序的次序排列。7. 若一棵二叉樹中只有葉子結(jié)點(diǎn)和左、右子樹皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為K，則左、右子樹皆非空的結(jié)點(diǎn)個(gè)數(shù)是_。8. 以折半（或二分）查找方法從長(zhǎng)度為8的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_。9. 表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為_、_和_。10. 對(duì)于線性表（78，4，56，30，6

41、5）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %5作為散列函數(shù)，則散列地址為0的元素有_個(gè)，散列地址為4的有_個(gè)。11. 在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為_，整個(gè)排序過程的時(shí)間復(fù)雜度為_，空間復(fù)雜度為_。12. 在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹中，帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為_。WPL稱為_。13. 在索引表中，若一個(gè)索引項(xiàng)對(duì)應(yīng)主表的一個(gè)記錄，則此索引為_索引 ，若對(duì)應(yīng)主表的若干條記錄，則稱此索引為_索引。三、 運(yùn)算題（每題 6 分，共24分）1. 寫出下列中綴表達(dá)式的后綴形式：（1） 3X/(Y-2H)+1（2） 2+X*(Y+3)2. 假定一棵二叉樹廣義表表示為a(b(c),d(e,

42、f)，分別寫出對(duì)它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。 先序： 中序： 后序： 按層： ab cde3. 已知一個(gè)無向圖的頂點(diǎn)集為a, b, c, d, e ,其鄰接矩陣如下所示 (1) 畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。4. 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為： V=0,1,2,3,4,5,6,7; E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20;按照普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各

43、條邊。四、 閱讀算法（每題7分，共14分）1. void AE(Stack& S) InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a5=2,5,8,22,15; for(i=0;i<5;i+) Push(S,ai); while(!StackEmpty(S) cout<<Pop(S)<<' ' 該算法被調(diào)用后得到的輸出結(jié)果為：2. int akm ( unsigned m, unsigned n ) if ( m = 0 ) return n