數(shù)據(jù)結(jié)構(gòu) 答案

第3章數(shù)據(jù)結(jié)構(gòu)一、選擇題圖形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種—B。A一對多關(guān)系B多對多關(guān)系C多對一關(guān)系D一對一關(guān)系算法分析的目的是C。A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進D分析算法的易懂性和文檔性算法的時間復(fù)雜度與A有關(guān)。A問題規(guī)模B計算機硬件性能C程序設(shè)計語言的類型或版本D算法設(shè)計者的水平有下面的算法段：for(i=0;i<n;i++)k++;其時間復(fù)雜度為B。0(1) B.0(n) C.O(log2n) D.0(n2)計算機算法必須具備輸入、輸出和C―。A、計算方法 B、排序方法C、解決問題的有限運算步驟 D、程序設(shè)計法是數(shù)據(jù)的基本單位。A、數(shù)據(jù)結(jié)構(gòu) B、數(shù)據(jù)元素 C、數(shù)據(jù)項 D、數(shù)據(jù)類型7.下面，對非空線性表特點的論述，C—是正確的。所有結(jié)點有且只有一個直接前驅(qū)所有結(jié)點有且只有一個直接后繼每個結(jié)點至多只有一個直接前驅(qū)，至多只有一個直接后繼結(jié)點間是按照1對多的鄰接關(guān)系來維系其邏輯關(guān)系的8.在順序表中，只要知道 D ，就可以在相同的時間內(nèi)求出任一結(jié)點的存儲地址。A、開始結(jié)點小B、終端結(jié)點C、向量大小D、基地址和結(jié)點大9.在非空線性表中，有且只有一個直接前驅(qū)和一個直接后繼的結(jié)點是__C―。A、開始結(jié)點B、終端結(jié)點C、內(nèi)部結(jié)點D、所有結(jié)點10.順序表中邏輯上相鄰的結(jié)點的物理位置為 A___。A、一定相鄰B、不必相鄰C、按某種規(guī)律排列。、不要求一個向量第一個元素的存儲地址是100，每個元素的長度為2,則第5個元素的地址是B。A110B108C100D120鏈表不具有的特點是A。A、可以隨機訪問任何一個元素 B、插入和刪除元素不需要移動元素C、不必事先估計存儲空間 D、所需的存儲空間和鏈表長度無關(guān)數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種D。A順序存儲線性表 B非順序存儲非線性表C順序存儲非線性表D非順序存儲線性表鏈接存儲的存儲結(jié)構(gòu)所占存儲空間AA分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B只有一部分，存放結(jié)點值C只有一部分，存儲表示結(jié)點間關(guān)系的指針D分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)線性表L在B情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。A需經(jīng)常修改L中的結(jié)點值B需不斷對L進行刪除插入CL中含有大量的結(jié)點DL中結(jié)點結(jié)構(gòu)復(fù)雜線性鏈表不具有的特點是A_。A隨機訪問B不必事先估計所需存儲空間大小C插入與刪除時不必移動元素D所需空間與線性表長度成正比在長度為n的順序表中，往其第i個元素（lWiWn）之前插入一個新的元素時，需要往后移動B—個元素。n-iB.n-i+1C.n-i-1D.i在長度為n的順序表中，刪除第i個元素（1WiWn）時，需要往前移動—A個元素。n-iB.n-i+1C.n-i-1D.i往一個順序表的任一結(jié)點前插入一個新數(shù)據(jù)結(jié)點時，平均而言，需要移動B―個結(jié)點。nB.n/2C.n+1D.（n+1）/2帶表頭結(jié)點的單鏈表Lk_h為空的判定條件是B。A.Lk_h==NULL B.Lk_h->Next==NULLC.Lk_h->Next==Lk_hD.Lk_h!=NULL在一個單鏈表中，已知qtr所指結(jié)點是ptr所指結(jié)點的直接前驅(qū)?，F(xiàn)要在qtr所指結(jié)點和ptr所指結(jié)點之間插入一個rtr所指的結(jié)點，要執(zhí)行的操作應(yīng)該是__C 。rtr->Next=ptr->Next;ptr->Next=rtr;ptr->Next=rtr->Next;qtr->Next=rtr; rtr->Next=ptr;ptr->Next=rtr; rtr->Next=qtr->Next;在單鏈表中，如果指針ptr所指結(jié)點不是鏈表的尾結(jié)點，那么在ptr之后插入由指針qtr所指結(jié)點的操作應(yīng)該是B。

A.qtr->Next=ptr;ptr->Next=qtr;CA.qtr->Next=ptr;ptr->Next=qtr;C.qtr->Next=ptr->Next;ptr=qtr;23.棧與一般線性表的區(qū)別在于A、數(shù)據(jù)元素的類型不同C、數(shù)據(jù)元素的個數(shù)qtr->Next=ptr->Next;ptr->Next=qtr;D.ptr->Next=qtr;qtr->Next=ptr;__B 。B、運算是否受限制D、邏輯結(jié)構(gòu)不同棧的插入和刪除操作在A進行。A、棧頂 B、棧底 C、任意位置 D、指定位置一個順序棧一旦被聲明，其占用空間大小A。A、已固定 B、可以變化C、不能固定D、動態(tài)變化設(shè)有一個順序棧S,元素si,s2,s3,s4,s5,s6依次進棧，如果6個元素的出棧順序為s2,s3,s4,s6,s5,si，則順序棧的容量至少應(yīng)為 B A2B3C4D5若讓元素1,2,3依次進棧，則出棧次序不可能出現(xiàn)C種情況。A3,2,1B2,1,3C3,1,2D1,3,2一個棧的入棧序列是abcde，則棧不可能的輸出序列是―C―。A、edcba B、decba C、dceabD、abcde隊列的插入操作是在B進行的。A、隊首 B、隊尾 C、隊前 D、隊后隊列的刪除操作是在―A進行的。A、隊首 B、隊尾 C、隊前 D、隊后為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是AOA.隊列B.棧C.線性表D.有序表下列關(guān)于線性表、棧和隊列的敘述，錯誤的是A。線性表是給定的n(n必須大于零)個元素組成的序列。線性表允許在表的任何位置進行插入和刪除操作。棧只允許在一端進行插入和刪除操作。隊列允許在一端進行插入，在令一端進行刪除。一個隊列的入隊序列是1,2,3,4，則隊列的確定輸出序列―BA.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列,且當前rear和front的值分別為0和3.當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為___B A.1和5B.2和4 C.4和2 D.5和1最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是B。A.(rear+1)%n==frontB.rear==frontrear+1==front D.(rear-l)%n==front循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為D。rear=rear+1 B.rear=(rear+1)%(m-1)rear=(rear+1)%m D.rear=(rear+1)%(m+1)數(shù)組Q[n]用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n，計算隊列中元素的公式為__D__Ar—f;B(n+f—r)%n;Cn+r—f; D(n+r—f)%n一個長度為50的循環(huán)隊列中，隊頭指針(front)等于41，隊尾指針(rer)等于20,則隊列中有—D個元素。A41B20C21D2939,二維數(shù)組M,行下標i的范圍從0到4,列下標j的范圍從0到5,M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素B的起始地址相同。A、M[2]⑷ B、M[3北4] C、M[3][5]D、Mee數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是__CA、80 B、100C、240 D、270有一個二維數(shù)組[m][n]，按行存儲，假設(shè)[0][0]存放位置在644（10進制），[2][2]存放位置在676（10進制），每個元素占一個空間，則[4][5]在__C位置。A692B626C709D724數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為___C___。A、SA+141 B、SA+144C、SA+222D、SA+225在具有100個結(jié)點的樹中，其邊的數(shù)目為—C―。A101B100C99D98按照樹的定義，具有3個結(jié)點的樹有A種形態(tài)。A、2 B、3 C、4 D、5按照二叉樹的定義，具有3個結(jié)點的二叉樹有__D__種形態(tài)。A、2 B、3 C、4 D、5下面說法中，_。__是正確的。A、 度為2的樹是二叉樹B、 度為2的有序樹是二叉樹C、 子樹有嚴格左、右之分的樹是二叉樹D、 子樹有左、右之分、且度不超過2的樹是二叉樹下面的說法中，―C—是正確的。A、二叉樹的度為2 B、二叉樹中任意一個結(jié)點的度都為2C、任何二叉樹中結(jié)點度可以小于2 D、任何二叉樹中至少有一個結(jié)點的度為2若一棵二叉樹有10個度為2的結(jié)點，則該二叉樹的葉結(jié)點的個數(shù)B。A、9 B、11 C、12 D、不確定具有10個葉結(jié)點的二叉樹中有A個度為2的結(jié)點。A、9 B、11 C、12 D、不確定若一棵滿二叉樹有2047個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)為B。A、512B、1024 C、2048D、4096具有65個結(jié)點的完全二叉樹的高度為B。A8B7C6D5深度為5的二叉樹至多有B個結(jié)點。A、16B、31C、15D、30在一棵樹的左孩子-右兄弟表示法中，一個結(jié)點的右孩子是該結(jié)點的A結(jié)點。A、兄弟B、父子 C、祖先D、子孫在一棵樹的雙親表示中，每個數(shù)據(jù)元素包含B_個域。A、1 B、2 C、3 D、4對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用—C—次序的遍歷實現(xiàn)編號。A.先序 B.中序 C.后序 D.從根開始按層次遍歷56.某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是

B__A.E,G,F,A,C,D,BB.E,A,C,B,D,G,FC.E,A,G,C,F,B,DD.上面的都不對二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹根的右子樹的根是CA、E B、F C、G D、H把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是A。A唯一的 B有多種，但根結(jié)點都沒有左孩子C有多種 D有多種，但根結(jié)點都沒有右孩子在一個圖中，所有頂點的度數(shù)之和等于所有邊的數(shù)目的。倍。A、1/2B、1C、2D、4在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B倍。A、1/2B、1C、2D、4一個具有n個頂點的無向圖最多有A條邊。A、nX(n—1)/2 B、nX(n—1)C、nX(n+1)/2D、nXn一個具有n個頂點的有向圖最多有B條邊。A、nX(n—1)/2 B、nX(n—1)C、nX(n+1)/2D、nXn一個無向圖采用鄰接矩陣存儲方法，其鄰接矩陣一定是一個A。A、對稱矩陣B、對角矩陣 C、三角矩陣 D、稀疏矩陣具有n個頂點、e條邊的無向圖采用鄰接矩陣存儲方法。則鄰接矩陣的大小為__D__。A、nBA、nB、(n-1)X(n+1)C、(n+1)X(n+1)D、nXn通常把查找過程中對關(guān)鍵字需要執(zhí)行的C作為衡量一個查找算法效率優(yōu)劣的標準。A、BST B、WPLC、ASLD、BFS在表長是N的順序表中，實施順序查找，在查找不成功時，與關(guān)鍵字比較的次數(shù)—C。A、N B、1C、N+1 D、N-1一個順序存儲結(jié)構(gòu)的線性表有255個記錄，采用線性查找法（也稱順序查找法）查找該表，在等概率條件下的平均查找長度為A。A128B127C126D255在表長為n的鏈表中進行線性查找，它的平均查找長度為B.AASL=n BASL=（n+l）/2CASL=n/2DASL^log2（n+l）-l69.線性表必須是，69.線性表必須是，A、用數(shù)組存儲的線性表C、用鏈表存儲的線性表B、用數(shù)組存儲的有序表D、用鏈表存儲的有序表70,有一個順序表為｛1，3折半查找值為82的結(jié)點時，100｝，當12，32，41，45，62，70,有一個順序表為｛1，3折半查找值為82的結(jié)點時，100｝，當次比較后查找成功。71.鏈表適用于A71.鏈表適用于A順序B A二分法查找C順序、，也能二分法D隨機折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素A比較大小。A28，6，12，20B38,12,20C20D38,70,88,100折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中A比較大小，查找結(jié)果是失敗。A20，70，30，50B30，88，70，50C20，50D30，88，50對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較C次關(guān)鍵字。A3B4C5D6散列查找是由鍵值__B確定散列表中的位置，并進行存儲或查找。A、本身B、散列函數(shù)值 C、相反數(shù)。、平方設(shè)某散列表長度為100,散列函數(shù)H(k)k%p,則P通常情況下最好選擇CA、91B、93 C、97D、99哈希表的地址區(qū)間為0-17,哈希函數(shù)為H(k)=kmod17。采用線性探測法處理沖突，并將關(guān)鍵字序列｛26,25,72,38,8,18,59｝依次存儲到哈希表中。那么，元素59存放在哈希表中的地址是D。A.8 B.9C.10 D.11給定n=8，對數(shù)組R中的8個元素做升序排列，數(shù)組R中的關(guān)鍵字為：(8,3,2,1，7,4,6,5)，則簡單選擇排序過程中第二趟排序結(jié)束后關(guān)鍵字的順序是___A A1,2,3,8,7,4,6,5B1,3,2,8,7,4,6,5C1,2,3,4,5,6,8,7D1,2,3,4,5,6,7,8每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做—A排序。人、插入B、交換C、選擇D、歸并有關(guān)鍵字序列｛20,6,15,7,3｝,作升序排列，則線性插入排序過程中第三趟排序結(jié)束后關(guān)鍵字的順序是___C___。A20，6，15，7，3B6，20，15，7，3C6，15，20，7，3D6，7，15，20，3在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是CA順序查找B折半查找C散列查找D線性查找在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是AA訪問第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將n個結(jié)點從小到大排序數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的數(shù)據(jù)元素的方法以及它們之間的A和運算等的學科。A、結(jié)構(gòu) B、關(guān)系C、運算D、算法算法的計算量的大小稱為計算的B。A、效率 B、復(fù)雜性 C、現(xiàn)實性D、難度以下數(shù)據(jù)結(jié)構(gòu)中，A是非線性數(shù)據(jù)結(jié)構(gòu)A、樹 B、字符串C、隊D、棧線性表元素之間的關(guān)系是A。A、一對一B、一對多C、多對多D、無關(guān)系下列四種基本的邏輯結(jié)構(gòu)中，結(jié)構(gòu)結(jié)點間不存在任何邏輯聯(lián)系的是A。A、集合 B、線性結(jié)構(gòu) C、樹形結(jié)構(gòu)D、圖形結(jié)構(gòu)―D不是線性表的特性。A、 除第一個元素之外，每個元素都有前驅(qū)B、 除最后一個元素外，每個元素都有后繼C、 線性表是數(shù)據(jù)的有限序列D、 線性表的長度為n，且n尹0下列關(guān)于線性表存儲結(jié)構(gòu)的敘述中正確的是D。A、 鏈表中的元素一定存放在不連續(xù)的存儲空間里B