數(shù)據(jù)結(jié)構(gòu)期末考試(題集)

數(shù)據(jù)結(jié)構(gòu)期末考試(題集)數(shù)據(jù)結(jié)構(gòu)期末考試(題集)數(shù)據(jù)結(jié)構(gòu)期末考試(題集)資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)期末考試(題集)版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：數(shù)據(jù)結(jié)構(gòu)的基本概念選擇題順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的。A．線性結(jié)構(gòu) B．非線性結(jié)構(gòu) C．存儲位置 D．指針假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)，子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承，則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（）。A．樹 B．圖 C．線性表 D．集合計算機(jī)所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指（）。A．?dāng)?shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系 B．元素和元素之間存在某種關(guān)系C．元素內(nèi)部具有某種結(jié)構(gòu) D．?dāng)?shù)據(jù)項和數(shù)據(jù)項之間存在某種關(guān)系在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的（）。A．樹 B．圖 C．線性表 D．集合在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，還要存儲（）。A．?dāng)?shù)據(jù)的處理方法 B．?dāng)?shù)據(jù)元素的類型C．?dāng)?shù)據(jù)元素之間的關(guān)系 D．?dāng)?shù)據(jù)的存儲方法在鏈接存儲結(jié)構(gòu)中，要求（）。A．每個結(jié)點占用一片連續(xù)的存儲區(qū)域 B．所有結(jié)點占用一片連續(xù)的存儲區(qū)域C．結(jié)點的最后一個域是指針類型 D．每個結(jié)點有多少個后繼就設(shè)多少個指針下列說法不正確的是（）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位 B．?dāng)?shù)據(jù)項是數(shù)據(jù)中不可分割的最小單位C．?dāng)?shù)據(jù)可由若干個數(shù)據(jù)項構(gòu)成 D．?dāng)?shù)據(jù)元素可由若干個數(shù)據(jù)項構(gòu)成以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。A．循環(huán)隊列 B．鏈表 C．散列表 D．棧以下術(shù)語屬于邏輯結(jié)構(gòu)的是（）。A．順序表 B．哈希表 C．有序表 D．單鏈表可以用（）定義一個完整的數(shù)據(jù)結(jié)構(gòu)。A．?dāng)?shù)據(jù)元素 B．?dāng)?shù)據(jù)對象 C．?dāng)?shù)據(jù)關(guān)系 D．抽象數(shù)據(jù)類型對于數(shù)據(jù)結(jié)構(gòu)的描述，下列說法中不正確的是（）。A．相同的邏輯結(jié)構(gòu)對應(yīng)的存儲結(jié)構(gòu)也必相同B．?dāng)?shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本操作三方面組成C．?dāng)?shù)據(jù)結(jié)構(gòu)基本操作的實現(xiàn)與存儲結(jié)構(gòu)有關(guān)D．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的機(jī)內(nèi)實現(xiàn)以下關(guān)于鏈接存儲結(jié)構(gòu)的敘述中，（）是不正確的。A．結(jié)點除數(shù)據(jù)信息外還包括指針域，因此存儲密度小于順序存儲結(jié)構(gòu)B．邏輯上相鄰的結(jié)點物理上不一定相鄰C．可以通過計算得到第i個結(jié)點的存儲地址D．插入和刪除操作方便，不必移動結(jié)點可以用（）、數(shù)據(jù)關(guān)系和基本操作定義一個完整的抽象數(shù)據(jù)類型。A．?dāng)?shù)據(jù)元素 B．?dāng)?shù)據(jù)對象 C．原子類型 D．存儲結(jié)構(gòu)應(yīng)用題設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D={1，2，3，4，5，6}，R={(1，2)，(2，3)，(2，4)，(3，4)，(3，5)，(3，6)，(4，5)，(4，6)}。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別。說明數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系。抽象數(shù)據(jù)類型的主要特點是什么數(shù)據(jù)類型和抽象數(shù)據(jù)類型的關(guān)系如何使用抽象數(shù)據(jù)類型的主要好處是什么

算法和算法分析選擇題算法指的是（）。A．對特定問題求解步驟的一種描述，是指令的有限序列B．計算機(jī)程序C．解決問題的計算方法D．?dāng)?shù)據(jù)處理下面（）不是算法所必須具備的特性。A．有窮性 B．確切性 C．高效性 D．可行性算法必須具備輸入、輸出和（）等特性。A．可行性、可移植性和可擴(kuò)充性 B．可行性、確定性和有窮性C．確定性、穩(wěn)定性和有窮性 D．易讀性、穩(wěn)定性和健壯性算法應(yīng)該具有確定性、可行性和有窮性，其中有窮性是指（）。A．算法在有窮的時間內(nèi)終止 B．輸入是有窮的C．輸出是有窮的 D．描述步驟是有窮的當(dāng)輸入非法錯誤時，一個“好”的算法會進(jìn)行適當(dāng)處理，而不會產(chǎn)生難以理解的輸出結(jié)果，這稱為算法的（）。A．可讀性 B．健壯性 C．正確性 D．有窮性算法分析的目的是（），算法分析的兩個主要方面是（）。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中輸入和輸出的關(guān)系C．分析算法的效率以求改進(jìn) D．分析算法的易讀性和文檔性E．空間性能和時間性能 F．正確性和簡明性G．可讀性和文檔性 H．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性算法的時間復(fù)雜度與（）有關(guān)。A．問題規(guī)模 B．計算機(jī)硬件性能C．編譯程序的質(zhì)量 D．程序設(shè)計語言算法的時間復(fù)雜度與（）有關(guān)。A．問題規(guī)模 B．待處理數(shù)據(jù)的初態(tài)C．算法的易讀性 D．A和B某算法的時間復(fù)雜度是○(n2)，表明該算法（）。A．問題規(guī)模是n2 B．執(zhí)行時間等于n2C．執(zhí)行時間與n2成正比 D．問題規(guī)模與n2成正比下面說法錯誤的是（）。①算法原地工作的含義是指示不需要如何額外的輔助空間②在相同的規(guī)模n下，復(fù)雜度○(n)的算法在時間上總是優(yōu)于復(fù)雜度○(2n)的算法③所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界④同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低算法for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) if(a[j]>a[j+1])a[j]與a[j+1]交換；其中n為正整數(shù)，則最后一行語句的頻度（執(zhí)行次數(shù)）在最壞情況下是（）。A．○(n) B．○(nlog2n) C．○(n3) D．○(n2)算法的時間復(fù)雜度屬于一種（）。A．事前統(tǒng)計的方法 B．事先分析估算的方法C．事后統(tǒng)計的方法 D．事后分析估算的方法設(shè)某算法完成對n個元素進(jìn)行處理，所需的時間是T(n)=100nlog2n+200n+500，則該算法的時間復(fù)雜度是（）。A．○(1) B．○(n) C．○(nlog2n) D．○(nlog2n+n)假設(shè)時間復(fù)雜度為○(n2)的算法在有200個元素的數(shù)組上運行需要3.1ms，則在有400個元素的數(shù)組上運行需要（）ms。A．3.1 B．6.2 C．12.4 D．x（無法確定）下列程序段加下劃線的語句執(zhí)行（）次。for(m=0,i=1;i<=1;i++) for(j=1;j<=2*i;j++) m=m+1；A．n2 B．3n C．n(n+1) D．n3應(yīng)用題將下列函數(shù)按它們的n→∞時的無窮大階數(shù)，從小到大排列。n，n-n3-7n5，nlog2n，2n/2，n3，log2n，n1/2+log2n，(3/2)n，n!，n2+log2n分析以下程序段，并用大○記號表示其執(zhí)行時間。i=1;k=0;while(i<n-1){ k=k+10*i; i++;}i=1;j=0;while(i+j<=n) if(i>j)j++; elsei++;for(i=1;i<=n;i++)for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++;i=1;k=0;do{ k=k+10*i; i++;}while(i<=n)y=0;while((y+1)*(y+1)<=n) y=y+1for(i=0;i<n;i++)for(j=0;j<m;j++) a[i][j]=0;有實現(xiàn)同一功能的兩個算法A1和A2，其中A1的時間復(fù)雜度為T1=○(2n)，A2的時間復(fù)雜度為T2=○(n2)，僅就時間復(fù)雜度而言，請具體分析這兩個算法哪一個好。綜合應(yīng)用題設(shè)n是偶數(shù)，且有程序段：for(i=1;i<=n;i++) if(2*i<=n) for(j=2*I;j<=n;j++) y=y+i*j;則語句y=y+i*j的執(zhí)行次數(shù)是多少？要求列出計算公式。斐波那契數(shù)列Fn定義如下：F0=0，F(xiàn)1=1，…，F(xiàn)n=Fn-1+Fn-2 n=2，3，…請就此斐波那契數(shù)列，回答下列問題。① 在遞歸計算Fn的時候，需要對較小的Fn-1，F(xiàn)n-2，…，F(xiàn)1，F(xiàn)0精確計算多少次？

用大○表示法給出遞歸計算時遞歸函數(shù)的時間復(fù)雜度是多少？

運算是數(shù)據(jù)結(jié)構(gòu)的一個重要方面。舉例說明兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲方式完全相同，只是對于運算的定義不同，因而具有不同的特性，則這兩個數(shù)據(jù)結(jié)構(gòu)是不同的。針對給定的實際問題建立數(shù)據(jù)結(jié)構(gòu)時，應(yīng)從哪些方面考慮。

線性表的邏輯結(jié)構(gòu)選擇題線性表是具有n個（）的有限序列。A．?dāng)?shù)據(jù) B．字符 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)項線性表是（）。A．一個有限序列，可以為空 B．一個有限序列，不能為空C．一個無限序列，可以為空 D．一個無限序列，不能為空關(guān)于線性表，下列說法中正確的是（）。A．線性表中每個元素都有一個直接前驅(qū)和一個直接后繼B．線性表中的數(shù)據(jù)元素可以具有不同的數(shù)據(jù)類型C．線性表中數(shù)據(jù)元素的類型是確定的D．線性表中任意一對相鄰的數(shù)據(jù)元素之間存在序偶關(guān)系（）是一個線性表。A．由n個實數(shù)組成的集合 B．由所有實數(shù)組成的集合C．由所有整數(shù)組成的序列 D．由n個字符組成的序列

順序線性表選擇題已知一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第9個元素的地址為144，則第一個元素的地址是（）。A．108 B．180 C．176 D．112在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復(fù)雜度為（）。A．○(0) B．○(1) C．○(n) D．○(n2)在一個長度為n的線性表的第i（1≤i≤n+1）個元素之前插入一個元素，需向后移動（）個元素，刪除第i（1≤i≤n）個元素時，需向前移動（）個元素。A．n-i B．n-i+1 C．n-i D．n-i+1線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取順序存儲結(jié)構(gòu)的優(yōu)點是（）。A．存儲密度大 B．插入運算方便C．刪除運算方便 D．可方便地用于各種邏輯結(jié)構(gòu)的存儲表示n個結(jié)點的線性表采用數(shù)組實現(xiàn)，算法的時間復(fù)雜度是○(1)的操作是（）。A．訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）B．在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）C．刪除第i個結(jié)點（1≤i≤n）D．以上都不對對于順序存儲的線性表，訪問某個元素和增加一個元素的時間復(fù)雜度為（）。A．○(n)、○(n) B．○(n)、○(1) C．○(1)、○(n) D．○(1)、○(1)順序表的插入算法中，當(dāng)n個空間已滿時，可再申請增加分配m個空間，若申請失敗，則說明系統(tǒng)沒有（）可分配的存儲空間。A．m個 B．m個連續(xù)的 C．n+m個 D．n+m個連續(xù)的應(yīng)用題設(shè)A是一個線性表（a1，a2，…，an），采用順序存儲結(jié)構(gòu)，則在等概論的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai與ai+1之間(1≤i≤n)的概率為（n-i）/（n（n-1）/2），則平均每插入一個元素所移動的元素個數(shù)是多少？設(shè)n表示線性表中的元素個數(shù)，E表示存儲數(shù)據(jù)元素所需要的存儲單元大小，D表示可以在數(shù)組中存儲線性表的最大元素個數(shù)（D≥n），則使用順序存儲方式存儲線性表需要多少存儲空間？

在什么情況下線性表使用順序存儲比較好？算法設(shè)計題試以順序表作存儲結(jié)構(gòu)，實現(xiàn)線性表就地逆置。設(shè)計算法判斷給定字符串是否是回文。所謂回文是正讀和反讀均相同的字符串，例如abcba或abba是回文，而abcda不是回文。設(shè)計一個時間復(fù)雜度為○(n)的算法，實現(xiàn)將數(shù)組A[n]中所有元素循環(huán)左移k個位置。已知數(shù)組A[n]中的元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復(fù)雜度為○(n)。假定數(shù)組中有多個零元素，設(shè)計算法將數(shù)組中所有非零元素移到數(shù)組的前端。順序存儲的線性表A，其數(shù)據(jù)元素為整型，設(shè)計算法將A拆成B和C兩個表，使A中值大于0的元素存入表B，值小于0的元素存入表C，要求B和C不另外設(shè)置存儲空間而利用A的空間。已知順序表L中的元素遞增有序排列，設(shè)計算法將元素x插入到表L中并保持表L仍遞增有序。設(shè)計一個高效算法，在順序表中刪除所有元素值為x的元素，要求空間復(fù)雜度為○(1)。設(shè)計算法實現(xiàn)從順序表L中刪除所有值在x和y之間的所有元素，要求時間性能復(fù)雜度為○(n)，空間性能為○(1)。設(shè)計算法刪除順序表中重復(fù)的元素，要求算法移動元素的次數(shù)較少并使剩余元素間的相對次序保持不變。給定n個記錄的有序序列A[n]和m個記錄的有序序列B[m]，將它們歸并為一個有序序列，存放在C[n+m]中，試寫出這一算法（假設(shè)A、B和C均為升序序列）。

線性鏈表選擇題線性表的鏈接存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取線性表采用鏈接存儲時，其（）。A．地址必須是連續(xù)的 B．部分地址必須是連續(xù)的C．地址一定是不連續(xù)的 D．地址連續(xù)與否均可以鏈表不具有的特點是（）。A．可隨機(jī)訪問任一元素 B．插入、刪除不需要移動元素C．不必事先估計存儲空間 D．所需空間與線性表長度成正比在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是（）。A．○(1) B．○(n) C．○(n2) D．○(nlog2n1)對于n個元素組成的線性表，建立一個單鏈表的時間復(fù)雜度是（）。A．○(1) B．○(n) C．○(n2) D．○(nlog2n1)對于n個元素組成的線性表，建立一個有序單鏈表的時間復(fù)雜度是（）。A．○(1) B．○(n) C．○(n2) D．○(nlog2n1)在單鏈表中刪除指針p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（）。A．p->next=p->next->next B．p->next=p->nextC．p=p->next->next D．p=p->next;p->next=p->next->next在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入s所指結(jié)點，則執(zhí)行（）操作。A．s->next=p->next;p->next=s; B．q->next=s;s->next=p;C．p->next=s->next;s->next=p; D．p->next=s;s->next=q在一個長度為n（n>1）的帶頭結(jié)點的單鏈表h上，另設(shè)有尾指針r指向尾結(jié)點，執(zhí)行（）操作與鏈表的長度有關(guān)。A．刪除單鏈表中的第一個元素B．刪除單鏈表中的最后一個元素C．在單鏈表第一個元素前插入一個新元素D．在單鏈表的最后一個元素后插入一個新元素在單鏈表中附加頭結(jié)點的目的是為了（）。A．保證單鏈表中至少有一個結(jié)點 B．標(biāo)識單鏈表中首結(jié)點的位置C．方便運算的實現(xiàn) D．說明單鏈表是線性表的鏈?zhǔn)酱鎯㈤L度為n個單鏈表鏈接在長度為m的單鏈表之后的算法，其時間復(fù)雜度是（）。A．○(1) B．○(n) C．○(m) D．○(n+m)循環(huán)單鏈表的主要優(yōu)點是（）。A．不再需要頭指針了B．從表中任一結(jié)點出發(fā)都能掃描到整個鏈表C．已知某個結(jié)點的位置后，能夠容易找到它的直接前驅(qū)D．在進(jìn)行插入、刪除操作時，能更好地保證鏈表不斷開將線性表（a1，a2，…，an）組織為一個帶頭結(jié)點的循環(huán)單鏈表，設(shè)H為鏈表的頭指針，則鏈表中最后一個結(jié)點的指針域中存放的是（）。A．變量H的地址 B．變量H的值C．元素a1的地址 D．空指針非空的循環(huán)單鏈表L的尾結(jié)點p滿足（）。A．p=NULL B．p->next=NULL C．p->next=L D．p=L若要在○(1)的時間內(nèi)實現(xiàn)兩個循環(huán)單鏈表的首尾相接，則兩個循環(huán)單鏈表應(yīng)各設(shè)一個指針，分別指向（）。A．各自的頭結(jié)點 B．各自的尾結(jié)點C．各自的第一個元素結(jié)點 D．一個表的頭結(jié)點，一個表的尾結(jié)點設(shè)線性表非空，（）可以在○(1)的時間內(nèi)在表尾插入一個新結(jié)點。A．帶頭結(jié)點的單鏈表，有一個鏈表指針指向頭結(jié)點B．帶頭結(jié)點的循環(huán)單鏈表，有一個鏈表指針指向頭結(jié)點C．不帶頭結(jié)點的單鏈表，有一個鏈表指針指向表的第一個結(jié)點D．不帶頭結(jié)點的循環(huán)單鏈表，有一個鏈表指針指向表中某個結(jié)點（除第一個結(jié)點外）設(shè)指針rear指向帶頭結(jié)點的循環(huán)單鏈表的尾指針，若要刪除鏈表的第一個元素結(jié)點，正確的操作是（）。A．s=rear;rear=rear->next;B．rear=rear->next;C．rear=rear->next->next;D．s=rear->next->next;rear->next->next=s->next;設(shè)有兩個長度為n個單鏈表，以h1為頭指針的鏈表是非循環(huán)的，以h2為尾指針的鏈表是循環(huán)的，則（）。A．在兩個鏈表上刪除第一個結(jié)點的操作，其時間復(fù)雜度均為○(1)B．在兩個鏈表的表尾插入一個結(jié)點的操作，其時間復(fù)雜度均為○(n)C．循環(huán)鏈表要比非循環(huán)鏈表占用更多的存儲空間D．循環(huán)鏈表要比非循環(huán)鏈表占用更少的存儲空間使用雙鏈表存儲線性表，其優(yōu)點是可以（）。A．提高查找速度 B．更方便數(shù)據(jù)的插入和刪除C．節(jié)約存儲空間 D．很快回收存儲空間與單鏈表相比，雙鏈表的優(yōu)點之一是（）。A．插入和刪除操作更簡單 B．可以進(jìn)行隨機(jī)訪問C．可以省略表頭指針或表尾指針 D．訪問其后相鄰結(jié)點更靈活帶頭結(jié)點的循環(huán)雙鏈表L為空表的條件是（）。A．L->next->prior=NULL B．L->prior=LC．L->next=L D．B和C都對在循環(huán)雙鏈表的p所指結(jié)點后插入s所指結(jié)點的操作是（）。A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;在雙鏈表中指針pa所指結(jié)點后面插入pb所指結(jié)點，執(zhí)行的語句序列是（）。①pb->next=pa->next; ②pb->prior=pa;③pa->next=pb; ④pa->next->prior=pb;A．①②③④ B．④③②① C．③④①② D．①④③②在一個雙鏈表中，刪除結(jié)點p的操作是（）。A．p->prior->next=p->next;p->next->prior=p->prior;B．p->prior=p->prior->prior;p->prior->prior=p;C．p->next->prior=p;p->next=p->next->next;D．p->next=p->prior->prior;p->prior=p->prior->prior;應(yīng)用題單鏈表設(shè)置頭結(jié)點的作用是什么？線性表的順序存儲結(jié)構(gòu)具有三個弱點：其一，插入或刪除操作需要移動大量元素；其二，由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴(kuò)充。試問，線性表的鏈接存儲結(jié)構(gòu)是否能夠克服上述三個弱點？

若頻繁地對一個線性表進(jìn)行插入和刪除操作，該線性表采用什么存儲結(jié)構(gòu)比較好？設(shè)n表示線性表中的元素個數(shù)，P表示指針?biāo)璧拇鎯卧笮。珽表示存儲數(shù)據(jù)元素所需的存儲單元大小，則使用單鏈表存儲方式存儲該線性表需要多少存儲空間（不考慮頭結(jié)點）算法設(shè)計題設(shè)計算法依次打印單鏈表中每個結(jié)點的數(shù)據(jù)信息。求單鏈表的長度。設(shè)計算法將值為x的結(jié)點插入到不帶頭結(jié)點的單鏈表L中值為k的結(jié)點之前，若找不到值為k的結(jié)點，則將x插入到鏈表的末尾。判斷非空單鏈表是否遞增有序。已知非空線性鏈表由list指出，結(jié)點結(jié)構(gòu)為（data，link）。請編寫算法，將鏈表中數(shù)據(jù)域最小的結(jié)點移到鏈表的最前面。要求：不得額外申請新的結(jié)點。給定一個帶頭結(jié)點的單鏈表，設(shè)head為頭指針，設(shè)計算法按遞增次序輸出單鏈表中各結(jié)點的數(shù)據(jù)元素，并釋放結(jié)點所占的存儲空間（要求：不允許使用數(shù)組作輔助空間）。已知非空線性鏈表由list指出，設(shè)計算法交換p所指結(jié)點與其后續(xù)結(jié)點在鏈表中的位置（設(shè)p所指結(jié)點不是鏈表的最后一個結(jié)點）。設(shè)計算法實現(xiàn)將單鏈表就地逆置。頭插法建立單鏈表。尾插法建立單鏈表復(fù)制一個單鏈表。設(shè)計算法實現(xiàn)將單鏈表就地逆置。在一個有序單鏈表（假設(shè)從小到大排列）中插入一個元素值為x的結(jié)點，使得插入后單鏈表仍然有序。設(shè)單鏈表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點。已知單鏈表中各結(jié)點的元素值為整型且遞增有序，設(shè)計算法刪除表中大于mink且小于maxk的所有元素，并釋放被刪結(jié)點的存儲空間。有兩個整數(shù)序列A=(a1，a2，…，am)和B=(b1，b2，…，bn)已經(jīng)存入兩個單鏈表中，設(shè)計算法判斷序列B是否是序列A的子序列。設(shè)線性表C=(a1，b1，a2，b2，…，an，bn)采用帶頭結(jié)點的單鏈表存儲，設(shè)計算法將表C拆分為兩個線性表A和B，使得A=(a1，a2，…，an)，B=(b1，b2，…，bn)。有兩個遞增有序的單鏈表la和lb，設(shè)計算法將這兩個單鏈表合并為一個有序鏈表。有兩個有序的單鏈表，一個表為升序，另一個表為降序，設(shè)計算法將這兩個鏈表合并為一個有序鏈表。已知單鏈表A和B的數(shù)據(jù)（設(shè)為整型）遞增有序，設(shè)計算法利用原有結(jié)點，將表A中與表B具有相同值的結(jié)點刪除，將表B中與原表A不同值的結(jié)點存入表A中，并保持表A的遞增有序。設(shè)計算法將循環(huán)單鏈表就地逆置。已知L為單鏈表的頭結(jié)點地址，表中共有m（m＞3）個結(jié)點，從表中第i個（1＜i＜m）結(jié)點起到第m個結(jié)點構(gòu)成一個部分循環(huán)鏈表。設(shè)計算法將這部分循環(huán)鏈表中所有結(jié)點順序完全倒置。假設(shè)在長度大于1的循環(huán)單鏈表中，即無頭結(jié)點也無頭指針，s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點s的前驅(qū)結(jié)點。設(shè)循環(huán)單鏈表L1，對其遍歷的結(jié)果是：x1，x2，x3，…，xn-1，xn。請將該循環(huán)鏈表拆成兩個循環(huán)單鏈表L1和L2，使得L1中含有原L1表中序號為奇數(shù)的結(jié)點且遍歷結(jié)果為：x1，x3，…；L2中含有原L1表中序號為偶數(shù)的結(jié)且遍歷結(jié)果為：…，x4，x2。已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個循環(huán)單鏈表，使每個循環(huán)鏈表中只含同一類字符。有兩個循環(huán)鏈表tail1和tail2（tail1和tail2分別指向循環(huán)鏈表的尾指針），編寫算法將循環(huán)鏈表tail2鏈接到循環(huán)鏈表tail1之后，并使鏈接后的鏈表仍是循環(huán)鏈表。已知p指向循環(huán)單鏈表最后一個結(jié)點的指針，試編寫只包含一個循環(huán)的算法，將線性表（a1，a2，…，an-1，an，）改造成（a1，a2，…，an-1，an，an-1，…，a2，a1）。判斷帶頭結(jié)點的循環(huán)雙鏈表是否對稱。設(shè)計算法實現(xiàn)雙鏈表中第i個結(jié)點的前面插入一個值為x的結(jié)點。已知非空循環(huán)雙鏈表head的存儲結(jié)構(gòu)為：StructDNode{ TEleminfo; StructDNode*left; StructDNode*right;};設(shè)計算法實現(xiàn)從鏈表中刪除指針p所指結(jié)點的前驅(qū)結(jié)點（假設(shè)該結(jié)點存在）。已知非空雙鏈表由d指出，結(jié)點結(jié)構(gòu)為（priordatanext），請設(shè)計算法將鏈表中數(shù)據(jù)值最大（假定唯一）的那個結(jié)點移至鏈表的最前面。要求不得額外申請新的雙鏈表結(jié)點。設(shè)計算法實現(xiàn)將雙鏈表中結(jié)點p與其后繼結(jié)點互換位置。設(shè)有一個雙鏈表，每個結(jié)點中除了有prior、data和next三個域外，還有一個訪問頻度域freq，在鏈表被起用之前，其值均初始化為零，每當(dāng)在雙鏈表上進(jìn)行一次LOCATE運算時，令元素值為x的結(jié)點中freq域的值增1，并使此鏈表中結(jié)點保持頻度遞減的順序排列，以便使頻繁訪問的結(jié)點總是靠近表頭。編寫算法實現(xiàn)符合上述要求的LOCATE算法。

靜態(tài)鏈表選擇題靜態(tài)鏈表中指針表示的是（）。A．下一結(jié)點在內(nèi)存中的地址 B．下一元素在數(shù)組中的下標(biāo)C．左、右孩子的存儲位置 D．左、右孩子的地址以下說法錯誤的是（）。①靜態(tài)鏈表既有順序存儲的優(yōu)點又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)②靜態(tài)鏈表中能容納的元素個數(shù)在定義表時必須是確定的③靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動A．①，② B．① C．①，②，③ D．②用數(shù)組r存儲靜態(tài)鏈表，結(jié)點的next域指向后繼，工作指針j指向鏈中某結(jié)點，使j沿鏈移動的操作為（）。A．j=r[j].next B．j=j+1C．j=j->next D．j=r[j]->next線性表的靜態(tài)鏈表存儲與順序存儲相比，優(yōu)點是（）。A．所有基本操作的算法實現(xiàn)簡單 B．便于隨機(jī)存取C．便于插入和刪除 D．便于利用零散的存儲空間下圖所示數(shù)組中以靜態(tài)鏈表形式存儲了一個線性表，設(shè)頭指針為a[0].link，則該線性表的元素依次為（）。下標(biāo)012345678data606340457425link4376201A．60，63，40，45，74，25 B．45，63，25，60，40，74C．74，25，45，60，40，63 D．25，45，60，40，63，74

線性表綜合選擇題下面關(guān)于線性表的敘述中，錯誤的是（）。A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B．線性表采用順序存儲，便于進(jìn)行插入和刪除操作C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元D．線性表采用鏈接存儲，便于插入和刪除操作若某線性表中最常用的操作是取第i個元素和找第i個元素的前驅(qū)，則采用（）存儲方法最節(jié)約時間。A．順序表 B．單鏈表 C．雙鏈表 D．循環(huán)單鏈表若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，則采用（）存儲方法最節(jié)約時間。A．單鏈表 B．循環(huán)雙鏈表C．循環(huán)單鏈表 D．帶尾指針的循環(huán)單鏈表設(shè)線性表有n個元素，以下操作中，（）在順序表上實現(xiàn)比在鏈表上實現(xiàn)的效率更高。A．輸出第i（1≤i≤n）個元素值B．交換第1個和第2個元素的值C．順序輸出所有n個元素D．查找與給定值x相等的元素在線性表中的序號如果對于具有n（n＞1）個元素的線性表的基本操作有4種：刪除第一個元素；刪除最后一個元素；在第一個元素前插入新元素；在最后一個元素的后面插入新元素。則最好使用（）。A．只設(shè)尾指針的循環(huán)單鏈表B．只設(shè)尾指針的非循環(huán)單鏈表C．只設(shè)頭指針的循環(huán)雙鏈表D．同時設(shè)置頭指針和尾指針的循環(huán)單鏈表應(yīng)用題請比較線性表的兩種基本的存儲結(jié)構(gòu)——順序表和單鏈表。舉例說明對相同的邏輯結(jié)構(gòu)，同一種運算在不同的存儲方式下實現(xiàn)，算法的效率不同。如果某線性表中數(shù)據(jù)元素的類型不一致，但是希望能根據(jù)下標(biāo)隨機(jī)存取每個元素，請為這個線性表設(shè)計一個合適的存儲結(jié)構(gòu)。線性鏈表有哪幾種常見的變形各有何特點

算法設(shè)計題用順序表表示集合，設(shè)計算法實現(xiàn)集合的求交集運算。用順序表表示集合，設(shè)計算法實現(xiàn)集合的求并集運算。用順序表表示集合，設(shè)計算法實現(xiàn)集合的求差集運算，要求不另外開辟空間。假定以有序表表示集合，設(shè)計算法判斷兩個給定集合是否相等。設(shè)兩個單鏈表L1和L2分別表示兩個集合，設(shè)計算法判斷L1是否是L2的子集。已知兩個不帶頭結(jié)點的單鏈表A和B分別表示兩個集合，并且其元素值遞增有序，求A、B的交集C，并以同樣的遞增形式存儲，要求盡可能節(jié)省時間。在某商店的倉庫中，對電視機(jī)按其價格從低到高建立一個單鏈表，鏈表的每個結(jié)點指出同樣價格的電視機(jī)的臺數(shù)。現(xiàn)有m臺價格為n元的電視機(jī)入庫，請編寫算法完成倉庫的進(jìn)貨管理。從鍵盤輸入n個英語單詞，輸入格式為n，w1，w2，…，wn，其中n表示隨后輸入英語單詞個數(shù)，試編寫算法建立一個單鏈表，要求：①如果單詞重復(fù)出現(xiàn)，則只在鏈表上只保留一個；②統(tǒng)計單詞重復(fù)出現(xiàn)的次數(shù)，然后輸出次數(shù)最多的前k（k＜n）個單詞。一元稀疏多項式可以采用單鏈表形式存儲，設(shè)計算法完成A(x)+B(x)，其中A(x)和B(x)均為稀疏的一元多項式，要求利用原表的存儲空間。假設(shè)用不帶頭結(jié)點的單鏈表表示八進(jìn)制數(shù)，例如，八進(jìn)制數(shù)536可以表示成三個結(jié)點的鏈表。要求寫一個函數(shù)Add，該函數(shù)有兩個參數(shù)P和Q，分別指向表示八進(jìn)制數(shù)的鏈表，執(zhí)行函數(shù)調(diào)用Add(P,Q)后，將返回表示八進(jìn)制數(shù)P加八進(jìn)制數(shù)Q所得結(jié)果數(shù)的鏈表。約瑟夫環(huán)問題：設(shè)有編號為1，2，…，n的n（n＞0）個人圍成一個圈，每個人持有一個密碼m（m≠1），從第1個人開始報數(shù)，報到m時停止報數(shù)，報m的人出圈，再從他的下一個人起重新報數(shù)，報到m時停止報數(shù)，報m的出圈，…，如此下去，直到所有人全部出圈為止。當(dāng)任意給定n和m后，設(shè)計算法求n個人出圈的次序。編寫算法，完成下述要求：①建立一個鏈表用于存放輸入的二進(jìn)制數(shù)，鏈表中的每個結(jié)點的data域存放一個二進(jìn)制位。②在此鏈表上實現(xiàn)對二進(jìn)制數(shù)加1的運算，并輸出運算結(jié)果。有一個不帶頭結(jié)點的單鏈表h，通過遍歷鏈表將鏈表中所有的鏈接方向逆轉(zhuǎn)，算法如下，請在空格處填寫正確的語句。voidInverse(&h){ if(①)return; p=h->next;pr=NULL; while(②){ h->next=pr;pr=h; h=p;③ }}設(shè)兩個帶頭結(jié)點的單鏈表A和B，表中結(jié)點的數(shù)據(jù)為整型，下面算法產(chǎn)生表A和表B的并集并以表C存儲，請?zhí)顚懰惴ㄖ锌瞻滋幍恼Z句，完成其功能。

棧的基本概念選擇題經(jīng)過以下棧運算后，x的值是（）。InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，GetTop(s,x)A．a(chǎn) B．b C．1 D．0經(jīng)過以下棧運算后，StackEmpty(s)的值是（）。InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，Pop(s,y)A．a(chǎn) B．b C．1 D．0（）不是棧的基本運算。A．刪除棧頂元素 B．刪除棧底元素C．判斷棧是否為空 D．將棧置為空棧設(shè)有一個空棧，棧頂指針為1000H（十六進(jìn)制，下同），每個元素需要1個單位的存儲空間，則執(zhí)行PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH操作后，棧頂指針值為（）。A．1002H B．1003H C．1004H D．1005H一個棧的入棧序列是{1，2，3，4，5}，則棧的不可能的輸出序列是（）。A．{5，4，3，2，1} B．{4，5，3，2，1}C．{4，3，5，1，2} D．{1，2，3，4，5}若一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素是（）。A．不確定 B．n-i C．n-i-1 D．n-i+1若一個棧的輸入序列是1，2，3，…，n，其輸出序列是p1，p2，…，pn，若p1=3，則p2的值（）。A．一定是2 B．一定是1 C．不可能是1 D．以上都不對若一個棧的輸入序列是p1，p2，…，pn，其輸出序列是1，2，3，…，n，若p3=1，則p1的值（）。A．可能是2 B．一定是2 C．不可能是2 D．不可能是3當(dāng)字符序列t3_依次通過棧，輸出長度為3且可用作C語言標(biāo)識符的序列有（）。A．4個 B．5個 C．3個 D．6個應(yīng)用題設(shè)有一個棧，元素進(jìn)棧的次序為A，B，C，D，E，能否得到如下出棧序列，若能，請寫出操作序列，若不能，請說明原因。①C，E，A，B，D ②C，B，A，D，E在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么（push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。）設(shè)元素1、2、3、P、A依次經(jīng)過一個棧，進(jìn)棧次序為123PA，在棧的輸出序列中，有哪些序列可作為C++程序設(shè)計語言的變量名。如果進(jìn)棧序列為A、B、C、D，則可能的出棧序列是什么？算法設(shè)計題假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。下面所示的序列中哪些是合法的？A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIOO通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。

順序棧選擇題在一個具有n個單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時，top的變化為（）。A．不變 B．top=0 C．top-1 D．top=top+1設(shè)數(shù)組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當(dāng)S[n]全滿時才不能進(jìn)行進(jìn)棧操作。為這兩個棧分配空間的最佳方案是（）。A．S1的棧底位置為0，S2的棧底位置為n-1B．S1的棧底位置為0，S2的棧底位置為n/2C．S1的棧底位置為0，S2的棧底位置為nD．S1的棧底位置為0，S2的棧底位置為1為了增加內(nèi)存空間的利用率和減少溢出的可能性，兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的棧底分別設(shè)在這片內(nèi)存空間的兩端，這樣，當(dāng)（）時才產(chǎn)生上溢。A．兩個棧的棧頂同時到達(dá)棧空間的中心點B．其中一個棧的棧頂?shù)竭_(dá)?？臻g的中心點C．兩個棧的棧頂在棧空間的某一位置相遇D．兩個棧均不空，且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底兩個棧共享一個數(shù)組空間的好處是（）。A．減少存取時間，降低發(fā)生上溢的可能性B．節(jié)省存儲空間，降低發(fā)生上溢的可能性C．減少存取時間，降低發(fā)生下溢的可能性D．節(jié)省存儲空間，降低發(fā)生下溢的可能性算法設(shè)計題假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅有I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非合法序列。①下面所示的序列中哪些是合法的？

②通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。下面的算法將一個整數(shù)e壓入到堆棧S，請在空格處填上適當(dāng)?shù)恼Z句實現(xiàn)該操作。Typedefstruct{ int*base; inttop; intstacksize;}SqStack;intPush(SqStackS,inte){if(①) { S.base=(int*)realloc(S.base,(S.stacksize+1)*sizeof(int));if(②){ printf(“NotEnoughMemory!\n”); retuan0;}S.top=③;S.stacksize=④;}⑤;retuan1;}

鏈棧選擇題向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應(yīng)執(zhí)行（）。A．h->next=s; B．s->next=h;C．s->next=h;h->next=s; D．s->next=h->next;h->next=s;從棧頂指針為top的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行（）。A．x=top;top=top->next; B．x=top->data;C．top=top->next;x=top->data; D．x=top->data;top=top->next;

隊列的基本概念選擇題隊列的“先進(jìn)先出”特性是指（）。A．最后插入隊列中的元素總是最后被刪除B．當(dāng)同時進(jìn)行插入、刪除操作時，總是插入操作優(yōu)先C．每當(dāng)有刪除操作時，總要先做一次插入操作D．每次從隊列中刪除的總是最早插入的元素允許對隊列進(jìn)行的操作有（）。A．對隊列中的元素排序 B．取出最近入隊的元素C．在隊頭元素之前插入元素 D．刪除隊頭元素一個隊列的入隊順序是1、2、3、4，則隊列的輸出順序是（）。A．4321 B．1234 C．1432 D．3241

順序隊列選擇題循環(huán)隊列存儲在數(shù)組A[0…m]中，則入隊時的操作為（）。A．rear=rear+1 B．rear=(rear+1)mod(m-1)C．rear=(rear+1)modm D．rear=(rear+1)mod(m+1)若用一個長度為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，則從隊列中刪除一個元素，再增加兩個元素后，rear和front的值分別為（）。A．1和5 B．2和4 C．4和2 D．5和1已知循環(huán)隊列的存儲空間為數(shù)組A[21]，front指向隊頭元素的前一個位置，rear指向隊尾元素，假設(shè)當(dāng)前front和rear的值分別是8和3，則該隊列的長度為（）。A．5 B．6 C．16 D．17如圖所示為一個元素類型為字符型的環(huán)形隊列，如果front指向隊頭元素的前一個位置，rear指向隊尾元素，則所表示的隊列為（）。012345678910111213141516171819202122ThefloweRIsbeauTiful↑rear↑frontA．Thef B．beautifulThef C．floweris D．eautifulThef應(yīng)用題舉例說明順序隊列的“假溢出”現(xiàn)象。簡述順序隊列假溢出的避免方法及隊列滿或空的判定條件。在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊頭元素和隊尾元素分別是什么（EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊。）算法設(shè)計題在循環(huán)隊列中設(shè)置一個標(biāo)志flag，當(dāng)front=rear且flag=0時為隊空，當(dāng)front=rear且flag=1時為隊滿。編寫相應(yīng)的入隊和出隊算法。如果設(shè)置一個計數(shù)器count累計隊列的長度，則當(dāng)count=0時隊列為空，當(dāng)count=QueueSize時隊列為滿。試設(shè)計相應(yīng)的入隊和出隊算法。

鏈隊列選擇題用不帶頭結(jié)點的單鏈表存儲隊列時，其隊頭指針指向隊頭結(jié)點，隊尾指針指向隊尾結(jié)點，則執(zhí)行刪除操作時，（）。A．僅修改隊首指針 B．僅修改隊尾指針C．隊首指針和隊尾指針都需要修改 D．隊首指針和隊尾指針可能都需要修改在鏈隊列中，設(shè)指針f和r分別指向隊首和隊尾，則插入s所指結(jié)點的操作是（）。A．f->next=s;f=s; B．r->next=s;r=s;C．s->next=r;r=s; D．s->next=f;f=s;設(shè)循環(huán)單鏈表表示的隊列長度為n，若只設(shè)頭指針，則進(jìn)隊操作的時間性能為（）。A．○(n) B．○(1) C．○(n2) D．○(nlog2n)最不適合用作鏈隊列的鏈表是（）。A．只帶隊首指針的非循環(huán)雙鏈表 B．只帶隊首指針的循環(huán)雙鏈表C．只帶隊尾指針的循環(huán)雙鏈表 D．只帶隊尾指針的循環(huán)單鏈表算法設(shè)計題假設(shè)以不帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針。試設(shè)計相應(yīng)的入隊和出隊算法。

棧和隊列的應(yīng)用選擇題設(shè)計一個判別表達(dá)式中左右括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A．順序表 B．棧 C．隊列 D．鏈表如果數(shù)據(jù)是在程序的運行過程中逐步產(chǎn)生的，并且要求先產(chǎn)生的數(shù)據(jù)后處理，后產(chǎn)生的數(shù)據(jù)先處理，則最合適的數(shù)據(jù)結(jié)構(gòu)是（）。A．順序表 B．順序棧 C．順序隊列 D．堆在解決計算機(jī)主機(jī)和打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個（）結(jié)構(gòu)。A．棧 B．隊列 C．?dāng)?shù)組 D．線性表執(zhí)行（）操作時，需要使用隊列作為輔助數(shù)據(jù)結(jié)構(gòu)。A．深度優(yōu)先遍歷圖 B．廣度優(yōu)先遍歷圖C．散列查找 D．遍歷二叉樹表達(dá)式3*2^(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時，對象棧和算符棧為（），其中^表示乘冪。A．3,2,4,1,1；#*^(+*- B．3,2,8；#*^-C．3,2,4,2,2；#*^(- D．3,2,8；#*^(-利用棧計算表達(dá)式的值時，設(shè)置操作數(shù)棧OPND，設(shè)OPND只有存儲單元，計算下列表達(dá)式是不發(fā)生上溢的是（）。A．a(chǎn)-b*(c-d) B．(a-b)*c-d C．(a-b*c)-d D．(a-b)*（c-d）與中綴表達(dá)式a*b+c/d-e等價的前綴表達(dá)式是（）。A．-+*ab/cde B．*+/-abcde C．+*ab-/cde D．*ab+cd/-e解決hanoi塔問題的遞歸算法，其時間復(fù)雜度是（）。A．○(n) B．○(n2) C．○(2n) D．○(n!)4個圓盤的漢諾塔，總的移動次數(shù)為（）。A．7 B．8 C．15 D．16一個遞歸的求解過程可以用遞歸函數(shù)求解，也可以用非遞歸函數(shù)求解，從運行時間上看，通常遞歸函數(shù)要比非遞歸函數(shù)（）。A．快一些 B．慢一些 C．相同 D．無法比較棧和隊列的主要區(qū)別在于（）。A．它們的邏輯結(jié)構(gòu)不一樣 B．它們的存儲結(jié)構(gòu)不一樣C．所包含的運算不一樣 D．插入、刪除運算的限定不一樣棧和隊列的共同點是（）。A．都是先進(jìn)先出 B．都是先進(jìn)后出C．只允許在端點處插入和刪除元素 D．沒有共同點棧和隊列具有相同的（）。A．邏輯結(jié)構(gòu) B．抽象數(shù)據(jù)類型 C．存儲結(jié)構(gòu) D．運算設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素出隊的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（）。A．6 B．4 C．3 D．2算法設(shè)計題假設(shè)一個算術(shù)表達(dá)式中可以包含三中括號：園括號“（”和“）”，方括號“[”和“]”以及花括號“{”和“}”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷表達(dá)式中所含括號是否配對出現(xiàn)。設(shè)計算法把一個十進(jìn)制整數(shù)轉(zhuǎn)換為二至九進(jìn)制之間的任一進(jìn)制數(shù)輸出。設(shè)計遞歸算法求解在n元集合A={1，2，…，n}中選取k（k≤n）個元素的所有組合。例如，從集合{1，2，3，4}中選取2個元素的所有組合為：{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{3，4}。已知Q是一個循環(huán)隊列，S是一個順序棧，設(shè)計算法實現(xiàn)將隊列中所有元素逆轉(zhuǎn)。設(shè)棧S中有2n個元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，…，a2，a1，要求通過一個循環(huán)隊列重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，請設(shè)計算法實現(xiàn)該操作，要求空間復(fù)雜度和時間復(fù)雜度均為○(n)。利用兩個棧S1和S2模擬一個隊列，已知棧的三個運算定義如下：PUSH(ST,x)元素x入ST；POP(ST,x)ST棧頂元素出棧，賦給變量x；Sempty(ST)判ST棧是否為空。那么如何利用棧的運算來實現(xiàn)該隊列的三個運算：enqueue插入一個元素入隊列；dequeue刪除一個元素出隊列；queue_empty判斷隊列是否為空。一個雙端隊列Q是限定在線性表的兩端（LEFT端和RIGHT端）都可以進(jìn)行插入和刪除操作的線性表，隊列為空的條件是LEFT=RIGHT。若采用順序存儲結(jié)構(gòu)存儲雙端隊列，要求：①定義雙端隊列的存儲結(jié)構(gòu)；②給出在指定端L（表示左端）和R（表示右端）進(jìn)行插入（QueueInsert）和刪除（QueueDelete）操作的算法。

數(shù)組選擇題數(shù)組通常具有的兩種基本操作是（）。A．查找和修改 B．查找和索引 C．索引和修改 D．建立和刪除將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因為（）。A．?dāng)?shù)組元素是隨機(jī)的 B．對數(shù)組任一元素的存取時間是相等的C．隨時可以對數(shù)組進(jìn)行訪問 D．?dāng)?shù)組的存儲結(jié)構(gòu)是不定的下面說法中，不正確的是（）。A．?dāng)?shù)組是一種線性結(jié)構(gòu)B．?dāng)?shù)組是一種定長的線性結(jié)構(gòu)C．除了插入和刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D．?dāng)?shù)組的基本操作有存取、修改、檢索和排序等，沒有插入和刪除操作二維數(shù)組SZ[-3..5，0..10]含有的元素個數(shù)是（）。A．88 B．99 C．80 D．90數(shù)組A[0..5，0..6]的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是（）。A．1175 B．1180 C．1205 D．1210C語言中定義的整數(shù)一維數(shù)組a[50]和二維數(shù)組b[10][5]具有相同的首元素地址，即&(a[0])=&(b[0][0])，在以列序為主序時，a[18]的地址和（）的地址相同。A．b[1][7] B．b[1][8] C．b[8][1] D．b[7][1]二維數(shù)組A的每個元素是由6個字符組成的串，行下標(biāo)的范圍從0～8，列下標(biāo)的范圍是0～9，則存放A至少需要（）個字節(jié)，A的第8列和第5行共占（）個字節(jié)，若A按行序優(yōu)先方式存儲，元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先存儲時的（）元素的起始地址一致。A．90 B．180 C．240 D．540E．108 F．114 G．54 H．A[8][5]I．A[3][10] J．A[5][8] K．A[4][9]三維數(shù)組A[8,8,10]采用行序為主的方式從地址A[0，0，0]開始存放，假設(shè)每個元素占用存儲空間大小為L，則元素A[3，2，8]的存放位置是（）。A．A[0，0，0]+198*L B．A[0，0，0]+108*LC．A[0，0，0]+268*L D．A[0，0，0]+13*L算法設(shè)計題若在矩陣A中存放一個元素ai,j（0≤i≤n-1，0≤j≤m-1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣A，試設(shè)計一個求矩陣所有馬鞍點的算法，并分析最壞情況下的時間復(fù)雜度。給定n×m矩陣A[a..b，c..d]滿足A[i，j]≤A[i，j+1]（a≤i≤b，c≤j≤d-1）和A[i，j]≤A[i+1，j]（a≤i≤b-1，c≤j≤d）。設(shè)計算法判定x是否在A中，要求時間復(fù)雜度為○(m+n)。

特殊矩陣選擇題對特殊矩陣采用壓縮存儲的目的主要是為了（）。A．表達(dá)變得簡單 B．對矩陣元素的存取變得簡單C．去除矩陣中的多余元素 D．減少不必要的存儲空間下面（）不屬于特殊矩陣。A．對角矩陣 B．三角矩陣 C．稀疏矩陣 D．對稱矩陣一個n×n的對稱矩陣，如果以行或列為主序放入內(nèi)存，則需要（）個存儲單元。A．n(n+1)/2 B．n(n-1)/2 C．n2 D．n2/2設(shè)A[n，n]是對稱矩陣，將其下三角（包括對角線）按行序存儲到一維數(shù)組T[n(n+1)/2]中，則上三角元素A[i][j]對應(yīng)T[k]的下標(biāo)k是（）。A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-i)/2+1 D．j(i-1)/2+1設(shè)有一個n行n列的對稱矩陣A將其下三角部分按行存放在一維數(shù)組B中，A[0][0]存放于B[0]中，那么第i行的對角元素A[i][i]存放于B中（）處。A．(i+3)*i/2 B．(i+1)*i/2 C．(2n-i+1)*i/2 D．(2n-i-1)*i/2若將n階上三角矩陣A按列優(yōu)先順序壓縮存放在一維數(shù)組B[1..n(n+1)/2]中。則存放到B[k]中的非零元素ai,j（1≤i，j≤n）的下標(biāo)i，j與k的對應(yīng)關(guān)系是（）。A．(i+1)*i/2+j B．(i+1)*i/2+j-1 C．(j+1)*j/2+i D．(j-1)*j/2+i-1若將n階下三角矩陣A按列優(yōu)先順序壓縮存放在一維數(shù)組B[1..n(n+1)/2]中。則存放到B[k]中的非零元素ai,j（1≤i，j≤n）的下標(biāo)i，j與k的對應(yīng)關(guān)系是（）。A．(j-1)(2n-j+1)/2+i-j B．(j-1)(2n-j+2)/2+i-j+1C．(j-1)(2n-j+2)/2+i-j D．(j-1)(2n-j+2)/2+i-j+1將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1..298]中，則A中元素A66,65在B數(shù)組中的位置k為（）。A．198 B．195 C．197 D．應(yīng)用題對于一個n行m列的上三角矩陣A，如果以行優(yōu)先的方式用一維數(shù)組B從0號位置開始存儲，求元素ai,j（1≤i≤n，1≤j≤m）在數(shù)組B中的存儲位置。設(shè)有三對角矩陣An×n（行、列下標(biāo)均從0開始），將其三條對角線上的元素逐行存于數(shù)組B[3n-2]中，使得B[k]=ai,j，求：①用i，j表示k的下標(biāo)變換公式；②用k表示i，j的下標(biāo)變換公式。設(shè)有五對角矩陣B=(ai,j)20×20，按特殊矩陣壓縮存儲的方式將其五條對角線上的元素存于數(shù)組A[-10..m]中，計算元素B[15][16]在數(shù)組A中的存儲位置。挑戰(zhàn)題對于給定的數(shù)組a[n][2n-1]，將3個頂點分別為a[0][n-1]、a[n-1][0]和a[n-1][2n-2]的三角形上的所有元素按行序存放在一維數(shù)組B[n×n]中，且元素a[0][n-1]存放在B[0]中。例如當(dāng)n=3時，數(shù)組a[3][5]中三角形如圖所示。如果位于三角形上的元素a[i][j]存放于B[k]中，請給出元素a[i][j]的下標(biāo)i，j和k的對應(yīng)關(guān)系。a00 a01 a02 a03a10 a11 a12 aa20 a21 a22 a設(shè)A和B均為n階下三角矩陣，另有一個n行n+1列的二維數(shù)組C，設(shè)計一個方案將兩個矩陣A和B壓縮存儲于同一個數(shù)組C中，并給出A的矩陣元素ai,j和B的矩陣元素bi,j在數(shù)組C中的存放位置。

查找的基本概念選擇題靜態(tài)查找與動態(tài)查找的根本區(qū)別在于（）。A．它們的邏輯結(jié)構(gòu)不一樣 B．施加在其上的操作不同C．所包含的數(shù)據(jù)元素的類型不一樣 D．存儲實現(xiàn)不一樣以下（）方法適合動態(tài)查找。A．順序查找 B．折半查找 C．散列查找 D．隨機(jī)查找能夠?qū)崿F(xiàn)動態(tài)查找的數(shù)據(jù)結(jié)構(gòu)是（）。A．有序表 B．雙鏈表 C．循環(huán)鏈表 D．二叉排序樹平均查找長度與查找集合中記錄個數(shù)n無關(guān)的查找方法是（）。A．折半查找 B．平衡二叉樹的查找 C．散列查找 D．不存在在以下數(shù)據(jù)結(jié)構(gòu)中，（）查找效率最低。A．有序順序表 B．二叉排序樹 C．堆 D．散列表

順序查找選擇題對線性表進(jìn)行順序查找，要求線性表的存儲結(jié)構(gòu)為（）。A．散列存儲 B．順序存儲 C．鏈接存儲 D．順序存儲或鏈接存儲用順序查找方法在長度為n的線性表中進(jìn)行查找，在等概率情況下，查找成功的平均查找長度為（）。A．n B．n/2 C．(n-1)/2 D．(n+1)/2假定查找成功與不成功的可能性相同，在查找成功的情況下每個記錄的查找概率相同，則順序查找的平均查找長度為（）。A．0.5(n+1) B．0.25(n+1) C．0.5(n-1) D．0.75n+0.25

折半查找選擇題有一個按元素值排好序的順序表（長度大于2），分別用順序查找和折半查找與給定值相等的元素，比較次數(shù)分別是s和b，在查找成功的情況下，s和b的關(guān)系是（）；在查找不成功的情況下，s和b的關(guān)系是（）。A．s=b B．s>b C．s<b D．不一定長度為12的有序表采用順序存儲結(jié)構(gòu)，采用折半查找技術(shù)，在等概率情況下，查找成功的平均長度是（），查找失敗時的平均查找長度是（）。A．37/12 B．62/13 C．39/12 D．49/13已知一個有序表為{12，18，24，35，47，50，62，83，90，115，134}，當(dāng)折半查找值為90的元素時，經(jīng)過（）次比較后查找成功。A．2 B．3 折半查找判定樹不屬于（）。A．平衡二叉樹 B．二叉排序樹 C．完全二叉樹 D．二叉樹當(dāng)n足夠大時，在有序順序表中進(jìn)行折半查找，假設(shè)順序表中每個元素的查找概率相同，則查找成功的平均查找長度為（）。A．(n+1)/2 B．n/2 C．log2(n+1)-1 D．log2(n+1)對表長為n的有序表進(jìn)行折半查找，其判定樹的高度為（）。A．log2(n+1) B．log2(n+1)-1 C．log2n D．log2(n-1)對100個元素進(jìn)行折半查找，在查找成功的情況下，比較次數(shù)最多是（）。A．25 B．50 C．10 D．7對具有14個元素的有序表R[]14]進(jìn)行折半查找，查找R[3]時比較需要比較（）。A．R[0]R[1]R[2]R[3] B．R[6]R[2]R[4]R[3]C．R[0]R[13]R[2]R[3] D．R[6]R[4]R[2]R[3]對有序表A[1..17]進(jìn)行折半查找，則查找長度為5的元素下標(biāo)依次是（）。A．8，17 B．5，10，12 C．9，16 D．9，17應(yīng)用題畫出長度為10的折半查找判定樹，并求等概率時查找成功和不成功的平均查找長度。對長度為2k-1的有序表進(jìn)行折半查找，查找成功的情況下最多需要比較多少次查找失敗的情況下需要比較多少次

散列查找選擇題散列技術(shù)中的沖突指的是（）。A．兩個元素具有相同的序號 B．兩個元素的鍵值不同，而其他屬性相同C．?dāng)?shù)據(jù)元素過多 D．不同鍵值的元素對應(yīng)于相同的存儲地址設(shè)散列表表長為m=14，散列函數(shù)H(k)=kmod11。表中已有15、38、61、84四個元素，如果用線性探測法處理沖突，則元素49的存儲地址是（）。A．8 B．3 C．5 D．9為一組關(guān)鍵碼{87，73，25，55，90，28，31，17，101，22，3，62}構(gòu)造散列表，設(shè)散列函數(shù)為H(key)=keymod11，在用鏈地址法處理后位于同一鏈表中的是（）。A．81，90 B．31，101 C．3，78 D．62，73在采用線性探測法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置的鍵值（）。A．一定都是同義詞 B．一定都不是同義詞C．不一定都是同義詞 D．都相同在散列函數(shù)H(key)=keymodm中，一般來講，m應(yīng)取（）。A．奇數(shù) B．偶數(shù) C．素數(shù) D．充分大的數(shù)下面關(guān)于散列查找的說法正確的是（）。A．散列函數(shù)越復(fù)雜越好，因為這樣隨機(jī)性好，沖突小B．除留余數(shù)法是所有散列函數(shù)中最好的C．不存在特別好和特別壞的散列函數(shù)，要視情況而定D．若在散列表中刪去一個元素，只要簡單地將該元素刪去即可關(guān)于散列查找說法不正確的有幾個（）。①采用鏈地址法解決沖突，查找一個元素的時間是相同的②采用鏈地址法解決沖突，若插入總是在鏈?zhǔn)?，則插入任一個元素的時間是相同的③采用鏈地址法解決沖突易引起聚集現(xiàn)象④再散列法易引起聚集現(xiàn)象A．1 B．2 C．3 D．4關(guān)于散列查找，下面說法正確的是（）。A．再散列法處理沖突不會產(chǎn)生聚集B．散列表的裝填因子越大說明空間利用率越高，因此應(yīng)使裝填因子盡可能大C．散列函數(shù)選擇得好可以減少沖突現(xiàn)象D．對任何關(guān)鍵碼集合都無法找到不產(chǎn)生沖突的散列函數(shù)散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（）取其值域的每個值。A．最大概率 B．最小概率 C．平均概率 D．同等概率散列函數(shù)方法一般適用于（）情況下的查找。A．查找表為鏈表 B．查找表為有序表C．關(guān)鍵碼集合比地址集合大得多 D．關(guān)鍵碼集合與地址集合存在對應(yīng)關(guān)系設(shè)哈希表長m=15，哈希函數(shù)H(key)=keymod13，關(guān)鍵碼集合為{53，17，12，61，89，70，87，25，64，46}，采用二次探測再散列方法處理沖突，則查找成功的平均比較長度為（）。A．1.4 B．1.6 C．1.8 D．2.0假設(shè)有10個關(guān)鍵碼，它們具有相同的散列函數(shù)值，用線性探測法把這10個關(guān)鍵碼存入散列表中至少需要做（）次探測。A．110 B．100 C．55 D．45采用開放定址法解決沖突的散列查找中，發(fā)生聚集的原因主要是（）。A．?dāng)?shù)據(jù)元素過多 B．裝填因子過大C．散列函數(shù)選擇不當(dāng) D．解決沖突的算法不好對具有n個關(guān)鍵碼的散列表進(jìn)行查找，平均查找長度是（）。A．○(log2n) B．○(n) C．○(nlog2n) D．與n無關(guān)應(yīng)用題已知關(guān)鍵碼序列為（Jan，F(xiàn)eb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec），散列表的地址空間為0~16，設(shè)散列函數(shù)為H(x)=[i/2]，其中i為關(guān)鍵碼中第一個字母在字母表中的序號，采用線性探測法和鏈地址法處理沖突，試分別構(gòu)造散列表，并求等概率情況下查找成功的平均查找長度。設(shè)散列表為T[0..12]，散列函數(shù)為H(key)=keymod13，采用再散列法處理沖突，再散列函數(shù)為Hi(key)=(Hi-1+REV(key+1)mod11+1)mod13，其中REV(key)表示顛倒10進(jìn)制數(shù)key的各位，如REV(73)=37，REV(7)=7等。將關(guān)鍵碼集合{2，8，31，20，19，18，53，27}插入到散列表中，畫出最后的散列表，并計算查找成功的平均查找長度。給定關(guān)鍵碼序列{26，25，20，34，28，24，45，64，42}，設(shè)定裝填因子為0.6，請給出除留余數(shù)法的散列函數(shù)，畫出采用線性探測法處理沖突構(gòu)造的散列表。

排序的基本概念選擇題排序算法的穩(wěn)定性是指（）。A．經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的相對位置不變B．經(jīng)過排序之后，能使值相同的數(shù)據(jù)保持原順序中的絕對位置不變C．排序算法的性能與被排序元素的數(shù)量關(guān)系不大D．排序算法的性能與被排序元素的數(shù)量關(guān)系密切對任意的7個關(guān)鍵碼進(jìn)行排序，至少要進(jìn)行（）次關(guān)鍵碼之間的比較。A．13 B．14 C．15 D．16一個待排序的n個記錄可分為n/k組，每組包含k個記錄，且任一組內(nèi)的各記錄分別大于前一組內(nèi)的所有記錄且小于后一組內(nèi)的所有記錄，若采用基于比較的排序方法，其時間下界為（）。A．○(klog2k) B．○(klog2n) C．○(nlog2k) D．○(nlog2n)關(guān)于排序，下列說法中正確的是（）。A．穩(wěn)定的排序方法優(yōu)于不穩(wěn)定的排序方法，因為穩(wěn)定的排序方法效率較高B．對同一個線性表使用不同的排序方法進(jìn)行排序，得到的排序結(jié)果可能不同C．排序方法都是在順序表上實現(xiàn)的，在鏈表上無法實現(xiàn)排序方法D．在順序表上實現(xiàn)的排序方法在鏈表上也可以實現(xiàn)下列不屬于內(nèi)部排序方法的是（）。A．歸并排序 B．拓?fù)渑判? C．堆排序 D．插入排序

插入排序選擇題用直接插入排序?qū)ο旅嫠膫€序列進(jìn)行由小到大排序，元素比較次數(shù)最小的是（）。A．94，32，40，90，80，46，21，69 B．21，32，46，40，80，69，90，94C．32，40，21，46，69，94，90，80 D．90，69，80，46，21，32，94，40當(dāng)待排序序列基本有序或個數(shù)較小的情況下，最佳的內(nèi)部排序方法是（）。A．起泡排序 B．直接插入排序 C．快速排序 D．簡單選擇排序數(shù)據(jù)序列{8，9，10，4，5，6，20，1，2}只能是（）的兩趟排序后的結(jié)果。A．選擇排序 B．冒泡排序 C．插入排序 D．堆排序?qū)?shù)據(jù)序列{15，9，7，8，20，-1，4}進(jìn)行排序，一趟后數(shù)據(jù)序列變?yōu)閧9，15，7，8，20，-1，4}，則采用的是（）。A．選擇排序 B．冒泡排序 C．插入排序 D．堆排序下列排序算法中，（）可能會出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在最終位置上。A．起泡排序 B．插入排序 C．快速排序 D．堆排序?qū)τ衝個記錄的線性表進(jìn)行直接插入排序，在最好情況下需比較（）次。A．n-1 B．n+1 C．n/2 D．n(n-1)/2

希爾排序選擇題以下排序算法中，（）不能保證每趟至少能將一個元素放到其最終位置上。A．快速排序 B．希爾排序 C．起泡排序 D．堆排序?qū)?shù)據(jù)序列{9