專科第二學期網絡工程數據結構模擬題答案資料

《數據結構》試卷（A卷）一、選擇題.數據結構是指（A）。A.數據元素的組織形式 B.數據類型C.數據存儲結構 D.數據定義.數據在計算機存儲器內表示時，物理地址與邏輯地址不相同的，稱之為（C）。A.存儲結構 B.邏輯結構C.鏈式存儲結構 D.順序存儲結構.樹形結構是數據元素之間存在一種（D）。A.一對一關系 B.多對多關系C.多對一關系 D.一對多關系.設語句x++的時間是單位時間，則以下語句的時間復雜度為（B）。for（i=1;i<=n;i++）for（j=i;j<=n;j++）x++;A.O(1)B.O(A.O(1)B.O(n2) C.O(n) D.O(n3).算法分析的目的是（1）C，算法分析的兩個主要方面是（2）A。（1）A.（1）A.找出數據結構的合理性C.分析算法的效率以求改進（2）A.空間復雜度和時間復雜度C.可讀性和文檔性B.研究算法中的輸入和輸出關系D.分析算法的易懂性和文檔性B.正確性和簡明性D.數據復雜性和程序復雜性6.計算機算法指的是（1）C，它具備輸入，輸出和（2）B等五個特性。6.計算機算法指的是（1）C，它具備輸入，輸出和（2）B等五個特性。（1）A.計算方法C.解決問題的有限運算序列（2）A.可行性，可移植性和可擴充性C.確定性，有窮性和穩(wěn)定性B.排序方法D.調度方法B.可行性，確定性和有窮性D.易讀性，穩(wěn)定性和安全性7.數據在計算機內有鏈式和順序兩種存儲方式，在存儲空間使用的靈活性上，鏈式存儲比順序存儲要（B）。A.低B.高A.低B.高C.相同D.不好說.數據結構作為一門獨立的課程出現是在(D)年。A.1946 B.1953 C.1964 D.1968.數據結構只是研究數據的邏輯結構和物理結構，這種觀點(B)。A.正確 B.錯誤C.前半句對，后半句錯 D.前半句錯，后半句對.計算機內部數據處理的基本單位是(B)。A.數據 B.數據元素C.數據項D.數據庫.若查找每個元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為(D)。A.n B.n+1 C.(n-1)/2D.(n+1)/2.對于長度為9的順序存儲的有序表，若采用折半查找，在等概率情況下的平均查找長度為(A)的9分之一。TOC\o"1-5"\h\zA.20 B.18 C.25 D.22.對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數為(B)。A.3 B.4 C.5 D.6.對于順序存儲的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，則查找元素26的比較次數為(C)。A.2 B. 3 C. 4 D. 5.對具有n個元素的有序表采用折半查找，則算法的時間復雜度為(D)。A.O(n) B. O(n2) C. O(1) D. O(log2n).在索引查找中，若用于保存數據元素的主表的長度為n，它被均分為k個子表，每個子表的長度均為n/k，則索引查找的平均查找長度為(D)。A.n+k B.k+n/kC.(k+n/k)/2D.(k+n/k)/2+1.在索引查找中，若用于保存數據元素的主表的長度為144,它被均分為12子表，每個子表的長度均為12,則索引查找的平均查找長度為(A)。A.13 B.24 C.12 D.79二、填空題.數據結構按邏輯結構可分為兩大類，分別是__線性結構—和—非線性結構.數據的邏輯結構有四種基本形態(tài)，分別是集合、線性、樹和圖。.線性結構反映結點間的邏輯關系是——對――的，非線性結構反映結點間的邏輯關系是——對多或多對多—的。.一個算法的效率可分為時間效率和—空間—效率。.在樹型結構中，樹根結點沒有前趨結點，其余每個結點的有且只有———個前趨驅結點；葉子結點沒有—后繼—結點；其余每個結點的后續(xù)結點可以—多_。.在圖型結構中，每個結點的前趨結點數和后續(xù)結點數可以有多個—。.線性結構中元素之間存在――對――關系；樹型結構中元素之間存在——對多—關系；圖型結構中元素之間存在多對多—關系。.下面程序段的時間復雜度是—O(n2)。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;.下面程序段的時間復雜度是O(冊)。i=s=0;while(s<n){i++;s+=i;).下面程序段的時間復雜度是O(n2)。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;.下面程序段的時間復雜度是O(log3n)。i=1;while(i<=n)i=i*3;三、判斷題TOC\o"1-5"\h\z.二叉樹中每個結點的度不能超過2,所以二叉樹是一種特殊的樹。 （X ）.二叉樹的前序遍歷中，任意結點均處在其子女結點之前。 （J ）.線索二叉樹是一種邏輯結構。 （X ）.哈夫曼樹的總結點個數（多于1時）不能為偶數。 （J ）.由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。 （X ）.樹的后序遍歷與其對應的二叉樹的后序遍歷序列相同。 （J ）.根據任意一種遍歷序列即可唯一確定對應的二叉樹。 （X ）.滿二叉樹也是完全二叉樹。 （J ）.哈夫曼樹一定是完全二叉樹。 （X ）.樹的子樹是無序的。 （X ）四、求下列程序段的時間復雜度。x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)x++;x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;inti,j,k;for(i=0;i<n;i++)for(j=0;j<=n;j++){c[i][j]=0;for(k=0;k<n;k++)c[i][j]=a[i][k]*b[k][j])解：1.O(n2) 2.O(n2) 3.O(n3)

《數據結構》試卷(B卷)一、單項選擇題.線性表是—A—。A.一個有限序列，可以為空 B.一個有限序列，不可以為空C.一個無限序列，可以為空 D.一個無限序列，不可以為空.在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動一個元素。A.n-iB.n-i+l C.n-i-1D.i.線性表采用鏈式存儲時，其地址D。A.必須是連續(xù)的 B.一定是不連續(xù)的C.部分地址必須是連續(xù)的 D.連續(xù)與否均可以.從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較—C—個元素結點。A.n/2B.n C.(n+1)/2D.(n-1)/2.在雙向循環(huán)鏈表中，在p所指的結點之后插入s指針所指的結點，其操作是_D__。p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;.設單鏈表中指針p指向結點m,若要刪除m之后的結點(若存在)，則需修改指針的操作為A。A.p->next=p->next->next; B.p=p->next;C.p=p->next->next; D.p->next=p;.在一個長度為n的順序表中向第i個元素(0<i<n+l)之前插入一個新元素時，需向后移動—B一個元素。A.n-iB.n-i+lC.n-i-1D.iA.n-iB.n-i+lC.n-i-1D.i.在一個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執(zhí)行(B)s->next=p->next;p->next=sq->next=s;s->next=pp->next=s->next;s->next=pp->next=s;s->next=q.以下關于線性表的說法不正確的是_C—。A.線性表中的數據元素可以是數字、字符、記錄等不同類型。B.線性表中包含的數據元素個數不是任意的。C.線性表中的每個結點都有且只有一個直接前趨和直接后繼。D.存在這樣的線性表：表中各結點都沒有直接前趨和直接后繼。.線性表的順序存儲結構是一種A的存儲結構。A.隨機存取 B.順序存取 C.索引存取D.散列存取.在順序表中，只要知道D，就可在相同時間內求出任一結點的存儲地址。A.基地址 B.結點大小C.向量大小 D.基地址和結點大小.在等概率情況下，順序表的插入操作要移動_B結點。A.全部 B. 一半C.三分之一 D.四分之一.在_C—運算中，使用順序表比鏈表好。A.插入 B.刪除C.根據序號查找 D.根據元素值查找.在一個具有n個結點的有序單鏈表中插入一個新結點并保持該表有序的時間復雜度是TOC\o"1-5"\h\z__B 。A. O(1) B. O(n)C. O(n2) D. O(log2n).設有一個棧，元素的進棧次序為A,B,C,D,E,下列是不可能的出棧序列—C。A. A,B, C, D, E B. B,C, D, E, AC.E,A, B, C, D D.E,D, C, B, A.在一個具有n個單元的順序棧中，假定以地址低端(即0單元)作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為C。A.top不變B.top=0C.top-- D.top++.向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執(zhí)行B。A.hs->next=s; B.s->next=hs;hs=s;C.s->next=hs->next;hs->next=s; D.s->next=hs;hs=hs->next;18.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為D。A.rear%n==front B.(front+l)%n==rearC.rear%n-1==front D.(rear+l)%n==front二、填空題.線性表是一種典型的—線性—結構。.在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移—n-i+1一個元素。.順序表中邏輯上相鄰的元素的物理位置—相鄰。.要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需前移一個位置，移動過程是從—前—向—后依次移動每一個元素。.在線性表的順序存儲中，元素之間的邏輯關系是通過.物理存儲位置—決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過鏈域的指針值決定的。.在雙向鏈表中，每個結點含有兩個指針域，一個指向—前趨結點，另一個指向—后繼—結點。.當對一個線性表經常進行存取操作，而很少進行插入和刪除操作時，則采用—順序—存儲結構為宜。相反，當經常進行的是插入和刪除操作時，則采用—鏈接—存儲結構為宜。.順序表中邏輯上相鄰的元素，物理位置—一定—相鄰，單鏈表中邏輯上相鄰的元素，物理位置—不一定_相鄰。.線性表、棧和隊列都是一線性—結構，可以在線性表的—任何—位置插入和刪除元素；對于棧只能在一棧頂—位置插入和刪除元素；對于隊列只能在—隊尾位置插入元素和在隊頭位置刪除元素。.根據線性表的鏈式存儲結構中每個結點所含指針的個數，鏈表可分為.單鏈表—和_雙鏈表」而根據指針的聯接方式，鏈表又可分為_非循環(huán)鏈表—和—循環(huán)鏈表_。.在單鏈表中設置頭結點的作用是.使空表和非空表統(tǒng)一；算法處理一致_。.對于一個具有n個結點的單鏈表，在已知的結點p后插入一個新結點的時間復雜度為—O(1),在給定值為x的結點后插入一個新結點的時間復雜度為_O(n)。.對于一個棧作進棧運算時，應先判別棧是否為_棧滿,作退棧運算時，應先判別棧是否為_?？誣__，當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為_m―。為了增加內存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內存空間時，應將兩棧的一棧底—分別設在這片內存空間的兩端，這樣只有當一兩個棧的棧頂在?？臻g的某一位置相遇—時才產生上溢。三、簡答題.描述以下三個概念的區(qū)別：頭指針，頭結點，表頭結點。答：頭指針是指向鏈表中第一個結點(即表頭結點)的指針；在表頭結點之前附設的結點稱為頭結點；表頭結點為鏈表中存儲線性表中第一個數據元素的結點。若鏈表中附設頭結點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。.線性表的兩種存儲結構各有哪些優(yōu)缺點？答：線性表具有兩種存儲結構即順序存儲結構和鏈接存儲結構。線性表的順序存儲結構可以直接存取數據元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率：而在鏈接存儲結構中內存采用動態(tài)分配，利用率高，但需增設指示結點之間關系的指針域，存取數據元素不如順序存儲方便，但結點的插入、刪除操作較簡單。.對于線性表的兩種存儲結構，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數也會自動改變，在此情況下，應選用哪一種存儲結構？為什么？答：應選用鏈接存儲結構，因為鏈式存儲結構是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結構對于元素的刪除或插入運算是不需要移動元素的，只需修改指針即可，所以很容易實現表的容量的擴充。.對于線性表的兩種存儲結構，若線性表的總數基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應選用何種存儲結構？試說明理由。答：應選用順序存儲結構，因為每個數據元素的存儲位置和線性表的起始位置相差一個和數據元素在線性表中的序號成正比的常數。因此，只要確定了其起始位置，線性表中的任一個數據元素都可隨機存取，因此，線性表的順序存儲結構是一種隨機存取的存儲結構，而鏈表則是一種順序存取的存儲結構。數據結構》試卷(C卷)一、單項選擇題.空串與空格字符組成的串的區(qū)別在于(B)。A.沒有區(qū)別 B.兩串的長度不相等C.兩串的長度相等 D.兩串包含的字符不相同.一個子串在包含它的主串中的位置是指(D)。A.子串的最后那個字符在主串中的位置B.子串的最后那個字符在主串中首次出現的位置C.子串的第一個字符在主串中的位置D.子串的第一個字符在主串中首次出現的位置.下面的說法中，只有(C)是正確的。A.字符串的長度是指串中包含的字母的個數B.字符串的長度是指串中包含的不同字符的個數C.若T包含在S中，則T一定是S的一個子串D.一個字符串不能說是其自身的一個子串4.兩個字符串相等的條件是(D)。A.兩串的長度相等B.兩串包含的字符相同C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且對應位置上的字符相同5.若SUBSTR(S，i，k)表示求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S="Beijing&Nanjing”，SUBSTR(S,4,5)=(B)。A."ijing" B.“jing&”C."ingNa" D."ing&N".若INDEX(S,T)表示求T在S中的位置的操作，則對于S="Beijing&Nanjing”,T="jing",INDEX(S,T)=(C)。A.2 B.3 C.4 D.5.若REPLACE(S,S1,S2)表示用字符串S2替換字符串S中的子串S1的操作，則對于S="Beijing&Nanjing”,S1二“Beijing”，S2=“Shanghai”,REPLACE(S,S1,S2)=(D)。A.“Nanjing&Shanghai” B.“Nanjing&Nanjing”C.“ShanghaiNanjing” D.“Shanghai&Nanjing”.在長度為n的字符串S的第i個位置插入另外一個字符串，i的合法值應該是(C)。A.i>0 B.iWnC.1WiWn D.1WiWn+1.字符串采用結點大小為1的鏈表作為其存儲結構，是指（D）。A.鏈表的長度為1B.鏈表中只存放1個字符C.鏈表的每個鏈結點的數據域中不僅只存放了一個字符D.鏈表的每個鏈結點的數據域中只存放了一個字符.在一棵度為3的樹中，度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為（C）個。TOC\o"1-5"\h\zA.4 B.5 C.6 D.7.假設在一棵二叉樹中,雙分支結點數為15,單分支結點數為30個，則葉子結點數為（B）個。A.15 B.16 C.17 D.47.假定一棵三叉樹的結點數為50,則它的最小高度為（C）。A.3 B.4 C.5 D.6.在一棵二叉樹上第4層的結點數最多為（D）。A.2 B.4 C.6 D.8.用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數組中R[1..n],結點R[i]若有左孩子，其左孩子的編號為結點（B）。A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1].由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（D ）。A. 24 B. 48 C. 72 D. 53.線索二叉樹是一種（C）結構。A.邏輯 B.邏輯和存儲 C.物理 D.線性.線索二叉樹中，結點p沒有左子樹的充要條件是（B）。10A. p->lc=NULL B. p->ltag=1C. p->ltag=1且p->lc=NULLD.以上都不對.設n,m為一棵二叉樹上的兩個結點，在中序遍歷序列中n在m前的條件是（B）。A. n在m右方 B. n在m左方C. n是m的祖先 D. n是m的子孫.如果F是由有序樹T轉換而來的二叉樹，那么T中結點的前序就是F中結點的（B）。A.中序B.前序 C.后序 D.層次序.欲實現任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（A）存儲結構。A.三叉鏈表B.廣義表C.二叉鏈表 D.順序.下面敘述正確的是（D ）。A.二叉樹是特殊的樹B.二叉樹等價于度為2的樹C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次序之分22.任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序（A）。A.不發(fā)生改變 B.發(fā)生改變C.不能確定 D.以上都不對二、填空題.計算機軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是—固定長度，第二種是設置長度指針—。.兩個字符串相等的充要條件是—兩個串的長度相等—和—對應位置的字符相等—。.設字符串S1="ABCDEF”，S2=“PQRS”，則運算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為“BCDEDE”―。.串是指—含n個字符的有限序列（nN0）。.空串是指—不含任何字符的串，空格串是指—僅含空格字符的字符串―。.假定一棵樹的廣義表表示為A（B（E）,C（F（H,I,J）,G）,D）,則該樹的度為__3―,樹的深度為_4,終端結點的個數為6,單分支結點的個數為1__,雙分支結點的個數為1,三分支結點的個數為__2,C結點的雙親結點為A―，其孩子11結點為__F和G結點。.設F是一個森林，B是由F轉換得到的二叉樹，F中有n個非終端結點，則B中右指針域為空的結點有_n+1個。.對于一個有n個結點的二叉樹，當它為一棵—完全 二叉樹時具有最小高度，即為__Llog少」+1，當它為一棵單支樹具有—最大—高度，即為n。.由帶權為3,9,6,2,5的5個葉子結點構成一棵哈夫曼樹，則帶權路徑長度為_55__。.在一棵二叉排序樹上按—中序―遍歷得到的結點序列是一個有序序列。.對于一棵具有n個結點的二叉樹，當進行鏈接存儲時，其二叉鏈表中的指針域的總數為2n__個，其中_n-1__個用于鏈接孩子結點，_n+1__個空閑著。.在一棵二叉樹中，度為