數(shù)據(jù)結構 答案

第3章數(shù)據(jù)結構一、選擇題圖形結構是數(shù)據(jù)元素之間存在一種—B。A一對多關系B多對多關系C多對一關系D一對一關系算法分析的目的是C。A找出數(shù)據(jù)結構的合理性 B研究算法中的輸入和輸出的關系C分析算法的效率以求改進D分析算法的易懂性和文檔性算法的時間復雜度與A有關。A問題規(guī)模B計算機硬件性能C程序設計語言的類型或版本D算法設計者的水平有下面的算法段：for(i=0;i<n;i++)k++;其時間復雜度為B。0(1) B.0(n) C.O(log2n) D.0(n2)計算機算法必須具備輸入、輸出和C―。A、計算方法 B、排序方法C、解決問題的有限運算步驟 D、程序設計法是數(shù)據(jù)的基本單位。A、數(shù)據(jù)結構 B、數(shù)據(jù)元素 C、數(shù)據(jù)項 D、數(shù)據(jù)類型7.下面，對非空線性表特點的論述，C—是正確的。所有結點有且只有一個直接前驅所有結點有且只有一個直接后繼每個結點至多只有一個直接前驅，至多只有一個直接后繼結點間是按照1對多的鄰接關系來維系其邏輯關系的8.在順序表中，只要知道 D ，就可以在相同的時間內求出任一結點的存儲地址。A、開始結點小B、終端結點C、向量大小D、基地址和結點大9.在非空線性表中，有且只有一個直接前驅和一個直接后繼的結點是__C―。A、開始結點B、終端結點C、內部結點D、所有結點10.順序表中邏輯上相鄰的結點的物理位置為 A___。A、一定相鄰B、不必相鄰C、按某種規(guī)律排列。、不要求一個向量第一個元素的存儲地址是100，每個元素的長度為2,則第5個元素的地址是B。A110B108C100D120鏈表不具有的特點是A。A、可以隨機訪問任何一個元素 B、插入和刪除元素不需要移動元素C、不必事先估計存儲空間 D、所需的存儲空間和鏈表長度無關數(shù)據(jù)結構反映了數(shù)據(jù)元素之間的結構關系。鏈表是一種D。A順序存儲線性表 B非順序存儲非線性表C順序存儲非線性表D非順序存儲線性表鏈接存儲的存儲結構所占存儲空間AA分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B只有一部分，存放結點值C只有一部分，存儲表示結點間關系的指針D分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù)線性表L在B情況下適用于使用鏈式結構實現(xiàn)。A需經(jīng)常修改L中的結點值B需不斷對L進行刪除插入CL中含有大量的結點DL中結點結構復雜線性鏈表不具有的特點是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往一個順序表的任一結點前插入一個新數(shù)據(jù)結點時，平均而言，需要移動B―個結點。nB.n/2C.n+1D.（n+1）/2帶表頭結點的單鏈表Lk_h為空的判定條件是B。A.Lk_h==NULL B.Lk_h->Next==NULLC.Lk_h->Next==Lk_hD.Lk_h!=NULL在一個單鏈表中，已知qtr所指結點是ptr所指結點的直接前驅。現(xiàn)要在qtr所指結點和ptr所指結點之間插入一個rtr所指的結點，要執(zhí)行的操作應該是__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所指結點不是鏈表的尾結點，那么在ptr之后插入由指針qtr所指結點的操作應該是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、邏輯結構不同棧的插入和刪除操作在A進行。A、棧頂 B、棧底 C、任意位置 D、指定位置一個順序棧一旦被聲明，其占用空間大小A。A、已固定 B、可以變化C、不能固定D、動態(tài)變化設有一個順序棧S,元素si,s2,s3,s4,s5,s6依次進棧，如果6個元素的出棧順序為s2,s3,s4,s6,s5,si，則順序棧的容量至少應為 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ù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結構應該是AOA.隊列B.棧C.線性表D.有序表下列關于線性表、棧和隊列的敘述，錯誤的是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ù)存放在存儲器內，存放該數(shù)組至少需要的單元數(shù)是__CA、80 B、100C、240 D、270有一個二維數(shù)組[m][n]，按行存儲，假設[0][0]存放位置在644（10進制），[2][2]存放位置在676（10進制），每個元素占一個空間，則[4][5]在__C位置。A692B626C709D724數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8,列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內，該數(shù)組按行存放時，元素A[8][5]的起始地址為___C___。A、SA+141 B、SA+144C、SA+222D、SA+225在具有100個結點的樹中，其邊的數(shù)目為—C―。A101B100C99D98按照樹的定義，具有3個結點的樹有A種形態(tài)。A、2 B、3 C、4 D、5按照二叉樹的定義，具有3個結點的二叉樹有__D__種形態(tài)。A、2 B、3 C、4 D、5下面說法中，_。__是正確的。A、 度為2的樹是二叉樹B、 度為2的有序樹是二叉樹C、 子樹有嚴格左、右之分的樹是二叉樹D、 子樹有左、右之分、且度不超過2的樹是二叉樹下面的說法中，―C—是正確的。A、二叉樹的度為2 B、二叉樹中任意一個結點的度都為2C、任何二叉樹中結點度可以小于2 D、任何二叉樹中至少有一個結點的度為2若一棵二叉樹有10個度為2的結點，則該二叉樹的葉結點的個數(shù)B。A、9 B、11 C、12 D、不確定具有10個葉結點的二叉樹中有A個度為2的結點。A、9 B、11 C、12 D、不確定若一棵滿二叉樹有2047個結點，則該二叉樹中葉結點的個數(shù)為B。A、512B、1024 C、2048D、4096具有65個結點的完全二叉樹的高度為B。A8B7C6D5深度為5的二叉樹至多有B個結點。A、16B、31C、15D、30在一棵樹的左孩子-右兄弟表示法中，一個結點的右孩子是該結點的A結點。A、兄弟B、父子 C、祖先D、子孫在一棵樹的雙親表示中，每個數(shù)據(jù)元素包含B_個域。A、1 B、2 C、3 D、4對二叉樹的結點從1開始進行連續(xù)編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用—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把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是A。A唯一的 B有多種，但根結點都沒有左孩子C有多種 D有多種，但根結點都沒有右孩子在一個圖中，所有頂點的度數(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通常把查找過程中對關鍵字需要執(zhí)行的C作為衡量一個查找算法效率優(yōu)劣的標準。A、BST B、WPLC、ASLD、BFS在表長是N的順序表中，實施順序查找，在查找不成功時，與關鍵字比較的次數(shù)—C。A、N B、1C、N+1 D、N-1一個順序存儲結構的線性表有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的結點時，100｝，當12，32，41，45，62，70,有一個順序表為｛1，3折半查找值為82的結點時，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比較大小，查找結果是失敗。A20，70，30，50B30，88，70，50C20，50D30，88，50對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較C次關鍵字。A3B4C5D6散列查找是由鍵值__B確定散列表中的位置，并進行存儲或查找。A、本身B、散列函數(shù)值 C、相反數(shù)。、平方設某散列表長度為100,散列函數(shù)H(k)k%p,則P通常情況下最好選擇CA、91B、93 C、97D、99哈希表的地址區(qū)間為0-17,哈希函數(shù)為H(k)=kmod17。采用線性探測法處理沖突，并將關鍵字序列｛26,25,72,38,8,18,59｝依次存儲到哈希表中。那么，元素59存放在哈希表中的地址是D。A.8 B.9C.10 D.11給定n=8，對數(shù)組R中的8個元素做升序排列，數(shù)組R中的關鍵字為：(8,3,2,1，7,4,6,5)，則簡單選擇排序過程中第二趟排序結束后關鍵字的順序是___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、歸并有關鍵字序列｛20,6,15,7,3｝,作升序排列，則線性插入排序過程中第三趟排序結束后關鍵字的順序是___C___。A20，6，15，7，3B6，20，15，7，3C6，15，20，7，3D6，7，15，20，3在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是CA順序查找B折半查找C散列查找D線性查找在n個結點的順序表中，算法的時間復雜度是O(1)的操作是AA訪問第i個結點（1<i<n）和求第i個結點的直接前驅（2<i<n）B在第i個結點后插入一個新結點（1<i<n）C刪除第i個結點（1<i<n）D將n個結點從小到大排序數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的數(shù)據(jù)元素的方法以及它們之間的A和運算等的學科。A、結構 B、關系C、運算D、算法算法的計算量的大小稱為計算的B。A、效率 B、復雜性 C、現(xiàn)實性D、難度以下數(shù)據(jù)結構中，A是非線性數(shù)據(jù)結構A、樹 B、字符串C、隊D、棧線性表元素之間的關系是A。A、一對一B、一對多C、多對多D、無關系下列四種基本的邏輯結構中，結構結點間不存在任何邏輯聯(lián)系的是A。A、集合 B、線性結構 C、樹形結構D、圖形結構―D不是線性表的特性。A、 除第一個元素之外，每個元素都有前驅B、 除最后一個元素外，每個元素都有后繼C、 線性表是數(shù)據(jù)的有限序列D、 線性表的長度為n，且n尹0下列關于線性表存儲結構的敘述中正確的是D。A、 鏈表中的元素一定存放在不連續(xù)的存儲空間里B