2025云南開放大學【數據結構】網上作業1-8答案

2025云南開放大學數據結構網上作業1答案一、單項選擇題(共17題,共68分)第1題（4分）：（A、數據元素正確答案:B）是性質相同的數據元素的集合，是數據的子集。B．數據對象C．數據結構D．數據項第2題（4分）：把數據存儲到計算機中，并具體體現數據元素間的邏輯結構稱為（）。D．給相關變量分配存儲單元A．物理結構正確答案:AB．邏輯結構C．算法的具體實現第3題（4分）：從n個數中選取最大元素（）。B．算法的時間復雜度是O(n2)A．基本操作是數據元素間的交換C．算法的時間復雜度是O(n)正確答案:CD．需要進行(n+1)次數據元素間的比較）結構與所使用的計算機無關。C．存儲D．邏輯與存儲第4題（4分）：數據的（A．邏輯B．物理正確答案:A第5題（4分）：數據的物理結構（A．與數據的邏輯結構無關C．只包括數據元素間關系的表示正確答案:D）。B．僅僅包括數據元素的表示D．包括數據元素的表示和關系的表示第6題（4分）：數據結構中，與所使用的計算機無關的是數據的（）結構。A．物理B．存儲C．邏輯與物理D．邏輯正確答案:D第7題（4分）：數據元素是數據的基本單位，它（A．只能有一個數據項組成）。B．至少有二個數據項組成C．可以是一個數據項也可以由若干個數據項組成D．至少有一個數據項為指針類型正確答案:C第8題（4分）：算法的時間復雜度與（）有關。A．所使用的計算機B．計算機的操作系統C．算法本身正確答案:CD．數據結構第9題（4分）：同一種邏輯結構（）。A．只能有唯一的存儲結構B．可以有不同的存儲結構C．只能表示某一種數據元素之間的關系D．以上三種說法均不正確正確答案:B答案解析：暫無解析第10題（4分）：線性結構中數據元素的位置之間存在（）的關系。A．一對一C．多對多B．一對多D．每一個元素都有一個直接前驅和一個直接后繼正確答案:A第11題（4分）：樹形結構中數據元素的位置之間存在（）的關系。BA．一對一B．一對多C．多對多D．每一個元素都有一個直接前驅和一個直接后繼正確答案:B第12題（4分）：圖形結構中數據元素的位置之間存在（）的關系。A．一對一B．一對多C．多對多D．每一個元素都有一個直接前驅和一個直接后繼正確答案:C第13題（4分）：以下特征中，（）不是算法的特性。A．有窮性B．確定性C．有效性D．有0個或多個輸出正確答案:D第14題（4分）：某算法的時間復雜度為O（n）,表明該算法的（）A.問題規模為nB.執行時間等于nC.執行的時間與n成正比D.問題規模與n成正比正確答案:C第15題（4分）：以下算法的時間復雜度為（）。publicstaticvoidfun(intn){intj=0;for(i=1;i<=n;i++)j=j+i;}A.O(n)B.O(n2)C.O(nlog2n)D.O(log2n)正確答案:A第16題（4分）：以下算法的時間復雜度為（）。publicstaticvoidfun(intn){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){System.out.print(j+”*”+i+”=”+i*j);}System.out.println();}}A.O(n)B.O(n2)C.O(nlog2n)D.O(log2n)正確答案:B第17題（4分）：以下算法的時間復雜度為（）。publicstaticvoidfun(intn){intj=0;for(i=1;i<=n;2*i){j=j+i;}System.out.println(j);}A.O(n)B.O(n2)C.O(nlog2n)D.O(log2n)正確答案:D二、判斷題(共8題,共32分)第18題（4分）：在相同的規模n下,時間復雜度為O(n)的算法在時間上總是優于復雜度為O(2n)的算法。（）正確答案:√第19題（4分）：所謂最壞的時間復雜度是指在最壞的情況下估算算法在執行時間上的一個上界。（）正確答案:√第20題（4分）：同一個算法，實現語言越高級，執行效率就越高。()正確答案:×第21題（4分）：同一種邏輯結構可以用不同的存儲結構實現（）。正確答案:√第22題（4分）：一個算法可以無限制的執行下去。（）。正確答案:×第23題（4分）：程序就是算法。（）。正確答案:×第24題（4分）：數據元素是數據的最小單位。（）正確答案:×第25題（4分）：數據的物理結構是指數據在計算機中世紀的存儲形式。（）正確答案:√2025云南開放大學數據結構網上作業2答案一、單項選擇題(共22題,共64分)第1題（3分）：線性表是有n個（）的有限序列。C.數據元素D.數據項A.數據表B.字符正確答案:C第2題（3分）：線性表是一個（A.有限序列，可以為空C.無限序列，可以為空正確答案:A）。B.有限序列，不可以為空D.無限序列，不可以為空第3題（3分）：以下（）是一個線性表。A.由n個實數組成的集合B.由100個字符組成的序列C.由所有整數組成的序列D.所有奇數組成的序列正確答案:B第4題（3分）：在線性表中，除了開始元素外，每個元素（）。A.只有唯一的前驅元素C.有多個前驅元素正確答案:AB.只有唯一的后即元素字符D.有多個后繼元素第5題（3分）：順序表的最大有優點是()。B.插入運算方便A.存儲密度大C.刪除運算方便D.可以方便地用于各種邏輯的存儲表示正確答案:A第6題（3分）：對于順序表，訪問編號為i的元素的時間復雜度為（）。A.O(n)B.O(1)C.O(nlog2n)D.O(log2n)正確答案:B第7題（3分）：對于順序表，在編號為i處插入一個新元素的間復雜度為（）。A.O(n)B.O(1)C.O(nlog2n)D.O(log2n)正確答案:A第8題（3分）：采用順序查找法對長度為n的線性表進行查找（不采用表尾設監視哨的方法），最壞的情況下要進行（A．n+2）次元素間的比較。B．nC．n-1D．n/2正確答案:B第9題（3分）：帶頭結點的單向鏈表的頭指針為head，該鏈表為空的判定條件是（）的值為真。A．head==NULLC．head.getNext()==NULLB．head.getNext()==headD．head==head.getNext()正確答案:C第10題（3分）：鏈表所具備的特點是（）。A．可以隨機訪問任一結點B．占用連續的存儲空間C．可以通過下標對鏈表進行直接訪問D．插入刪除元素的操作不需要移動元素結點正確答案:D第11題（3分）：設順序存儲的線性表長度為n，對于插入操作，設插入位置是等概率的，則插入一個元素平均移動元素的次數為（）。A．n/2B．nC．n-1D．n-i+1正確答案:A第12題（3分）：設順序存儲的線性表長度為n，對于刪除操作，設刪除位置是等概率的，則刪除一個元素平均移動元素的次數為（）。A．(n-1)/2B．nC．2nD．n-i正確答案:A第13題（3分）：設順序存儲的線性表長度為n，要刪除第i（0<=i<=n-1）個元素，按課本的算法，當i=（）時，移動元素的次數為3。A．3B．n/2C．n-4D．4正確答案:C第14題（3分）：設順序存儲的線性長度為n，要在第i（0<=i<=n）個元素之前插入一個新元素，按課本的算法當i=（）時，移動元素次數為2。A．n/2B．nC．1D．n-2正確答案:D答案解析：在表長為3的現象表上，在位序號為0位置插入的元素，需要向后移動3元素開辟空間供新元素存儲，移動元素次數為3-0=32。歸納出在表長為n的表上，在位序號為i的位置插入一個元素，需要移動x=n-i個元素。現在已知x=2,2=n-i,則i=n-2第15題（3分）：設有一個長度為n的順序表，要刪除第i(0<=i<=n-1)個元素，按照課本算法，需移動元素的個數為（）。A．n-i+1B．n-iC．n-i-1D．i正確答案:C第16題（3分）：下述各線性結構中可以隨機訪問的是（）。A.單向鏈表B.雙向鏈表C.單向循環鏈表D.順序表正確答案:D第17題（3分）：線性表采用鏈式存儲時，其地址（）。A．一定是不連續的B．必須是連續的C．可以連續也可以不連續D．部分地址必須是連續的正確答案:C第18題（3分）：在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現要刪除q所指結點，可用的語句是（）。A．p=q.getNext();B．p.setNext(q);C．p.setNext(q.getNext());D．q.setNext(NULL);正確答案:C第19題（3分）：在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執行（）。A．p.setNext(s);s.setNext(p.getNext());B．p,setNext(s.getNext());C．p=s.getNext();D．s.setNext(p.getNext());p.setNext(s);正確答案:D第20題（3分）：按照教材算法，在一個長度為n的順序表中為了刪除第5個元素，從前到后依次移動了15個元素。則原順序表的長度為（）。A.21B.20C.19D.25正確答案:A第21題（2分）：針對線性表，在存儲后如果最常用的操作是取第i個結點及其前驅，則采用（）存儲方式最節省時間。A．單鏈表B．雙鏈表C．順序表D．單循環鏈表正確答案:C第22題（2分）：假設在順序表中，每一個數據元素所占的存儲單元的數目為4，且第一個數據元素的存儲地址為100，則第位序號為7的數據元素的存儲地址是：（）。A．106B．107C．124D．128正確答案:D二、判斷題(共18題,共36分)第23題（2分）：線性表采用順序存儲必須占用一片連續的存儲空間。（）正確答案:√第24題（2分）：正確答案:√第25題（2分）：線性表采用鏈式存儲不必占用一片連續的存儲空間。（）正確答案:√第26題（2分）：正確答案:√第27題（2分）：線性表采用鏈式存儲便于插入和刪除操作的實現。（）正確答案:√第28題（2分）：正確答案:√第29題（2分）：線性表采用順序存儲便于插入和刪除操作的實現。（）正確答案:√第30題（2分）：正確答案:√第31題（2分）：線性表的順序結構中，邏輯上相鄰的元素在物理位置上不一定相鄰。（）正確答案:√第32題（2分）：正確答案:√第33題（2分）：線性表的順序結構中，數據元素是不能隨機訪問的。（）正確答案:√第34題（2分）：正確答案:√第35題（2分）：線性表的順序結構中，邏輯上相鄰的元素在物理位置上也相鄰。（）正確答案:√第36題（2分）：正確答案:√第37題（2分）：線性表的順序結構中，進行數據元素的插入、刪除效率較高。（）正確答案:√第38題（2分）：答案：錯正確答案:√第39題（2分）：順序存儲方式只適合存儲線性結構。（）錯正確答案:√第40題（2分）：答案：錯正確答案:√2025云南開放大學數據結構網上作業3答案一、單項選擇題(共23題,共73分)第1題（4分）：隊列的插入操作在（）進行。C．隊頭或隊尾A．隊頭B．隊尾D．在任意指定位置D．在任意指定位置D．在任意指定位置正確答案:B第2題（4分）：隊列的刪除操作在（A．隊頭B．隊尾正確答案:A第3題（4分）：棧的插入操作在（）進行。C．隊頭或隊尾）進行。C．棧頂或棧底A．棧頂B．棧底正確答案:A第4題（4分）：棧的刪除操作在（）進行。A.棧頂B.棧底C.棧頂或棧底正確答案:AD.在任意指定位置第5題（3分）：一個隊列的入隊序列是2，4，6，8，則隊列的輸出序列是（）。D．6，4，2，8A．8，6，4，2正確答案:BB．2，4，6，8C．4，2，8，6第6題（3分）：一個隊列的入隊序列是5，6，7，8，則隊列的輸出序列是（）。A.5678C.7865B.8765D.可能有多種情況正確答案:A第7題（3分）：一個棧的進棧序列是1，2，3，4，則不可能的出棧序列是（A．3，2，4，1C．4，3，2，1正確答案:B第8題（3分）：一個棧的進棧序列是5，6，7，8，則棧的不可能的出棧序列是（A．5，8，6，7正確答案:A）（進出棧操作可以交替進行）。）（進出棧操作可以交替進行）B．7，6，8，5C．7，6，5，8D．8，7，6，5B．1，4，2，3D．3，2，1，4第9題（3分）：一個棧的進棧序列是a，b，c，d，e，則棧的不可能輸出序列是（）（進棧出棧可以交替進行）。A．dceabB．edcbaC．decbaD．abcde正確答案:A第10題（3分）：以下說法不正確的是（）。A．順序棧中，棧滿時再進行進棧操作稱為“上溢”B．順序棧中，棧空時再作出棧棧操作稱為“下溢”C．順序隊列中，當尾指針已經超越隊列存儲空間的上界，則一定是隊列已滿D．順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空正確答案:C第11題（3分）：以下說法不正確的是（）。A．棧的特點是后進先出B．隊列的特點是先進先出C．棧的刪除操作在棧底進行，插入操作在棧頂進行D．隊列的插入操作在隊尾進行，刪除操作在隊頭進行答題歷史：C正確答案:C第12題（3分）：元素2，4，6，8按順序依次進棧，則該棧的不可能輸出序列是（）（進棧出棧可以交替進行）。A．8，6，4，2B．2，4，6，8C．4，2，8，6D．8，6，2，4正確答案:D第13題（3分）：元素2，4，6按順序依次進棧，則該棧的不可能的輸出序列是（）。A.642B.624C.426D.264正確答案:B第14題（3分）：棧和隊列的相同點是（）。A．都是后進先出B．都是后進后出C．邏輯結構與線性表不同D．邏輯結構與線性表相同，都是操作規則受到限制的線性表正確答案:D第15題（3分）：從一個棧頂指針為top的鏈棧中插入一個由P指向的新結點時，則執行的操作是（）。A．p.setNext(top);top=p;B．top=p;p.setNext(top);C．top.setNext(p);p=top;D．top.setNext(p);p=top;正確答案:A第16題（3分）：設top是一個鏈棧的棧頂指針，棧中每個結點由一個數據域data和指針域next組成，設用x接收棧頂元素，則出棧操作為（）。A．x=top.getData();top=top.getNext();B．top=top.getNext();x=top.getData();C．x=top.getNext();top=top.getData();D．top.setNext(top);x=top.getData();正確答案:A第17題（3分）：設有一個帶頭結點的鏈隊列，隊列中每個結點由一個數據域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執行出隊操作，用x保存出隊元素的值，p為指向結點類型的指針，可執行如下操作：p=front.getNext();x=p.getData();然后執行（）。A．front=p.getNext();B．front.setNext(p.getNext());C．front=p;D．front.setNext(p);正確答案:B第18題（3分）：設有一個帶頭結點的鏈隊列，隊列中每個結點由一個數據域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設p指向要入隊的新結點(該結點已被賦值)，則入隊操作為（）。A．rear.setNext(p);rear=p;B．rear.setNext(p);p=rear;C．p=rear.getNext();rear=p;D．rear=p;rear.setNext(p);正確答案:A第19題（3分）：在一個鏈隊列中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的操作為（）。A．f．setNext(s);f=s;B．r.setNext（s）;r=s;C．s．setNext(r);r=s;D．s.setNext(f);f=s;正確答案:B第20題（3分）：在一個鏈隊列中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的操作為（）。A．r=f.getNext();B．r=r.getNext();C．f=r.getNext();D．f=f.getNext();正確答案:D第21題（3分）：在一個循環隊列中，隊列的空間大小為length,設對頭指針為front,隊尾指針為rear,按照教材采用減少一個存儲元素的方法，以下那個能判斷隊列已滿。（）A.(rear+1)%length==front;B.rear==front;C.rear%length==front;D.(rear-1)%length==front;正確答案:A第22題（3分）：若一個棧用數組data[n]存儲,空棧初始棧頂指針top為n-1,則如元素x進棧的正確操作是：（）A.top++;data[top]=x;B.data[top]=x;top++;C.top–;data[top]=x;D.data[top]=x;top–;正確答案:D第23題（3分）：為解決計算機主機與打印機之間速度不匹配問題，通常設計打印機數據緩沖區，主機將輸出的數據依次寫入緩沖區，而打印機依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是：（）。A.棧B.隊列C.樹D.圖正確答案:B二、判斷題(共9題,共27分)第24題（3分）：棧和隊列都是一種特殊的線性表。（）對正確答案:√第25題（3分）：棧可以用順序結構實現，也可以使用鏈表結構實現。（）對正確答案:√第26題（3分）：隊列可以使用順序結構實現，也可以使用鏈表結構實現。（）正確答案:√第27題（3分）：編輯軟件的撤銷編輯內容操作可以通過棧結構來實現。（）正確答案:√第28題（3分）：瀏覽器記錄用戶的訪問地址以實現“回撤”操作，可以通過隊列結構來實現。（）正確答案:×第29題（3分）：不考慮優先級的前提下，打印機任務可以采用棧結構實現。（）正確答案:×第30題（3分）：遞歸的實現過程，可以使用棧實現。（）正確答案:√第31題（3分）：方法調用的實現過程，通常采用棧實現。（）正確答案:√第32題（3分）：操作系統進程管理設計中，不考慮優先級的條件下，可以采用隊列結構設計。（）正確答案:√2025云南開放大學數據結構網上作業4答案一、單項選擇題(共29題,共86分)第1題（3分）：串方法concat(str)的功能是進行串（）。D．連接A．比較B．復制正確答案:DC．賦值第2題（3分）：串函數s=“Hello”;s.indexOf(“e”,0)的值為（）。A．1正確答案:A第3題（3分）：空串的長度為（A．0B．0C．“He”）。D．3D．“e”B．1C．2正確答案:A第4題（3分）：以下陳述中正確的是（A．串是一種特殊的線性表C．串中元素只能是字母正確答案:A）。B．串的長度必須大于零D．空串就是空白串第5題（3分）：設有兩個串p和q，其中q是p的子串，q在p中首次出現的位置的算法稱為（）。A．求子串B．連接C．匹配D．求串長正確答案:C第6題（3分）：串是（）。A．不少于一個字母的序列C．不少于一個字符的序列正確答案:DB．任意個字母的序列D．有限個字符的序列第7題（3分）：串的長度是指（）。A．串中所含不同字母的個數B．串中所含字符的個數C．串中所含不同字符的個數D．串中所含非空格字符的個數正確答案:B第8題（3分）：若串S=“English”，其子串的個數是（D．29）。A．9B．16C．36正確答案:D第9題（3分）：下面關于串的敘述中，不正確的是（）。A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串即可以采用順序存儲，也可以采用鏈式存儲正確答案:B第10題（3分）：串與普通的線性表相比較，它的特殊性體現在（）。A．順序的存儲結構C．數據元素是一個字符正確答案:CB．鏈接的存儲結構D．數據元素可以任意第11題（3分）：空串與空格串（）。A．相同B．不相同C．可能相同D．無法確定正確答案:B第12題（3分）：兩個字符串相等的條件是（）。A．兩串的長度相等B．兩串包含的字符相同C．兩串的長度相等，并且兩串包含的字符相同D．兩串的長度相等，并且對應位置上的字符相同正確答案:D第13題（3分）：在實際應用中，要輸入多個字符串，且長度無法預定。則應該采用（）存儲比較合適。A．鏈式B．順序C．堆結構D．無法確定正確答案:A第14題（3分）：對特殊矩陣進行壓縮的目的是()。A．表達式變得簡單B．對矩陣元素存取方便C．去掉矩陣中多于元素D．減少不必要的存儲空間正確答案:D第15題（3分）：對于n階對稱矩陣，如果以行或者列存放到內存中，則需要()個存儲單元進行保存。A．n*(n+1)/2B．n*n/2C.n*(n-1)/2D.n*n正確答案:A第16題（3分）：對于n階對稱矩陣A(矩陣A的第一個元素為A[0][0])，利用數組S存儲（數組S的下標從0開始），以行優先順序存儲則A[5][3]元素，在S數組中的下標是：()A.S[18]B.S[13]C.S[16]D.S[15]正確答案:A第17題（3分）：對于n階對稱矩陣A(矩陣A的第一個元素為A[0][0])，利用數組S存儲（數組S的下標從0開始），以行優先順序存儲則A[4][6]元素在S數組中的下標是：()A.S[25]B.S[16]C.S[21]D.S[15]正確答案:A第18題（3分）：設有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數組b中（數組下標從0開始），則矩陣中元素A[8][5]在一維數組b中的下標是（）。A．b[33]B．b[32]C．b[85]D．b[41]正確答案:D第19題（3分）：設有一個10階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數組b中。（矩陣A的第一個元素為A[0][0]，數組b的下標從0開始），則矩陣元素A[5][3]對應一維數組b的數組元素是（）。A．b[18]B．b[8]C．b[13]D．b[10]正確答案:A第20題（3分）：設有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數組b中（矩陣A的第一個元素為A[0][0]，數組b的下標從0開始），則矩陣A中第4行的元素在數組b中的下標i一定有（）。A．7≤i≤10B．11≤i≤15C．9≤i≤14D．6≤i≤9正確答案:D第21題（3分）：設有一個15階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從0開始），則矩陣中元素a[7][6]在一維數組B中的下標是（）。A．42B．13C．27D．34正確答案:D第22題（3分）：設有一個15階的對稱矩陣a，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數組b中。（矩陣A的第一個元素為a0,0，數組b的下標從0開始），則數組元素b[13]對應A的矩陣元素是（）。A．a[4][3]B．a[6][4]C．a[7][2]D．a[6][8]正確答案:A第23題（3分）：設有一個20階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從0開始），則矩陣中元素a[9][2]在一維數組B中的下標是（）。A．41B．32C．18D．47正確答案:D第24題（3分）：設有一個10階的對角矩陣，其半帶寬為2，則需要使用（）個存儲空間存儲該矩陣元素。A．44B．45C．34D．35正確答案:A第25題（3分）：在Java語言中，利用數組a存放字符串“Hello”，以下語句中正確的是（）。A．chara[10]=“Hello”;B．chara[10];a=“Hello”;C．chara[10]=‘Hello’;D．chara[]={‘H’,’e’,’l’,’l’,’o’};正確答案:D第26題（3分）：稀疏矩陣的三元組存儲方法（）。A．實現矩陣的轉置操作,只需將每個三元組行和列的下標交換即可B．矩陣的非零元素個數和位置在操作中變化不大時較有效C．是一種鏈式存儲結構D．比十字鏈表更高效正確答案:B第27題（3分）：采用十字鏈表表示一個稀疏矩陣,每一個非零元素一般用一個含有（）域的結點表示。A．5B．4C．3D.2正確答案:A第28題（3分）：在稀疏矩陣壓縮后，必然會失去（）功能。A．順序存儲B．隨機存儲C．輸入輸出D.以上都不對正確答案:B第29題（2分）：以下()是稀疏矩陣的一種存儲方法。A．十字鏈表B．循環鏈表C．數組D.棧正確答案:A二、判斷題(共7題,共14分)第30題（2分）：空串是任何串的子串。（）正確答案:√第31題（2分）：任何串都是其自身的子串。（）正確答案:√第32題（2分）：空白串與空串是一樣的。（）正確答案:×第33題（2分）：若兩個串有相同的字符集，則說明兩個串相等。（）正確答案:×第34題（2分）：串中任意多個連續的字符組成的子序列稱為該串的子串。（）正確答案:√第35題（2分）：特殊矩陣壓縮是為了去掉矩陣中多于元素。（）正確答案:×第36題（2分）：特殊矩陣壓縮是減少不必要的存儲空間。（）正確答案:√2025云南開放大學數據結構網上作業5答案一、單項選擇題(共35題,共100分)第1題（3分）：樹最適合用來表示（A．有序數據元素C.數據元素之間存在層次關系的數據正確答案:C）。B.無序數據元素D.元素之間無聯系第2題（3分）：對于一顆有n個節點的樹，其中所有度之和等于：（）。A．nB．n-1C．n-2D．n+1正確答案:B第3題（3分）：對于一顆有n個節點、度為4的樹來說，（）。A．樹的高度最多為n-3B．樹的高度最多為n-4C．第i層上最多有4(i-1)個節點D．至少在某一層上正好有4個節點正確答案:A第4題（3分）：對于一顆高度為h、度為4的樹來說，（）。A．至少有h+3個節點C．至多有4h個節點正確答案:AB．至多有4h-1個節點D．至少有h+4個節點第5題（3分）：對于一顆有50個節點的，度為3的樹來說，其最小高度為（）。A．3B．4C．5D．6正確答案:C第6題（3分）：對于一顆度為4的樹來說，若有20個度為4的節點，10個度為3的節點，1個度為2的節點，10個度為1的節點，則樹有多少個葉子節點：（）。D．122A．41B．82C．115正確答案:B第7題（3分）：二叉樹與度為2的樹的相同之處包括：（A．每個節點都有一個或兩個孩子B．至少有一個根節點）。C．至少有一個度為2的節點D.每個節點至多只有一個雙親節點正確答案:D第8題（3分）：假設一顆二叉樹的節點個數為50，則它的最小高度為：（）。A．4B．5C．6D．7正確答案:C第9題（3分）：高度為h的二叉樹最大節點個數為：（）。D．2h-1-1A．2hB．2h-1C．2h-1正確答案:C第10題（3分）：具有10個葉子節點的二叉樹有（）個度為2的節點。D．11A．8B．9C．10正確答案:B第11題（3分）：一個具有1025個節點的二叉樹的高度為（）。A．11B．10C．11~1025D．12~1024正確答案:C第12題（3分）：一顆完全二叉樹的節點個數為100，則第60個節點的度為（）。A．0B．1C．2D．不確定正確答案:A第13題（3分）：一顆滿二叉樹的節點個數為n，其中有m個葉子節點，高度為h，則（）。A．n=h+mB．h+m=2nC．m=h-1D．n=2h-1正確答案:D第14題（3分）：根據使用頻率為5的字符設計的哈夫曼編碼，不能的是（）。A．111，110，10，01，00B．000，001，010，011，1C．100，11，10，1，0D．001，000，01，11，10正確答案:C第15題（3分）：若二叉樹的中序遍歷結果是abcdef，且c為根節點，則（）。A．節點C有兩顆子樹B．二叉樹有兩個度為0的節點C．二叉樹的高為5D．以上都不對正確答案:A第16題（3分）：任何一顆二叉樹，采用自上而下,自左至右的方法遍歷,如果節點a有左孩子b,右孩子c，則在節點的先序遍歷、中序遍歷、后續遍歷中，（）。A．節點b一定在節點a的前面B．節點a一定在節點c的前面C．節點b一定在節點c的前面D．節點a一定在節點b的前面正確答案:C第17題（3分）：若唯一確定一顆二叉樹，只需知道二叉樹的（）。A．先序序列B．中序序列C．中序和后序序列D．先序和后序序列正確答案:C第18題（3分）：若唯一確定一顆二叉樹，只須知道二叉樹的（）。A．先序序列和后序序列B．先序序列和層次序列C．層次序列和后序序列D．層次序列和中序序列正確答案:D第19題（3分）：一顆二叉樹的中序序列為ABDCEFG,后序序列為BDCAFGE,則其左子樹中的節點個數為（）。A．3B．2C.4D.5正確答案:C第20題（3分）：若一顆二叉樹的中序序列為BDAECF,先序序列為ABDCEF,則該樹的后序序列為（）。A．DBEFCAB．DEBFCAC.DFEBCAD．DBFECA正確答案:A第21題（3分）：若一顆二叉樹的先序序列為EFHIGJK,中序序列為HFIEJKG,,則該樹根節點的右孩子節點為（）。A．EB．FC.GD．H正確答案:C第22題（3分）：若一顆二叉樹的后序序列為DABEC,中序序列為DEBAC，則該樹的先序序列為（）。A．ACBEDB．DECABC.DEABCD．CEDBA正確答案:D第23題（3分）：對二叉排序樹進行（）遍歷，遍歷所得到的序列是有序序列。A．按層次B．前序C．中序D．后序正確答案:C第24題（3分）：深度為5的完全二叉樹第5層上有4個結點，該樹一共有（）個結點。A．28B．30C．31D．19正確答案:D第25題（3分）：深度為5的完全二叉樹共有20個結點，則第5層上有（）個結點(根所在結點為第一層)。A．3B．8C．5D．6正確答案:C第26題（3分）：一棵哈夫曼樹共有n個非葉結點，則該樹一共有（）個結點。A.2*n-1B.2*n+1C.2*nD.2*(n-1)正確答案:B第27題（3分）：一棵哈夫曼樹共有n個非葉結點，則該樹有（）個葉結點。A．nB．n+1C．n-1D．2n正確答案:B第28題（3分）：一棵哈夫曼樹共有n個葉結點，則該樹有（）個非葉結點。A．n-1B．nC．n+1D．2n正確答案:A第29題（3分）：一棵哈夫曼樹有n個葉子結點（終端結點），該樹總共有（）個結點。A．2n-2B．2n-1C．2nD．2n+2正確答案:B第30題（3分）：設有13個權值的結點，用它們組成一棵哈夫曼樹，則該樹有（）個結點。A．13B．12C．26D．25正確答案:D第31題（2分）：一棵哈夫曼樹總共有23個結點，該樹共有（）個葉結點（終端結點）。A．10B．13C．11D．12正確答案:D第32題（2分）：一棵完全二叉樹共有30個結點，則該樹的高度是（）。A．6B．4C．3D．5正確答案:D第33題（2分）：一棵完全二叉樹的高度是5，最后一層上有6個結點，該樹共有（）個結點。A．30B．20C．21D．23正確答案:C第34題（2分）：一棵有n個結點采用鏈式存儲的二叉樹，則該樹共有（）個指針域為空。A．2nB．2n+1C．2n+2D．n+1正確答案:D第35題（2分）：在一棵二叉樹中，若根的編號從0開始,若編號為i的結點存在右孩子，則右孩子的順序編號為（）。A．2iB．2i-1C．2i+2D．2i+1正確答案:C2025云南開放大學數據結構網上作業6答案一、單項選擇題(共23題,共100分)第1題（5分）：在一個無向圖中，所有頂點的度之和等于邊數的（）倍。A.1/2B.1C.2D.4正確答案:C答案解析：無向圖中，一條邊計入兩個頂點的度數。第2題（5分）：有n個頂點的無向圖，最多有（）條邊。A.nB.n(n-1)C.n（n-1）/2D.2n正確答案:C答案解析：完全無向圖的邊數最多。有n個頂點的完全無向圖有n（n-1）/2條邊。第3題（5分）：在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（）條邊。A.nB.n+1C.n-1正確答案:CD.n/2答案解析：成為樹圖是邊最少。第4題（5分）：在無向圖中，定義頂點i到頂點j的路徑，是從頂點i到頂點j的一個（A.頂點序列B.頂點個數C.權值之和D.邊的條數正確答案:A答案解析：路徑是由頂點序列構成的。第5題（5分）：在n個頂點的連通圖中，任意一條簡單的路徑，其長度不可能超過（A.1B.n/2C.n-1D.n）。）。正確答案:C答案解析：若路徑長度超過n-1,則其中必存在重復的頂點。第6題（5分）：以說法錯誤的是（）。A.圖和樹的區別在于圖的邊數大于等于頂點數B.無向圖的連通分量是指無向圖中極大連通子圖C.一個強連通圖只有一個強連通分量D.一個圖中所有頂點的度之和等于邊數的兩倍正確答案:A答案解析：一個有向圖可以有很多頂點沒有邊。第7題（5分）：對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣大小是（）。A.nB.(n-1)*(n-1)C.n-1D.n*n正確答案:D答案解析：含有n個頂點的圖采用鄰接矩陣存儲，矩陣大小為n*n。第8題（5分）：對于一個具有n個頂點e條邊的無向圖存儲在鄰接矩陣中，則非零元素的個數是（）。）。A.nB.2eC.eD.n+e正確答案:B答案解析：無向圖的鄰接矩陣中，每個非零元素記2次，即非零元素個數為2e。第9題（4分）：對于一個具有n個頂點e條邊的有向圖存儲在鄰接矩陣中，則非零元素的個數是（A.n正確答案:C答案解析：有向圖的鄰接矩陣中，每個非零元素記1次，即非零元素個數為e。B.2eC.eD.n+e第10題（4分）：如果從無向圖的任一頂點出發進行一次深度優先遍歷即可訪問所有的頂點。則該圖一定是一個（）。A.完全圖B.連通圖C.有回路D.一棵樹正確答案:B答案解析：只有連通圖才能一次深度優先遍歷即可訪問所有頂點。第11題（4分）：一個無向連通圖的生出樹是含有該連通圖的全部頂點的（）。A.極小連通子圖B.極小連通圖C.極大連通子圖D.極大子圖正確答案:A答案解析：生成樹是含有全部頂點的極小連通子圖。第12題（4分）：最小生成樹是指（）。A.由連通圖所得到的邊數最少的生成樹B.由連通圖所得到的頂點數相對較少的生成樹C.由連通圖所有生成樹中權值之和為最小的生成樹D.連通圖的極小連通子圖正確答案:A第13題（4分）：求最短路徑的Dijkstra算法的時間復雜度為（）。A.O(n)B.O(n+e)C.O(n2)D.O(ne)正確答案:C第14題（4分）：求最短路徑的Floyd算法的時間復雜度為（）。A.O(n)B.O(n+e)C.O(n2)D.O(n3)正確答案:D第15題（4分）：在一個有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和為（）。A.sB.s-1C.s+1D.n正確答案:A第16題（4分）：一個有向圖有n個頂點，則每個頂點的度可能的最大值是（）。A.n-1B.2(n-1)C.nD.2n正確答案:B第17題（4分）：具有6個頂點的無向圖至少應有（）條邊才能確保是一個連通圖。A.5B.6C.7D.8正確答案:A第18題（4分）：一個有n個頂點的無向圖最多有（）條邊。A.nB.n(n-1)C.n(n-1)/2D.2n正確答案:C第19題（4分）：任何一個無向連通圖的最小生成樹（）。A.至少有一棵B.只有一棵C.一定有多棵D.可能不存在正確答案:A第20題（4分）：已知一個圖的邊數為m，則該圖的所有頂點的度數之和為（）。A．2mB．mC．2m+1D．m/2正確答案:A答案解析：一條邊連接兩個頂點，可以記為兩個頂點的度。第21題（4分）：已知一個圖的所有頂點的度數之和為m，則m一定不可能是（）。A．4B．8C．12D．9正確答案:D答案解析：在一個無向圖中，所有頂點的度之和等于邊數的2倍。因此，度之和肯定是偶數。第22題（4分）：以下說法不正確的是（）。A．連通圖G一定存在生成樹B．連通圖G的生成樹中一定包含G的所有頂點C．連通圖G的生成樹中不一定包含G的所有邊D．連通圖G的生成樹可以是不連通的正確答案:D第23題（4分）：以下說法正確的是（）。A．連通圖G的生成樹中可以包含回路B．連通圖G的生成樹可以是不連通的C．連通圖G的生成樹一定是唯一的D．連通圖G的生成樹一定是連通而不包含回路的正確答案:D2025云南開放大學數據結構網上作業7答案一、單項選擇題(共25題,共100分)第1題（4分）：穩定的排序算法指（）。A．經過排序后，能使關鍵字相同的元素保持原順序中的相對位置不變B．經過排序后，能使關鍵字相同的元素保持原順序中的絕對位置不變C．排序算法的性能與被排序元素的個數關系不大D．排序算法的性能與被排序元素的個數關系密切正確答案:A第2題（4分）：以下排序方法中，（）不需要進行關鍵字的比較。C．基數排序D．堆排序A．快速排序正確答案:CB．歸并排序第3題（4分）：以下排序方法中，穩定的排序方式是（）。C．基數排序D．堆排序A．快速排序正確答案:CB．希爾排序第4題（4分）：將1000個英文單詞進行排序，采用（）方法最好。A．快速排序正確答案:DB．直接插入排序C．堆排序D．基數排序第5題（4分）：外排序是指（）。A．在外存上進行的排序方法B．不需要使用內存的排序方法C．數據很大，需要人工干預的排序方法D.排序前后數據在外存，排序時數據調入內存的排序方法正確答案:D第6題（4分）：在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。A.直接插入排序正確答案:AB．簡單選擇排序C．快速排序D．歸并排序第7題（4分）：內部排序算法的穩定性是指()。A．該排序算法不允許有相同的關鍵字記錄B．該排序算法允許有相同的關鍵字記錄C．平均時間為0（nlogn）的排序方法D．以上都不對正確答案:D第8題（4分）：下面給出的四種排序算法中，(A．插入排序正確答案:B)是不穩定的排序。C．二路歸并排序B．堆排序D．冒泡排序第9題（4分）：在下列排序算法中，哪一種算法的時間復雜度與初始排序序列無關（）。D．直接選擇排序A．直接插入排序B．冒泡排序正確答案:DC．快速排序第10題（4分）：關鍵字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中()的兩趟排序后的結果。A．選擇排序B.冒泡排序C.插入排序D.堆排序正確答案:C第11題（4分）：下列排序方法中，()所需的輔助空間最大。A．選擇排序B．希爾排序C．快速排序D．歸并排序正確答案:D第12題（4分）：一組記錄的關鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為支點得到的一次劃分結果為（）。A．(38,40,46,56,79,84)B．(40,38,46,79,56,84)C．(40,38,46,56,79,84)D．(40,38,46,84,56,79)正確答案:C第13題（4分）：在對一組關鍵字序列{70，55，100，15，33，65，50，40，95}，進行直接插入排序時，把65插入，需要比較()次。A.2B.4C.6D.8正確答案:A第14題（4分）：從待排序的序列中選出關鍵字值最大的記錄放到有序序列中，該排序方法稱為()。A.希爾排序B.直接選擇排序C.冒泡排序D.快速排序正確答案:B第15題（4分）：當待排序序列基本有序時，以下排序方法中，()最不利于其優勢的發揮。A.直接選擇排序B.快速排序C.冒泡排序D.直接插入排序正確答案:B第16題（4分）：對n個元素進行冒泡排序，要求按升序排列，程序中設定某一趟冒泡沒有出現元素交換，就結束排序過程。對某n個元素的排序共進行了3n-6次元素間的比較就完成了排序，則（）。A.原序列是升序排列B.原序列是降序排列C.對序列只進行了2趟冒泡D.對序列只進行了3趟冒泡正確答案:D第17題（4分）：對n個元素進行冒泡排序，通常要進行n-1趟冒泡，在第j趟冒泡中共要進行（）次元素間的比較。A．jB．j-1C．n-jD．n-j-1正確答案:C第18題（4分）：對n個元素進行冒泡排序若某趟冒泡中只進行了（）次元素間的交換，則表明序列已經排好序。A．1B．2C．0D．n-1正確答案:C第19題（4分）：排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。A．歸并B．插入C．選擇D．快速正確答案:C第20題（4分）：排序過程中，每一趟從無序子表中將一個待排序的記錄按其關鍵字的大小放置到已經排好序的子序列的適當位置，直到全部排好序為止，該排序算法是()。A．直接插入排序B．快速排序C．冒泡排序D．選擇排序正確答案:A第21題（4分）：排序算法中，從未排序序列中依次取出元素與已排序序列（初始為