2017年電大考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題填空題小抄

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