數(shù)據(jù)結(jié)構(gòu)(Python)考試題庫(含參考答案)

PAGE第=page5*2-19頁，共=numpages5*210頁第=page5*210頁，共=numpages5*210頁一、填空題1．構(gòu)成數(shù)據(jù)元素的不可分割的最小單位是。2．以順序存儲結(jié)構(gòu)實現(xiàn)的線性表被稱為。3．隊列中允許進行刪除元素的一端稱為。4．最大容量為M的循環(huán)隊列，隊尾指針是r，隊首指針是f，則隊滿時r，f，M三者之間滿足的關系是。5．串包含的字符個數(shù)稱為串的。6．串中任意個連續(xù)字符組成的子序列被稱為該串的。7．設一個廣義表為(a,(),(c,(d)),(e,f))，則其長度為。8．設有二維數(shù)組array[10][10]，其每個元素的長度為1字節(jié)，按行先序順序存儲，其首地址為2000，則元素A[9][2]的存儲地址為。9．由3個結(jié)點可以構(gòu)造出種不同的二叉樹。10．若一棵二叉樹有10個度為2的結(jié)點，則該二叉樹的葉子結(jié)點個數(shù)是。二、判斷題1．數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)可以劃分為：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀（或網(wǎng)狀）結(jié)構(gòu)。（）2．無向圖中的某個頂點的入度稱為此頂點度。（）3．對含有n個元素的查找表執(zhí)行順序查找時，假定每個元素的查找概率相同，則順序查找某個元素A的平均時間復雜度為O(n)。（）4．對一個長度為n的列表使用冒泡排序算法進行排序，此排序過程的平均時間復雜度為O(n)。（）5．內(nèi)排序的整個排序過程完全在內(nèi)存中進行。（）三、單項選擇題1．連續(xù)存儲設計中，存儲單元的地址（）。A．一定連續(xù) B．一定不連續(xù)C．不一定連續(xù) D．部分連續(xù)、部分不連續(xù)2．設無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。A．n-1 B．n(n+1)/2 C．n(n-1)/2 D．n3．折半查找的平均時間復雜性為（）。A．O（n2） B．O(n) C．O(nlog2n) D．O(log2n)4．在具有n個元素的序列中進行查找，平均查找長度為O(n)的方法是（）。A．順序查找方法 B．散列查找方法 C．分塊查找方法 D．樹形查找方法5．快速排序是一種（）排序。A．插入 B．選擇 C．交換 D．歸并四、簡答題1．假設有一個合適大小的棧S，三個元素的進棧順序為a,b,c，在進棧過程中允許任意的進棧、出棧操作，最終棧S要為空。請寫出可能產(chǎn)生的所有出棧序列。2．請簡述隊列和線性表之間的區(qū)別。3．設串S=“str”，請寫出其所有真子串。4．請簡述空格串和空串的區(qū)別。五、綜合題1．設廣義表A=(a,b)，B=(c,(d,e,g))，C=(A,B)，D=(f,C)。試寫出廣義表D的長度，深度，表頭，表尾。2．設一顆二叉樹的前序和中序遍歷分別為：前序遍歷序列：A,B,D,F,C,E,G,H中序遍歷序列：B,F,D,A,G,E,H,C。請畫出這棵二叉樹。3．設有一無向圖G=(V,E)，其中頂點集合V={1,2,3,4,5,6}，邊集合E={(1,2),(1,3),(1,4),(1,6),(2,3),(3,6),(4,5),(5,6)}。請畫出這一無向圖。4．已知一組記錄為{46,74,53,14,26,38,86,65,27,34}，給出采用冒泡排序法進行排序時每一趟的排序結(jié)果。六、程序設計題1．設有一個單鏈表，請設計算法并編程實現(xiàn)：在這個單鏈表里查找指定元素‘a(chǎn)’。要求：（1）采用面向?qū)ο蟮姆绞骄幊?。?）需要自己定義單鏈表的結(jié)點類和單鏈表類。（3）題目要求的功能請在單鏈表類的一個函數(shù)里實現(xiàn)。答案解析：一、填空題12345數(shù)據(jù)項順序表隊頭F=(r+1)%M長度678910子串42092511二、判斷題12345√×√×√三、單項選擇題12345ACDAC四、簡答題1.c,b,aa,b,cb,a,cb,c,aa,c,b2.隊列是一種受限的（或者特殊的）線性表；線性表可以在任意位置刪除或者插入元素；隊列在隊尾插入元素；隊列在隊頭刪除元素。3.“”（或空串），“s”，“t”，“r”，“st”，“tr”4.空格串表示只含空格的串，其長度為串中空格字符的個數(shù)；空串表示所含字符數(shù)為0的串，其長度為0。五、綜合題1.長度：2深度：4表頭：f表尾：(C)2.A/\BC\/DE//\FGH3.4.(1)[465314263874652734]86(2)[4614263853652734]7486(3)[14263846532734]657486(4)[142638462734]53657486(5)[1426382734]4653657486(6)[14262734]384653657486六、程序設計題1.classNode(object):def__init__(self,data):self.data=dataself.next=NoneclassSingleLinkedList(object):def__init__(self):self.head=Node(None)defIsEmpty(self):ifself.GetLength()==0:returnTrueelse:returnFalsedefFindElement(self):Pos=0cNode=self.headkey=int(input('請輸入想要查找的元素值：'))ifself.IsEmpty():print("當前單鏈表為空！")returnwhilecNode.next!=NoneandcNode.data!=key:cNode=cNode.next