2017年電大考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題填空題小抄
《2017年電大考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題填空題小抄》由會(huì)員分享,可在線閱讀,更多相關(guān)《2017年電大考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題填空題小抄(4頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
專(zhuān)業(yè)好文檔電大資料整理電大數(shù)據(jù)結(jié)構(gòu)復(fù)核習(xí)題(填空題)1、 在一個(gè)長(zhǎng)度為 n 的順序存儲(chǔ)結(jié)構(gòu)的線性表中,向第 i(1?i?n+1)個(gè)元素之前插入新元素時(shí),需向后移動(dòng) n-i+1 個(gè)數(shù)據(jù)元素。2、 從長(zhǎng)度為 n 的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第 i(1?i?n+1)個(gè)元素 ,需向前移動(dòng) n-i 個(gè)元素。3、 數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系,可分為 4 種邏輯結(jié)構(gòu): 集合 、 線性結(jié)構(gòu) 、 樹(shù)形結(jié)構(gòu) 、 圖狀結(jié)構(gòu) 。4、 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為 物理結(jié)構(gòu) 或 存儲(chǔ)結(jié)構(gòu) 。5、 除了第 1 個(gè)和最后一個(gè)結(jié)點(diǎn)外,其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為 線性結(jié)構(gòu) ,每個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為 非線性結(jié)構(gòu) 。6、 算法的 5 個(gè)重要特性是 有窮性 、 確定性 、 可形性 、 有零個(gè)或多個(gè)輸入 、 有零個(gè)或多個(gè)輸出 。7、 數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱(chēng)為 圖狀結(jié)構(gòu) 結(jié)構(gòu)。8、 數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱(chēng) 樹(shù)形結(jié)構(gòu) 結(jié)構(gòu)。9、 數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱(chēng)為 線性結(jié)構(gòu) 結(jié)構(gòu)。10、 要求在 n 個(gè)數(shù)據(jù)元素中找其中值最大的元素,設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為 n-1 和 O(n) 。11、 在一個(gè)單鏈表中 p 所指結(jié)點(diǎn)之后插入一個(gè) s 所指結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行__s->next=p->next;__和 p->next=s;的操作。12、 設(shè)有一個(gè)頭指針為 head 的單向循環(huán)鏈表,p 指向鏈表中的結(jié)點(diǎn),若 p->next= = head ,則 p 所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。13、 在一個(gè)單向鏈表中,要?jiǎng)h除 p 所指結(jié)點(diǎn),已知 q 指向 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。則可以用操作 q->next=p->next; 。14、 設(shè)有一個(gè)頭指針為 head 的單向鏈表,p 指向表中某一個(gè)結(jié)點(diǎn),且有 p->next= =NULL,通過(guò)操作 p->next=head; ,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。15、 每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的線性表叫 單鏈表 。16、 線性表具有 順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 兩種存儲(chǔ)結(jié)構(gòu)。17、 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的關(guān)系 存儲(chǔ)結(jié)構(gòu) 無(wú)關(guān),是獨(dú)立于計(jì)算機(jī)的。18、 在雙向循環(huán)鏈表的每個(gè)結(jié)點(diǎn)中包含 兩個(gè) 指針域,其中 next 指向它的 直接后繼 ,prior 指向它的 直接前驅(qū) ,而頭結(jié)點(diǎn)的 prior 指向 尾結(jié)點(diǎn) ,尾結(jié)點(diǎn)的 next 指向 頭結(jié)點(diǎn) 。19、 單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充,當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí),把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為 頭結(jié)點(diǎn)的指針 ;當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí),則把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為指向 指向第一個(gè)結(jié)點(diǎn)的指針 。20、 線性鏈表的邏輯關(guān)系時(shí)通過(guò)每個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序不再一致,而是一種 鏈?zhǔn)? 存儲(chǔ)結(jié)構(gòu),又稱(chēng)為 鏈表 。21、 棧是限定在表的一端進(jìn)行插入和刪除操作的線性表,又稱(chēng)為 后進(jìn)先出表 。22、 隊(duì)列的特性是 先進(jìn)先出表 。23、 往棧中插入元素的操作方式是:先 移動(dòng)棧頂指針 ,后 存入元素 。24、 刪除棧中元素的操作方式是:先 取出元素 ,后 移動(dòng)棧頂指針 。25、 循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針 下一個(gè) 位置,隊(duì)列是“滿”狀態(tài)專(zhuān)業(yè)好文檔電大資料整理26、 在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中,當(dāng)插入一個(gè)新的隊(duì)列元素時(shí),尾指針 增 1 ,當(dāng)刪除一個(gè)元素隊(duì)列時(shí),頭指針 增 1 。27、 循環(huán)隊(duì)列的引入,目的是為了克服 假上溢 。28、 向順序棧插入新元素分為三步:第一步進(jìn)行 棧是否滿 判斷,判斷條件是 s->top=MAXSIZE-1 ;第二步是修改 棧頂指針 ;第三步是把新元素賦給 棧頂對(duì)應(yīng)的數(shù)組元素 。同樣從順序棧刪除元素分為三步:第一步進(jìn)行 棧是否空 判斷,判斷條件是 s->top=-1 。第二步是把 棧頂元素 ;第三步 修改棧頂指針 。29、 假設(shè)以 S 和 X 分別表示入棧和出棧操作,則對(duì)輸入序列 a,b,c,d,e 一系列棧操作 SSXSXSSXXX 之后,得到的輸出序列為 bceda 。30、 一個(gè)遞歸算法必須包括 終止條件 和 遞歸部分 。31、 判斷一個(gè)循環(huán)隊(duì)列 LU(最多元素為 m0)為空的條件是 LU->front==LU->rear 。32、 在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中,都需要使用棧,對(duì)于前者,進(jìn)入棧中的元素為表達(dá)式中的 運(yùn)算符 ,而對(duì)于后者,進(jìn)入棧的元素為 操作數(shù) ,中綴表達(dá)式(a+b)/c-(f-d/c)所對(duì)應(yīng)的后綴表達(dá)式是 ab+c/fde/-- 。 33、 向一個(gè)棧頂指針為 h 的鏈棧中插入一個(gè) s 所指結(jié)點(diǎn)時(shí),可執(zhí)行 s->next=h; 和 h=s;操作。(結(jié)點(diǎn)的指針域?yàn)閚ext)。34、 從一個(gè)棧頂指針為 h 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用 x 保存被刪結(jié)點(diǎn)的值,可執(zhí)行 x=h->data;和 h=h->next; 。(結(jié)點(diǎn)的指針域?yàn)?next)35、 在一個(gè)鏈隊(duì)中,設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針,則插入 s 所指結(jié)點(diǎn)的操作為 r->next=s; 和 r=s; (結(jié)點(diǎn)的指針域?yàn)?next)36、 在一個(gè)鏈隊(duì)中,設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的操作為 f=f->next; 。 (結(jié)點(diǎn)的指針域?yàn)?next)37、 串是一種特殊的線性表,其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是 字符 。38、 串的兩種最基本的存儲(chǔ)方式是 順序存儲(chǔ)方式 和 鏈?zhǔn)酱鎯?chǔ)方式 。39、 空串的長(zhǎng)度是 0 ;空格串的長(zhǎng)度是 空格字符的個(gè)數(shù) 。40、 需要壓縮存儲(chǔ)的矩陣可分為 特殊 矩陣和 稀疏 矩陣兩種。41、 設(shè)廣義表 L=(() , () ) ,則表頭是 () ,表尾是 () ) ,L 的長(zhǎng)度是 2 。42、 廣義表 A((a,b,c),(d,e,f))的表尾為 ((d,e,f) ) 。43、 兩個(gè)串相等的充分必要條件是 串長(zhǎng)度相等且對(duì)應(yīng)位置的字符相等 。44、 設(shè)有 n 階對(duì)稱(chēng)矩陣 A,用數(shù)組 s 進(jìn)行壓縮存儲(chǔ),當(dāng) i?j 時(shí),A 的數(shù)組元素 aij 相應(yīng)于數(shù)組 s 的數(shù)組元素的下標(biāo)為 i(i-1)/2+j 。 (數(shù)組元素的下標(biāo)從 1 開(kāi)始) 。45、 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的 行下標(biāo) 、 列下標(biāo) 和 非零元素值 三項(xiàng)信息。46、 結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的 子樹(shù)樹(shù)木或后繼結(jié)點(diǎn)數(shù) 。47、 樹(shù)的度是指 樹(shù)中所有結(jié)點(diǎn)的度的最大值 。48、 度大于 0 的結(jié)點(diǎn)稱(chēng)作 分支結(jié)點(diǎn) 或 非終端結(jié)點(diǎn) 。49、 度等于 0 的結(jié)點(diǎn)稱(chēng)作 葉子結(jié)點(diǎn) 或 終端結(jié)點(diǎn) 。50、 在一棵樹(shù)中,每個(gè)結(jié)點(diǎn)的 子樹(shù)的根 或者說(shuō)每個(gè)結(jié)點(diǎn)的 后繼結(jié)點(diǎn) 稱(chēng)為該結(jié)點(diǎn)的 孩子結(jié)點(diǎn) ,簡(jiǎn)稱(chēng)為孩專(zhuān)業(yè)好文檔電大資料整理子。51、 一個(gè)結(jié)點(diǎn)稱(chēng)為其后繼結(jié)點(diǎn)的 雙親結(jié)點(diǎn)(簡(jiǎn)稱(chēng)雙親) 。52、 具有 同一雙親 的結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn),簡(jiǎn)稱(chēng)為兄弟。53、 每個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)被稱(chēng)為該結(jié)點(diǎn)的 子孫 。54、 從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的 祖先 。55、 樹(shù)的深度或高度是指 樹(shù)中結(jié)點(diǎn)的最大層數(shù) 。56、 m(m?0)棵互不相交的樹(shù)的集合稱(chēng)為 森林 。57、 度為 k 的樹(shù)中的第 i 層上最多有 K i-1 結(jié)點(diǎn)。 58、 深度為 k 的二叉樹(shù)最多有 2 k-1 結(jié)點(diǎn)。59、 在一棵二叉樹(shù)中,如果樹(shù)中的每一層都是滿的,則稱(chēng)此樹(shù)為 滿二叉樹(shù) ;但如果出最后一層外,其余層都是滿的,并且最后一層是滿的,或者是在缺少若干連續(xù)個(gè)結(jié)點(diǎn),則稱(chēng)此二叉樹(shù)為 完全二叉樹(shù) 。60、 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是 。??1log2?n61、 先序遍歷二叉樹(shù)的的操作定義為;若二叉樹(shù)為空,則為空操作,否則進(jìn)行如下操作,訪問(wèn)二叉樹(shù)的 根結(jié)點(diǎn) ;先序遍歷二叉樹(shù)的 左子樹(shù) ,先序遍歷二叉樹(shù)的 右子樹(shù) 。62、 中序遍歷二叉樹(shù)的的操作定義為;若二叉樹(shù)為空,則為空操作,否則進(jìn)行如下操作,中序遍歷二叉樹(shù)的 左子樹(shù) ;訪問(wèn)而叉樹(shù)的 根結(jié)點(diǎn) ,中序遍歷二叉樹(shù)的 右子樹(shù) 。63、 后序遍歷二叉樹(shù)的的操作定義為;若二叉樹(shù)為空,則為空操作,否則進(jìn)行如下操作,后序遍歷二叉樹(shù)的 左子樹(shù) ;后序遍歷二叉樹(shù)的 右子樹(shù) ,訪問(wèn)而叉樹(shù)的 根結(jié)點(diǎn) 。64、 將樹(shù)中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù),稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)的 權(quán) 。65、 樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的 帶權(quán)路徑長(zhǎng)度之和 。66、 哈夫曼樹(shù)又稱(chēng)為 最優(yōu)二叉樹(shù) ,它是 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中帶權(quán)路徑長(zhǎng)度 WPL 最小的二叉樹(shù) 。67、 若以 4,5,6,7,8 作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù),則其帶權(quán)路徑長(zhǎng)度是 69 。68、 具有 m 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有 2m-1 結(jié)點(diǎn)。69、 在圖中,任何兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系,因此圖的數(shù)據(jù)元素之間是一種 多對(duì)多 的關(guān)系。70、 圖的鄰接矩陣表示法是用一個(gè) 二維數(shù)組 來(lái)表示圖中頂點(diǎn)之間的相鄰關(guān)系。71、 鄰接表是圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的 單鏈表 。72、 圖的遍歷是從圖的某一頂點(diǎn)出發(fā),按照一定的搜索方法對(duì)圖中 所有頂點(diǎn) 各做 一次 訪問(wèn)的過(guò)程。73、 圖的深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的 先序 遍歷。74、 圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的 按層次 遍歷。75、 具有 n 個(gè)頂點(diǎn)的有向圖的鄰接矩陣,其元素個(gè)數(shù)為 n 2 。76、 具有 n 個(gè)頂點(diǎn)的無(wú)向圖至少有 條邊,才能確保其為一個(gè)連通圖。77、 圖常用的兩種存儲(chǔ)結(jié)構(gòu)是 鄰接矩陣 和 鄰接表 。78、 一個(gè) AOV 網(wǎng)(頂點(diǎn)活動(dòng)圖)應(yīng)該是一個(gè) 有向無(wú)環(huán)圖 。即不應(yīng)該帶有回路,否則回路上的所有活動(dòng)都 無(wú)法進(jìn)行 。79、 用鄰接矩陣存儲(chǔ)有向圖 G,其第 i 行的所有元素之和等于頂點(diǎn) i 的 出度 。80、 在有 n 個(gè)頂點(diǎn)的有向圖中,每個(gè)頂點(diǎn)的度最大可達(dá) 2(n-1) 。專(zhuān)業(yè)好文檔電大資料整理81、 在一個(gè)帶權(quán)圖中,兩頂點(diǎn)之間的最段路徑最多經(jīng)過(guò) n-1 條邊。82、 為了實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷,其非遞歸的算法中需要使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)為 棧 。83、 在各種查找方法中,平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù) n 無(wú)關(guān)的查找方法是 哈希表查找法 。84、 如果對(duì)查找表只進(jìn)行查詢(xún)某個(gè)特定的數(shù)據(jù)元素是否在查找表中,以及查找某個(gè)特定數(shù)據(jù)元素的各種屬性?xún)煞N類(lèi)型的基本操作,而不進(jìn)行插入和刪除操作數(shù)據(jù)元素的查找表稱(chēng)為 靜態(tài)查找表 。85、 如果在查找表中進(jìn)行查詢(xún)的過(guò)程中,同時(shí)插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素,則稱(chēng)此類(lèi)查找表為 動(dòng)態(tài)查找表 。86、 關(guān)鍵字是記錄某個(gè) 數(shù)據(jù)項(xiàng)的值 ,用它可以識(shí)別、確定一個(gè) 記錄 。87、 在一個(gè)查找表中,能夠唯一地確定一個(gè)記錄的關(guān)鍵字稱(chēng)為 主關(guān)鍵字 。88、 平均查找長(zhǎng)度是指為確定記錄在查找表中的位置,需要與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的 數(shù)學(xué)期望值 。89、 順序 查找是一種最簡(jiǎn)單的查找方法。90、 折半查找又稱(chēng)為 二分查找 。使用該查找算法的前提條件是,查找表中記錄相應(yīng)的關(guān)鍵字值必須按 升序或降序排列 。91、 折半查找只適用于 順序存儲(chǔ)結(jié)構(gòu) 的有序表 。92、 分塊查找又稱(chēng)為 索引順序查找 ,它是一種介于 順序查找 和折半查找之間的查找方法。93、 二叉排序樹(shù)或者是一棵空樹(shù),或者是具有下列性質(zhì)的一棵二叉樹(shù):(1)若左子數(shù)不空,則左子樹(shù)所有結(jié)點(diǎn)的值 均小于根結(jié)點(diǎn)的值 。(2)若右子數(shù)不空,則右子樹(shù)所有結(jié)點(diǎn)的值 均大于根結(jié)點(diǎn)的值 。(3)左右子樹(shù)又分別是 二叉排序樹(shù) 。94、 哈希表是用來(lái)存放查找表中記錄序列的表,每一個(gè)記錄的存儲(chǔ)位置是以該記錄得到關(guān)鍵字為 自變量 ,由相應(yīng)哈希函數(shù)計(jì)算所得到的 函數(shù)值 。95、 在有序表 A[1….18]中,采用二分查找算法查找元素值等于 A[17]的元素,所比較過(guò)的元素的下標(biāo)依次是 9, 14, 16 ,17 。96、 根據(jù)排序過(guò)程中所用的存儲(chǔ)器不同,可以將排序方法分為 內(nèi)部排序 和 外部排序 。97、 冒泡排序是一種比較簡(jiǎn)單的 交換排序 方法。98、 在對(duì)一組記錄(50,40,95,20,15,70,60,45,80)進(jìn)行直接插入排序時(shí),當(dāng)把第 7 個(gè)記錄 60 插入到有序表時(shí),為尋找插入位置需要比較 3 次。99、 在歸并排序中,在第 3 趟歸并中,是把長(zhǎng)度為 4 的有序表歸并為長(zhǎng)度為 8 有序表。100、 在堆排序和快速排序中,若原始記錄接近正序和反序,則選用 堆排序 ,若原始記錄無(wú)序,則最好選用 快速排序 。101、 對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序,記錄序列按 主關(guān)鍵字 排序結(jié)果是唯一的。102、 按某關(guān)鍵字對(duì)記錄序列排序, 關(guān)鍵字相等的記錄 若在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。103、 n 個(gè)元素進(jìn)行冒泡法排序,通常需要進(jìn)行 n-1 趟冒泡,第 j 趟冒泡要進(jìn)行 n-j 次元素間的比較。104、 當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí),需要把 堆尾 元素填補(bǔ)到 堆頂 位置,然后再按條件把它逐層 向下 調(diào)整- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2017 電大 考試 數(shù)據(jù)結(jié)構(gòu) 復(fù)習(xí)題 填空 題小抄
鏈接地址:http://www.3dchina-expo.com/p-341133.html