2017年電大考試數(shù)據(jù)結構復習題填空題小抄

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