寧波財(cái)經(jīng)學(xué)院數(shù)據(jù)結(jié)構(gòu)期末考試題

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