數(shù)據(jù)結(jié)構(gòu)期末考試試題

數(shù)據(jù)結(jié)構(gòu)期末考試試題（）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)元素數(shù)據(jù)對象（正確答案）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)項把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（）物理結(jié)構(gòu)（正確答案）邏輯結(jié)構(gòu)算法的具體實現(xiàn)給相關(guān)變量分配存儲單元從n個數(shù)中選取最大元素（）?；静僮魇菙?shù)據(jù)元素間的交換算法的時間復(fù)雜度是O（n2）算法的時間復(fù)雜度是O（n）（正確答案）需要進行（n+1）次數(shù)據(jù)元素間的比較數(shù)據(jù)的（）結(jié)構(gòu)與所使用的計算機無關(guān)。邏輯（正確答案）物理C?存儲D?邏輯與存儲數(shù)據(jù)的物理結(jié)構(gòu)（）。與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)僅僅包括數(shù)據(jù)元素的表示只包括數(shù)據(jù)元素間關(guān)系的表示包括數(shù)據(jù)元素的表示和關(guān)系的表示（正確答案）數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。物理B?存儲邏輯與物理邏輯（正確答案）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（）。只能有一個數(shù)據(jù)項組成至少有二個數(shù)據(jù)項組成可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成（正確答案）至少有一個數(shù)據(jù)項為指針類型算法的時間復(fù)雜度與（）有關(guān)。所使用的計算機計算機的操作系統(tǒng)算法本身（正確答案）數(shù)據(jù)結(jié)構(gòu)同一種邏輯結(jié)構(gòu)（）。只能有唯一的存儲結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)（正確答案）只能表示某一種數(shù)據(jù)元素之間的關(guān)系以上三種說法均不正確線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。—對一（正確答案）一對多多對多每一個元素都有一個直接前驅(qū)和一個直接后繼樹形結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。一對一一對多（正確答案）多對多每一個元素都有一個直接前驅(qū)和一個直接后繼圖形結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。一對一一對多多對多（正確答案）D.每一個元素都有一個直接前驅(qū)和一個直接后繼以下特征中，()不是算法的特性。有窮性確定性有效性D?有0個或多個輸出(正確答案)某算法的時間復(fù)雜度為O(n),表明該算法的()問題規(guī)模為n執(zhí)行時間等于n執(zhí)行的時間與n成正比(正確答案)問題規(guī)模與n成正比以下算法的時間復(fù)雜度為()。voidfun(intn){intj=0;for(i=1;i<=n;i++)j=j+i;}O(n)(正確答案)O(n2)O(nlog2n)O(log2n)以下算法的時間復(fù)雜度為()。voidfun(intn){intsum=0;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)sum+=ji;}O(n)O(n2)(正確答案)O(nlog2n)O(log2n)線性表是有n個()的有限序列。數(shù)據(jù)表字符數(shù)據(jù)元素(正確答案)數(shù)據(jù)項線性表是一個()。有限序列，可以為空(正確答案)有限序列，不可以為空無限序列，可以為空無限序列，不可以為空以下（）是一個線性表。由n個實數(shù)組成的集合由100個字符組成的序列（正確答案）由所有整數(shù)組成的序列所有奇數(shù)組成的序列在線性表中，除了開始元素外，每個元素（）。只有唯一的前驅(qū)元素（正確答案）只有唯一的后即元素字符有多個前驅(qū)元素有多個后繼元素順序表的最大有優(yōu)點是（）。存儲密度大（正確答案）插入運算方便刪除運算方便可以方便地用于各種邏輯的存儲表示對于順序表，訪問編號為i的元素的時間復(fù)雜度為（）。O（n）O（1）（正確答案）O（nlog2n）O（log2n）對于順序表，在編號為i處插入一個新元素的間復(fù)雜度為（）。O（n）（正確答案）O（1）O（nlog2n）O（log2n）采用順序查找法對長度為n的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進行（）次元素間的比較。A．n+2B.n（正確答案）C．n-1D．n/2帶頭結(jié)點的單向鏈表的頭指針為head，該鏈表為空的判定條件是()的值為真。A．head==NULLB．head.getNext()==headC．head.getNext()二二NULL(正確答案)D．head==head.getNext()非空的單向循環(huán)鏈表的尾結(jié)點滿足()(設(shè)頭指針為head，指針p指向尾結(jié)點)。A．p.getNext()==NULLB．p==NULLp.getNext()二二head(正確答案)D．p==head鏈表所具備的特點是()?？梢噪S機訪問任一結(jié)點占用連續(xù)的存儲空間可以通過下標(biāo)對鏈表進行直接訪問插入刪除元素的操作不需要移動元素結(jié)點(正確答案)28?設(shè)鏈表中的結(jié)點是Node類型的類，且有Nodep；為了申請一個新結(jié)點，并由p指向該結(jié)點，可用以下Java語句()。p=newNode();(正確答案)p=newNode();p=(NODE)malloc(sizeof(p));p=(NODE)malloc(sizeof(p));29.設(shè)順序存儲的線性表長度為n,對于插入操作，設(shè)插入位置是等概率的，則插入一個元素平均移動元素的次數(shù)為()。n/2(正確答案)nn-1n-i+130?設(shè)順序存儲的線性表長度為n,對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（）。A.（n—l）/2（正確答案）B．nC．2nD．n-i31?設(shè)順序存儲的線性表長度為n,要刪除第i（0〈二i<=n-l）個元素，按課本的算法，當(dāng)i=（）時，移動元素的次數(shù)為3。A．3B．n/2n-4（正確答案）D．432?設(shè)順序存儲的線性長度為n,要在第i（0〈二i<=n）個元素之前插入一個新元素，按課本的算法當(dāng)i=（）時，移動元素次數(shù)為2。A．n/2B．nC．1n-2（正確答案）33?設(shè)有一個長度為n的順序表，要刪除第i（0<=i<=n-1）個元素，按照課本算法，需移動元素的個數(shù)為（）。A．n-i+1B．n-iC.n-iT（正確答案）D．i34.下述各線性結(jié)構(gòu)中可以隨機訪問的是（）。單向鏈表雙向鏈表單向循環(huán)鏈表順序表（正確答案）35?線性表采用鏈?zhǔn)酱鎯r，其地址（）。一定是不連續(xù)的必須是連續(xù)的可以連續(xù)也可以不連續(xù)(正確答案)部分地址必須是連續(xù)的在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用的語句是()。A．p=q.getNext();B．p.setNext(q);p.setNext(q.getNext());(正確答案)D．q.setNext(NULL);在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行()。p.setNext(s);s.setNext(p.getNext());p,setNext(s.getNext());p=s.getNext();s.setNext(p.getNext());p.setNext(s);(正確答案)按照教材算法，在一個長度為n的順序表中為了刪除第5個元素，從前到后依次移動了15個元素。則原順序表的長度為()。2120(正確答案)192539?針對線性表，在存儲后如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用()存儲方式最節(jié)省時間。單鏈表雙鏈表順序表(正確答案)D?單循環(huán)鏈表假設(shè)在順序表中，每一個數(shù)據(jù)元素所占的存儲單元的數(shù)目為4，且第一個數(shù)據(jù)元素的存儲地址為100，則位序號是7的數(shù)據(jù)元素的存儲地址是：()。106107124D.128（正確答案）隊列的插入操作在（）進行。隊頭隊尾（正確答案）隊頭或隊尾在任意指定位置隊列的刪除操作在（）進行。A?隊頭（正確答案）隊尾隊頭或隊尾在任意指定位置棧的插入操作在（）進行。A.棧頂（正確答案）B?棧底棧頂或棧底在任意指定位置一個隊列的入隊序列是2，4，6，8，則隊列的輸出序列是（）。8，6，4，22，4，6，8（正確答案）4，2，8，66，4，2，8一個隊列的入隊序列是5，6，7，8，則隊列的輸出序列是（）。5678（正確答案）87657865可能有多種情況一個棧的進棧序列是1，2，3，4，則不可能的出棧序列是（）（進出棧操作可以交替進行）。3，2，4，11,4，2，3（正確答案）4，3，2，1D．3，2，1，4一個棧的進棧序列是5，6，7，8，則棧的不可能的出棧序列是（）（進出棧操作可以交替進行）A.5,8,6,7（正確答案）B．7，6，8，5C.8,7,6,5C.7,6,8,5一個棧的進棧序列是a,b,c,d,e,則棧的不可能輸出序列是（）（進棧出?？梢越惶孢M行）。dceab（正確答案）edcbadecbaabcde以下說法不正確的是（）。順序棧中，棧滿時再進行進棧操作稱為“上溢”順序棧中，棧空時再作出棧棧操作稱為“下溢”順序隊列中，當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿（正確答案）順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空以下說法不正確的是（）。棧的特點是后進先出隊列的特點是先進先出棧的刪除操作在棧底進行，插入操作在棧頂進行（正確答案）隊列的插入操作在隊尾進行，刪除操作在隊頭進行以下說法正確的是（）。棧的特點是先進先出，隊列的特點是先進后出棧和隊列的特點都是先進后出棧的特點是先進后出，隊列的特點是先進先出D.棧和隊列的特點都是先進先出（正確答案）以下說法正確的是（）。棧的特點是先進先出，隊列的特點是先進后出棧和隊列的特點都是先進后出棧的特點是先進后出，隊列的特點是先進先出D.棧和隊列的特點都是先進先出（正確答案）元素2，4，6，8按順序依次進棧，則該棧的不可能輸出序列是（）（進棧出?？梢越惶孢M行）。A.8，6，4，2B.2，4，6，8C.4，2，8，6D.8，6，2，4（正確答案）元素2，4，6按順序依次進棧，則該棧的不可能的輸出序列是（）。642624（正確答案）426264棧的插入刪除操作在（）進行。A?棧底任意位置指定位置棧頂（正確答案）棧和隊列的相同點是（）。都是后進先出都是后進后出邏輯結(jié)構(gòu)與線性表不同邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表（正確答案）從一個棧頂指針為top的鏈棧中插入一個由P指向的新結(jié)點時，則執(zhí)行的操作是（）。p.setNext（top）;top=p;（正確答案）top=p;p.setNext（top）;top.setNext（p）;top=p;top.setNext（p）;p=top;設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則出棧操作為()。x二top.getData();top二top.getNext();(正確答案)B．top=top.getNext();x=top.getData();x=top.getNext();top=top.getData();top.setNext(top);x=top.getData();設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作：p二front.next;x二p.data;然后執(zhí)行()。front=p.next;Front.next=p.next;(正確答案)front=p;Front.next=p;設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被賦值)，則入隊操作為()。Rear.next=p;rear=p;(正確答案)Rear.next=p;p=rear;p=rear.next;rear=p;rear=p;rear.next=p;A在一個鏈隊列中，假設(shè)f和r分別為隊頭和隊尾指針，貝V插入s所指結(jié)點的運算為()。f.setNext(s);f=s;r.setNext(s);r=s;(正確答案)s.setNext(r);r=s;s.setNext(f);f=s;在一個鏈隊列中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為()。r=f.getNext();r=r.getNext();C．f=r.getNext（）;f=f.getNext（）;（正確答案）在一個循環(huán)隊列中，隊列的空間大小為length,設(shè)對頭指針為front,隊尾指針為rear，按照教材采用減少一個存儲元素的方法，以下那個能判斷隊列已滿。（）（rear+l）%length二二front;（正確答案）rear==front;rear%length==front;（rear-1）%length==front;若一個棧用數(shù)組data[l..n]存儲,初始棧頂指針top為n,則如元素x進棧的正確操作是：（）top++;data[top]=x;data[top]=x;top++;top--;data[top]=x;data[top]=x;top--;（正確答案）為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)計打印機數(shù)據(jù)緩沖區(qū)，主機將輸出的數(shù)據(jù)依次寫入緩沖區(qū)，而打印機依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是：（）TOC\o"1-5"\h\z棧隊列（正確答案）樹圖串方法concat（str）的功能是進行串（）。比較復(fù)制賦值連接（正確答案）67?串函數(shù)s二“Hello”；s.indexOf（“e”，O）的值為（）。1（正確答案）0“He”“e”D.D.29（正確答案）空串的長度為（）。A.0（正確答案）B．1C.23以下陳述中正確的是（）。串是一種特殊的線性表（正確答案）串的長度必須大于零串中元素只能是字母空串就是空白串70?設(shè)有兩個串p和q,其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（）。求子串B?連接匹配（正確答案）求串長串是（）。不少于一個字母的序列任意個字母的序列不少于一個字符的序列有限個字符的序列（正確答案）串的長度是指（）。串中所含不同字母的個數(shù)串中所含字符的個數(shù)（正確答案）串中所含不同字符的個數(shù)串中所含非空格字符的個數(shù)73?若串S=“English”，其子串的個數(shù)是（）。TOC\o"1-5"\h\z91636A.33A.33下面關(guān)于串的敘述中，不正確的是（）。串是字符的有限序列空串是由空格構(gòu)成的串（正確答案）模式匹配是串的一種重要運算串即可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯Υc普通的線性表相比較，它的特殊性體現(xiàn)在（）。順序的存儲結(jié)構(gòu)鏈接的存儲結(jié)構(gòu)數(shù)據(jù)元素是一個字符（正確答案）數(shù)據(jù)元素可以任意空串與空格串（）。相同不相同（正確答案）可能相同無法確定兩個字符串相等的條件是（）。兩串的長度相等兩串包含的字符相同兩串的長度相等，并且兩串包含的字符相同兩串的長度相等，并且對應(yīng)位置上的字符相同（正確答案）在實際應(yīng)用中，要輸入多個字符串，且長度無法預(yù)定。則應(yīng)該采用（）存儲比較合適。鏈?zhǔn)剑ㄕ_答案）順序堆結(jié)構(gòu)無法確定設(shè)有一個10階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標(biāo)從0開始），則矩陣中元素A[8][5]在一維數(shù)組B中的下標(biāo)是（）。32C．85D.41（正確答案）設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為A[0][0]，數(shù)組b的下標(biāo)從0開始），則矩陣元素A[5][3]對應(yīng)一維數(shù)組b的數(shù)組元素是（）。b[18]（正確答案）TOC\o"1-5"\h\zb[8]b[13]b[10]設(shè)有一個12階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為A[0][0]，數(shù)組b的下標(biāo)從0開始），則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有（）。7WiW1011WiW1510WiW14（正確答案）6WiW9設(shè)有一個15階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從0開始），則矩陣中元素a7,6在一維數(shù)組B中的下標(biāo)是（）。42（正確答案）TOC\o"1-5"\h\z132734設(shè)有一個15階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為a1,1，數(shù)組b的下標(biāo)從1開始），則數(shù)組元素b[13]對應(yīng)A的矩陣元素是（）。a5,3（正確答案）TOC\o"1-5"\h\za6,4a7,2a6,8D.D.19（正確答案）設(shè)有一個20階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（矩陣A的第一個元素為al,l，數(shù)組下標(biāo)從1開始），則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是（）。A．41B．32C．18D.38（正確答案）設(shè)有一個20階的對稱矩陣A,采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為all，數(shù)組b的下標(biāo)從1開始），則矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是（）。A．30B．28C．40D.33（正確答案）86?在Java語言中，利用數(shù)組a存放字符串“Hello”，以下語句中正確的是（）。A．Chara[10]=“Hello”;B．Chara[10];a=“Hello”;C．Chara[10]=‘Hello';Chara[]={'H','e','l','l','o'};（正確答案）對二叉排序樹進行（）遍歷，遍歷所得到的序列是有序序列。按層次B?前序C?中序（正確答案）后序深度為5的完全二叉樹第5層上有4個結(jié)點，該樹一共有（）個結(jié)點。TOC\o"1-5"\h\z283031D.D.12（正確答案）深度為5的完全二叉樹共有20個結(jié)點，則第5層上有（）個結(jié)點（根所在結(jié)點為第一層）。A．3B．8C.5（正確答案）D．690?—棵哈夫曼樹共有n個非葉結(jié)點，則該樹一共有（）個結(jié)點。TOC\o"1-5"\h\z2n-12n+1（正確答案）2n2（n-1）91.一棵哈夫曼樹共有n個非葉結(jié)點，則該樹有（）個葉結(jié)點。nn+1（正確答案）n-12n92?一棵哈夫曼樹共有n個葉結(jié)點，則該樹有（）個非葉結(jié)點。n-1（正確答案）nn+12n一棵哈夫曼樹有n個葉子結(jié)點（終端結(jié)點），該樹總共有（）個結(jié)點。2n-22n-l（正確答案）2n2n+2一棵哈夫曼樹總共有23個結(jié)點，該樹共有（）個葉結(jié)點（終端結(jié)點）。101311一棵完全二叉樹共有30個結(jié)點，則該樹一共有（）層（根結(jié)點所在層為第一層）。A．6B．4C．3D.5（正確答案）一棵完全二叉樹共有5層，且第5層上有六個結(jié)點，該樹共有（）個結(jié)點302021（正確答案）23一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄洌瑒t該樹共有（）個指針域為空。2n2n+12n+2n+1（正確答案）在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為（）。2i2i-12i+22i+l（正確答案）任何一個無向連通圖的最小生成樹（）。至少有一棵（正確答案）只有一棵一定有多棵可能不存在已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（）。2m（正確答案）m2m+1D．m/2已知一個圖的所有頂點的度數(shù)之和為m則m—定不可能是（）。A．4B．8C．12D.9（正確答案）以下說法不正確的是（）。連通圖G—定存在生成樹連通圖G的生成樹中一定包含G的所有頂點連通圖G的生成樹中不一定包含G的所有邊連通圖G的生成樹可以是不連通的（正確答案）以下說法正確的是（）。連通圖G的生成樹中可以包含回路連通圖G的生成樹可以是不連通的連通圖G的生成樹一定是唯一的連通圖G的生成樹一定是連通而不包含回路的（正確答案）以下說法正確的是（）。連通圖G的生成樹中可以包含回路連通圖G的生成樹可以是不連通的連通圖G的生成樹一定是唯一的連通圖G的生成樹一定是連通而不包含回路的（正確答案）以下說法正確的是（）。連通圖G的生成樹中不一定包含G的所有頂點連通圖G的生成樹中一定要包含G的所有邊連通圖G的生成樹一定是唯一的連通圖G一定存在生成樹（正確答案）以下說法正確的是（）。連通圖G的生成樹中不一定包含G的所有頂點連通圖G的生成樹中一定要包含G的所有邊連通圖G的生成樹一定是唯一的連通圖G—定存在生成樹（正確答案）在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（）倍。A．3B．2.5C．1.5D.2（正確答案）對n個元素進行冒泡排序，要求按升序排列，程序中設(shè)定某一趟冒泡沒有出現(xiàn)元素交換，就結(jié)束排序過程。對某n個元素的排序共進行了3n-6次元素間的比較就完成了排序，則（）。原序列是升序排列原序列是降序排列對序列只進行了2趟冒泡對序列只進行了3趟冒泡（正確答案）對n個元素進行冒泡排序，通常要進行n-1趟冒泡，在第j趟冒泡中共要進行（）次元素間的比較。jj-1n-j（正確答案）n-j-1對n個元素進行冒泡排序若某趟冒泡中只進行了（）次元素間的交換，則表明序列已經(jīng)排好序。TOC\o"1-5"\h\z120（正確答案）n-1排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。A?歸并插入C?選擇（正確答案）D.快速排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到