綿陽數(shù)據(jù)結(jié)構(gòu)

1、一、 單項(xiàng)選擇題（本大題共20小題，每小題1分，共20分）請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1. 在順序存儲(chǔ)的線性表(a1,a2,.,an)中,刪除任意一個(gè)結(jié)點(diǎn)時(shí)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為（）。 A、n B、n/2 C、(n-1)/2 D、(n+1)/22.下列算法suanfa2的時(shí)間復(fù)雜度為_。int suanfa2(int n) int t=1； while(t<=n) t=t*2；return t； A.O(log2n) B.O(n) C.O(n2) D.O(2n) 3._又稱為FIFO表。A.隊(duì)列 B.棧 C.散列表 D.哈希表 4.若6行8列的數(shù)組以列序?yàn)橹餍蝽樞虼鎯?chǔ),基地址

2、為1000,每個(gè)元素占2個(gè)存儲(chǔ)單元,則第5行第3列的元素(假定無第0行第0列)的地址是_。 A.1086 B.1068 C.1032 D.答案A,B,C都不對(duì)5.廣義表(a,(b,( ),c),(d,(e)的深度是_。 A.2 B.3 C.4 D.56. 若待排序列已基本有序，要使它們完全有序，從關(guān)鍵碼比較次數(shù)和移動(dòng)次數(shù)考慮，應(yīng)當(dāng)使用的排序方法是（）。 A、歸并排序 B、快速排序 C、直接選擇排序 D、直接插入排序7.與中綴表達(dá)式a+b*c-d等價(jià)的前綴表達(dá)式是_。 A.+a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*- 8.折半查找有序表(6,15,30,37,65,

3、68,70,72,89,99),若查找元素37,需依次與表中元素_進(jìn)行比較,。 A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,379.對(duì)長(zhǎng)度為10的表作選擇(簡(jiǎn)單選擇)排序,共需比較_次關(guān)鍵字。 A.45 B.55 C.90 D.11010.對(duì)n個(gè)元素的表作快速排序,在最壞情況下,算法的時(shí)間復(fù)雜度為_。 A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )11.一組記錄的關(guān)鍵字經(jīng)一趟二路歸并排序后得到含有5個(gè)長(zhǎng)度為2的有序表如下：25，48，16，35，79，82，23，40，36，72，在此基礎(chǔ)上按二路歸并排序方法再對(duì)該

4、序列進(jìn)行一趟歸并后的結(jié)果為（）。 A、16，25，35，48，79，82，23，36，40，72 B、16，25，35，48，23，40，79，82，36，72 C、16，25，48，35，79，82，23，36，40，72 D、16，25，35，48，79，23，36，40，72，8212.將線性表的數(shù)據(jù)元素以_結(jié)構(gòu)存放, 查找一個(gè)數(shù)據(jù)元素所需的時(shí)間不依賴于表的長(zhǎng)度。A.循環(huán)雙鏈表 B單鏈表 C.哈希(Hash)表 C.一維數(shù)組 13.設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d,不可得到出棧的元素序列有_。 A.a.b,c,d B.a,d,b,c C.b,a,d,c D.c,d,a,b14.

5、 _ 又是一棵滿二叉樹。 A.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹 B.有15個(gè)結(jié)點(diǎn)的完全二叉樹C.哈夫曼(Huffman)樹 D.二叉排序樹15.查找哈希(Hash)表,解決沖突的的方法有_B_。 A.除留余數(shù)法 B.線性探測(cè)再散列法 C.直接地址法 D.鏈地址法16.算法指的是（ c ） A計(jì)算機(jī)程序 B解決問題的計(jì)算方法 C解決問題的有限運(yùn)算序列 D排序算法 17.由_D_組成的集合是一個(gè)數(shù)據(jù)對(duì)象。 A.不同類型的數(shù)據(jù)項(xiàng) B.不同類型的數(shù)據(jù)元素 C.相同類型的數(shù)據(jù)項(xiàng) D.相同類型的數(shù)據(jù)元素18、在一個(gè)單鏈表HL中，若要向q所指結(jié)點(diǎn)之后插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行  （D

6、）      A、HL=p;p->next=HL     B、p->next=HL;HL=pC、P->next=q->next;q->next=p  D、p->next=q->next;q=p>next19、由權(quán)值分別為3，8，10，2，6的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，該樹中雙分支結(jié)點(diǎn)數(shù)為 A、2  B、3  C、4     D、520 設(shè)sub(s,i,j)的功能是返回串s從第i

7、個(gè)字符開始長(zhǎng)度為j的子串，scopy(s,t)的功能是復(fù)制串t到s，若字符串s=SCIENCESTUDY，則調(diào)用scopy(p,sub(s,1,7)后得到( A)A、p=SCIENCEB、p=STUDY C、s=SCIENCED、s=STUDY17.下圖是一個(gè)AOV網(wǎng)，（B）是它的拓?fù)湫蛄?。ABCDEA.ABCDE B.ACDBE C.ADBCE D.CADBE 18.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（D ）方面的內(nèi)容。A.可讀性 B.正確性 C.時(shí)間復(fù)雜度 D.并行性19.遞歸算法必須使用（A）。A.線性表 B.圖 C.棧 D.隊(duì)列20.當(dāng)稀疏矩陣采用十字鏈表的鏈?zhǔn)酱鎯?chǔ)時(shí)，它的包括元素的行號(hào)、列

8、號(hào)、元素本身的信息和（D）的指針域。A.指向同一行中下一個(gè)有效節(jié)點(diǎn)的指針B.指向同一列中下一個(gè)有效節(jié)點(diǎn)的指針C.分別指向所在行和列的的下一個(gè)有效節(jié)點(diǎn)的指針D.指向頭節(jié)點(diǎn)的指針二、填空題（本大題共10小題，每小題2分，共12分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。1. 在串S=“structure”中，以t為首字符的子串有     2  個(gè)。2. 查找表分為靜態(tài)查找表和動(dòng)態(tài)查找表兩種，二叉排序樹屬于  動(dòng)態(tài)樹表    。3. .第i趟在n-i+l (i=1，2，n-l)個(gè)記錄中

9、選取鍵值最小的記錄作為有序序列的第i個(gè)記錄。這樣的排序方法稱為  選擇排序 。4. 對(duì)某非空二叉樹進(jìn)行前序、中序遍歷時(shí)，所得的結(jié)果完全相同（即結(jié)點(diǎn)序列一致），則這棵二叉樹必定是 完全二叉樹5. 一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱為 數(shù)據(jù)的物理結(jié)構(gòu)6. .線性表中 _元素的個(gè)數(shù) 稱為表的長(zhǎng)度。7. 從二叉排序樹種查找一個(gè)元素的時(shí)間復(fù)雜度是O（log2N）_。8. 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)的元素個(gè)數(shù)為n，n>=0，則該數(shù)據(jù)結(jié)構(gòu)不可能是_空表_。9. 一個(gè)二叉樹可以還原為一棵樹的條件是該二叉樹_中序上將左右子樹分開。10. 有一個(gè)5維矩陣的元素k，則k最多有_24_個(gè)后繼。1. 當(dāng)線性表

10、經(jīng)常需要查找表中的數(shù)據(jù)時(shí)，應(yīng)該采用_順序_存儲(chǔ)結(jié)構(gòu)。2. 一個(gè)棧的輸入順序?yàn)?23，則棧的可能輸出序列有_321_。3. 隊(duì)列的插入是在_隊(duì)尾部_，在_隊(duì)頭_刪除，因此隊(duì)列又稱為_先進(jìn)后出_。4. 一棵二叉樹有30個(gè)節(jié)點(diǎn)，其中葉節(jié)點(diǎn)有10個(gè)，則度為2的節(jié)點(diǎn)有_9_個(gè)，度為1的節(jié)點(diǎn)有_6_個(gè)。5. 一棵二叉樹有n個(gè)節(jié)點(diǎn)，則有_1_指針域被浪費(fèi)了，所以我們通常用這些沒有使用的指針域指向該節(jié)點(diǎn)的前驅(qū)或者后繼，稱之為_線索二叉_樹。6. 如果串采用動(dòng)態(tài)的順序存儲(chǔ)，我們稱為_堆存儲(chǔ)_。在循環(huán)隊(duì)列中，為了正確判定隊(duì)滿和隊(duì)空，常常留一個(gè)空間不存儲(chǔ)數(shù)據(jù)，則隊(duì)滿的條件是_（Q.rear+1）%MAXQSIZE=

11、Q.front_，隊(duì)空的條件是_Q.front=Q.rear_。7. 在線性表的散列存儲(chǔ)中，處理沖突的常用方法有_線性探測(cè)再散列、二次探測(cè)再散列_和_兩種。8. 有一個(gè)8階上三角矩陣（行列序號(hào)從0開始編號(hào)），采用行優(yōu)先順序存儲(chǔ)為一個(gè)順序表，如果第一個(gè)元素的起始地址為L(zhǎng)(0)，每個(gè)元素需要4個(gè)字節(jié)，則任意數(shù)組元素ai,j的存儲(chǔ)開始地址是_。11. 對(duì)某非空二叉樹進(jìn)行前序、中序遍歷時(shí)，所得的結(jié)果完全相同（即結(jié)點(diǎn)序列一致），則這棵二叉樹必定是_完全二叉樹_12. 一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱為 _數(shù)據(jù)的物理結(jié)構(gòu)_。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，具有出隊(duì)和入隊(duì)兩種基本操作，如果采用順序存儲(chǔ)，

12、循環(huán)隊(duì)列的出隊(duì)操作是_p->front= (p->front+1) % MAXLEN13. _（隊(duì)頭：front，隊(duì)列的最大元素個(gè)數(shù)為m）。14. 和隊(duì)列相反，棧是一種具有_先進(jìn)后出_特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。15. 已知單鏈表每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)為：struct nodeint data;node *next;，想在p節(jié)點(diǎn)后插入e元素的操作為：struct node q;q=(struct node *)malloc(sizeof(struct node);q->data=e;q->next=_q->data_;p->next=_q->

13、next_; 16. 堆存儲(chǔ)是指_動(dòng)態(tài)分配的空間都在堆上_。17. 廣義表的表頭可以是廣義表或者獨(dú)立元素，表尾則一定是 第一個(gè)元素去掉剩余的部分_。18. 排序是指 排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。分內(nèi)部排序和外部排序。抽象數(shù)據(jù)類型定義包括三部分：數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作19. 字符串是指_由數(shù)字、字母、下劃線組成的一串字符，模式匹配是指_數(shù)據(jù)結(jié)構(gòu)中字符串的一種基本運(yùn)算，給定一個(gè)子串，要求在某個(gè)字符串中找出與該子串相同的所有子串_。1. 廣義表A=(a)，(),()的表尾是_(a)，(),()_，深度是_3_。2. 有一個(gè)順序表，

14、數(shù)據(jù)元素的定義為：struct datachar name10;int num;data;如果第一個(gè)元素的起始地址為L(zhǎng)(0)，每個(gè)元素需要_個(gè)字節(jié)的存儲(chǔ)空間，則任意第i個(gè)元素的存儲(chǔ)首地址是_。3. 數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)主要包括順序和_鏈?zhǔn)酱鎯?chǔ)_兩種情況。4. 設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較_7_次就可以斷定數(shù)據(jù)元素X是否在查找表中。已知P節(jié)點(diǎn)是某雙向量表的中間節(jié)點(diǎn)，在P節(jié)點(diǎn)后插入S節(jié)點(diǎn)的語句序列是：_ s->next=p->next; p->next=s;5. _三、判斷下列敘述是否正確(本大題共5小題，每小題1分，共5分)1字符串

15、的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。對(duì)2 存在這樣的二叉樹，對(duì)它采用任何次序遍歷結(jié)果都相同。對(duì)3 在堆排序中，一個(gè)堆的堆根元素一定是一個(gè)最小數(shù)或最大數(shù) 對(duì)4 完全二叉樹中，若某個(gè)結(jié)點(diǎn)沒有左孩子，則該結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。對(duì)5 線性表的邏輯順序與存儲(chǔ)順序總是一致的。錯(cuò)四、試畫出下列存儲(chǔ)結(jié)構(gòu)圖(每小題5分,共15分)1.數(shù)組A1.2,0.2 的以列序?yàn)橹餍虻捻樞虼鎯?chǔ)結(jié)構(gòu)。2.依次將元素 A,C,D,B 插入一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出所有插入完成之后的鏈?zhǔn)綏！?.二叉樹的順序存儲(chǔ)結(jié)構(gòu):1.廣義表L=（a,b,(c)）的鏈?zhǔn)酱鎯?chǔ)。3、如下稀疏矩陣的三元組存儲(chǔ)結(jié)構(gòu)。1.畫出數(shù)組A0.2,0.2的以列序?yàn)?/p>

16、主序的順序存儲(chǔ)結(jié)構(gòu)圖，起始地址為loc，每個(gè)元素占有4個(gè)字節(jié)。2.依次將元素 A,C,D,B 插入一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出所有插入完成之后的鏈?zhǔn)綏?，指明棧頂和棧底?.已知圖G中的邊為<a,b>,<a,f>,<c,d>,<e,a>,<b,c>，畫出該圖五、解答題 (每小題6分,共24分)1. 設(shè)電文中出現(xiàn)字字母A、B、C、D、E、F、G、H每個(gè)字母在電文中出現(xiàn)的次數(shù)分別是5，25，4，7，9，12，30，8，請(qǐng)畫出哈夫曼樹，求A,B,C,D的哈夫曼編碼及哈夫曼樹的WPL。2.試按表( 10,8,9,12,20,5,6,15,

17、19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹中, 使之仍是一棵二叉排序樹。 (1)試畫出插入完成之后的二叉排序樹； (2)假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹的平均查找長(zhǎng)度 ASL。3.1 (3)對(duì)該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。中：5,6,8,9,10,12,15,19,20,253.試將森林 F= T1,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹。 T1 T2 T3 T44.已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別是： I,A,B,E,F,G,C,H,D 和 A,E,F,B,I,G,H,C,D 試畫出該二叉樹。1. 設(shè)電文中出現(xiàn)字字母A、B、C、D、E、F

18、、G、H每個(gè)字母在電文中出現(xiàn)的次數(shù)分別是5，25，4，7，9，12，30，8，請(qǐng)畫出哈夫曼樹，求A,B,C,D的哈夫曼編碼及哈夫曼樹的WPL。2.試按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹中, 使之仍是一棵二叉排序樹。 (1)試畫出插入完成之后的二叉排序樹； (2)假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹的平均查找長(zhǎng)度 ASL。 (3)對(duì)該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。4.已知一個(gè)網(wǎng)的鄰接矩陣，畫出它的關(guān)鍵路徑。aij=0表示節(jié)點(diǎn)i到節(jié)點(diǎn)j沒有有向邊aij=k，表示<i,j>的權(quán)為k。0645000

19、000000100000000100000000020000000009700000000400000000020000000040000000003.比較順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)和哈希存儲(chǔ)等幾種存儲(chǔ)模式六、閱讀題（本大題共3小題，每小題5分，共15分）1該算法是用折半查找法在一有序數(shù)組中查找key。若找到，返回其下標(biāo)值，否則返回-1。將算法填充完整。int BinSearch(DataType list,int low,int high,DataType key) int mid; DataType midvalue; while(low<=high) mid=(low+high)/2; m

20、idvalue=listmid; if (key=midvalue) return mid; else if(key<midvalue) high=_mid_ else low=_mid_ return 1;2閱讀下面的算法      void mynote(LinkList &L)       /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針           &#

21、160; if(L&&L->next)                   q=L；L=L>next；p=L；        while(p>next) p=p>next；        p>next=q；q>next=NULL

22、；                             設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。a2,.,an,a13已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。      typedef struct nod

23、e          DateType data；         Struct node * next；      ListNode；      typedef ListNode * LinkList ；      LinkList Leafhead=NUL

24、L；      void Inorder (BinTree T)                     LinkList s；            If(T)     

25、;           Inorder(T>lchild)；                If (!T>lchild)&&(!T>rchild)            

26、60;        s=(ListNode*)malloc(sizeof(ListNode)；                     s>data=T>data；            

27、0;        s>next=Leafhead；                     Leafhead=s；                 &#

28、160;                     Inorder(T>rchild)；                          

29、60;     對(duì)于如下所示的二叉樹                           畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)； 七、算法設(shè)計(jì)題（選一題，本題共9分）1. 設(shè)n個(gè)元素的線性表順序存儲(chǔ)在一維數(shù)組st1.maxlen的前n個(gè)位置上,試將新元素e插入表中第i-1個(gè)和第i個(gè)元素之間,寫出算法。#include <stdio.h>int insert(int arr, int index, int maxlen, int value) int start_index = index-1; for (int i = max