數(shù)據(jù)結(jié)構(gòu)第1階段練習(xí)題答案 江南大學(xué)2022年秋季

第10頁/共NUMPAGES\*ARABIC10頁江南大學(xué)網(wǎng)絡(luò)教育第一階段練習(xí)題答案，答案在最后一頁。考試科目:《數(shù)據(jù)結(jié)構(gòu)》第章至第章（總分100分）__________學(xué)習(xí)中心（教學(xué)點）批次：層次：專業(yè)：學(xué)號：身份證號：姓名：得分：一單選題(共10題，總分值20分，下列選項中有且僅有一個選項符合題目要求，請在答題卡上正確填涂。)1.設(shè)輸入序列為ABC，輸出序列為CBA，則經(jīng)過的棧操作為（）。（2分）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop2.設(shè)串s1='abcdefg'，s2='ab'，則Concat(s1,s2)的返回值（）。（2分）A.abB.cdefgC.abcdefgD.abcdefgab3.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前隊尾指針rear和隊頭指針front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（）。（2分）A.1和5B.2和4C.4和2D.5和14.下列說法中錯誤的是（）。（2分）A.棧是一種非線性結(jié)構(gòu)B.一個數(shù)據(jù)元素由一或多個數(shù)據(jù)項構(gòu)成C.在順序存儲結(jié)構(gòu)中，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)D.語句的頻度就是語句的執(zhí)行次數(shù)5.串是一種特殊的線性表，其特殊性體現(xiàn)在（）。（2分）A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符6.（）是數(shù)據(jù)的不可分割的最小單位。（2分）A.數(shù)據(jù)元素B.數(shù)據(jù)對象C.數(shù)據(jù)項D.數(shù)據(jù)結(jié)構(gòu)7.順序表中數(shù)據(jù)元素的存取方式為（）。（2分）A.隨機存取B.順序存取C.索引存取D.連續(xù)存取8.以下屬單鏈表優(yōu)點的是（）。（2分）A.順序存取B.插入操作能在O(1)的時間復(fù)雜度上完成C.插入時不需移動數(shù)據(jù)元素D.節(jié)省存儲空間9.若采用順序映象，則數(shù)據(jù)元素在內(nèi)存中占用的存儲空間（）。（2分）A.一定連續(xù)B.一定不連續(xù)C.可連續(xù)可不連續(xù)10.設(shè)串s='abcdefgh'，則其子串?dāng)?shù)為（）。（2分）A.8B.37C.36D.9二多選題(共5題，總分值10分，下列選項中至少有2個或2個以上選項符合題目要求，請在答題卡上正確填涂。)11.下列說法正確的是（）。（2分）A.在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的;B.在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間沒有明顯的層次關(guān)系;C.在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間僅有線性關(guān)系;D.在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系12.算法設(shè)計的要求包括（）。（2分）A.正確性;B.可讀性;C.健壯性;D.確定性13.兩串相等必須有（）。（2分）A.串長度相等;B.串中各位置字符任意;C.串中各位置字符均對應(yīng)相等;D.串長度不等;E.串長度任意14.下列屬于算法的重要特征的是（）。（2分）A.有窮性;B.確定性;C.可行性;D.輸入和輸出15.下列不是順序存儲結(jié)構(gòu)優(yōu)點的有（）。（2分）A.存儲密度大;B.插入運算方便;C.可方便的用于各種邏輯結(jié)構(gòu)的存儲表示;D.刪除運算方便三判斷題(共10題，總分值10分正確的填涂“A”，錯誤的填涂“B”。)16.循環(huán)鏈表可以做到從任一結(jié)點出發(fā)，訪問到鏈表的全部結(jié)點。（1分）（

）17.順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩＃?分）（

）18.在順序表上進行插入、刪除操作時需要移動元素的個數(shù)與待插入或待刪除元素的位置無關(guān)。（1分）（

）19.算法分析的兩個主要方面是時間復(fù)雜度和空間復(fù)雜度的分析。（1分）（

）20.若一個棧的輸入序列為1，2，3，…，N，輸出序列的第一個元素是i，則第j個輸出元素是j?i?1。（1分）（

）21.2N和NN具有相同的增長速度。（1分）（

）22.n個元素進隊的順序和出隊的順序總是一致的。（1分）（

）23.單鏈表中引入頭結(jié)點會使結(jié)點插入操作的時間復(fù)雜度降為常數(shù)階。（1分）（

）24.所謂隨機存取，就是通過首地址和元素的位序號值可以在O(1)的時間內(nèi)找到指定的元素。（1分）（

）25.線性表采用鏈?zhǔn)酱鎯Ρ硎緯r，所有結(jié)點之間的存儲單元地址可以連續(xù)也可以不連續(xù)。（1分）（

）四簡答題(共2題，總分值20分)26.設(shè)n為正整數(shù)，則在下面的程序段中，語句“a+=2;”的頻度為多少？for(x=0;x<n;++x)for(y=0;y<n;++y)a+=2;（10分）27.有5個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？（10分）五綜合題(共3題，總分值40分)28.設(shè)a='colomn'，b='How

areyou!'，c='please'，試求：（1）StrLength(b)的返回值；（2）Index(a,'o',5)的返回值；（3）執(zhí)行StrInsert(a,3,c)后串a(chǎn)的值；（4）執(zhí)行Replace(c,'e','x')后串c的值；（5）執(zhí)行SubString(s,b,5,3)后串s的值。（13分）29.設(shè)單鏈表L帶頭結(jié)點且非空，指針變量p指向L中的一個結(jié)點，且該結(jié)點既不是L中的第一個結(jié)點，也不是L中的最后一個結(jié)點，指針變量s指向一個待插入L的新結(jié)點。試寫出能完成下列操作的語句序列。⑴在p所指結(jié)點之前插入s所指結(jié)點；⑵在L中最后一個結(jié)點之后插入s所指結(jié)點；⑶刪除p所指結(jié)點的直接后繼；⑷刪除L中第一個結(jié)點。（13分）30.假設(shè)將循環(huán)隊列定義為：以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)，試寫出其入隊和出隊算法（在出隊算法中要返回隊頭元素）。（14分）

一單選題(共10題，總分值20分，下列選項中有且僅有一個選項符合題目要求，請在答題卡上正確填涂。)1.參考答案為：B解析過程：2.參考答案為：D解析過程：3.參考答案為：B解析過程：4.參考答案為：A解析過程：5.參考答案為：B解析過程：6.參考答案為：C解析過程：7.參考答案為：A解析過程：8.參考答案為：C解析過程：9.參考答案為：A解析過程：10.參考答案為：B解析過程：二多選題(共5題，總分值10分，下列選項中至少有2個或2個以上選項符合題目要求，請在答題卡上正確填涂。)11.參考答案為：A,B,D解析過程：12.參考答案為：A,B,C解析過程：13.參考答案為：A,C解析過程：14.參考答案為：A,B,C,D解析過程：15.參考答案為：B,C,D解析過程：三判斷題(共10題，總分值10分正確的填涂“A”，錯誤的填涂“B”。)16.參考答案為：T解析過程：17.參考答案為：F解析過程：18.參考答案為：F解析過程：19.參考答案為：T解析過程：20.參考答案為：F解析過程：21.參考答案為：F解析過程：22.參考答案為：T解析過程：23.參考答案為：F解析過程：24.參考答案為：T解析過程：25.參考答案為：T解析過程：四簡答題(共2題，總分值20分)26.參考答案為：答：n2解析過程：27.參考答案為：答：CDEBACDBEACDBAE解析過程：五綜合題(共3題，總分值40分)28.參考答案為：（1）12（2）0（3）’copleaselomn’（4）’plxasx’（5）’are’解析過程：29.參考答案為：⑴q=L;while(q->next!=p)q=q->next;//q指向p的直接前驅(qū)s->next=p;q->next=s;⑵q=L;while(q->next)q=q->next;s->next=NULL;q->next=s;⑶q=p->next;//q指向待刪結(jié)點p->next=q->next;free(q);⑷q=L->next;L->next=q->next;free(q);解析過程：30.參考答案為：#defineMAXQSIZE100typedefstruct{ElemTypebase[MAXQSIZE];intrear;intlength;}Queue;StatusEnQueue(Queue&Q,ElemTypee){if(Q.length==MAXQSIZE)returnERROR;Q.rear