數(shù)據(jù)結(jié)構(gòu)習(xí)題-第2章

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院單項(xiàng)選擇題鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)單元的地址（）。A．一定連續(xù) B．一定不連續(xù)C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù)在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行。As->next=p;p->next=s;Bs->next=p->next;p->next=s;Cs->next=p->next;p=s;Dp->next=s;s->next=p;2/3/20232單項(xiàng)選擇題鏈表不具有的特點(diǎn)是（）。A．插入、刪除不需要移動(dòng)元素 B．可隨機(jī)訪問任一元素C．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與線性長度成正比算法的計(jì)算量的大小稱為計(jì)算的（）。A．效率 B．復(fù)雜性 C．現(xiàn)實(shí)性 D．難度若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i(1<=i<=n+1)個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）。A．O（0）B．O（1）C．O（n）D．O（n2）2/3/20233算法分析的兩個(gè)主要方面是（）。A．空間復(fù)雜性和時(shí)間復(fù)雜性 B．正確性和簡明性C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性下列哪一項(xiàng)是鏈表具有的特點(diǎn)

。A．必事先估計(jì)存儲(chǔ)空間B．可隨機(jī)訪問任一元素C．插入、刪除不需要移動(dòng)元素 D．邏輯地址與物理存儲(chǔ)地址一致在順序表中刪除一個(gè)元素，需要平均移動(dòng)的元素個(gè)數(shù)為（）。A．(n-1)/2 B．n/2 C．(n+1)/2 D．n-12/3/20234對(duì)于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。A．O(n)O(n)B．O(n)O(1) C．O(1)O(n) D．O(1)O(1)對(duì)于頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（）A．head＝＝NULL B．head->next＝＝NULLC．head->next＝＝head D．head!=NULL2/3/20235判斷題1、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。2、數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。 3、對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。4、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。5、線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。2/3/20236判斷題線性表就是順序存儲(chǔ)的表。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位，數(shù)據(jù)元素是數(shù)據(jù)的最小單位。線性表采用鏈接存儲(chǔ)，必須要申請(qǐng)占用一片連續(xù)的存儲(chǔ)單元。 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。 2/3/20237填空題1、下面程序段的時(shí)間復(fù)雜度為________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;2、已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是：________。3、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：________。4、鏈接存儲(chǔ)的特點(diǎn)是利用________來表示數(shù)據(jù)元素之間的邏輯關(guān)系。2/3/20238填空題5、對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共______個(gè)，單鏈表為_______個(gè)6、在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：________7、循環(huán)單鏈表的最大優(yōu)點(diǎn)是：________8、順序存儲(chǔ)結(jié)構(gòu)是通過________表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過________表示元素之間的關(guān)系的。2/3/20239算法設(shè)計(jì)設(shè)有一個(gè)由正整數(shù)組成的無序（向后）單鏈表，編寫能夠完成下列功能的算法：（1）找出最小值結(jié)點(diǎn)，且打印該數(shù)值；（2）若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點(diǎn)的數(shù)值交換；（3）若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除。。2/3/202310算法設(shè)計(jì)Intfunc(Linklist*L){Inttemp;Linklist*p=L->next；q=p;If(p==NULL)Return0;While(p){if(p->data<q->data)q=p;p=p->next;}Printf(“%d\n”,q->data);If(q->next==null)return0;If(q->data%2==1){temp=q->data;q->data=q->next->data;q->next->data=temp;}Else{p=q->next;q->next=p->next;free(p);}Return1;}2/3/202311算法設(shè)計(jì)在一個(gè)單鏈表L中，設(shè)計(jì)算法用指針P返回單鏈表中數(shù)據(jù)域最大的結(jié)點(diǎn)，并刪除該結(jié)點(diǎn)。2/3/202312算法設(shè)計(jì)LinkedListL_MAXDEL(LinkedListL)∥L是單鏈表的頭結(jié)點(diǎn)的指針{ pre=q=L;p=L->next;∥P指向最大的結(jié)點(diǎn) while(q->next)∥查最后一個(gè)元素結(jié)點(diǎn){if(q->next->data>p->