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

第11頁(yè)/共NUMPAGES\*ARABIC11頁(yè)江南大學(xué)網(wǎng)絡(luò)教育第一階段練習(xí)題答案參考答案在最后一頁(yè)正確答案是附最后考試科目:《數(shù)據(jù)結(jié)構(gòu)》第章至第章（總分100分）__________學(xué)習(xí)中心（教學(xué)點(diǎn)）批次：層次：專業(yè)：學(xué)號(hào)：身份證號(hào)：姓名：得分：一單選題(共10題，總分值20分，下列選項(xiàng)中有且僅有一個(gè)選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)1.在長(zhǎng)為n的順序表中刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)（）個(gè)數(shù)據(jù)元素。（2分）A.nB.n-1C.n/2D.(n-1)/22.在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素間存在（）的關(guān)系。（2分）A.一對(duì)一B.一對(duì)多C.多對(duì)多D.除同屬一個(gè)集合外別無(wú)關(guān)系3.下列不屬算法特性的是（）。（2分）A.有窮性B.確定性C.零或多個(gè)輸入D.健壯性4.設(shè)在一不帶頭結(jié)點(diǎn)的鏈隊(duì)列中，front和rear分別為其隊(duì)頭和隊(duì)尾指針，則判定該隊(duì)中只有一個(gè)結(jié)點(diǎn)的條件是（）。（2分）A.front->nextB.rear->nextC.front==rearD.front!=rear5.在一個(gè)可存放n個(gè)數(shù)據(jù)元素的順序棧中，假設(shè)以高地址端為棧底，以top為棧頂指針，當(dāng)向棧中壓入一個(gè)數(shù)據(jù)元素時(shí)，top的變化是（）。（2分）A.不變B.top=nC.top++D.top--6.判定一個(gè)棧頂指針為S且不帶頭結(jié)點(diǎn)的鏈棧為空棧的條件是（）。（2分）A.SB.S->nextC.S->next==NULLD.!S7.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。（2分）A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表D.單循環(huán)鏈表8.串的長(zhǎng)度是指（）。（2分）A.串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)9.下列說(shuō)法中錯(cuò)誤的是（）。（2分）A.數(shù)據(jù)對(duì)象是數(shù)據(jù)的子集B.數(shù)據(jù)元素間關(guān)系在計(jì)算機(jī)中的映象即為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.非順序映象的特點(diǎn)是借助指示元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素間邏輯關(guān)系D.抽象數(shù)據(jù)類型指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作10.設(shè)在一不帶頭結(jié)點(diǎn)的鏈隊(duì)列中，front和rear分別為其隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作是（）。（2分）A.rear=front->nextB.rear=rear->nextC.front=front->nextD.front=rear->next二多選題(共6題，總分值12分，下列選項(xiàng)中至少有2個(gè)或2個(gè)以上選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)11.下列關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的說(shuō)法中，正確的是（）。（2分）A.結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu);B.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接;C.可以通過(guò)計(jì)算直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址;D.插入、刪除操作方便，不必移動(dòng)節(jié)點(diǎn)12.下列敘述中錯(cuò)誤的是（）。（2分）A.順序文件不要求物理記錄的順序和邏輯記錄的順序一致;B.散列文件既適合隨機(jī)存取，也適合順序存取;C.按桶散列可減小內(nèi)存開(kāi)銷，提高內(nèi)存利用率;D.索引文件中包括文件數(shù)據(jù)區(qū)和索引表兩大部分，其主文件關(guān)鍵字不一定有序13.線性表（）。（2分）A.存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素;B.不存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素;C.存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素;D.不存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素14.下列說(shuō)法正確的有（）。（2分）A.算法和程序原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者通用;B.從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu);C.所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系D.同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)相等;E.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān);F.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體15.下列數(shù)據(jù)結(jié)構(gòu)中，屬于線性數(shù)據(jù)結(jié)構(gòu)的是（）。（2分）A.棧;B.隊(duì)列;C.樹(shù);D.圖16.從表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)表的是（）。（2分）A.靜態(tài)鏈表;B.單鏈表;C.順序表;D.雙鏈表;E.循環(huán)鏈表三判斷題(共10題，總分值10分正確的填涂“A”，錯(cuò)誤的填涂“B”。)17.在一個(gè)設(shè)置有頭指針和尾指針的單鏈表中，執(zhí)行刪除該單鏈表中最后一個(gè)元素的操作與鏈表的長(zhǎng)度無(wú)關(guān)。（1分）（

）18.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（1分）（

）19.若一個(gè)棧的輸入序列為{1,2,3,4,5}，則不可能得到{3,4,1,2,5}這樣的出棧序列。（1分）（

）20.對(duì)順序棧進(jìn)行進(jìn)棧、出棧操作不涉及元素的前、后移動(dòng)問(wèn)題。（1分）（

）21.將長(zhǎng)度分別為m,n的兩個(gè)單鏈表合并為一個(gè)單鏈表的時(shí)間復(fù)雜度為O(m+n)。（1分）（

）22.帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，任一結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針域均不空。（1分）（

）23.算法可以沒(méi)有輸入，但是必須有輸出。（1分）（

）24.鏈表中邏輯上相鄰的元素，其物理位置也一定相鄰。（1分）（

）25.對(duì)于順序存儲(chǔ)的長(zhǎng)度為N的線性表，訪問(wèn)結(jié)點(diǎn)和增加結(jié)點(diǎn)的時(shí)間復(fù)雜度分別對(duì)應(yīng)為O(1)和O(N)。（1分）（

）26.在順序表中邏輯上相鄰的元素，其對(duì)應(yīng)的物理位置也是相鄰的。（1分）（

）四簡(jiǎn)答題(共2題，總分值20分)27.設(shè)元素的入棧次序?yàn)閍、b、c、d，且在入棧的過(guò)程中允許出棧，試寫(xiě)出所有不可能得到的出棧序列。（10分）28.設(shè)ｎ為正整數(shù)，試確定如下程序段中語(yǔ)句“x++;”的頻度。for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=n;k++)x++;（10分）五綜合題(共3題，總分值38分)29.已知單鏈表L中含有三類字符的數(shù)據(jù)元素，即字母字符、數(shù)字字符和其他字符，試編寫(xiě)算法將L分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表只含一類字符。（12分）30.設(shè)a='datastructure'，b='computer'，c='demo'，試求：⑴StrLength(a)的返回值；⑵執(zhí)行StrInsert(b,4,c)后串b的值；⑶Index(a,'u',10)的返回值；⑷執(zhí)行Replace(a,'structure',b)后串a(chǎn)的值；⑸執(zhí)行SubString(s,b,3,3)后串s的值。（13分）31.設(shè)單鏈表Ｌ如圖所示：畫(huà)出執(zhí)行如下程序段后，各指針變量及單鏈表Ｌ的示意圖。p=L;for(i=1;i<=3;i++){q=(LinkList)malloc(sizeof(LNode));q->data=i*3;q->next=p->next;p->next=q;}（13分）

一單選題(共10題，總分值20分，下列選項(xiàng)中有且僅有一個(gè)選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)1.參考正確答案是為：D解析過(guò)程：2.參考正確答案是為：B解析過(guò)程：3.參考正確答案是為：D解析過(guò)程：4.參考正確答案是為：C解析過(guò)程：5.參考正確答案是為：D解析過(guò)程：6.參考正確答案是為：D解析過(guò)程：7.參考正確答案是為：A解析過(guò)程：8.參考正確答案是為：B解析過(guò)程：9.參考正確答案是為：B解析過(guò)程：10.參考正確答案是為：C解析過(guò)程：二多選題(共6題，總分值12分，下列選項(xiàng)中至少有2個(gè)或2個(gè)以上選項(xiàng)符合題目要求，請(qǐng)?jiān)诖痤}卡上正確填涂。)11.參考正確答案是為：A,B,D解析過(guò)程：12.參考正確答案是為：A,B解析過(guò)程：13.參考正確答案是為：A,C解析過(guò)程：14.參考正確答案是為：B,C,E解析過(guò)程：15.參考正確答案是為：A,B解析過(guò)程：16.參考正確答案是為：D,E解析過(guò)程：三判斷題(共10題，總分值10分正確的填涂“A”，錯(cuò)誤的填涂“B”。)17.參考正確答案是為：F解析過(guò)程：18.參考正確答案是為：F解析過(guò)程：19.參考正確答案是為：T解析過(guò)程：20.參考正確答案是為：T解析過(guò)程：21.參考正確答案是為：F解析過(guò)程：22.參考正確答案是為：T解析過(guò)程：23.參考正確答案是為：T解析過(guò)程：24.參考正確答案是為：F解析過(guò)程：25.參考正確答案是為：T解析過(guò)程：26.參考正確答案是為：T解析過(guò)程：四簡(jiǎn)答題(共2題，總分值20分)27.參考正確答案是為：dabcdacbdbacdbcadcabcadbcabdcdabbdacadbc解析過(guò)程：28.參考正確答案是為：解析過(guò)程：五綜合題(共3題，總分值38分)29.參考正確答案是為：voidpartition(LinkList&L,LinkList&LC,LinkList&LN,LinkList&LO){//L帶頭結(jié)點(diǎn)，LC為含字母字符的循環(huán)鏈表，LN為含數(shù)字字符的循環(huán)鏈表，//LO為含其他字符的循環(huán)鏈表InitCL(LC);InitCL(LN);InitCL(LO);//對(duì)三個(gè)循環(huán)鏈表進(jìn)行初始化p=L->next;//p指向第一個(gè)結(jié)點(diǎn)while(p){q=p;p=p->next;//q指向當(dāng)前待處理結(jié)點(diǎn)，p指向剩余鏈表if(q->data>=’A’&&q->data<=’Z’||q->data>=’a’&&q->data<=’z’){q->next=LC->next;LC->next=q;}//字母字符入循環(huán)鏈表LCelseif(q->data>=’0’&&q->data<=’9’){q->next=LN->next;LN->next=q;}//數(shù)字字符入循環(huán)鏈表LNelse{q->next=LO->next;LO->next=q;}//其他字符入循環(huán)