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

1、一、 單項選擇題（本大題共20小題，每小題1分，共20分）請將正確選項前的字母填在題后的括號內(nèi)。1. 在順序存儲的線性表(a1,a2,.,an)中,刪除任意一個結(jié)點時所需移動結(jié)點的平均次數(shù)為（）。 A、n B、n/2 C、(n-1)/2 D、(n+1)/22.下列算法suanfa2的時間復(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.隊列 B.棧 C.散列表 D.哈希表 4.若6行8列的數(shù)組以列序為主序順序存儲,基地址

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

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

4、序列進行一趟歸并后的結(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)存放, 查找一個數(shù)據(jù)元素所需的時間不依賴于表的長度。A.循環(huán)雙鏈表 B單鏈表 C.哈希(Hash)表 C.一維數(shù)組 13.設(shè)依次進入一個棧的元素序列為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個結(jié)點的二叉樹 B.有15個結(jié)點的完全二叉樹C.哈夫曼(Huffman)樹 D.二叉排序樹15.查找哈希(Hash)表,解決沖突的的方法有_B_。 A.除留余數(shù)法 B.線性探測再散列法 C.直接地址法 D.鏈地址法16.算法指的是（ c ） A計算機程序 B解決問題的計算方法 C解決問題的有限運算序列 D排序算法 17.由_D_組成的集合是一個數(shù)據(jù)對象。 A.不同類型的數(shù)據(jù)項 B.不同類型的數(shù)據(jù)元素 C.相同類型的數(shù)據(jù)項 D.相同類型的數(shù)據(jù)元素18、在一個單鏈表HL中，若要向q所指結(jié)點之后插入一個由指針p指向的結(jié)點，則執(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é)點生成一棵哈夫曼樹，該樹中雙分支結(jié)點數(shù)為 A、2  B、3  C、4     D、520 設(shè)sub(s,i,j)的功能是返回串s從第i

7、個字符開始長度為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.下圖是一個AOV網(wǎng)，（B）是它的拓撲序列。ABCDEA.ABCDE B.ACDBE C.ADBCE D.CADBE 18.對一個算法的評價，不包括如下（D ）方面的內(nèi)容。A.可讀性 B.正確性 C.時間復(fù)雜度 D.并行性19.遞歸算法必須使用（A）。A.線性表 B.圖 C.棧 D.隊列20.當稀疏矩陣采用十字鏈表的鏈式存儲時，它的包括元素的行號、列

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

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

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

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

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

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

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

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

16、主序的順序存儲結(jié)構(gòu)圖，起始地址為loc，每個元素占有4個字節(jié)。2.依次將元素 A,C,D,B 插入一個初始狀態(tài)為空的鏈式棧中,試畫出所有插入完成之后的鏈式棧，指明棧頂和棧底。4.已知圖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每個字母在電文中出現(xiàn)的次數(shù)分別是5，25，4，7，9，12，30，8，請畫出哈夫曼樹，求A,B,C,D的哈夫曼編碼及哈夫曼樹的WPL。2.試按表( 10,8,9,12,20,5,6,15,

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

19、000000100000000100000000020000000009700000000400000000020000000040000000003.比較順序存儲、鏈式存儲和哈希存儲等幾種存儲模式六、閱讀題（本大題共3小題，每小題5分，共15分）1該算法是用折半查找法在一有序數(shù)組中查找key。若找到，返回其下標值，否則返回-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é)點的單鏈表的頭指針           &#

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