2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題

2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題2021級(jí)數(shù)據(jù)2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第1頁(yè)。第1章緒論一、單選題：（從給定選項(xiàng)中選擇最合適的答案）1。算法分析的目的是_;。a．找出數(shù)據(jù)結(jié)構(gòu)的合理性b．研究算法中的輸入和輸出的關(guān)系c．分析算法的效率以求改進(jìn)d．分析算法的易懂性和文檔性2．線性表的順序存儲(chǔ)結(jié)構(gòu)是一種____的存儲(chǔ)結(jié)構(gòu)。a、隨機(jī)存取B.順序存取C.索引存取D.散列存取3.順序存儲(chǔ)設(shè)計(jì)中，存儲(chǔ)單元的地址。a．一定連續(xù)b．一定不連續(xù)c．不一定連續(xù)d．部分連續(xù)，部分不連續(xù)4.下列數(shù)據(jù)中_______是非線性數(shù)據(jù)結(jié)構(gòu)。a、堆棧B.隊(duì)列C.完整的二叉樹(shù)D.字符串5。算法應(yīng)該是___。a．程序b．問(wèn)題求解步驟的描述c．要滿(mǎn)足五個(gè)基本特性d．a(chǎn)和c.6．以下屬于邏輯結(jié)構(gòu)的是_______。a、序列表B.哈希表C.線性表D.單鏈表7。當(dāng)計(jì)算機(jī)執(zhí)行以下語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行頻率為_(kāi)_。對(duì)于（i=l；i=i；j--）s；a．o（n）b．o(nlogn)c．o(n3)d．o(n2)8．算法分析的兩個(gè)主要方面是_____。a、空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)潔性c．可讀性和文檔性d．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性9．下面說(shuō)法錯(cuò)誤的是________.a、算法的原位工作意味著不需要添加額外的輔助空間b.在相同的規(guī)模n下，復(fù)雜度o(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度o(2n)的算法c.所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界d.同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低10.如果序列表的第一個(gè)元素的存儲(chǔ)地址為100，每個(gè)元素的長(zhǎng)度為2，則第五個(gè)元素的地址為_(kāi)_。a．110b．108c．100d．12011.從存儲(chǔ)結(jié)構(gòu)來(lái)看，數(shù)據(jù)結(jié)構(gòu)可以分為兩類(lèi)。a．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)b．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)c．線性結(jié)構(gòu)、非線性結(jié)構(gòu)d．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)12．下列敘述中正確的是_____。a、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一個(gè)存儲(chǔ)結(jié)構(gòu)。2021級(jí)數(shù)據(jù)2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第2頁(yè)。c、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，而各種存儲(chǔ)結(jié)構(gòu)不會(huì)影響數(shù)據(jù)處理的效率。d、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率。13．算法的計(jì)算量的大小稱(chēng)為計(jì)算的_______。a、效率B.復(fù)雜性C.現(xiàn)實(shí)D.困難14。以下是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是什么？a、高存儲(chǔ)密度B.便于插入和操作c．刪除運(yùn)算方便d．可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示15．以下敘述中錯(cuò)誤的是_______。a．算法正確的程序最終一定會(huì)結(jié)束b．算法正確的程序可以有零個(gè)輸出c．算法正確的程序可以有零個(gè)輸入d、對(duì)于相同的輸入，具有正確算法的程序必須具有相同的結(jié)果。16.數(shù)據(jù)結(jié)構(gòu)的定義是（D，s），其中D是_________________。a．算法b．?dāng)?shù)據(jù)元素c．?dāng)?shù)據(jù)操作d．邏輯結(jié)構(gòu)17．執(zhí)行完下列語(yǔ)句段后，i值為_(kāi)______。intf(intx){return（（x>0）？x*f（x-1）：2）；}因蒂；i=f（f（1））；a．2b．4c．8d．無(wú)限遞歸18．一個(gè)遞歸算法必須包括______。a、遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分二、判斷對(duì)錯(cuò)題：（正確的選a，錯(cuò)誤的選b）1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（）2.順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（）3.記錄是數(shù)據(jù)處理的最小單位。（）4.程序一定是算法。（）5.在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)還存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。（）6.數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴(lài)于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。（）7.遞歸的算法簡(jiǎn)單、易懂、容易編寫(xiě)，而且執(zhí)行效率也高。（）8.每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和搜索。（）三、申請(qǐng)問(wèn)題1.給出圓環(huán)類(lèi)的聲明（內(nèi)徑為r1,外徑為r2）（包括求圓環(huán)面積、圓環(huán)內(nèi)周長(zhǎng)和外周長(zhǎng)）。2.給出等腰三角形類(lèi)的聲明（腰長(zhǎng)為a,底長(zhǎng)為b）（包括求面積與周長(zhǎng)）。第2章線性表2021級(jí)數(shù)據(jù)2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第3頁(yè)。1.如果線性表最常見(jiàn)的操作是訪問(wèn)具有指定序列號(hào)的任何元素，并在最后執(zhí)行插入和刪除操作，請(qǐng)使用__________________。a．順序表b．雙鏈表c．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表d．單循環(huán)鏈表2．以下數(shù)據(jù)結(jié)構(gòu)中，_______是線性結(jié)構(gòu)。a、哈希表B.二叉樹(shù)C.有向圖D.字符串3．設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為structnode{elemtypedata；structnode*link；}；已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列______操作。a．s->link=p；p->link=s；b．s->link=p->link；p->link=s；c．s->link=p->link；p=s；d．p->link=s；s->link=p；4.在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否_____。a、空B.滿(mǎn)C.溢出D.下溢5．若棧頂指針指向棧頂元素，當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為_(kāi)____。a、n-1b。北卡羅來(lái)納州。n+1d。n/26。如果堆棧以順序存儲(chǔ)模式存儲(chǔ)，那么兩個(gè)堆棧的共享空間v[1..M]，top[i]表示第i個(gè)堆棧的頂部（i=1,2），堆棧1的底部為v[1]，堆棧2的底部為v[M]。如果堆棧頂部指針指向頂部元素，則堆棧已滿(mǎn)的條件為_(kāi);。a、|頂部[2]-頂部[1]|=0b。top[1]+1=top[2]c.top[1]+top[2]=md.top[1]=top[2]7.遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱(chēng)為_(kāi)______的數(shù)據(jù)結(jié)構(gòu)。a．隊(duì)列b．多維數(shù)組c．棧d.線性表8.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為_(kāi)_____.a.1和5b.2和4c.4和2d.5和19.若進(jìn)隊(duì)列的序列為1,2,3,4則_____是一個(gè)出隊(duì)列序列。a.3,2,1,4b.3,2,4,1c.4,3,2,1d.1,2,3,410.在鏈?zhǔn)疥?duì)列中，假設(shè)f和R分別是隊(duì)列頭部和尾部的指針，則刪除節(jié)點(diǎn)的操作時(shí)間u。a、r=f->next；b、r=r->next；c、f=f->next；d、f=r->next；11.當(dāng)線性表（A1、A2、…、an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜度為_(kāi)__。a、o（i）b.o（1）c.o（n）d.o（i-1）12．刪除一單向鏈表中p指針?biāo)赶蚪Y(jié)點(diǎn)的后繼結(jié)點(diǎn)，正確的操作是_______。a．p->next=p->next->next;b．p=p->next;c、p->next=p；d.p->next->next=p->next13．為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的_______設(shè)在內(nèi)存空間的兩端。2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第4頁(yè)。a、2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第4頁(yè)。a．遞歸調(diào)用b．子程序調(diào)用c．表達(dá)式求值d．a(chǎn)，ｂ，ｃ31．棧和隊(duì)列都是_______。a、順序存儲(chǔ)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.受限訪問(wèn)點(diǎn)的線性結(jié)構(gòu)D.受限訪問(wèn)點(diǎn)的非線性結(jié)構(gòu)15.堆棧是否為。a.空b.滿(mǎn)c.上溢d.下溢16.如果堆棧的輸入序列是1,2,3，。。。，N、輸出序列的第一個(gè)元素是I，第j個(gè)輸出元素是_。a.i-j-1b.i-jc.j-i+1d.不確定的17．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算時(shí)____。a．f->next=s;f=s;b．r->next=s;r=s;c．s->next=r;r=s;d．s->next=f;f=s;18.確定循環(huán)隊(duì)列Qu（最大元素為M0）為空的條件為。a．qu.front==（qu.rear+1）%m0b．qu.front！=（qu.rear+1）%m0c．qu.front==qu.reard．qu.front！=qu.rear19.在單循環(huán)鏈表頭的末尾插入s指針指向的節(jié)點(diǎn)（后指針指向）。正確的操作是__;。a．rear->next=s;s->next=head;b．s->next=rear;rear->next=head;c．rear=s;s->next=head;d．rear->next=s;s=head;20．已知函數(shù)sub(s,i,j)的功能是返回串s中從第i個(gè)字符起長(zhǎng)度為j的子串，函數(shù)scopy(s,t)的功能為復(fù)制串t到s。若字符串s=〃sciencestudy〃，則調(diào)用函數(shù)scopy(p,sub(s,1,7))后得到_______。a、p=“科學(xué)”b.p=“研究”c.s=“科學(xué)”d.s=“研究”21.設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用______數(shù)據(jù)結(jié)構(gòu)最佳。a．線性表的順序存儲(chǔ)結(jié)構(gòu)b.隊(duì)列c.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)d.棧22.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)______。a.僅修改頭指針b.僅修改尾指針c.頭、尾指針都要修改d.頭、尾指針都不修改23.以下算法的函數(shù)為_(kāi)__________________。voidalgo（stacks，inte）｛stackt；intd；initstack（t）while(!stackempty(s)){流行音樂(lè)（s，d）；如果（d！=e）推（t，d）；}而（！stackempty（t））{pop（t，d）；push（s，d）；}2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第5頁(yè)。a．刪除棧s中的數(shù)據(jù)eb.判斷棧s中是否存在數(shù)據(jù)ec．將棧s中的數(shù)據(jù)逆置d.2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第5頁(yè)。而（！stackempty（s））{n++；pop（s，a[n]）；}對(duì)于（i=1；i<=n；i++）推送（s，a[i]）；}a．將棧s中的元素逆置b．將數(shù)組a中的元素逆置c．輸出棧s中的元素d．輸出數(shù)組a中的元素25.與單向鏈表相比，使用雙向鏈表存儲(chǔ)數(shù)據(jù)的優(yōu)點(diǎn)是它可以。a、提高檢索速度B.輕松插入和刪除數(shù)據(jù)C.節(jié)省存儲(chǔ)空間D.快速恢復(fù)存儲(chǔ)空間26．當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為_(kāi)_____。a．n-2b．n-1c．nd．n+127.指針P、Q和R依次指向循環(huán)鏈表中的三個(gè)相鄰節(jié)點(diǎn)。交換節(jié)點(diǎn)*q和節(jié)點(diǎn)*r的程序段在列表中的順序?yàn)開(kāi);。a、p->next=r；q->next=r->next；r->next=q；b.p->next=r；r->next=q；q->next=r->next；c.r->next=q；q->next=r->next；28。字符串操作函數(shù)STR被定義為：intstr（char*s）{char*P=s；while（*P！='\\0'）P++；returnp-s；}那么str（“'ABCDE'）的返回值是u。a．3b．4c．5d．629.與線性表相比，字符串插入和刪除操作的特點(diǎn)是。a．通常以串整體作為操作對(duì)象b．需要更多的輔助空間c．算法的時(shí)間復(fù)雜度較高d．涉及移動(dòng)的元素更多30.對(duì)線性表（7、34、55、25、64、46、20、10）進(jìn)行散列時(shí)，如果選擇h（k）=k%9作為散列函數(shù)，則散列地址為1的元素為1。a．1b．2c．3d．431.如果主串長(zhǎng)度為n，模式串長(zhǎng)度為m（m≤n），則在匹配失敗的情況下，樸素匹配算法執(zhí)行的無(wú)效位移數(shù)為_(kāi)_。a．mb．n-mc．n-m+1d．n32．已知順序表的存儲(chǔ)結(jié)構(gòu)為：typedefstruct{elemtypev[];intlength;}l;以下算法的功能是__。voidsorta（sqlist&l）{inti=0，zerosum=0；if（l.length==0）返回（0）；elsefor(i=1;i<=l.length;i++){if(l.v[i]<>0)l.v[i-zerosum]=l.v[i];elsezerosum++;}｝2021級(jí)數(shù)據(jù)結(jié)構(gòu)習(xí)題全文共6頁(yè)，當(dāng)前為第6頁(yè)。a、計(jì)算線性表L.B中非零元素的數(shù)量。將線性表L中的零元素集中到表C的末尾。刪除線性表L.D中的零元素。計(jì)算線性表L.33中的零元素?cái)?shù)量。在序列表上的以下操作中，時(shí)間復(fù)雜度為