數(shù)據(jù)結(jié)構(gòu)答疑材料

數(shù)據(jù)構(gòu)造答疑材料1、數(shù)據(jù)構(gòu)造是一門爭論 計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。 〔〕A、數(shù)值 B、非數(shù)值 C、字符 答案：B2、快速排序的分區(qū)結(jié)果唯一嗎？答案：不唯一，取決于樞軸元素的選取。3、小頂堆的堆頂元素是序列中 〔〕A、最大的元素B、次大的元素C、最小的元素答案：C4s1=“GOOD”,s2=“BY12〔〕a、BYEGOODb、GOODBYE、BYEDGOODd、GOODBYEd5、在一個(gè)單鏈表中，pps結(jié)點(diǎn)，則執(zhí)行?答案：s->next=p->next;p->next=s數(shù)據(jù)的規(guī)律構(gòu)造中非線性構(gòu)造有A、集合B、線形構(gòu)造C、樹形構(gòu)造E、鏈?zhǔn)綐?gòu)造答案：C樹形構(gòu)造，D網(wǎng)狀構(gòu)造線性構(gòu)造中元素之間存在 關(guān)系，樹形構(gòu)造中元素之間存在 關(guān)系，圖形構(gòu)造中元素之間存在 關(guān)系A(chǔ)、一對一，多對多，一對多B、一對多，一對一，多對多C、一對一，一對多，多對多E、以上都不正確答案：C、一對一，一對多，多對多廣義表〔〕a〕的表尾是 〔〕A、a B、b C〔a〕 D、((a))答案：C算法有哪些重要特性?答案：1．有窮性2．確定性3．可行性4．有輸入5．有輸出數(shù)據(jù)構(gòu)造是一門爭論什么內(nèi)容的學(xué)科？答案：數(shù)據(jù)構(gòu)造是一門爭論在非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。后，輸出序列是 a、1、2、3、4、5b2、3、5、4、1c、5、4、3、2、1d、1、3、4、2、5答案：b2、3、5、4、1解析：1，2進(jìn)棧，最先出棧確實(shí)定是2。兩個(gè)串相等的條件是A、長度相等C、存儲(chǔ)位置一樣E、以上都是挨次查找適用于存儲(chǔ)構(gòu)造為 A、散列C、壓縮．設(shè)哈希表長，哈希函數(shù)314的地址是選項(xiàng):c、3答案：b11〔1〕最常用的哈希函數(shù)構(gòu)造方法為B、直接定址法C、折疊法答案：A一個(gè)鏈?zhǔn)疥?duì)列中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算是 A、r->next=sB、r=ss=r->nextE、s->next=r答案：ABa,(x,y),((x)))的長度是 ,深度是 A、33B、２３C、３２D、４３E、３４答案：A、 3 3LSLS的長度;LSLS的深度。在一個(gè)單鏈表中，p所指結(jié)點(diǎn)，假設(shè)在p之后插入s結(jié)點(diǎn)，則執(zhí)行 A、s->next=p->nextBp->next=sC、p->nexts->nextD、p->next=sE、p->nextp->next->nextS為空的判定條件aS.top==S.baseb、S==S.basec、S.top==S答案：a20?針的下一位置〔指環(huán)狀的下一位置〕上”作為隊(duì)列呈滿狀態(tài)的標(biāo)志。通常承受其次種方法。一個(gè)隊(duì)列的入隊(duì)序列是1、3、4、2，則隊(duì)列的首次輸出元素是 A、3 B、2 C、1 D、4答案：C計(jì)算機(jī)算法指的是〔1，它必需具備〔2〕A．計(jì)算方法 B.排序方法 C.解決問題的步驟序列 D.調(diào)度方法A．可執(zhí)行性、可移植性、可擴(kuò)大性 B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性 D.易讀性、穩(wěn)定性、安全性答案：C. B.從規(guī)律上可以把數(shù)據(jù)構(gòu)造分為〔 〕兩大類。A．動(dòng)態(tài)構(gòu)造、靜態(tài)構(gòu)造 B．挨次構(gòu)造、鏈?zhǔn)綐?gòu)造C．線性構(gòu)造、非線性構(gòu)造 等構(gòu)造、構(gòu)造型構(gòu)造答案：C．答案：四種表示方法挨次存儲(chǔ)方式。數(shù)據(jù)元素挨次存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的規(guī)律關(guān)系。存儲(chǔ)密度大，但有些操作〔如插入、刪除〕效率較差。〔至少一個(gè)〕指針。指針反映數(shù)據(jù)元素間的規(guī)律關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作〔如插入、刪除等，但存儲(chǔ)空間開銷大〔用于指針，另外不能折半查找等。指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置〔下標(biāo)〕或存儲(chǔ)區(qū)間端點(diǎn)〔下標(biāo)，兼有靜態(tài)和動(dòng)態(tài)特性。散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能挨次存取，也不能折半存取。n個(gè)〔〕的有限序列〔0。A．表元素 B．字符答案：CC．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)項(xiàng)E．信息項(xiàng)假設(shè)長度為n的線性表承受挨次存儲(chǔ)構(gòu)造在其第i個(gè)位置插入一個(gè)元素的算法的時(shí)間簡單度〔 〕(1<=i<=n+1)。A.O(0) B.O(1) C.O(n) D.O(n2)答案：C線性表有兩種存儲(chǔ)構(gòu)造：一是挨次表，二是鏈表。試問：那么應(yīng)承受哪種存儲(chǔ)構(gòu)造？為什么？〔1〕選鏈?zhǔn)酱鎯?chǔ)構(gòu)造。它可動(dòng)態(tài)申請內(nèi)存空間，不受表長度〔即表中元素個(gè)數(shù)〕O1?！?〕〔1。假設(shè)較頻繁地對一個(gè)線性表進(jìn)展插入和刪除操作，該線性表宜承受何種存儲(chǔ)構(gòu)造？為什么？在鏈?zhǔn)酱鎯?chǔ)構(gòu)造中插入和刪除操作不需要移動(dòng)元素。線性構(gòu)造包括 、 、 和 。線性表的存儲(chǔ)構(gòu)造分成 和 答案：線性表 棧 隊(duì)列 串 挨次存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造對于棧操作數(shù)據(jù)的原則是〔 。A.先進(jìn)先出 B.后進(jìn)先出 C.后進(jìn)后出 D.不分挨次答案：B.。A.不確定 B.n-i+1 C. i D.n-i答案：B素6，5，4，3，2，1的挨次進(jìn)棧，問以下哪一個(gè)不是合法的出棧序列？〔 〕A.543612 B.453126C.346521 D.234156答案：C.棧和隊(duì)列的共同點(diǎn)是〔 。A.都是先進(jìn)先出 B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素 D.沒有共同點(diǎn)答案：C推斷：棧與隊(duì)列是一種特別操作的線性表〔 答案：√推斷：棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制〔 〕答案：√名詞解釋：棧。答案：棧是只準(zhǔn)在一端進(jìn)展插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最終插入的元素最先刪除，故棧也稱后進(jìn)先出〔LIFO〕表。名詞解釋：隊(duì)列最先插入隊(duì)的元素最先離開〔刪除，故隊(duì)列也常稱先進(jìn)先出〔〕表。假設(shè)元素的進(jìn)棧序列為：A、B、C、D、E，運(yùn)用棧操作，能否得到出棧序列B、C、A、E、DD、B、A、C、E？為什么？答案：能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：假設(shè)出棧序列以DA、BCC是棧頂元素，BAC出棧，故D、B、A、C、E出棧序列。39、什么叫串的模式匹配算法答案：就是給定一個(gè)串和子串，定位字串在串中位置的算法。下面關(guān)于串的的表達(dá)中，哪一個(gè)是不正確的？〔 〕串是字符的有限序列 B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以承受挨次存儲(chǔ)，也可以承受鏈?zhǔn)酱鎯?chǔ)答案：B串的長度是指〔 〕串中所含不同字母的個(gè)數(shù) B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù) 中所含非空格字符的個(gè)數(shù)答案：B2s=“IAMASTUDENT,＝？A、11B、12C、14空格串是指 (1) ，其長度等于 (2) 。由空格字符〔ASCII值32〕所組成的字符串 (2)空格個(gè)數(shù)串是一種特別的線性表，其特別性表現(xiàn)在 (1) ；串的兩種最根本的存儲(chǔ)方式是 (2) 、 (3) 兩個(gè)串相等的充分必要條件是 (4) 。描述以下概念的區(qū)分：空格串與空串答案：空格是一個(gè)字符，其ASCII碼值是32。空格串是由空格組成的串，其長度等于空格的個(gè)數(shù)?？沾遣缓魏巫址拇?，即空串的長度是零。46、廣義表有兩個(gè)特別的根本運(yùn)算取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對空表操作。廣義表〔〕的表頭是〔 ，表尾是〔 。Aa B.〔〕 C.〔a,b,c,d〕 答案：C廣義表〔a,(b,c),d,e〕的表頭為〔 。A.a B.a,(b,c) C.(a,(b,c)) D.(a)答案：A49、廣義表〔a,b,c,d〕的表頭是 ，表尾是 A、bC、aE、b,c,d答案：B〔a〕 后綴形式為ABC*+DE/-，其前綴形式為( )A．-A+B*C/DE B.-A+B*CD/E C．-+*ABC/DE D.-+A*BC/DE答案：D51、假設(shè)承受孩子兄弟鏈表作為樹的存儲(chǔ)構(gòu)造，則樹的先根遍歷應(yīng)承受二叉樹的 A、層次遍歷B、先序遍歷C、中序遍歷答案：B5共性質(zhì)有關(guān)二叉樹以下說法正確的選項(xiàng)是〔 〕A．二叉樹的度為2 B．一棵二叉樹的度可以小于2二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2答案：B一棵樹高為K的完全二叉樹至少有〔 〕個(gè)結(jié)點(diǎn)A．2k–1 B.2k-1–1 C.2k-1 D.2k答案：C。A．CBEFDA B．FEDCBA CCBEDFA D．不定答案：A線索二叉樹是一種〔 〕構(gòu)造。A．規(guī)律 B．規(guī)律和存儲(chǔ) C．物理 性答案：C由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？〔 〕A．2 B．3 C．4 D．5答案：D并指出樹和二叉樹的主要區(qū)分。答案：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說〕可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)分有三：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使不允許為空〔個(gè)別書上允許為空。樹和二叉樹之間有什么樣的區(qū)分與聯(lián)系？答案：樹和二叉樹規(guī)律上都是樹形構(gòu)造，區(qū)分有以上題1所述三點(diǎn)。二叉樹不是樹的特例。請分析線性表、樹、廣義表的主要構(gòu)造特點(diǎn)，以及相互的差異與關(guān)聯(lián)。一個(gè)”元素；除第一個(gè)元素外，每個(gè)元素有唯一前驅(qū)；除最終一個(gè)元素外，每個(gè)元素有唯一后繼。樹是一種層次構(gòu)造，有且只有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以有多個(gè)子女，但只有一個(gè)雙親〔根無雙親義上說存在一〔雙親〕對多〔子女〕的關(guān)系。廣義表中的元素既可以是原子，也可以是子表，子表可以為它表共享。從表中套表意義上說，廣義表也是層次構(gòu)造。從規(guī)律上講，樹和廣義表均屬非線性構(gòu)造。但在1的樹，以及廣義表中的元素都是原數(shù)據(jù)對象。0的結(jié)點(diǎn)？答案：1563、假設(shè)有向圖含n個(gè)頂點(diǎn)及e條弧，則表示該圖的鄰接表中包含的弧結(jié)點(diǎn)個(gè)數(shù)為〔 〕A.nB.eC.2eD.n·eB一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為〔 。A．n-1 B．n C．n+1 D．nlogn；答案：A65．n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目〔。A．n*n Ｂ．n〔n＋１〕 C．n／2 D．n*〔n－l〕答案：D推斷一個(gè)無向圖是一棵樹的條件是 答案：有n個(gè)頂點(diǎn)，n-1條邊的無向連通圖頂點(diǎn)的無向圖，邊的總數(shù)最多為 答案：45求圖的最小生成樹有兩種算法， 于求稀疏圖的最小生成樹。答案：克魯斯卡爾nVnA表示，邊的權(quán)全是正數(shù)。請?jiān)谝韵聞澗€處填上正確表達(dá)。1．假設(shè)ij〕是邊，則〔〕的值等 ，假設(shè)ij〕不是邊，則〔〕的值是一比任何邊的權(quán) ，矩陣的對角線元素全為0?！?iA〔，〕置成 已包括進(jìn)生成樹，就把矩陣元素A〔i，j〕置成 。3．算法完畢時(shí)，相鄰矩陣中 的元素指出最小生成樹的 。答案：〔i，j〕邊上的權(quán)值 都大的數(shù) 〔2〕1 負(fù)值 〔3〕為負(fù) 邊n個(gè)頂點(diǎn)的有向連通圖最少有多少條邊？答案：n-1，n下面關(guān)于二分查找的表達(dá)正確的選項(xiàng)是( )表必需有序，表可以挨次方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)C.表必需有序，而且只能從小到大排列表必需有序且表中數(shù)據(jù)必需是整型，實(shí)型或字符型 D.表必需有序，且表只能以挨次方式存儲(chǔ)答案：DMOD13,散列地址為1的鏈中有〔 〕個(gè)記錄。A．1 B.2 C.3 D.4答案：D表中已有