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

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

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