數(shù)據(jù)結(jié)構(gòu)練習題——帶答案

1、數(shù)據(jù)結(jié)構(gòu)第 1-2 章練習題、選擇 1、通常從正確性、 易讀性、健壯性、高效性等四個方面評價算法 （ 包括程序 ）的質(zhì)量。以下解釋錯誤的是 （ ）A、正確性 算法應能正確地實現(xiàn)預定的功能 （ 即處理要求 ）B、易讀性 算法應易于閱讀和理解 以便于調(diào)試 修改和擴充C、健壯性 當環(huán)境發(fā)生變化時，算法能適當?shù)刈龀龇磻蜻M行處理，不會產(chǎn)生不需要的運行結(jié)果D、高效性 即達到所需要的時間性能2、以下說法正確的是 （ ）A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位BC、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合、數(shù)據(jù)項是數(shù)據(jù)的基本單位D、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合3、對于順序表，以下說法錯誤的是（）A、順序表是用一維數(shù)組實

2、現(xiàn)的線性表，數(shù)組的下標可以看成是元素的絕對地址B 、順序表的所有存儲結(jié)點按相應數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C、順序表的特點是 : 邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰D 、順序表的特點是 :邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中 數(shù)組的下標可以看成是元素的相對地址4、對順序表上的插入、刪除算法的時間復雜性分析來說，通常以（A、條件判斷B 、結(jié)點移動C5、對于順序表的優(yōu)缺點，以下說法錯誤的是 A 、無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間C、插入和刪除運算較方便 到充分利用 6、鏈表不具有的特點是：A 、可隨機訪問任一個元素、算術(shù)表達式 D（）B）為標準操作、賦值語句、

3、可以方便地隨機存取表中的任一結(jié)點D、容易造成一部分空間長期閑置而得不C、不必事先估計存儲空間7、若線性表最常用的操作是存取第 A 、單鏈表 B 、雙向鏈表 順序表可以隨機存取B、插入刪除不需要移動元素D、所需空間與線性表長度成正比 i 個元素及其前驅(qū)的值，則采用（ C、單循環(huán)鏈表D、順序表）存儲方式節(jié)省時間）式來刻畫8、設指針 P 指向雙鏈表的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性可用（A、p-prior-next-=p-next-nextB 、 p-prior-prior-=p-next-priorC、 p-prior-next-=p-next-prior D、 p-next-next=p-prio

4、r-prior9、以下說錯誤的是 （ ）A、對循環(huán)來說，從表中任一結(jié)點出發(fā)都能通過前后操作而掃描整個循環(huán)鏈表B、對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點C、雙鏈表的特點是找結(jié)點的前趨和后繼都很容易D、對雙鏈表來說，結(jié)點 *P 的存儲位置既存放在其前趨結(jié)點的后繼指針域中，也存放在它的后繼結(jié)點的 前趨指針域中。10、在帶頭結(jié)點的循環(huán)鏈表中， 將頭指針改設為尾指針 （rear） 后，其頭結(jié)點和尾結(jié)點的存儲位置分別是 （ ）A、rear 和 rear-next-nextB、 rear-next 和 rearC、 rear-next-next 和 rearD、 rear 和 rear-next

5、11. 以下說錯誤的是 （ ）A、對于線性表來說，查找定位運算在順序表和單鏈表上的量級均為O（ n）B、讀表元運算在順序表上只需常數(shù)時間O（ 1）便可實現(xiàn)，因此順序表是一種隨機存取結(jié)構(gòu)C、在鏈表上實現(xiàn)讀表元運算的平均時間復雜性為O（ 1）D、插入、刪除操作在鏈表上的實現(xiàn)可在O（ n）時間內(nèi)完成12、循環(huán)鏈表主要優(yōu)點是（）A、不再需要頭指針了B 、已知某個結(jié)點的位置后，能夠容易找到它的直接前趨C、從表中任一結(jié)點出發(fā)都能掃描到整個鏈表D、在進行插入、刪除運算時，能更好地保證鏈表不斷開13、以下說法錯誤的是( )A、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式B、算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)

6、中二者是通用的C、對鏈表進行插人和刪除操作時，不必移動結(jié)點D、雙鏈表中至多只有一個結(jié)點的后繼指針為空14、以下說法正確的是A、線性結(jié)構(gòu)的基本特征是：每個結(jié)點有且僅有一個直接前趨和一個直接后繼B、線性表的各種基本運算在順序存儲結(jié)構(gòu)上的實現(xiàn)均比在鏈式存儲結(jié)構(gòu)上的實現(xiàn)效率要低C、在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時，移動元素的個數(shù)與該元素位置有關(guān) D、順序存儲的線性表的插入和刪除操作不需要付出很大的代價，因為平均每次操作只有近一半的元素需要移動15、以下說法錯誤的是( )A、求表長、定位這二種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈式存儲結(jié)構(gòu)時實現(xiàn)的效率低B、順序存儲的線性表可以隨機存取C

7、、由于順序存儲要求連續(xù)約存儲區(qū)域所以在存儲管理上不夠靈活D、線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)16、以下說法錯誤的是( )A、線性表的元素可以是各種各樣的，邏輯上相鄰的元素在物理位置上不一定相鄰B、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰C、在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰 D、線性表的鏈式存儲結(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素17、以下說法正確的是()A、在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結(jié)點進行查找任何一個元素B、在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表

8、是隨機存取的存儲結(jié)構(gòu)C、順序存儲方式只能用于存儲線性結(jié)構(gòu)D、順序存儲方式的優(yōu)點是存儲密度大、且插入、刪除運算效率高18、線性表 L=(a1,a2,.,ai,.,an),下列說法正確的是 ( )A、每個元素都有一個直接前驅(qū)和直接后繼B、線性表中至少要有一個元素C、表中諸元素的排列順序必須是由小到大或由大到小的D、除第一個元素和最后一個元素外其余每個元素都有一個數(shù)且僅有一個直接前驅(qū)和直接后繼19、線性表若采用鏈表存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址( )A、必需是聯(lián)系的B 、部分地址必須是連續(xù)的 C 、一定是不連續(xù)的D、連續(xù)不連續(xù)都可以20. 設REAR是指向非空帶頭結(jié)點的循環(huán)單鏈表的尾指針,

9、則刪除表首結(jié)點的操作可表示為 ( )A、 p=rear;rear=rear-next;free(p)B 、 rear=rear-next;free(rear);C、 rear=rear-next-next;free(rear);D、 p=rear-next-next;rear-next-next=p-next;free(p);21、單鏈表中，增加頭結(jié)點的目的是為了( )A、使單鏈表至少有一個結(jié)點B 、標示表結(jié)點中首結(jié)點的位置C、方便運算的實現(xiàn)D 、說明單鏈表是線性表的鏈式存儲實現(xiàn)22、帶頭結(jié)點的單鏈表 Head 為空的判定條件是A、 Head=NullB 、 Head-next=NULL C

10、、 Head-next=Head23、空的單循環(huán)鏈表 L 的尾結(jié)點 *P, 滿足A、 P-next=NULL B 、P=NULL C 、 P-next=LD 、P=L24、算法的時間復雜度是指()A 、執(zhí)行算法程序所需要的時間C、算法程序的長度25、算法的空間復雜度是指()A 、執(zhí)行算法程序所占的存儲空間C、算法程序的長度26、下列敘述中正確的是()A 、線性表是線性結(jié)構(gòu)C、線性鏈表是非線性結(jié)構(gòu)27、數(shù)據(jù)的存儲結(jié)構(gòu)是指()A 、數(shù)據(jù)所占的存儲空間量C、數(shù)據(jù)在計算機中的順序存儲方式28、下列屬于線性數(shù)據(jù)結(jié)構(gòu)的是 ( )A、隊列B 、樹 C 、圖B、算法執(zhí)行過程中所需要的基本運算次數(shù)D、算法程序中

11、的指令條數(shù)B、算法程序中的指令條數(shù)D、算法執(zhí)行過程中所需要的存儲空間B 、棧和隊列是非線性結(jié)構(gòu)D 、二叉樹是線性結(jié)構(gòu)B、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示D、存儲在外存中的數(shù)據(jù)D 、不確定29、單鏈表的每個結(jié)點中包括一個指針next，它指向該結(jié)點的后繼結(jié)點?，F(xiàn)要將指針到指針 P 指向的單鏈表結(jié)點之后，下面的操作序列中哪一個是正確的？( )A、 P-next = q- next; q = p- next; B 、 P- next = q; q- next = p- nextC、q- next = p- next; p- next =q; D、 q = p- next; p- next = q- ne

12、xt30、在一個單鏈表中，若刪除 p 所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行( )A、 p-next=p-next-next;B、 p=p-next; p-next=p-next-next;C、p-next=p-next;D 、 p=p-next-next;31、循環(huán)鏈表指 ( )A、最后一個節(jié)點的指針域總是指向鏈表頭B、可以自由膨脹的鏈表C、鏈表含有指向上一級節(jié)點的指針域D、都不是32、線性表是 ( ) 。A 、一個有限序列，可以為空；B 、一個有限序列，不能為空；C、一個無限序列，可以為空；D 、一個無序序列，不能為空。二、填空題33、下面程序段的時間復雜度是 _ O(n*m) _for(i=0;in

13、;i+) for(j=0;jm;j+)Arrayij=0;34、下面程序段的時間復雜度是 死循環(huán) i=0;while(i=n)i=i*3;35、在下面程序段中， s=s+p 語句的執(zhí)行次數(shù)為 n， p*=j 語句的執(zhí)行次數(shù)為段的時間復雜度為O(n2) 。int i=0,s=0;while (+i=n) int p=1;for (int j=1;jnext!=NULL)_ p=p-next ;j+; return(j); /* 回傳表長 */37、以下為單鏈表的定位運算，分析算法，請在 處填上正確的語句。int locate_lklist(lklist head,datatype x)/* 求表

14、 head 中第一個值等于 x 的結(jié)點的序號。不存在這種結(jié)點時結(jié)果為 0*/ p=head;j=0;while( p-next!=NULL & p-data!=x _) p=p-next;j+;if ( p-data=x ) return( j );else return(0);38、以下為單鏈表按序號查找的運算，分析算法，請在 處填上正確的語句。Pointer find_lklist(lklist head,int i) p=head;j=0;while(_p-next!=NULL & jnext; j+; if(i=j) return(p);else return(NULL);39、以下為

15、單鏈表的建表算法，分析算法，請在 處填上正確的語句。lklist create_lklist()/* 直接實現(xiàn)的建表算法。 */ head=malloc(size);p=head;scanf( “%f”,&x);while(x!= $ ) q=malloc(size);q-data=x;p-next=q;_ p=q ;scanf(“%f”,&x);_ q-next=NULL _; return(head);40、循環(huán)鏈表與單鏈表的區(qū)別僅僅在于其尾結(jié)點的鏈域值不是_空( NULL)_，而是一個指向 _頭指針 _的指針。41、在單鏈表中若在每個結(jié)點中增加一個指針域, 所含指針指向前驅(qū)結(jié)點，這樣構(gòu)成

16、的鏈表中有兩個方向不同的鏈，稱為 _雙向鏈表 _ 。42、一個好的算法應當具有下列好的特性：正確性、(可讀性 )、( 健壯性 )和效率和低存儲需求。43、采用順序存儲結(jié)構(gòu)的線性表，其每個元素占用個單元。第一個元素的地址為，則第i 個元素的存 儲位置為（ N+（i-1）*L ）。44、數(shù)據(jù)元素之間的關(guān)系在計算機中的表示有兩種不同的表示方法，即（ 順序映像 ）和（ 非順序映像 ），從而得到兩種不同的存儲結(jié)構(gòu)（ 順序存儲結(jié)構(gòu) ）和（ 鏈式存儲結(jié)構(gòu) ）。45、帶頭結(jié)點的單鏈表 H 為空的條件是 _H-next=NULL _。不帶頭結(jié)點的單鏈表 H 為空的條件是 H=NULL46、非空單循環(huán)鏈表 L 中

17、 *p 是尾結(jié)點的條件是 _p-next=L 。47、在一個單鏈表中 p所指結(jié)點之后插入一個由指針 s所指結(jié)點，應執(zhí)行 s-next=_ p-next _;和 p-next=_ s_ 的操作。48、在一個單鏈表中 p 所指結(jié)點之前插入一個由指針 s 所指結(jié)點，可依次執(zhí)行以下操作： s-next=_ p-next _; p-next=s; t=p-data; p-data=_s -data_; s-data=_ t_;三、判斷題49、在順序表中取出第 i 個元素所花費的時間與 i 成正比 （ X ）50、線性表的長度是線性表所占用的存儲空間的大?。?X ）51、已知指針 P 指向鏈表 L中某結(jié)點，執(zhí)行語句 P=P-next 不會刪除該鏈表中結(jié)點 （ ）52、在帶頭結(jié)點的單循環(huán)鏈表中，任一結(jié)點的后繼指針均不空（ ）53、線性表采用鏈表方式和順序表方式存儲，執(zhí)行插入和刪除運算的時間復雜度都是O（N），因而兩種存儲方式的插入、刪除運算所花費的時間相同 （ X ）四、算法設計帶頭結(jié)點的單鏈表，其長度存放在頭結(jié)點的數(shù)據(jù)域中，設計一算法求 倒數(shù)第 k 個結(jié)點的值，并且刪除該 結(jié)點。要求：（ 1）用類 C 語言描述該單鏈表（ 3）寫出解決該問題的類 C語言算法過程類型定義略算法思路：1） 合法性檢查，若不合法，返回 error若合法： 2）遍歷鏈表查找倒數(shù)第 k 個結(jié)點的前驅(qū)結(jié)點3） 將