數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題庫

1、.1. 、選擇題1) （無序或有序）順序表中插入元素的時間復(fù)雜度：_O(n)_。2) 帶頭結(jié)點的鏈表，如何判斷其是否為空鏈表：_head->data=0_。頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計入表長度。頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針.3) 數(shù)組形式存放的隊列，其大小為n，最多可存放多少個元素（即在具有n個單元的循環(huán)隊列中，隊滿時共有多少個元素 ）：_n-1_。常用空閑單元法（人為浪費一個單元，則隊滿特征可改為front=(rear+1)%N）：即front和rear之一指向?qū)嵲?，另一指向空閑元素。4) 棧操作

2、的原則：只能在棧頂運算，且訪問結(jié)點時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。5) 樹的前驅(qū)結(jié)點： 在一棵樹中，每個結(jié)點稱為它的每棵子樹的根結(jié)點的前驅(qū)結(jié)點（即該結(jié)點的上層的那個結(jié)點(直接前驅(qū))）。如孩子的前驅(qū)結(jié)點是雙親結(jié)點 6) 二叉樹存儲是用二叉鏈表，二叉樹的空指針域與非空指針域的關(guān)系：具有n個結(jié)點的二叉鏈表中，共有2n個指針域。其中有n-1個非空鏈表，用來指示結(jié)點的左孩子和右孩子，其余的n+1個指針域為空。7) 折半（二分）查找的平均查找長度：當(dāng)n很大時，ASL= log2(n+1)-1 可以作為二分查找成功時的平均查找長度。8) 有向圖的度的計算：即頂點的度的計算。入度和出度

3、：頂點 v 的入度是以 v 為終點的有向邊的條數(shù), 記作 ID(v)；頂點 v 的出度是以 v 為始點的有向邊的條數(shù), 記作 OD(v)；在有向圖中, 頂點的度等于該頂點的入度與出度之和。 9) 列出各種排序中，最壞的時間復(fù)雜度： 平均時間 最差 最佳 輔助空間 穩(wěn)定性直接插入 O(n2) O(n2) O(n) O(1) 穩(wěn)定起泡排序 O(n2) O(n2) O(n) O(1) 穩(wěn)定直接選擇 O(n2) O(n2) O(n2) O(1) 不穩(wěn)定希爾排序 O(n1.5) O(1) 不穩(wěn)定快速排序 O(nlog2n) O(n2) 同平均 O(log2n) 不穩(wěn)定堆排序 O(nlog2n) 同平均

4、同平均 O(1) 不穩(wěn)定歸并排序 O(nlog2n) 同平均 同平均 O(n) 穩(wěn)定基數(shù)排序 O(d(n+r) 同平均 同平均 O(n+r) 穩(wěn)定在最壞情況下，快速排序法的時間復(fù)雜度為O(n2) ，變?yōu)榕判蜃盥姆椒ā?0) 順序存儲與鏈?zhǔn)酱鎯Φ膬?yōu)缺點：2、 判斷題1) 數(shù)組與元素之間的關(guān)系：若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組Vn的下標(biāo)）。設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：LOC(ai+1) = LOC(ai)+L LOC(ai) = LOC(a1) + L *（

5、i-1）2) 鏈?zhǔn)降奈锢斫Y(jié)構(gòu)與邏輯結(jié)構(gòu)的相關(guān)判斷：鏈?zhǔn)酱鎯Y(jié)構(gòu)特點：其結(jié)點在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。 3) 循環(huán)單鏈表隊列是否一定需要頭指針和尾指針：一個隊列需要兩個分別指示隊頭和隊尾的指針（頭指針和尾指針）才能唯一確定；解決假溢出的途徑采用循環(huán)隊列。4) 遞歸法的優(yōu)點是：遞歸可以代替循環(huán)，但是，不是所有的可計算問題都可由遞歸轉(zhuǎn)換為循環(huán)。遞歸清晰易懂，易于設(shè)計算法，具有較高的開發(fā)效率，所設(shè)計的程序具有更好可讀性和可維護(hù)性。5) 廣義表：廣義表是線性表的推廣，也稱為列表（lists） 記為： LS = ( a1 , a2 , ， an ) 在廣義表中約定

6、：1 第一個元素是表頭，而其余元素組成的表稱為表尾；2 用小寫字母表示原子類型，用大寫字母表示列表。3 ai 區(qū)別于線性表中只限于是單個元素，而在廣義表中或者是單個元素或者是一個廣義表，分別稱為廣義表的原子和子表。注意：a. 為了區(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。b. 廣義表是遞歸定義的。因為在描述廣義表時又用到了廣義表的概念。6) 堆排序（選擇排序中的一種，考堆排序的操作）： 堆排序：將無序序列建成一個堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1個元素重又建成一個堆，則可得到n個元素的次小值；重復(fù)執(zhí)行，得到一個有序序列，這個過程

7、叫堆排序.。 堆排序需解決的兩個問題：如何由一個無序序列建成一個堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？ 第二個問題解決方法篩選方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”。7) 二叉樹遍歷的時間復(fù)雜度：三種遍歷具有相同的時間復(fù)雜度和空間復(fù)雜度。若二叉樹的結(jié)點個數(shù)為n，則算法的時間復(fù)雜度為O（n）。8) 鄰接矩陣的大小有什么決定：鄰接矩陣 表示各個頂點之間關(guān)系，設(shè)圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是

8、一個二維數(shù)組 A.Edgenn9) 判斷某種排序是否穩(wěn)定：參看選擇題910) 什么是物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示（又稱映射）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲結(jié)構(gòu)。 3、填空題1 數(shù)組結(jié)構(gòu)（與判斷第1題類似）2 鏈表的插入刪除操作： 插入：（先挖“坑”,后種“蘿卜”！)x結(jié)點的生成方式： S= new node; S->data=x; Step1：S->next=p->next Step2： p->next=s （思考：Step1和2能互換么？）刪除：要借助輔助指針變量q q = p->next; p->next=q->next delete q 3

9、鏈棧用鏈表實現(xiàn)棧的操作：插入，刪除等（程序函數(shù)相互調(diào)用，將關(guān)鍵的值保存在棧，保證順序返回） 鏈棧的構(gòu)造方式以頭指針為棧頂，在頭指針處插入或刪除.一個鏈棧由其棧頂指針唯一指定 設(shè)st指向棧頂元素，則 st = NULL 表示?？真湕５娜霔?、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。順序棧入棧函數(shù)PUSH（） 順序棧出棧函數(shù)pop()status Push(ElemType e) status pop( ) if(top>M)上溢 if(top=L) 下溢 else s+top=e; else e=s-top; return(e);4 樹的后驅(qū)結(jié)點：在一棵樹中，每棵子樹的根結(jié)點稱為

10、該結(jié)點的后繼結(jié)點。5 在廣義表中，如何判斷結(jié)點層次：有長度表中元素個數(shù) 有深度表中括號的重數(shù)E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E為遞歸表;6 高度平衡二叉樹，左子樹，右子樹高度最多相差多少：7 圖中最多有多少條邊，頂點最大會有幾度：若 n 個頂點的無向圖有 n(n-1)/2 條邊, 稱為無向完全圖若 n 個頂點的有向圖有n(n-1) 條邊, 稱為有向完全圖 圖任意兩個頂點都有一條邊相連接4、 分析題1) 樹轉(zhuǎn)化為二叉樹，直接寫出結(jié)果（孩子是有左右之分的）2) 二叉樹的遍歷（前，中，后）3) 哈夫曼編碼（給你一串字符，自己統(tǒng)計每個字符出現(xiàn)的概率），要寫過程的4) 圖里面

11、最小生成樹：Prim算法和Kruskal算法，都要寫過程，過程是畫圖5、 編程題1、冒泡排序（用主函數(shù)調(diào)用子函數(shù)，寫一個完整程序）#include<stdio.h>#define N 5void MAOPAO(int arryN) int j,k; int temp;for (j=0; j<N-1; j+) for (k=0; k<N-1-j; k+) if(arryk >arryk+1) temp=arryk; arryk=arryk+1; arryk+1=temp; main()int j;int aN;printf("請輸入5個數(shù):n")

12、;for (j=0 ;j<N ; j+)scanf("%d",&aj);MAOPAO(a);printf("排序后的數(shù)字為:n");for (j=0;j<N;j+)printf("%5d",aj); 2、順序查找#include"stdio.h"int seek(int a10,int key)int i; for(i=0;i<5;i+) if(key=ai) return i; return -1;main()int a5,i,key,loc;printf("enter 5 n

13、umbers:n");for(i=0;i<5;i+)scanf("%d",&ai);printf("enter key:n");scanf("%d",&key);if(seek(a,key)=-1)printf("not find!");elseloc=seek(a,key);printf("find and loctiong is:%d",loc); 總復(fù)習(xí)第1章 視覺特性與計色制1. 視覺特性：（1）亮度感覺：人眼的明暗感覺是相對的，重現(xiàn)的圖像亮度無需與景物的

14、實際亮度相等，只需保持二者的對比度C不變。 （2）分辨率：眼睛分辨景色細(xì)節(jié)的能力有一個極限值；人眼對彩色細(xì)節(jié)的分辨能力較差，對黑白細(xì)節(jié)的分辨力較強(qiáng)。 （3）視覺暫留與閃爍：人眼的主觀亮度感覺總是在時間上滯后于實際亮度的改變；人眼在周期性光脈沖的刺激下，當(dāng)頻率偏低時，人眼會產(chǎn)生一明一暗的感覺閃爍。2.描述彩色的三個基本參量：（1）亮度光的明暗程度； （與光通量有關(guān)）（2）色調(diào)顏色的類別； （與彩色光中各基色的比例有關(guān)）（3）色飽和度彩色的深淺。（與彩色光中白光的 比例有關(guān)）3. 三基色原理與相加混色：自然界中，絕大多數(shù)的彩色都可以由三種基色按不同的比例相加混合得到。 混色規(guī)律： 紅綠黃 紅蘭紫

15、綠蘭青 紅綠蘭白4. 配色方程 F=RR+GG+BB R、G、B為三色系數(shù); R、G、B為基色單位。5. 亮度方程: Y=0.3R+0.59G+0.11B第2章 電視成像原理與視頻信號的產(chǎn)生1. CCD圖像傳感器： 工作原理： （1）光電轉(zhuǎn)換； （2）電荷轉(zhuǎn)移； （3）自掃描。 基本結(jié)構(gòu)： （1）幀轉(zhuǎn)移型FTCCD； （2）行間轉(zhuǎn)移型IT CCD； （3）幀行間轉(zhuǎn)移型 FITCCD。 2. 逐行掃描與隔行掃描： （1）逐行掃描：一幀畫面（圖像）一次性完成掃描。 （2）隔行掃描：一幀畫面（圖像）分二場完成掃描。優(yōu)點： 既保證了圖像的清晰度，又壓縮了視頻信號頻帶寬度。 缺點： 行間閃爍效應(yīng)。 并行

16、現(xiàn)象。 垂直邊沿鋸齒化現(xiàn)象。 3.掃描參數(shù): （1）行掃描：行頻fH=15 625 Hz，行掃描周期 TH=64 s（2）場掃描：場頻 fV50Hz，場周期TV=20ms（3）每幀掃描行數(shù)：Z625行，每幀有效掃描行數(shù)：575行；（4）清晰度與分解力：垂直分解力決定于圖像的每幀有效掃描行數(shù)；水平分解力主要與視頻信號帶寬有關(guān)。4. 視頻圖像信號:黑白:（1）亮度信號：電平高低反映圖像的亮度（2）同步信號：確保收發(fā)二端掃描同步（3）消隱信號：使行、場逆程期間不產(chǎn)生回掃（4）開槽脈沖：保證場同步期間行掃描的穩(wěn)定 （5）均衡脈沖：保證隔行掃描的準(zhǔn)確性彩色 （1）基色信號：R、G、B （2）亮度信號：Y

17、=0.30R+0.59G+0.11B （3）色差信號： RY BY 第3章 彩色視頻信號的處理與制式 1. 頻譜交錯與高頻混合：根據(jù)頻譜交錯原理，采用調(diào)幅技術(shù)將色差信號的頻譜搬移到亮度信號的頻譜中間，使色度信號的頻譜與亮度信號的頻譜相互錯開，實現(xiàn)共頻帶傳送； 根據(jù)高頻混合原理，亮度信號以06MHz寬帶傳輸，色度信號以01.3MHz窄帶傳輸，既節(jié)省頻帶又可以減少亮度信號和色度信號共帶傳輸產(chǎn)生的相互干擾。 2. NTSC制：（1）正交平衡調(diào)幅與同步檢波： 兩路色差信號分別對相位差為900的載波進(jìn)行調(diào)制，這樣，色度信號所占的帶寬就只有2.6 MHZ，減小色度對亮度的干擾。同步檢波：色度信號的解調(diào)同步

18、檢波電路由模擬乘法器和低通濾波器組成 （2）色同步信號：作為接收機(jī)恢復(fù)副載波的頻率和相位的基準(zhǔn)，用于解調(diào)色度信號。（3）色度信號的幅度壓縮：壓縮后的色差信號：色度信號：色度信號的幅度表示彩色的飽和度，相位角表示色調(diào)。（5）微分增益和微分相位失真：微分相位失真：亮度電平的變化而引起的色度信號相位移的變化導(dǎo)致色調(diào)失真。微分增益失真：亮度電平變化而引起的色度信號增益的變化引起色飽和度失真。 3. PAL制： （1）技術(shù)特點：將色度信號 ec(t)=u(t)+v(t)中的 V分量 逐行倒相為 ec(t)=u(t)±v(t) U(t)Sinsct±V(t)Cossct （2）PAL制

19、編碼：5個組成部分  矩陣變換：將R、G、B線性組合（信號變換和幅度壓縮）形成Y、U和V信號。 亮度陷波及延遲：陷波在副載波fSC附近對亮度信號進(jìn)行衰減，減少色度信號對亮度信號的干擾。延遲將亮度信號延遲0.6 s使亮度信號和色度信號在時間上一致，消除彩色鑲邊現(xiàn)象。 副載波形成：由同步芯片產(chǎn)生副載波信號fSC 、 P脈沖、 K脈沖、 復(fù)合同步和復(fù)合消隱信號， 供平衡調(diào)幅和信號合成使用。 sinsct cossct ± cossct 平衡調(diào)幅：將色差信號和K脈沖平衡調(diào)幅為色度信號和色同步信號。 ec(t)= U（t） sinSCt ±V (t)cosSCt eb(t)

20、= Ksinsct ±Kcossct 信號混合：將Y、 ec(t) 、 eb(t)以及復(fù)合同步信號S脈沖混合， 組成彩色全電視信號CVBS 。 (3). PAL制解碼：五步信號處理 亮度信號和色度信號的分離頻帶分離法；色同步信號和色度信號的分離時間分離法；色度信號的兩個分量FU、FV的分離頻譜分離法；（梳狀濾波器） 同步檢波； 從色度信號分量u和±v中解調(diào)出色差信號U、V，用模擬乘法器和低通濾波器來實現(xiàn)。矩陣變換：將Y、 U、 V 信號還原為三基色信號。（4） PAL制色同步信號的兩個功能：一是給接收機(jī)恢復(fù)副載波提供解調(diào)副載波的基準(zhǔn)頻率和相位（與N制相同）；二是給接收機(jī)提供逐行倒相的識別信息。給接收機(jī)提供一個極性切換信息，來識別哪一行是不倒相NTSC行， 哪一行是倒相PAL行。 第4章 電視廣播與視頻信號的傳輸1.地面電視廣播:（1）圖像信號采用調(diào)幅方式，伴音信號采用調(diào)頻方式，調(diào)制后的圖像信號和伴音信號統(tǒng)稱為射頻電視信號（RF）。 （2）殘留邊帶