寧波財經(jīng)學(xué)院數(shù)據(jù)結(jié)構(gòu)期末考試題一、選擇題1、評價一個算法時間性能的主要標(biāo)準(zhǔn)是(D)。A、算法易于調(diào)試B、算法易于理解C、算法的穩(wěn)定性和正確性D、算法的時間復(fù)雜度2、計算機(jī)算法具備有輸入、輸出、（B）等五個特性。A、可行性、可移植性和可擴(kuò)充性B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性3、帶頭結(jié)點的單鏈表head為空的判定條件是（B）。A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL4、以下關(guān)于線性表的說法不正確的是(C)。A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B、線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。C、線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D、存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。5、在順序表中，只要知道(D)，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A、基地址B、結(jié)點大小C、向量大小D、基地址和結(jié)點大小6、(C)運(yùn)算中，使用順序表比鏈表好。A、插入B、刪除C、根據(jù)序號查找D、根據(jù)元素值查找7、一個長度為n的順序表中，向第i個元素之前插入一個新元素時，需要向后移動（B）個元素。A、n-iB、n-i+1C、n-i-1D、i8、(D)適合作為經(jīng)常在首尾兩端操作線性表的存儲結(jié)構(gòu)。A、順序表B、單鏈表C、循環(huán)鏈表D、雙向鏈表9、棧和隊列的共同點是（C）A、都是先進(jìn)后出B、都是先進(jìn)先出C、只允許在端點處插入和刪除元素D、沒有共同點10、一個隊列的入列序列是1234，則隊列的輸出序列是(B)。A、4321B、1234C、1432D、324111、隊列與一般的線性表的區(qū)別在于(D)。A、數(shù)據(jù)元素的類型不同B、運(yùn)算是否受限制C、數(shù)據(jù)元素的個數(shù)不同D、邏輯結(jié)構(gòu)不同12、“假上溢”現(xiàn)象會出現(xiàn)在(C)中。A、循環(huán)隊列B、隊列C、鏈隊列D、順序隊列二、填空題1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為(集合)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)。2、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線性結(jié)構(gòu)、(樹形結(jié)構(gòu))和圖狀結(jié)構(gòu)。3、下面程序段的時間復(fù)雜度是(O（n）)。i=s=0;while(s<n){i++;s++;;}4、樹型結(jié)構(gòu)和圖形結(jié)構(gòu)合稱是(非線性結(jié)構(gòu))。5、在長度為n的順序存儲線性表的第i個元素（1≤i≤n）之前插入一個元素時，需要向后移動(n-i+1)個元素。6、在一個長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，需要向前移動(n-i)個元素。7、指針p指向非空循環(huán)單鏈表head的尾結(jié)點，則p滿足(p->next=head)。8、已知L是帶頭結(jié)點的非空單鏈表，且P結(jié)點既不是第一個數(shù)據(jù)結(jié)點，也不是最后一個結(jié)點，試從下列提供的答案中選擇合適的語句序列，實現(xiàn)刪除P結(jié)點的直接后繼結(jié)點的語句序列是(⑥①⑨)。①P->next=P->next->next;②P=P->next->next;③while(P->next!=Q)P=P->next;④while(P->next->next=Q)P=P->next;⑤Q=P;⑥Q=P->next;⑦P=L;⑧L=L->next;⑨free(Q);9、在線性結(jié)構(gòu)中，第一個結(jié)點(無)前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點。10、單鏈表是線性表的(鏈?zhǔn)?存儲表示。11、棧是限定僅在(表尾)進(jìn)行插入或刪除操作的線性表。12、在棧頂指針為HS的鏈棧中，判定?？盏臈l件是(HS=NULL)。13、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對輸入序列a、b、c、d、e進(jìn)行一系列棧操作SSXSXSSXXX后，得到的輸出序列為(bceda)。14、設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧S，一個元素出棧后即進(jìn)入隊列若這6個元素出隊列的順序是b、d、c、f、e、a，則棧S的容量至少應(yīng)該是(3)。三、算法填空1、已知一個順序表中的元素按關(guān)鍵字值非遞減有序，下列算法刪除順序表中關(guān)鍵字相同的多余元素，使每個關(guān)鍵字不同的元素在表中只保留一個。voidpurge_sq(SqList&la){//刪除順序表la中關(guān)鍵字相同的多余元素，即使操作之后的順序表中只保留操作之前表中所有按關(guān)鍵字值都不相同的元素k=-1;//k指示新表的表尾for(i=0;i<La.length;++i)//順序考察表中每個元素{j=0;while(j<=k&&la.elem[j]!=la.elem[i])++j;//在新表中查詢是否存在和la.elem[i]相同的元素if(k==-1||j>k)//k=-1表明當(dāng)前考察的是第一個元素la.elem[++k]=la.elem[i];}//forla.length=k+1;//修改表長}//purge_sq2、一個頭指針為head的單鏈表，其中每個結(jié)點存放一個整數(shù)，以下算法將其拆分為兩個單鏈表head1使head1中僅含有正整數(shù)，head2中僅含有負(fù)整數(shù)。voidseparate(LinkList&head,LinkList&head1,LinkList&head2){//將頭指針為head的單鏈表（帶頭結(jié)點）拆分為兩個單鏈表head1和head2，//使head1中僅含有正整數(shù)，head2中僅含有負(fù)整數(shù)head1=(LinkList)malloc(sizeof(Lnode));head1->next=NULL;head2=(LinkList)malloc(sizeof(Lnode));head2->next=NULL;p=head->next;