2018年電大考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題填空題小抄
《2018年電大考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題填空題小抄》由會員分享,可在線閱讀,更多相關(guān)《2018年電大考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題填空題小抄(4頁珍藏版)》請在裝配圖網(wǎng)上搜索。
專業(yè)好文檔電大資料整理電大數(shù)據(jù)結(jié)構(gòu)復(fù)核習(xí)題(填空題)1、 在一個長度為 n 的順序存儲結(jié)構(gòu)的線性表中,向第 i(1?i?n+1)個元素之前插入新元素時,需向后移動 n-i+1 個數(shù)據(jù)元素。2、 從長度為 n 的采用順序存儲結(jié)構(gòu)的線性表中刪除第 i(1?i?n+1)個元素 ,需向前移動 n-i 個元素。3、 數(shù)據(jù)結(jié)構(gòu)按結(jié)點間的關(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é)點外,其余結(jié)點有且只有一個前驅(qū)結(jié)點和后繼結(jié)點的數(shù)據(jù)結(jié)構(gòu)為 線性結(jié)構(gòu) ,每個結(jié)點可有任意多個前驅(qū)和后繼結(jié)點數(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é)點之后插入一個 s 所指結(jié)點時,應(yīng)執(zhí)行__s->next=p->next;__和 p->next=s;的操作。12、 設(shè)有一個頭指針為 head 的單向循環(huán)鏈表,p 指向鏈表中的結(jié)點,若 p->next= = head ,則 p 所指結(jié)點為尾結(jié)點。13、 在一個單向鏈表中,要刪除 p 所指結(jié)點,已知 q 指向 p 所指結(jié)點的前驅(qū)結(jié)點。則可以用操作 q->next=p->next; 。14、 設(shè)有一個頭指針為 head 的單向鏈表,p 指向表中某一個結(jié)點,且有 p->next= =NULL,通過操作 p->next=head; ,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。15、 每個結(jié)點只包含一個指針域的線性表叫 單鏈表 。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é)點中包含 兩個 指針域,其中 next 指向它的 直接后繼 ,prior 指向它的 直接前驅(qū) ,而頭結(jié)點的 prior 指向 尾結(jié)點 ,尾結(jié)點的 next 指向 頭結(jié)點 。19、 單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充,當(dāng)單向鏈表帶有頭結(jié)點時,把單向鏈表中尾結(jié)點的指針域由空指針改為 頭結(jié)點的指針 ;當(dāng)單向鏈表不帶頭結(jié)點時,則把單向鏈表中尾結(jié)點的指針域由空指針改為指向 指向第一個結(jié)點的指針 。20、 線性鏈表的邏輯關(guān)系時通過每個結(jié)點指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致,而是一種 鏈?zhǔn)? 存儲結(jié)構(gòu),又稱為 鏈表 。21、 棧是限定在表的一端進(jìn)行插入和刪除操作的線性表,又稱為 后進(jìn)先出表 。22、 隊列的特性是 先進(jìn)先出表 。23、 往棧中插入元素的操作方式是:先 移動棧頂指針 ,后 存入元素 。24、 刪除棧中元素的操作方式是:先 取出元素 ,后 移動棧頂指針 。25、 循環(huán)隊列隊頭指針在隊尾指針 下一個 位置,隊列是“滿”狀態(tài)專業(yè)好文檔電大資料整理26、 在隊列的順序存儲結(jié)構(gòu)中,當(dāng)插入一個新的隊列元素時,尾指針 增 1 ,當(dāng)刪除一個元素隊列時,頭指針 增 1 。27、 循環(huán)隊列的引入,目的是為了克服 假上溢 。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)隊列 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é)點時,可執(zhí)行 s->next=h; 和 h=s;操作。(結(jié)點的指針域為next)。34、 從一個棧頂指針為 h 的鏈棧中刪除一個結(jié)點時,用 x 保存被刪結(jié)點的值,可執(zhí)行 x=h->data;和 h=h->next; 。(結(jié)點的指針域為 next)35、 在一個鏈隊中,設(shè) f 和 r 分別為隊頭和隊尾指針,則插入 s 所指結(jié)點的操作為 r->next=s; 和 r=s; (結(jié)點的指針域為 next)36、 在一個鏈隊中,設(shè) f 和 r 分別為隊頭和隊尾指針,則刪除一個結(jié)點的操作為 f=f->next; 。 (結(jié)點的指針域為 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) i?j 時,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) 和 非零元素值 三項信息。46、 結(jié)點的度是指結(jié)點所擁有的 子樹樹木或后繼結(jié)點數(shù) 。47、 樹的度是指 樹中所有結(jié)點的度的最大值 。48、 度大于 0 的結(jié)點稱作 分支結(jié)點 或 非終端結(jié)點 。49、 度等于 0 的結(jié)點稱作 葉子結(jié)點 或 終端結(jié)點 。50、 在一棵樹中,每個結(jié)點的 子樹的根 或者說每個結(jié)點的 后繼結(jié)點 稱為該結(jié)點的 孩子結(jié)點 ,簡稱為孩專業(yè)好文檔電大資料整理子。51、 一個結(jié)點稱為其后繼結(jié)點的 雙親結(jié)點(簡稱雙親) 。52、 具有 同一雙親 的結(jié)點互稱為兄弟結(jié)點,簡稱為兄弟。53、 每個結(jié)點的所有子樹中的結(jié)點被稱為該結(jié)點的 子孫 。54、 從根結(jié)點到該結(jié)點所經(jīng)分支上的所有結(jié)點稱為該結(jié)點的 祖先 。55、 樹的深度或高度是指 樹中結(jié)點的最大層數(shù) 。56、 m(m?0)棵互不相交的樹的集合稱為 森林 。57、 度為 k 的樹中的第 i 層上最多有 K i-1 結(jié)點。 58、 深度為 k 的二叉樹最多有 2 k-1 結(jié)點。59、 在一棵二叉樹中,如果樹中的每一層都是滿的,則稱此樹為 滿二叉樹 ;但如果出最后一層外,其余層都是滿的,并且最后一層是滿的,或者是在缺少若干連續(xù)個結(jié)點,則稱此二叉樹為 完全二叉樹 。60、 具有 n 個結(jié)點的完全二叉樹的深度是 。??1log2?n61、 先序遍歷二叉樹的的操作定義為;若二叉樹為空,則為空操作,否則進(jìn)行如下操作,訪問二叉樹的 根結(jié)點 ;先序遍歷二叉樹的 左子樹 ,先序遍歷二叉樹的 右子樹 。62、 中序遍歷二叉樹的的操作定義為;若二叉樹為空,則為空操作,否則進(jìn)行如下操作,中序遍歷二叉樹的 左子樹 ;訪問而叉樹的 根結(jié)點 ,中序遍歷二叉樹的 右子樹 。63、 后序遍歷二叉樹的的操作定義為;若二叉樹為空,則為空操作,否則進(jìn)行如下操作,后序遍歷二叉樹的 左子樹 ;后序遍歷二叉樹的 右子樹 ,訪問而叉樹的 根結(jié)點 。64、 將樹中結(jié)點賦上一個有著某種意義的實數(shù),稱此實數(shù)為該結(jié)點的 權(quán) 。65、 樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的 帶權(quán)路徑長度之和 。66、 哈夫曼樹又稱為 最優(yōu)二叉樹 ,它是 n 個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中帶權(quán)路徑長度 WPL 最小的二叉樹 。67、 若以 4,5,6,7,8 作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹,則其帶權(quán)路徑長度是 69 。68、 具有 m 個葉子結(jié)點的哈夫曼樹共有 2m-1 結(jié)點。69、 在圖中,任何兩個數(shù)據(jù)元素之間都可能存在關(guān)系,因此圖的數(shù)據(jù)元素之間是一種 多對多 的關(guān)系。70、 圖的鄰接矩陣表示法是用一個 二維數(shù)組 來表示圖中頂點之間的相鄰關(guān)系。71、 鄰接表是圖中的每個頂點建立一個鄰接關(guān)系的 單鏈表 。72、 圖的遍歷是從圖的某一頂點出發(fā),按照一定的搜索方法對圖中 所有頂點 各做 一次 訪問的過程。73、 圖的深度優(yōu)先搜索遍歷類似于樹的 先序 遍歷。74、 圖的廣度優(yōu)先搜索類似于樹的 按層次 遍歷。75、 具有 n 個頂點的有向圖的鄰接矩陣,其元素個數(shù)為 n 2 。76、 具有 n 個頂點的無向圖至少有 條邊,才能確保其為一個連通圖。77、 圖常用的兩種存儲結(jié)構(gòu)是 鄰接矩陣 和 鄰接表 。78、 一個 AOV 網(wǎng)(頂點活動圖)應(yīng)該是一個 有向無環(huán)圖 。即不應(yīng)該帶有回路,否則回路上的所有活動都 無法進(jìn)行 。79、 用鄰接矩陣存儲有向圖 G,其第 i 行的所有元素之和等于頂點 i 的 出度 。80、 在有 n 個頂點的有向圖中,每個頂點的度最大可達(dá) 2(n-1) 。專業(yè)好文檔電大資料整理81、 在一個帶權(quán)圖中,兩頂點之間的最段路徑最多經(jīng)過 n-1 條邊。82、 為了實現(xiàn)圖的深度優(yōu)先搜索遍歷,其非遞歸的算法中需要使用的一個輔助數(shù)據(jù)結(jié)構(gòu)為 棧 。83、 在各種查找方法中,平均查找長度與結(jié)點個數(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ù)項的值 ,用它可以識別、確定一個 記錄 。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é)點的值 均小于根結(jié)點的值 。(2)若右子數(shù)不空,則右子樹所有結(jié)點的值 均大于根結(jié)點的值 。(3)左右子樹又分別是 二叉排序樹 。94、 哈希表是用來存放查找表中記錄序列的表,每一個記錄的存儲位置是以該記錄得到關(guān)鍵字為 自變量 ,由相應(yīng)哈希函數(shù)計算所得到的 函數(shù)值 。95、 在有序表 A[1….18]中,采用二分查找算法查找元素值等于 A[17]的元素,所比較過的元素的下標(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)整- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2018 電大 考試 數(shù)據(jù)結(jié)構(gòu) 復(fù)習(xí)題 填空 題小抄
鏈接地址:http://www.szxfmmzy.com/p-342169.html