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

1、計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)（普專(zhuān)）數(shù)據(jù)結(jié)構(gòu)模擬試卷模擬試卷一一、 單選題（每題 2 分，共20分）1. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線(xiàn)性結(jié)構(gòu)？( ) A. 有向圖 B. 隊(duì)列 C. 線(xiàn)索二叉樹(shù) D. B樹(shù)2. 在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下( )語(yǔ)句序列。 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的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為( )。EAGCBDF圖1A 11 B.35 C. 19 D. 53以下6-8題基于圖1。6. 該二叉樹(shù)結(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. 該二叉樹(shù)結(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. 該二叉樹(shù)的按層遍歷的序列為( )。 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ù)無(wú)關(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ù)無(wú)關(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)被分為_(kāi)、_、_和_四種。2. 對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線(xiàn)性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)，在表尾插入元素的時(shí)間復(fù)雜度為_(kāi)。3. 向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是_;刪除

5、一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是_（假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn)）。4. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，一個(gè)結(jié)點(diǎn)的編號(hào)為i(1in)，若它有左孩子則左孩子結(jié)點(diǎn)的編號(hào)為_(kāi)，若它有右孩子，則右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)，若它有雙親，則雙親結(jié)點(diǎn)的編號(hào)為_(kāi)。5. 當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層_調(diào)整，直到被調(diào)整到_位置為止。6. 以二分查找方法從長(zhǎng)度為10的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_(kāi)。7. 表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為_(kāi)、_和_。8. 對(duì)于線(xiàn)性表（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ù)雜度為_(kāi)，整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)，空間復(fù)雜度為_(kāi)。10. 在一棵m階B_樹(shù)上，每個(gè)非樹(shù)根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為_(kāi)個(gè)，最多為_(kāi)個(gè)，其子樹(shù)數(shù)目最少為_(kāi)，最多為_(kāi)。三、 運(yùn)算題（每題 6 分，共24分）圖21. 寫(xiě)出下列中綴表達(dá)式的后綴形式：（1） 3X/(Y-2)+1（2） 2+X*(Y+3)2. 試對(duì)圖2中的二叉樹(shù)畫(huà)出其：(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ā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。四、 閱讀算法（每題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; 六、 編寫(xiě)算法（共8分）編寫(xiě)從類(lèi)型為L(zhǎng)ist的線(xiàn)性表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）見(jiàn)圖3所示： 3. (1)不是小根堆。調(diào)整為：12,65,33,70,24,56,48,92,86,33 (2)是小根堆。

12、4. 普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)為：(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所指向的二叉樹(shù)的結(jié)點(diǎn)總數(shù)和葉子總數(shù) 五、 算法填空（共8分，每一空2分）newptr=NULL newptr->=data newptr p=p->next六、 編寫(xiě)算法（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è)空間，問(wèn)A23(10)存放在什么位置？(腳注(10)表示用10進(jìn)制表示,m>3) A658 B648 C633 D6535. 下列關(guān)于二叉樹(shù)遍歷的敘述中，正確的是( ) 。A. 若一個(gè)樹(shù)葉是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)B若一個(gè)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn) C若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷

15、的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn) D若一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)6. k層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17. 對(duì)線(xiàn)性表進(jìn)行二分法查找，其前提條件是( ).A. 線(xiàn)性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序 B. 線(xiàn)性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C. 線(xiàn)性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D. 線(xiàn)性表以鏈接方式存儲(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ì)于線(xiàn)性表（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ù)組是不同類(lèi)型值的集合 B. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C. 樹(shù)是一種線(xiàn)性結(jié)構(gòu)D. 用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法二、 填空題（每空1分，共26分）1. 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_(kāi)、_、_和_四種。2. 一個(gè)算法的時(shí)間復(fù)雜度為(3n3+2000nlog2n+90)/n2，其數(shù)量級(jí)表示為_(kāi)。3. 對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的

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

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

19、2 3 4 5 6 7 data605078903440next40527132 已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABKCDFGHIJ, 中序遍歷的結(jié)果是KBCDAFHIGJ, 試畫(huà)出這棵二叉樹(shù)。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試用克魯斯卡爾算法依次求出該圖的最小生成樹(shù)中所得到的各條邊及權(quán)值。4 畫(huà)出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。四、 閱讀算法（每題7分，共14分）1. 在下面的每個(gè)程序段中

20、，假定線(xiàn)性表La的類(lèi)型為L(zhǎng)ist，元素類(lèi)型ElemType為int，并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫(xiě)出每個(gè)程序段執(zhí)行后所得到的線(xiàn)性表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 六、 編寫(xiě)算法（共8分）HL為單鏈表的表頭指針，試寫(xiě)出在該單鏈表中查找具有給定的元素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) 線(xiàn)性結(jié)構(gòu) 樹(shù)結(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. 線(xiàn)性表為：（90，40，78，50，34，60）2. 當(dāng)前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時(shí)，逐步形成二叉樹(shù)的過(guò)程如下圖4所示： AAAAFBBFFBGKCGKCHIGJCDKFHIGJHDJHIJDIKBCD圖43. 用克魯斯卡爾算法得到的最小生成樹(shù)為： (1,6

24、)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)74. 見(jiàn)圖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ǔ)的二叉樹(shù)。五、 算法填空（每空2分，共8 分）(low<=high) K=Amid.key Binsch(A,mid+1,hight,K) return -1六、 編寫(xiě)算法（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ì)線(xiàn)性表，在下列哪種情況下應(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無(wú)向圖 C無(wú)向無(wú)環(huán)圖 D有向無(wú)環(huán)圖6. 采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（ ）。A低于鏈接法處理沖突 B. 高于

27、鏈接法處理沖突 C與鏈接法處理沖突相同 D高于二分查找7. 若需要利用形參直接訪(fǎng)問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（ ）參數(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. 從二叉搜索樹(shù)中查找一個(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í)，稱(chēng)這種結(jié)構(gòu)為_(kāi)。2. 隊(duì)列的插入操作是在隊(duì)列的_進(jìn)行，刪除操作是在隊(duì)列的_進(jìn)行。3. 當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t表示棧滿(mǎn)的條件是_。4. 對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線(xiàn)性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)，在表尾插入元素的時(shí)間復(fù)雜度為_(kāi)。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的起始地址為_(kāi)。6. 廣義表A=

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

30、線(xiàn)性表的散列存儲(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） 寫(xiě)出它的三元組線(xiàn)性表；（2） 給出三元組線(xiàn)性表的順序存儲(chǔ)表示。2. 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 , 試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。3. 對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，

31、試寫(xiě)出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)； 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. 寫(xiě)出下述算法的功能： 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分）如下為二分查找的非遞歸算法，試將其填寫(xiě)完整。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六、 編寫(xiě)算法（共8分）HL是單鏈表的頭指針，試寫(xiě)出刪除頭結(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. 開(kāi)放定址法 鏈接法12. 快速 歸并三、 運(yùn)算題（每題6分，共24分）1. （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元組線(xiàn)性表的順序存儲(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 六、 編寫(xiě)算法（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è)是線(xiàn)性結(jié)構(gòu)？( ) A. 有向圖 B. 棧 C. 二叉樹(shù) D. B樹(shù)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的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為( )。A 11 B.37 C. 19 D. 53以下6-8題基于下面的敘述：若某二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。6. 則該二叉樹(shù)結(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. 該二叉樹(shù)有（ ）個(gè)葉子。 A3 B.2 C.5 D.48. 該二叉樹(shù)的按層遍歷的序列為( ) 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. 下面的二叉樹(shù)中，( )不是完全二叉樹(shù)。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í)，稱(chēng)這種結(jié)構(gòu)為_(kāi)。2. 一個(gè)廣義表中的元素分為_(kāi)元素和_元素兩類(lèi)。3. 對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線(xiàn)性表，在表頭插入元素

40、的時(shí)間復(fù)雜度為_(kāi)，在表尾插入元素的時(shí)間復(fù)雜度為_(kāi)。4. 向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是_;刪除一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是_（假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn)）。5. 棧又稱(chēng)為_(kāi)表，隊(duì)列又稱(chēng)為_(kāi)表。6. 在稀疏矩陣所對(duì)應(yīng)的三元組線(xiàn)性表中，每個(gè)三元組元素按_為主序、_為輔序的次序排列。7. 若一棵二叉樹(shù)中只有葉子結(jié)點(diǎn)和左、右子樹(shù)皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為K，則左、右子樹(shù)皆非空的結(jié)點(diǎn)個(gè)數(shù)是_。8. 以折半（或二分）查找方法從長(zhǎng)度為8的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_(kāi)。9. 表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為_(kāi)、_和_。10. 對(duì)于線(xiàn)性表（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ù)雜度為_(kāi)，整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)，空間復(fù)雜度為_(kāi)。12. 在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱(chēng)為_(kāi)。WPL稱(chēng)為_(kāi)。13. 在索引表中，若一個(gè)索引項(xiàng)對(duì)應(yīng)主表的一個(gè)記錄，則此索引為_(kāi)索引 ，若對(duì)應(yīng)主表的若干條記錄，則稱(chēng)此索引為_(kāi)索引。三、 運(yùn)算題（每題 6 分，共24分）1. 寫(xiě)出下列中綴表達(dá)式的后綴形式：（1） 3X/(Y-2H)+1（2） 2+X*(Y+3)2. 假定一棵二叉樹(shù)廣義表表示為a(b(c),d(e,

42、f)，分別寫(xiě)出對(duì)它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。 先序： 中序： 后序： 按層： ab cde3. 已知一個(gè)無(wú)向圖的頂點(diǎn)集為a, b, c, d, e ,其鄰接矩陣如下所示 (1) 畫(huà)出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫(xiě)出相應(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ā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各

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+