“數據結構”知識要點02試卷課程編號：BWCST2013學習中心： 學籍號： 姓名： 注意事項：1、本試卷滿分100分，考試時間120分鐘；2、考試形式：閉卷考試。一、單選題（每題3分，共45分）.算法是（）。A、計算機代碼 B、解決問題的計算方法C、查找算法 D、解決問題的有限運算序列.抽象數據類型的三個組成部分分別為（）。A、數據對象、數據關系和數據操作 B、數據元素、邏輯結構和存儲結構C、數據項、數據元素和數據類型 D、數據元素、邏輯結構和數據類型.線性表L=（a1,a2,……,an），下列說法正確的是（ ）。A、每個元素都有一個直接前驅和一個直接后繼B、線性表中不可以為空C、表中諸元素的排列順序必須是由小到大或由大到小D、除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅和直接后繼.在等概率的條件下，采用順序查找的方法查找長度為n的線性表時，查找成功的平均查找長度為（）。A、n B、n+1 C、（n+1）/2 D、（n-1）/2.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）。A、必須是連續的 B、部分地址必須是連續的C、一定是不連續的D、連續或不連續都可以.任何一個無向連通圖的最小生成樹中( )。A、只有一棵 B、有一棵或多棵C、一定有多棵 D、可能不存在.在無向圖中，一個頂點的度是指圖中( )。A、通過該頂點的簡單路徑數 B、與該頂點相相鄰的頂點數C、通過該頂點的回路數 D、與該頂點連通的頂點數.程序段k=i=0；do{i=i+1；k=k+i；}while(i<=n)；的時間復雜度為( )。A、O(n) B、O(nlog2n) C、O(n2) D、O(n3/2).在一個單鏈表中，已知q結點，若在q后插入一個結點s，則執行( )。A、q=s; B、q=s->next; C、q->next=s; D、q->next=s->next;.在具有n個結點的順序表上查找值為X的元素時，其時間復雜度為( )。A、O(n) B、O(1) C、O(n2) D、O(log2n).串s="abcdebda”，關于下面的說法，不正確的是( )。A、StrIndex(“abcdebda”,“bc”)=2B、StrLength(s)=8C、StrASSign(SLS)，則Us1=abcdebdaD、StrASSign(S,s1),則Us1=abcdebda.關于循環隊列的說法，不正確的是()。人、入隊時的隊尾指針加1操作改為：rear=(rear+1)%SiZeB、出隊時隊頭指針加1操作改為：front=(front+1)%SiZeC、隊滿條件：front=rear%size口、隊空條件：front=rear.一個順序表的第一個元素的存儲地址是90，每個元素的長度為4，則第6個元素的存儲地址是()。A、102B、110C、112D、108.一組記錄的的序列（46，79，56，38，40，84，90），則利用插入排序的方法將其從小到大，經過2輪排序，序列變為（ ）。A、46，79，40，38，56，84，90B、46，79，38，40，56，84，90C、46，56，79，38，40，84，90D、38，40，46，56，79，84，90.設棧S和隊列q均為空，先將a,b,c,d,e前3個元素進隊列q,后2個元素進棧，再將隊列4中的元素順次出隊的元素進棧s,得到棧里的元素為（ ）。A、cbaed B、abcde C、abced D、acedb二、判斷題（每題2.5分，共25分）.隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。.查找的方法可以分靜態查找和動態查找。.線性結構中元素之間存在一對一關系,.樹形結構中元素之間存在多對多關系,圖形結構中元素之間存在一對一關系。.棧和隊列都是特殊的線性表,棧的元素進出規則是先進先出。.隊列的元素進出規則是先進后出。7,規模為n的序列，使用直接插入排序，則最好情況下的時間復雜度是O（n），最好情況下比較的次數是n-1。.在一棵具有5層的滿二叉樹中結點總數為30。.在二叉樹的第i層上最多有i-1個節點。.若以鄰接矩陣表示有向圖，鄰接矩陣上第j列中非零元素的個數即為頂點vj的入度。三、計算題（每題15分，共30分）1.（1）寫出用冒泡排序將關鍵字序列｛54,23,89,48,64,50,25｝排序過程的第一趟結果。（8分）（2）寫出用直接插入排序將關鍵字序列｛54,23,89,48,64,50,25｝排序過程的每一趟結果。（7分）2.（1）某不帶權無向圖如下所示，求該圖的鄰接矩陣；并求該圖的廣度優先遍歷序列，以結點6開始。（7分）（2）已知有向圖的鄰接矩陣如下,請問該有向圖有幾個節點？怎么看出來的？畫出該有向圖。（8分）一0 1 0 0 0 1 「0 0 0 0 0 0 10 1 0 0 0 0 00 0 1 0 0 0 00 0 0 1 0 0 010001000011010“數據結構”知識要點02答案 -單選題（每題3分，共45分）1、D2、B3、D4、C5、D6、B7、B8、A9、C10、B11、D12、C13、B14、C15、A二、判斷題（每題2.5分，共25分）1、T2、T3、T4、F5、F6、F7、F8、F9、F10、T三、計算題（每題15分，共30分）1、答:（1）冒泡排序的第一趟結果：（8分）（）（54,23,89,48,64,50,25）（）（54,23,89,48,64,25,50）（）（54,23,89,48,25,64,50）（）（54,23,89,25,48,64,50）（）（54,23,25,89,48,64,50）（）（54,23,25,89,48,64,50）（23）（54,25,89,48,64,50）（2）直接插入排序：（7分）第一趟:[54],23,89,48,64,50,25第二趟:[23，54],89,48,64,50,25第三趟:[23，54，89],48,64,50,25第四趟:[23，48,54，89],64,50,25第五趟:[23，48,54，64，89],50,25第六趟:[23，48,50，54，64，89],25第七趟:[23，25，48,50，54，64，89]2、答：（1）該圖的鄰接矩陣是：01100000100001001000011100100111010000110111