北外《數(shù)據(jù)結(jié)構(gòu)》知識(shí)要點(diǎn)0223672

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