數(shù)據(jù)結(jié)構選擇填空題

數(shù)據(jù)結(jié)構（C語言版）選擇、填空題一概論選擇1、 （）是數(shù)據(jù)的基本單位。A、 數(shù)據(jù)結(jié)構B、 數(shù)據(jù)元素C、 數(shù)據(jù)項D、 數(shù)據(jù)類型2、 以下說法不正確的是（）。A、 數(shù)據(jù)結(jié)構就是數(shù)據(jù)之間的邏輯結(jié)構。B、 數(shù)據(jù)類型可看成是程序設計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構。C、 數(shù)據(jù)項是組成數(shù)據(jù)元素的最小標識單位。D、 數(shù)據(jù)的抽象運算不依賴具體的存儲結(jié)構。3、 學習數(shù)據(jù)結(jié)構主要目的是（）。A、 處理數(shù)值計算問題B、 研究程序設計技巧C、 選取合適數(shù)據(jù)結(jié)構，寫出更有效的算法。D、 是計算機硬件課程的基礎。4、 一般而言，最適合描述算法的語言是（）。入、自然語言B、 計算機程序語言C、 介于自然語言和程序設計語言之間的偽語言D、 數(shù)學公式5、 通常所說的時間復雜度指（）。A、 語句的頻度和B、 算法的時間消耗C、 漸近時間復雜度D、 最壞時間復雜度6、 A算法的時間復雜度為O（n”3）,B算法的時間復雜度為。（2圣），則說明（）。A、 對于任何數(shù)據(jù)量，A算法的時間開銷都比B算法小B、 隨著問題規(guī)模n的增大，A算法比B算法有效C、 隨著問題規(guī)模n的增大，B算法比A算法有效D、 對于任何數(shù)據(jù)量，B算法的時間開銷都比A算法小填空1、 數(shù)據(jù)的（）結(jié)構依賴于計算機語言.2、 數(shù)據(jù)的邏輯結(jié)構可分為線性結(jié)構和（）結(jié)構。3、 算法的時間復雜度與問題的規(guī)模有關外，還與輸入實例的（）有關。4、 常用的四種存儲方法是什么？5、 常見的數(shù)據(jù)的邏輯結(jié)構有哪兩種？6、 一般，將算法求解問題的輸入量稱為（）。二線性表選擇題1、以下關于線性表的說法不正確的是（）。A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。

B、B、C、D、2、A、B、C、D、3、A、線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。線性表的順序存儲結(jié)構是一種（）的存儲結(jié)構。隨機存取順序存取索引存取散列存取在順序表中，只要知道（），就可在相同時間內(nèi)求出任一結(jié)點的存儲地址?；刂稡、 結(jié)點大小C、 向量大小D、 基地址和結(jié)點大小4、 在等概率情況下，順序表的插入操作要移動（）結(jié)點。A、 全部B、 一半C、 三分之一D、 四分之一5、 在（）運算中，使用順序表比鏈表好。入、插入B、 刪除C、 根據(jù)序號查找D、 根據(jù)元素值查找6、 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復雜度是（）。A、 O（1）B、 O（n）C、 O（n"2）D、 O（log2n）填空題1、 線性表是一種典型的（）結(jié)構。2、 在一個長度為n的順序表中刪除第i個元素，要移動（）個元素3、 如果要在第i個元素前插入一個元素，要后移（）個元素。4、 采用（）存儲結(jié)構的線性表叫順序表。5、 順序表中邏輯上相鄰的元素的物理位置（）。6、 在無頭結(jié)點的單鏈表中，第1個結(jié)點的地址存放在頭指針中，其他結(jié)點的存儲地址存放在（）結(jié)點的next域中。三棧和隊列選擇1、 棧與一般的線性表的區(qū)別在于（）。A、 數(shù)據(jù)元素的類型不同B、 運算是否受限制C、 數(shù)據(jù)元素的個數(shù)不同D、 邏輯結(jié)構不同2、 一個棧的入棧序列是abcde，則棧的不可能的輸出序列是（）。A、 EdcbaB、decbaC、dceabD、abcde3、 在對棧的操作中，能改變棧的結(jié)構的是（）。A、 InitStack（S）B、 StackEmpty（S）C、 StackTop（S）D、 StackFull（S）4、 順序棧的類型定義如下：typedefmaxsize64;typedefstruct{intdata[maxsize];inttop;}seqstack;seqstack*s;順序棧s棧滿條件是（）。（A） s->top<>0（B） s->top==maxsize（C） s->top==maxsize-1（D） S->top!=maxsize5、 向一個棧頂指針為HS的鏈棧中將一個S指針所指的結(jié)點入棧，執(zhí)行（）。A、 HS->next=s;B、 S->next=HS->next;HS->next=s;C、 S->next=HS->next;HS=s;D、 S->next=HS;HS=HS->next;6、 若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列是p1,p2,p3，…，pn，若p1=n，則pi=（）。TOC\o"1-5"\h\zA、 IB、 n-IC、 n-i+1D、 不確定填空1、 在棧中，可進行插入和刪除操作的一端稱（）。2、 在棧的出棧操作中，要先判斷棧是否空，否則會產(chǎn)生（）現(xiàn)象。3、 當程序中同時使用（）個棧時，讓它們共享同一向量空間可減少上溢的發(fā)生。4、 棧的特點是（）。5、 由于鏈棧的操作只在鏈表頭部進行，所以沒有必要設置（）結(jié)點。6、 若內(nèi)存空間充足，（）?？刹欢x棧滿運算。四串選擇1、 串是一種特殊的線性表，其特殊性體現(xiàn)在（）。2、 A、可以順序存儲3、 B、數(shù)據(jù)元素是一個字符4、 C、可以鏈接存儲5、 D、數(shù)據(jù)元素可以是多個字符6、 有兩個串P和Q，求P和Q中首此出現(xiàn)的位置的運算稱（）。7、 A、連接

8、8、9、B、 模式匹配C、 求子串10、 D、求串長11、 設串s1='ABCDEFG',s2='PQRST',函數(shù)con(x,y)返回x和y串的連接串，subs(s,I,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2)))的結(jié)果串是()。A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF12、 在串的模式匹配中，一般()。13、 A、有效位移的個數(shù)大于合法位移的個數(shù)14、 B、有效位移的個數(shù)等于合法位移的個數(shù)15、 C、有效位移的個數(shù)小于合法位移的個數(shù)16、 D、有效位移和合法位移無關17、 順序串中，根據(jù)空間分配方式的不同，可分為()。18、 A、直接分配和間接分配19、 B、靜態(tài)分配和動態(tài)分配20、 C、順序分配和鏈式分配21、 D、隨機分配和固定分配填空1、 在空串和空格串中，長度不為0的是()。2、 按存儲結(jié)構不同，串可分為()。3、 C語言中，以字符()表示串值的終結(jié)。4、 在鏈串中，為了提高存儲密度，應該增大().5、 假設每個字符占1個字節(jié)，若結(jié)點大小為4的鏈串的存儲密度為50%，則其每個指針占()個字節(jié)。五多維數(shù)組和廣義表選擇1、 稀疏矩陣的一般的壓縮方法有()。2、 A、二維數(shù)組B、廣義表C、三元組表D、一維數(shù)組3、 設矩陣A是一個對稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先存放在一維數(shù)組B中。對下三角矩陣中任一元素aij(設矩陣A是一個對稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先存放在一維數(shù)組B中，對下三角矩陣中任一元素aij(i>=j)，在一維數(shù)組B中下標K的值是()。4、 A、i(i-1)/2+j-1B、i(i-1)/2+jC、i(i+1)/2+j-1D、i(i+1)/2+j5、 在稀疏矩陣的三元組表表示法中，每個三元組表示()。6、 (A)矩陣中數(shù)據(jù)元素的行號、列號和值7、 (B)矩陣中非零元素的值8、 ？矩陣中非零元素的行號和列號9、 (D)矩陣中非零元素的行號、列號和值10、 對稀疏矩陣進行壓縮存儲是為了()。11、 (A)便于進行矩陣運算12、 (B)便于輸入和輸出13、 ？節(jié)約存儲空間14、 (D)降低運算的時間復雜度15、 廣義表是線性表的推廣，它們之間的區(qū)別在于()。

16、17、116、17、18、19、20、21、22、23、24、填空A、B、C、D、能否使用子表能否使用原子項表的長度是否能為空在廣義表中，限制了表中成分遞歸，但沒有限制共享的是（）。純表再入表遞歸表線性表A、B、C、D、1、 n維數(shù)組中的每個元素都最多有（）個直接前趨。2、 對于一個一維數(shù)組A[12]，若一個數(shù)據(jù)元素占用字節(jié)數(shù)為S，首地址為1，則A[i]（i>=0）的存儲地址為（A），若首地址為D，則A[i]的存儲地址為（B）。3、 已知二維數(shù)組A[m][n]采用行優(yōu)先順序存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址LOC（A[0][0]），則A[i][j]的地址是（）。4、 在多維數(shù)組中，數(shù)據(jù)元素的存放地址直接可通過地址計算公式計算出。因此，數(shù)組是一種（）存取結(jié)構。5、 矩陣的壓縮存儲就是為多個相同的非零元素分配（）個存儲空間，不為零元素分配空間。6、 一般，特殊矩陣按規(guī)律壓縮存儲到一個向量中后，能（）存取。六樹選擇題1、 在樹中，互為堂兄弟的結(jié)點擁有相同的（）。2、 入、雙親3、 B、祖先4、 C、路徑5、 D、孩子6、 樹最適合用來表示。7、 A、有序數(shù)據(jù)元素8、 B、無序數(shù)據(jù)元素9、 C、元素之間具有分支層次關系的數(shù)據(jù)10、 D、元素之間無聯(lián)系的數(shù)據(jù)11、 已知二叉樹如下圖所示，此二叉樹的順序存儲結(jié)構是：（）。TOC\o"1-5"\h\z12、 OA13、 /14、 OC15、 /\16、 OFOG17、18、 A、123419、 | |III20、 |A|C|F|G|21、 1——1——1——1——122、23、 B、1234524、25、|4|A|C|F|G|26、27、28、 C、01234529、 iiiI II30、 | 4| A| C| |F|G|31、 1一1-一1一1-一1一1-一32、33、 D、0123434、 iiiiiI35、 |A|C||F|G|36、 1■一1-一1■一1-一1■一137、 在一棵高度為h的滿四叉樹中，結(jié)點總數(shù)為（）。38、 A、4"h-139、 B、（4"h-1）/240、 C、（4"h-1）/441、 D、4"h42、 若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為0的結(jié)點個數(shù)是（）。TOC\o"1-5"\h\z43、 A.944、 B.1145、 C.1246、 D.不確定47、 按二叉樹的定義，具有3個結(jié)點的二叉樹有（）種。48、 A、3B、4C、5D、6填空1、 在樹中，度為（）的結(jié)點稱為葉子。2、 在樹中，除跟結(jié)點外，其他結(jié)點都有且只有一個（）結(jié)點。3、 有100個結(jié)點的樹有（）條邊。4、 若將樹中的每個結(jié)點的各子樹看成從左到右有次序，則該樹為（）樹。5、 一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0,要么是2。這棵二叉樹中度為2的結(jié)點有（）個。6、 深度為K的完全二叉樹至少有2"（k-1）個結(jié)點，至多有2"（k-1）-2個結(jié)點，若按自上而下，從左到右次序給結(jié)點編號（從1開始），則編號最小的葉子結(jié)點的編號是（）。七圖選擇1、 設G1=（V1,E1）和G2=（V2,E2）為兩個圖，如果V2包含V1，E2包含E1，則稱（）。2、 A、G1是G2的子圖3、 B、G1是G2的連通分量4、 C、G2是G1的連通分量5、 D、G2是G1的子圖6、 設有6個結(jié)點的無向圖，該圖至少應有（）條邊才能確保是一個連通圖。7、 A、5B、6C、7D、88、 下面關于圖的存儲的敘述中，哪一個是正確的。（）9、A.用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關，與邊數(shù)無關9、A.10、 B.用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，與結(jié)點個數(shù)無關11、 C.用鄰接表存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關，與邊數(shù)無關12、 D.用鄰接表存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，與結(jié)點個數(shù)無關13、 在圖的表示法中，表示形式唯一的是（）。14、 A、鄰接矩陣表示法15、 B、鄰接表表示法16、 C、逆鄰接表表示法17、 D、鄰接表和逆鄰接表表示法18、 （）適合用鄰接表表示。19、 A、稠密圖20、 B、有向完全圖21、 C、無向完全圖22、 D、稀疏圖23、 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（）.24、 （1）A、NB.n+1C.n-1D.n+e填空1、 具有n個頂點的有向圖最多有（）條邊。2、 具有n個頂點的強連通圖最少有（）條邊。3、 有向圖的鄰接表表示適于求頂點的（）。4、 有向圖的鄰接矩陣表示中，第i（）上非零元素的個數(shù)為頂點vi的入度。5、 對有向圖進行深度優(yōu)先搜索時，若該圖不是（），可得到一個深度優(yōu)先搜索生辰森林。6、 當對用（）表示法表示的圖，從某指定頂點作為初始點進行廣度優(yōu)先搜索，得到的廣度優(yōu)先搜索序列唯一。八排序選擇1、 內(nèi)部排序和外部排序的區(qū)別不在于（）。2、 A、待排序文件的大小3、 B、有無內(nèi)外存的交換4、 C、是否在內(nèi)存中排序5、 D、可采用的排序策略評價排序算法好壞的標準主要是（）。6、 A、執(zhí)行時間7、 B、輔助空間8、 C、算法本身的復雜度9、 D、執(zhí)行時間和所需的輔助空間10、 “就地排序”指排序中，需要的輔助空間為（）。11、 A、0（1）12、 B、013、 C、0（n）14、 D、0（n"2）15、 一個待排序文件的關鍵字如下：16、 26530175112993786374269407643817、 經(jīng)過（）趟直接插入排序后可得到如下序列：69407643818、 129265301751937863742694076438TOC\o"1-5"\h\z19、 A120、 B221、 C322、 D4若用冒泡排序?qū)﹃P鍵字序列{18,16,14,12,10，8}進行從小到大的排序，所要進行的關23、 鍵字比較總次數(shù)為（）。24、 A、1025、 B、1526、 C、2127、 D、3428、 用某種排序方法對線性表（25，84，21，47，15，27，68，35，20）進行排序時，結(jié)點序列的變化情況如下：29、(1)25842147152768352030、(2)20152125472768358431、(3)15202125352747688432、(4)15202125273547688433、那么，所米用的排序方法是（）。34、A、直接插入排序B、希爾排序C、冒泡排序D、快速排序填空1、 若待排序的文件中存在多個關鍵字相同的記錄，經(jīng)過某種排序方法排序后，具有相同關鍵字的記錄間的相對位置保持不變。則這種排序方法是（）的排序方法。2、 當增量為1時，該趟希爾排序與（）排序基本一致。3、 最壞情況，在第i趟直接插入排序中，要進行（）次關鍵字的比較。4、 兩個序列如下：5、 L1={25，57，48，37，92，86，12，33}6、 L2={25，37，33，12，48，57，86，92}7、 用冒泡排序方法分別對序列L1和L2進行排序，交換次序較少的是序列（）。8、 在（）堆中，所有雙親結(jié)點的關鍵字的值大于它們孩子的關鍵字的值。9、 直接選擇排序的總的關鍵字比較次數(shù)與（）無關。九查找選擇1、通常把查找過程中對關鍵字需要執(zhí)行的（）作為衡量一個查找算法效率優(yōu)劣的標準。2、 A、BST3、 B、 WPLTOC\o"1-5"\h\z4、 C、 ASL5、 D、 BFS6、 用二分法在有序表{3，4，10，13，33，42，46，63，76，78，95，96，120}中查找95時，要進行的比較次數(shù)為（）。7、 A、28、 B、39、 C、410、 D、511、 線性表必須是（），才能進行二分查找。

12、13、112、13、14、15、16、17、18、19、20、21、A、B、C、D、用向量存儲的線性表用鏈表存儲的有序表用鏈表存儲的線性表用向量存儲的有序表二分查找過程可以用（1）樹描述，該樹的形態(tài)只與（2）有關。1-二叉查找樹2-表中元素個數(shù)1-二叉判定樹2-表中元素關鍵字的取值1-二叉比較樹2-表中元素個數(shù)1-二叉樹2-表中元素關鍵字的取值D長度為12的按關鍵字有序的查找表采用順序組織方式，若用二分查找方法，則在等概率情況下，查找不成功的平均查找長度是（）。22、 A、37/12B、63/13C、39/12D、49/1323、 在表長是N的順序表中，實施順序查找，在查找不成功時，與關鍵字比較的次數(shù)（）。24、 A、NB、1C、N+1D、N-1填空1、 若在查找的同時對表作修改，則相應的表稱（）。2、 對表長為n的鏈表進行順序查找，等概率情況下，查找成功的平均查找長度