西安電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題(編輯修改稿)
2025-05-14 12:21 本頁面
【文章內(nèi)容簡介】 . 插入排序法 B. 選擇排序法 C. 拓?fù)渑判蚍? D. 歸并排序法28. 直接插入排序在最好情況下的時(shí)間復(fù)雜度為 B 。A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2) ，在最壞情況，算法的時(shí)間復(fù)雜度是 D 。A. O(n3) B. O(n) C. O(nlog2n) D. O(n2) ，穩(wěn)定是 A 。A. 直接插入排序法 B. 快速排序法 C. 直接選擇排序法 D. 堆排序法二、 填空題1. 一個(gè)算法具有5個(gè)特性： 、 、 、有零個(gè)或多個(gè)輸入，一個(gè)或多個(gè)輸出。2. .設(shè)數(shù)組a[1…50，1…80]的基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[45，68]的存儲(chǔ)地址為 9174 ；若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[45，68]的存儲(chǔ)地址為 8788 。3. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用 存儲(chǔ)結(jié)構(gòu)。 長度相等且對(duì)應(yīng)位置上的字符相等 。5. 字符串“abcd”中共有 個(gè)長度大于0的字串。6. 廣義表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10））的長度及深度分別為 和 。，則該二叉樹一定滿足只有一個(gè)葉子結(jié)點(diǎn) 。 有n1條邊的連通圖 ，則該圖是樹。，則其邊數(shù)最少為 n1 ，最多為 n(n1)/2 。 O(nlog2n) 和 O(1) 。三、 名詞解釋（1）抽象數(shù)據(jù)類型 （2）算法及其特性 （3）串的模式匹配 （4）優(yōu)先級(jí)隊(duì)列（5）完全二叉樹 （6）堆（7）Huffman編碼（8）Huffman樹（9）連通分量及重連通分量（10）最小生成樹（11）克魯斯卡爾算法（12）普里姆算法（13）希爾排序（14）快速排序（15）教材等等相關(guān)名次解釋題四、 簡答題1. 請(qǐng)對(duì)線性表進(jìn)行順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)作比較。（西電2004年考研試題）2. 單鏈表為什么要引入頭結(jié)點(diǎn)？、循環(huán)鏈表、雙向鏈表，試問它們各有什么優(yōu)點(diǎn)和缺點(diǎn)？參考答案：l 單鏈表的優(yōu)點(diǎn)是空間動(dòng)態(tài)分配，插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，缺點(diǎn)是不能隨機(jī)訪問數(shù)據(jù)。和其它兩種相比，它還節(jié)省了空間。l 循環(huán)鏈表除了具有單鏈表的優(yōu)點(diǎn)外，它從任意結(jié)點(diǎn)出發(fā)可以找到其它結(jié)點(diǎn)。缺點(diǎn)同單鏈表的缺點(diǎn)。l 雙向鏈表除了具有循環(huán)鏈表的優(yōu)點(diǎn)，它還可以方便地找到某個(gè)結(jié)點(diǎn)的前驅(qū)。缺點(diǎn)是增加了空間開銷。（不妨假設(shè)地址從1到m），提供給兩個(gè)棧使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。5. 假設(shè)有一個(gè)適當(dāng)大小的棧S，輸入棧的序列為A，B，C，D，E。問：（1）能否得到下列的輸出序列： ① B，C，D，E，A； ② E，A，B，C，D；③E，D，C，B，A。（2）寫出所有可能正確的輸出序列（至少5種
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1