最新自考數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)

自考數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）

自考02331數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)（最終修訂）自考數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）第一章概論1.瑞士計(jì)算機(jī)科學(xué)家沃思提出：算法+數(shù)據(jù)結(jié)構(gòu)=程序。算法是對(duì)數(shù)據(jù)運(yùn)算的描述，而數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu).由此可見,程序設(shè)計(jì)的實(shí)質(zhì)是針對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。2.數(shù)據(jù)是信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合.3.數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算①數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān),是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)分類：線性結(jié)構(gòu)和非線性結(jié)構(gòu).線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。②數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式,稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語(yǔ)言。③數(shù)據(jù)的運(yùn)算。最常用的檢索、插入、刪除、更新、排序等.4.數(shù)據(jù)的四種基本存儲(chǔ)方法：順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)（1)順序存儲(chǔ)：通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組描述。(2）鏈接存儲(chǔ)：通常借助于程序語(yǔ)言的指針來(lái)描述。（3）索引存儲(chǔ)：索引表由若干索引項(xiàng)組成。關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)元素的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的組合。（4)散列存儲(chǔ)：該方法的基本思想是:根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址。5。算法必須滿足5個(gè)準(zhǔn)則：輸入，0個(gè)或多個(gè)數(shù)據(jù)作為輸入;輸出，產(chǎn)生一個(gè)或多個(gè)輸出;有窮性，算法執(zhí)行有限步后結(jié)束；確定性，每一條指令的含義都明確；可行性,算法是可行的。算法與程序的區(qū)別：程序必須依賴于計(jì)算機(jī)程序語(yǔ)言,而一個(gè)算法可用自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言、數(shù)學(xué)語(yǔ)言或約定的符號(hào)語(yǔ)言來(lái)描述.目前常用的描述算法語(yǔ)言有兩類：類Pascal和類C。6。評(píng)價(jià)算法的優(yōu)劣:算法的"正確性”是首先要考慮的.此外,主要考慮如下三點(diǎn):

①執(zhí)行算法所耗費(fèi)的時(shí)間，即時(shí)間復(fù)雜性；

②執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間,主要是輔助空間，即空間復(fù)雜性;

③算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。以上幾點(diǎn)最主要的是時(shí)間復(fù)雜性,時(shí)間復(fù)雜度常用漸進(jìn)時(shí)間復(fù)雜度表示。7。算法求解問(wèn)題的輸入量稱為問(wèn)題的規(guī)模，用一個(gè)正整數(shù)n表示.8。常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為:常數(shù)階0（1)、對(duì)數(shù)階0（log2n）、線性階0(n）、線性對(duì)數(shù)階0（nlog2n)、平方階0(n2)立方階0（n3)、…、k次方階0(nk)、指數(shù)階0（2n）和階乘階0(n!）。9.一個(gè)算法的空間復(fù)雜度S(n）定義為該算法所耗費(fèi)的存儲(chǔ)空間，它是問(wèn)題規(guī)模n的函數(shù)，它包括存儲(chǔ)算法本身所占的存儲(chǔ)空間、算法的輸入輸出數(shù)據(jù)所占的存儲(chǔ)空間和算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間。第二章線性表1.數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的,而運(yùn)算的具體實(shí)現(xiàn)是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。

2.只要確定了線性表存儲(chǔ)的起始位置，線性表中任意一個(gè)元素都可隨機(jī)存取，所以順序表是一種隨機(jī)存取結(jié)構(gòu).3。常見的線性表的基本運(yùn)算:（1)置空表InitList（L）構(gòu)造一個(gè)空的線性表L。

(2）求表長(zhǎng)ListLength（L）求線性表L中的結(jié)點(diǎn)個(gè)數(shù),即求表長(zhǎng).

（3)GetNode（L，i）取線性表L中的第i個(gè)元素。（4)LocateNode（L，x）在L中查找第一個(gè)值為x的元素，并返回該元素在L中的位置。若L中沒(méi)有元素的值為x，則返回0值.

（5）InsertList（L，i，x）在線性表L的第i個(gè)元素之前插入一個(gè)值為x的新元素，表L的長(zhǎng)度加1。

(6）DeleteList（L，i）刪除線性表L的第i個(gè)元素,刪除后表L的長(zhǎng)度減1.4.順序存儲(chǔ)方法:把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里的方法。順序表（SequentialList)：用順序存儲(chǔ)方法存儲(chǔ)的線性表稱為順序表。順序表是一種隨機(jī)存取結(jié)構(gòu)，順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。順序表中結(jié)點(diǎn)ai的存儲(chǔ)地址:LOC(ai）=LOC（a1）+（i-1）*c

1≤i≤n，5.順序表上實(shí)現(xiàn)的基本運(yùn)算：(1）插入：該算法的平均時(shí)間復(fù)雜度是O(n），即在順序表上進(jìn)行插入運(yùn)算，平均要移動(dòng)一半結(jié)點(diǎn)（n/2）。在第i個(gè)位置插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n—i+1（2）刪除：順序表上做刪除運(yùn)算,平均要移動(dòng)表中約一半的結(jié)點(diǎn)（n-1）/2，平均時(shí)間復(fù)雜度也是O（n)。刪除第i個(gè)結(jié)點(diǎn)移動(dòng)次數(shù)為n-i6。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以避免頻繁移動(dòng)大量元素。一個(gè)單鏈表可由頭指針唯一確定,因此單鏈表可以用頭指針的名字來(lái)命名.①生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=(ListNode＊）malloc(sizeof(ListNode))；//函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中②釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free(p);//釋放p所指的結(jié)點(diǎn)變量空間③結(jié)點(diǎn)分量的訪問(wèn)

方法二:p-﹥data和p-﹥next④指針變量p和結(jié)點(diǎn)變量*p的關(guān)系：指針變量p的值——結(jié)點(diǎn)地址，結(jié)點(diǎn)變量*p的值—-結(jié)點(diǎn)內(nèi)容7.建立單鏈表：（1）頭插法建表：算法：p=（ListNode*)malloc(sizeof(ListNode）)；①//生成新結(jié)點(diǎn)

p—〉data=ch；②//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中

p—>next=head;③head=p;④（2）尾插法建表：算法：p=（ListNode＊）malloc（sizeof(ListNode)）;①//生成新結(jié)點(diǎn)

p—>data=ch；

②//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中

if（head==NULL）head=p；//新結(jié)點(diǎn)插入空表

elserear-〉next=p;③//將新結(jié)點(diǎn)插到＊r之后

rear=p；④//尾指針指向新表尾(3）尾插法建帶頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)。它具有兩個(gè)優(yōu)點(diǎn):

⒈由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中,所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上操作一致，無(wú)須進(jìn)行特殊處理；

⒉無(wú)論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域空），因此空表和非空表的處理也就統(tǒng)一了.頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表示該部分不存儲(chǔ)信息.在有的應(yīng)用中可用于存放表長(zhǎng)等附加信息。具體算法:r=head;//

尾指針初值也指向頭結(jié)點(diǎn)

while（(ch=getchar())！=’\n’）｛

s=（ListNode*)malloc（sizeof(ListNode)）;//生成新結(jié)點(diǎn)

s—>data=ch;

//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中

r—〉next=s；

r=s；｝

r—>next=NULL；//終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空以上三個(gè)算法的時(shí)間復(fù)雜度均為O(n).8.單鏈表上的查找：（帶頭結(jié)點(diǎn))(1）按結(jié)點(diǎn)序號(hào)查找：序號(hào)為0的是頭結(jié)點(diǎn)。算法：p=head;j=0；//從頭結(jié)點(diǎn)開始掃描

while(p-〉next&&j〈i){//順指針向后掃描，直到p-〉next為NULL或i=j為止

p=p—〉next;

j++;}

if（i==j）returnp；//找到了第i個(gè)結(jié)點(diǎn)

elsereturnNULL；//當(dāng)i〈0或i〉0時(shí)，找不到第i個(gè)結(jié)點(diǎn)

時(shí)間復(fù)雜度：在等概率假設(shè)下，平均時(shí)間復(fù)雜度為：為n/2=O（n)（2）按結(jié)點(diǎn)值查找:具體算法:ListNode＊p=head—〉next；//從開始結(jié)點(diǎn)比較。表非空，p初始值指向開始結(jié)點(diǎn)

while(p&&p—>data!=key）//直到p為NULL或p—〉data為key為止

p=p—>next;//掃描下一結(jié)點(diǎn)

returnp；//若p=NULL，則查找失敗，否則p指向值為key的結(jié)點(diǎn)時(shí)間復(fù)雜度為：O（n)9.插入運(yùn)算：插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。

s=（ListNode*）malloc（sizeof(ListNode）)；②s—〉data=x;③s-〉next=p—〉next;④p—〉next=s；⑤算法的時(shí)間主要耗費(fèi)在查找結(jié)點(diǎn)上,故時(shí)間復(fù)雜度亦為O（n)。

10.刪除運(yùn)算r=p—>next;②//使r指向被刪除的結(jié)點(diǎn)aip—〉next=r—〉next③;//將ai從鏈上摘下free（r）;④//釋放結(jié)點(diǎn)ai的空間給存儲(chǔ)池算法的時(shí)間復(fù)雜度也是O（n).p指向被刪除的前一個(gè)結(jié)點(diǎn)。鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。11。單循環(huán)鏈表—在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)即可。判斷空鏈表的條件是head==head—〉next；12.僅設(shè)尾指針的單循環(huán)鏈表：用尾指針rear表示的單循環(huán)鏈表對(duì)開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是O(1)。而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表.判斷空鏈表的條件為rear==rear-〉next;13。循環(huán)鏈表：循環(huán)鏈表的特點(diǎn)是無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。若在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無(wú)須遍歷，其執(zhí)行時(shí)間是O(1）。具體算法：LinkListConnect(LinkListA，LinkListB)

{//假設(shè)A，B為非空循環(huán)鏈表的尾指針LinkListp=A—>next；//①保存A表的頭結(jié)點(diǎn)位置

A-〉next=B—>next—>next;//②B表的開始結(jié)點(diǎn)鏈接到A表尾

free（B—>next）；//③釋放B表的頭結(jié)點(diǎn)

B—〉next=p；//④

returnB;//返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒(méi)有NULL指針。涉及遍歷操作時(shí)，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p—＞next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。在單鏈表中，從一已知結(jié)點(diǎn)出發(fā)，只能訪問(wèn)到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無(wú)法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問(wèn)到表中所有結(jié)點(diǎn),這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。14。雙向鏈表:雙（向）鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指向其直接前趨的指針域prior。①雙鏈表由頭指針head惟一確定的。

②帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。

③將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)，為雙（向)循環(huán)鏈表。15。雙向鏈表的前插和刪除本結(jié)點(diǎn)操作①雙鏈表的前插操作voidDInsertBefore（DListNode*p，DataTypex)｛//在帶頭結(jié)點(diǎn)的雙鏈表中，將值為x的新結(jié)點(diǎn)插入*p之前，設(shè)p≠NULL

DListNode*s=malloc(sizeof(DListNode)）；//①

s—〉data=x；//②

s—〉prior=p-〉prior;//③

s-〉next=p；//④

p-〉prior-〉next=s;//⑤

p—〉prior=s;//⑥｝②雙鏈表上刪除結(jié)點(diǎn)＊p自身的操作voidDDeleteNode（DListNode＊p)

｛//在帶頭結(jié)點(diǎn)的雙鏈表中，刪除結(jié)點(diǎn)＊p，設(shè)*p為非終端結(jié)點(diǎn)

p->prior-〉next=p—〉next；//①

p—>next—〉prior=p—>prior;//②

free（p);｝//③

與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算法的時(shí)間復(fù)雜度均為O(1）。順序表和鏈表比較時(shí)間性能:a、線性表：經(jīng)常性的查找；b、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：經(jīng)常插入刪除操作；空間性能:a、對(duì)數(shù)據(jù)量大小事先能夠知道的用線性表；b、數(shù)據(jù)量變化較大的用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)密度越大，存儲(chǔ)空間的利用率越高.顯然，順序表的存儲(chǔ)密度是1，鏈表的存儲(chǔ)密度肯定小于1。第三章棧和隊(duì)列1。棧稱為后進(jìn)先出(LastInFirstOut）的線性表,簡(jiǎn)稱為L(zhǎng)IFO表。

棧是運(yùn)算受限的線性表，順序棧也是用數(shù)組表示的.進(jìn)棧操作：進(jìn)棧時(shí),需要將S-＞top加1，①S—＞top==StackSize—1表示棧滿②"上溢"現(xiàn)象--當(dāng)棧滿時(shí),再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。

退棧操作：退棧時(shí)，需將S—＞top減1，①S—＞top〈0表示空棧②"下溢”現(xiàn)象-—當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。

下溢是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件.空棧時(shí)棧頂指針不能是0，只能是-1。兩個(gè)棧共享同一存儲(chǔ)空間：當(dāng)程序中同時(shí)使用兩個(gè)棧時(shí)，可以將兩個(gè)棧的棧底分別設(shè)在順序存儲(chǔ)空間的兩端,讓兩個(gè)棧頂各自向中間延伸。當(dāng)一個(gè)棧中的元素較多而棧使用的空間超過(guò)共享空間的一半時(shí)，只要另一個(gè)棧的元素不多，那么前者就可以占用后者的部分存儲(chǔ)空間。當(dāng)Top1=Top2-1時(shí)，棧滿2。為了克服順序存儲(chǔ)分配固定空間所產(chǎn)生的溢出和空間浪費(fèi)問(wèn)題.可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)棧.鏈棧是沒(méi)有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表.棧頂指針就是鏈表的頭指針。鏈棧中的結(jié)點(diǎn)是動(dòng)態(tài)分配的,所以可以不考慮上溢,無(wú)須定義StackFull運(yùn)算棧的一個(gè)重要應(yīng)用是實(shí)現(xiàn)遞歸,直接調(diào)用自己或間接調(diào)用自己的函數(shù)。3。隊(duì)列(Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。允許刪除的一端稱為隊(duì)頭(Front）,允許插入的一端稱為隊(duì)尾（Rear),當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列,隊(duì)列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡(jiǎn)稱為FIFO表。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是一個(gè)受限的線性表.順序隊(duì)列的基本操作①入隊(duì)時(shí):將新元素插入rear所指的位置,然后將rear加1.

②出隊(duì)時(shí)：刪去front所指的元素，然后將front加1并返回被刪元素.當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。

在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而隊(duì)尾指針始終指向隊(duì)尾元素的下一位置.而棧頂指針指向棧頂元素.循環(huán)隊(duì)列:為充分利用數(shù)組空間，克服上溢，可將數(shù)組空間想象為一個(gè)環(huán)狀空間，并稱這種環(huán)狀數(shù)組表示的隊(duì)列為循環(huán)隊(duì)列。循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1，朝前移動(dòng)。只不過(guò)當(dāng)頭尾指針指向向量上界（QueueSize-1）時(shí),其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為：①方法一:

if(i+1==QueueSize）i=0;//i表示front或rear

elsei++；

②方法二-—利用"模運(yùn)算”

i=（i+1）%QueueSize；循環(huán)隊(duì)列中，由于入隊(duì)時(shí)尾指針向前追趕頭指針；出隊(duì)時(shí)頭指針向前追趕尾指針，造成隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等.因此，無(wú)法通過(guò)條件Q.front==Q.rear來(lái)判別隊(duì)列是"空"還是"滿”.解決這個(gè)問(wèn)題的方法至少有三種：

①另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿；

②設(shè)置一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（即隊(duì)列長(zhǎng)度）。

③少用一個(gè)元素的空間。約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針,若相等則認(rèn)為隊(duì)列滿即尾指針Q.rear所指的單元始終為空。5.循環(huán)隊(duì)列的基本運(yùn)算：①置隊(duì)空:Q-〉front=Q-〉rear=0;②判隊(duì)空:returnQ—>rear==Q-〉front;③判隊(duì)滿：return(Q—>rear+1)%QueueSize==Q—〉front；④入隊(duì)Q—>data[Q—〉rear]=x;

//新元素插入隊(duì)尾

Q—>rear=（Q—〉rear+1)%QueueSize;

⑤出隊(duì)temp=Q->data［Q->front]；

Q—〉front=(Q—>front+1）%QueueSize;

//循環(huán)意義下的頭指針加1

returntemp;⑥取隊(duì)頭元素returnQ—〉data[Q—>front］；隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。為了簡(jiǎn)化處理，在隊(duì)頭結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn)，并設(shè)隊(duì)頭指針指向此結(jié)點(diǎn)。鏈隊(duì)列的基本運(yùn)算:(帶頭結(jié)點(diǎn))（1）構(gòu)造空隊(duì):Q—〉rear=Q->front；Q—>rear->next=NULL;（2）判隊(duì)空：returnQ->rear==Q->front;（3）入隊(duì):QueueNode＊p=（QueueNode*)malloc(sizeof(QueueNode))；//申請(qǐng)新結(jié)點(diǎn)

p-〉data=x；

p—〉next=NULL；

Q-〉rear—>next=p；

//*p鏈到原隊(duì)尾結(jié)點(diǎn)后

Q—〉rear=p；

//隊(duì)尾指針指向新的尾(4)出隊(duì)：當(dāng)隊(duì)列長(zhǎng)度大于1時(shí)，只需修改頭結(jié)點(diǎn)指針，尾指針不變

s=Q->front—〉next；Q-〉front-〉next=s—〉next;x=s—〉data;free（s)；returnx；當(dāng)隊(duì)列長(zhǎng)度等于1時(shí),不僅要修改頭結(jié)點(diǎn)指針,還要修改尾指針s=Q->front-〉next;Q—>front-〉next=NULL；Q—>rear==Q-〉front;x=s—>data；free（s）;returnx；（5)取隊(duì)頭元素:returnQ—>front—〉next->data;因?yàn)橛蓄^結(jié)點(diǎn)，所以用了next①和鏈棧類似，無(wú)須考慮判隊(duì)滿的運(yùn)算及上溢。②在出隊(duì)算法中,一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí),該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針,且刪去此結(jié)點(diǎn)后隊(duì)列變空。7.用計(jì)算機(jī)來(lái)處理計(jì)算算術(shù)表達(dá)式問(wèn)題，首先要解決的問(wèn)題是如何將人們習(xí)慣書寫的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。第四章多維數(shù)組和廣義表1。數(shù)組的順序存儲(chǔ)方式：一般采用順序存儲(chǔ)方法表示數(shù)組。(1)行優(yōu)先順序

a11，a12，…，a1n，a21,a22，…，a2n，……，am1,am2,…，amn（2）列優(yōu)先順序

a11，a21，…,am1,a12，a22,…，am2,……,a1n,a2n,…，amnPascal和C語(yǔ)言是按行優(yōu)先順序存儲(chǔ)的,而Fortran語(yǔ)言是按列優(yōu)先順序存儲(chǔ)的。按行優(yōu)先順序存儲(chǔ)的二維數(shù)組Amn地址計(jì)算公式

LOC(aij）=LOC（a11）+［（i-1）×n+j—1]×d(注:此公式下界為1，如下界為0,則公式變?yōu)椋踚×n+j］）按列優(yōu)先順序存儲(chǔ)的二維數(shù)組Amn地址計(jì)算公式

LOC（aij)=LOC(a11）+[（j—1)×m+i—1］×d(注：此公式下界為1，如下界為0，則公式變?yōu)椋踛×m+i])按行優(yōu)先順序存儲(chǔ)的三維數(shù)組Amnp地址計(jì)算公式

LOC(aijk)=LOC（a111)+［(i-1)×n×p+(j-1）×p+k—1]×d(注：此公式下界為1，如下界為0，則公式變?yōu)椋踚×n×p+j×p+k])2.為了節(jié)省存儲(chǔ)空間，可以對(duì)矩陣中有許多值相同或值為零的元素的矩陣，采用壓縮存儲(chǔ)。特殊矩陣是指相同值的元素或零元素在矩陣中的分布有一定的規(guī)律。常見的有對(duì)稱矩陣、三角矩陣。(1)對(duì)稱矩陣在一個(gè)n階方陣A中,若元素滿足下述性質(zhì)：

aij=aji0≤i，j≤n—1稱為n階對(duì)稱矩陣，它的元素是關(guān)于主對(duì)角線對(duì)稱的，所以只需要存儲(chǔ)矩陣上三角或下三角元素即可,讓兩個(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間.矩陣元素aij和數(shù)組元素sa【k】之間的關(guān)系是k=i×（i+1）/2+ji≥j0≤k<n（n+1)/2—1k=j×（j+1)/2+ii＜j0≤k<n（n+1)/2—1對(duì)稱矩陣的地址計(jì)算公式:LOC(aij)=LOC(sa[0］)+[I×(I+1）/2+J］×d，其中I=max（i,j)，J=min（i，j)（2)三角矩陣：以主對(duì)角線劃分,三角矩陣有上三角和下三角兩種。上三角矩陣是指它的下三角(不包括主角線)中的元素均為常數(shù)c或零；下三角矩陣的主對(duì)角線上方均為常數(shù)c或零。一般情況，三角矩陣的常數(shù)c均為零.三角矩陣的壓縮存儲(chǔ)：三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間,其余的元素正好有n×（n+1)/2個(gè),因此，三角矩陣可壓縮存儲(chǔ)在一維數(shù)組sa[n(n+1）/2+1］中，其中c存放在數(shù)組的最后一個(gè)元素中。①上三角矩陣中aij和sa[k］之間的對(duì)應(yīng)關(guān)系k=i×（2n—i+1)/2+j—i當(dāng)i≤jk=n×（n+1)/2當(dāng)i＞j②下三角矩陣中aij和sa[k]之間的對(duì)應(yīng)關(guān)系k=i×（i+1）/2+j當(dāng)i≥jk=n×（n+1）/2當(dāng)i＜j三角矩陣的壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取結(jié)構(gòu)。3.稀疏矩陣：設(shè)矩陣Amn中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù),則稱A為稀疏矩陣。為了節(jié)省存儲(chǔ)單元，可用壓縮存儲(chǔ)方法只存儲(chǔ)非零元素.由于非零元素的分布一般是沒(méi)有規(guī)律的,因此在存儲(chǔ)非零元素的同時(shí)，還必須存儲(chǔ)非零元素所在的行、列位置,所以可用三元組（i，j,aij)來(lái)確定非零元素.稀疏矩陣進(jìn)行壓縮存儲(chǔ)通常有兩類方法:順序存儲(chǔ)（三元組表）和鏈?zhǔn)酱鎯?chǔ)（十字鏈表）。稀疏矩陣的壓縮存儲(chǔ)會(huì)失去隨機(jī)存取功能.4.廣義表是線性表的推廣,又稱列表.廣義表是n(n≥0)個(gè)元素a1，a2,…，ai,…,an的有限序列.其中ai或者是原子或者是一個(gè)廣義表.

①?gòu)V義表通常用圓括號(hào)括起來(lái)，用逗號(hào)分隔其中的元素。

②為了區(qū)分原子和廣義表，書寫時(shí)用大寫字母表示廣義表,用小寫字母表示原子。

③若廣義表Ls非空(n≥1),則al是LS的表頭，其余元素組成的表(a1，a2，…，an)稱為L(zhǎng)s的表尾.

④廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個(gè)表展開后所含括號(hào)的層數(shù)稱為廣義表的深度。19.廣義表是一種多層次的線性結(jié)構(gòu)，實(shí)際上這就是一種樹形結(jié)構(gòu).廣義表的兩個(gè)特殊的基本運(yùn)算：取表頭head（Ls）和取表尾tail（Ls).任何一個(gè)非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。

head=(a，b)=a，tail（a，b)=（b）

對(duì)非空表A和(y），也可繼續(xù)分解.

注意:廣義表（)和（（））不同。前者是長(zhǎng)度為0的空表，對(duì)其不能做求表頭和表尾的運(yùn)算；而后者是長(zhǎng)度為l的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表（）。廣義表是一種有層次的非線性結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)由3個(gè)域構(gòu)成，其中一個(gè)是tag標(biāo)志位，用來(lái)區(qū)分結(jié)點(diǎn)是原子還是子表，當(dāng)tag為零時(shí)結(jié)點(diǎn)是子表，第二個(gè)域?yàn)閟link，用以存放子表的地址；當(dāng)tag為1時(shí)結(jié)點(diǎn)是原子，第二個(gè)域?yàn)閐ata，用以存放元素值。第五章樹和二叉樹1。樹的表示法：最常用的是樹形圖表示法；還有3種嵌套集合、凹形、廣義表.樹結(jié)構(gòu)的基本術(shù)語(yǔ)

（1）結(jié)點(diǎn)的度（Degree)

樹中的一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度（Degree）。一棵樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù)。

度為零的結(jié)點(diǎn)稱為葉子（Leaf）或終端結(jié)點(diǎn)。度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。

除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。根結(jié)點(diǎn)又稱為開始結(jié)點(diǎn).

（2）①路徑（path）若樹中存在一個(gè)結(jié)點(diǎn)序列k1，k2，…，ki，使得ki是ki+1的雙親(1≤i<j）,則稱該結(jié)點(diǎn)序列是從kl到kj的一條路徑（Path）。一個(gè)結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)過(guò)的所有結(jié)點(diǎn)，而一個(gè)結(jié)點(diǎn)的子孫則是以該結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)。

結(jié)點(diǎn)的層數(shù)（Level)從根起算：根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1.

雙親在同一層的結(jié)點(diǎn)互為堂兄弟.

樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度(Height)或深度(Depth).

若將樹中每個(gè)結(jié)點(diǎn)的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹（OrderedTree）；否則稱為無(wú)序樹（UnoderedTree)。若不特別指明，一般討論的樹都是有序樹。

森林(Forest)是m(m≥0)棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根，就得到一個(gè)森林；反之,加上一個(gè)結(jié)點(diǎn)作樹根,森林就變?yōu)橐豢脴洹?.二叉樹與度數(shù)為2的有序樹不同：在有序樹中,雖然一個(gè)結(jié)點(diǎn)的孩子之間是有左右次序的,但是若該結(jié)點(diǎn)只有一個(gè)孩子,就無(wú)須區(qū)分其左右次序.而在二叉樹中，即使是一個(gè)孩子也有左右之分.二叉樹的性質(zhì):性質(zhì)1二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2i—1（i≥1).例如5層的二叉樹，第5層上的結(jié)點(diǎn)數(shù)目最多為24=16性質(zhì)2深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）。例如深度為5的二叉樹,至多有25—1=31個(gè)結(jié)點(diǎn)性質(zhì)3在任意—棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則no=n2+1。例如一棵深度為4的二叉樹（a）,其終端結(jié)點(diǎn)數(shù)n0為8，度為2的結(jié)點(diǎn)樹為7，則8=7+1，no=n2+1成立（b）其終端結(jié)點(diǎn)數(shù)n0為6,度為2的結(jié)點(diǎn)樹為5，則6=5+1，no=n2+1成立滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二又樹稱為滿二叉樹。滿二叉樹的特點(diǎn)：（1）每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。即對(duì)給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹.（2）滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹，且樹葉都在最下一層上。完全二叉樹:若一棵深度為k的二叉樹,其前k-1層是一棵滿二叉樹，而最下面一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹.特點(diǎn)：

（1）滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。

(2）在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。

（3）在完全二叉樹中，若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子,則它一定沒(méi)有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn).性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。?logn?+1或?log（n+1)?例,具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為:?lg100?+1=7,26=6427=128所以?lg100?=6，?lg(100+1）?=74。完全二叉樹的編號(hào)特點(diǎn)：完全二叉樹中除最下面一層外，各層都充滿了結(jié)點(diǎn)。每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié)點(diǎn)個(gè)數(shù)的2倍.從一個(gè)結(jié)點(diǎn)的編號(hào)就可推得其雙親，左、右孩子等結(jié)點(diǎn)的編號(hào)。編號(hào)從0開始①若i=0,則qi為根結(jié)點(diǎn),無(wú)雙親；否則，qi的雙親編號(hào)為?（i—1)/2?。②若2i+1〈n，則qi的左孩子的編號(hào)是2i+1;否則，qi無(wú)左孩子，即qi必定是葉子。③若2i+2〈n，則qi的右孩子的編號(hào)是2i+2；否則，qi無(wú)右孩子.對(duì)于完全二叉樹而言，使用順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單又節(jié)省存儲(chǔ)空間。但對(duì)于一般二叉樹來(lái)說(shuō)，采用順序存儲(chǔ)時(shí),為了使用結(jié)點(diǎn)在數(shù)組中的相對(duì)位置來(lái)表示結(jié)點(diǎn)之間的邏輯關(guān)系，就必須增加一些虛結(jié)點(diǎn)使其成為完全二叉樹的形式。5.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。用鏈接方式存儲(chǔ)二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針域lchild和rchild,分別指向該結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)的結(jié)構(gòu)為：二叉鏈表是一種常用的二叉樹存儲(chǔ)結(jié)構(gòu)。建立二叉鏈表方法：a、按廣義表方法，靠近左括號(hào)的結(jié)點(diǎn)是在左子樹上，而逗號(hào)右邊結(jié)點(diǎn)是在右子樹上。b、按完全二叉樹的層次順序建立結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有2n個(gè)指針域。其中有n-1個(gè)用來(lái)指示結(jié)點(diǎn)的左、右孩子，其余的n+1個(gè)為空。二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。中序遍歷的遞歸算法定義：（1)遍歷左子樹；（2)訪問(wèn)根結(jié)點(diǎn);（3）遍歷右子樹。先序遍歷的遞歸算法定義:(1）訪問(wèn)根結(jié)點(diǎn);(2）遍歷左子樹；(3)遍歷右子樹.后序遍歷得遞歸算法定義：(1)遍歷左子樹;（2）遍歷右子樹；(3）訪問(wèn)根結(jié)點(diǎn)。遞歸工作棧中包括兩項(xiàng):一項(xiàng)是遞歸調(diào)用的語(yǔ)句編號(hào),另一項(xiàng)則是指向根結(jié)點(diǎn)的指針。已知一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。具體方法如下:首先根據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根，然后根據(jù)中序遍歷序列確定各子樹根的左右子樹。6.線索二叉樹：n個(gè)結(jié)點(diǎn)的二叉鏈表必定存在n+1個(gè)空指針域，可以利用這些空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針，這種指向前驅(qū)和后繼結(jié)點(diǎn)的指針?lè)Q為"線索”，這種加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded

BinaryTree)。線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)：其中：ltag和rtag是增加的兩個(gè)標(biāo)志域，用來(lái)區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針,還是指向其前趨或后繼的線索。

圖中的實(shí)線表示指針，虛線表示線索。線索二叉樹中，一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為:左、右標(biāo)志均是1。7。二叉樹的線索化：把對(duì)一棵二叉線索鏈表結(jié)構(gòu)中所有結(jié)點(diǎn)的空指針域按照某種遍歷次序加線索的過(guò)程稱為線索化.和中序遍歷算法一樣，遞歸過(guò)程中對(duì)每結(jié)點(diǎn)僅做一次訪問(wèn)。因此對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹，線索化的算法時(shí)間復(fù)雜度為O(n）。8.樹、森林到二叉樹的轉(zhuǎn)換：樹中每個(gè)結(jié)點(diǎn)最多只有一個(gè)最左邊的孩子(長(zhǎng)子）和一個(gè)右鄰的兄弟。將樹轉(zhuǎn)換成二叉樹:①在所有兄弟結(jié)點(diǎn)之間加一道連線;②對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其長(zhǎng)子的連線外，去掉該結(jié)點(diǎn)與其它孩子的連線.由于樹根沒(méi)有兄弟,故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點(diǎn)的右子樹必為空。將一個(gè)森林轉(zhuǎn)換為二叉樹:將森林中的每棵樹轉(zhuǎn)化成二叉樹,然后再將二叉樹的根節(jié)點(diǎn)看做兄弟連在一起,形成一棵二叉樹9。二叉樹到樹、森林的轉(zhuǎn)換：方式是：若二叉樹中結(jié)點(diǎn)x是雙親y的左孩子,則把x的右孩子,右孩子的右孩子，…，都與y用連線連起來(lái)，最后去掉所有雙親到右孩子的連線。10。樹的存儲(chǔ)結(jié)構(gòu)：1.雙親表示法：雙親鏈表表示法利用樹中每個(gè)結(jié)點(diǎn)的雙親唯一性，在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指向其雙親的指針parent，惟一地表示任何-棵樹。（1)雙親鏈表表示法的實(shí)現(xiàn)分析：E和F所在結(jié)點(diǎn)的雙親域是1,它們的雙親結(jié)點(diǎn)在向量中的位置是1，即B是它們的雙親。

注意：①根無(wú)雙親,其parent域?yàn)椤?.

②雙親鏈表表示法中指針parent向上鏈接,適合求指定結(jié)點(diǎn)的雙親或祖先（包括根)；求指定結(jié)點(diǎn)的孩子或其它后代時(shí)，可能要遍歷整個(gè)數(shù)組。2.孩子鏈表法:孩子鏈表表示法是為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表,并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。注意：①孩子結(jié)點(diǎn)的數(shù)據(jù)域僅存放了它們?cè)谙蛄靠臻g的序號(hào)。

②與雙親鏈表表示法相反,孩子鏈表表示便于實(shí)現(xiàn)涉及孩子及其子孫的運(yùn)算,但不便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算。

③將雙親鏈表表示法和孩子鏈表表示法結(jié)合起來(lái)，可形成雙親孩子鏈表表示法。3。孩子兄弟表示法：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域，即可得樹的孩子兄弟鏈表表示。注意：

這種存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是:它和二叉樹的二叉鏈表表示完全一樣.可利用二叉樹的算法來(lái)實(shí)現(xiàn)對(duì)樹的操作.11。樹的遍歷：一般都只給出兩種次序遍歷樹的方法:前序（先根次序)遍歷和后序(后根次序）遍歷.①前序遍歷一棵樹等價(jià)于前序遍歷該樹對(duì)應(yīng)的二叉樹

②后序遍歷一棵樹等價(jià)于中序遍歷該樹對(duì)應(yīng)的二叉樹。

對(duì)下面(a)圖中所示的森林進(jìn)行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE。而（b）圖所示二叉樹的前序序列和中序序列也分別為ABCDEFIGJH和BDCAIFJGHE。前序遍歷森林等同于前序遍歷該森林對(duì)應(yīng)的二叉樹后序遍歷森林等同于中序遍歷該森林對(duì)應(yīng)的二叉樹12.從根結(jié)點(diǎn)到某結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度，樹種所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和稱為樹的帶權(quán)路徑長(zhǎng)度.帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。哈夫曼樹不一定是二叉樹。哈夫曼樹又稱為最優(yōu)樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹.完全二叉樹就是這種路徑長(zhǎng)度最短的二叉樹。①只有葉結(jié)點(diǎn)上的權(quán)值均相同時(shí)，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹。

②最優(yōu)二叉樹中,權(quán)越大的葉子離根越近。③最優(yōu)二叉樹的形態(tài)不唯一，WPL最小。13.哈夫曼算法:基本思想是：（1)根據(jù)給定的n個(gè)權(quán)值wl，w2，…，wn構(gòu)成n棵二叉樹的森林F=｛T1，T2,…，Tn}，其中每棵二叉樹Ti中都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左右子樹均空。

（2)在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹（當(dāng)這樣的樹不止兩棵樹時(shí)，可以從中任選兩棵），將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個(gè)新結(jié)點(diǎn)作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子（誰(shuí)左，誰(shuí)右無(wú)關(guān)緊要）,將這兩個(gè)孩子的權(quán)值之和作為新樹根的權(quán)值。

（3)對(duì)新的森林F重復(fù)（2)，直到森林F中只剩下一棵樹為止.這棵樹便是哈夫曼樹。

注意：①初始森林中的n棵二叉樹，每棵樹有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子

②n個(gè)葉子的哈夫曼樹要經(jīng)過(guò)n—1次合并，產(chǎn)生n—1個(gè)新結(jié)點(diǎn).最終求得的哈夫曼樹中共有2n—1個(gè)結(jié)點(diǎn)。

③哈夫曼樹是嚴(yán)格的二叉樹，沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)。14。哈夫曼編碼：數(shù)據(jù)壓縮過(guò)程稱為編碼，反之，解壓縮的過(guò)程稱為解碼.設(shè)計(jì)一種長(zhǎng)短不等的編碼，則必須保證任一字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼稱為前綴編碼.可以利用二叉樹來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼,其左分支表示字符0，右分支表示字符1,則以根結(jié)點(diǎn)到葉結(jié)點(diǎn)路徑上的分支字符組成的串作為該葉節(jié)點(diǎn)的字符編碼。因此設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是哈夫曼編碼。譯碼過(guò)程是從樹根結(jié)點(diǎn)出發(fā)，逐個(gè)讀入電文中的二進(jìn)制碼。第六章圖1。圖G由兩個(gè)集合構(gòu)成，頂點(diǎn)集合和邊集合,也可以圖G只有頂點(diǎn)而沒(méi)有邊。用尖括號(hào)表示圖的有向邊<vi,vj〉,有向邊又稱為弧，起點(diǎn)稱為弧尾,終點(diǎn)稱為弧頭。無(wú)向圖的頂點(diǎn)對(duì)用圓括號(hào)表示（vi，vj）。在無(wú)向圖中，稱vi和vj相鄰接，在有向圖中稱頂點(diǎn)vi鄰接到vj,頂點(diǎn)vj鄰接于vi在無(wú)向圖中，n的取值范圍是0—n(n—1）/2，將具有n(n—1)/2條邊的無(wú)向圖稱為無(wú)向完全圖。在有向圖中，n的取值范圍是0—n（n-1）,將具有n（n—1)條邊的有向圖稱為有向完全圖。無(wú)向圖中，頂點(diǎn)的度定義為以該頂點(diǎn)為一個(gè)端點(diǎn)的邊的數(shù)目，有向圖的度等于出度和入度之和。在無(wú)向圖中，任意兩頂點(diǎn)都有路徑，則稱兩頂點(diǎn)連通.若圖G中的任意兩個(gè)頂點(diǎn)都連通，稱G為連通圖。無(wú)向圖的極大連通子圖稱為連通分量,顯然，任何連通圖的連通分量只有一個(gè)，即其自身,而非連通的無(wú)向圖有多個(gè)連通分量.在有向圖中，圖G中任意兩頂點(diǎn)連通,稱為強(qiáng)連通圖，極大連通子圖稱為強(qiáng)連通分量.若在一個(gè)圖的每條邊上標(biāo)上某種數(shù)值，該數(shù)值稱為該邊的權(quán)。邊上帶權(quán)的圖稱為帶權(quán)圖,帶權(quán)的連通圖稱為網(wǎng)絡(luò)。2.圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。圖的頂點(diǎn)編號(hào)從0開始。鄰接矩陣表示法:<vi,vj>或（vi,vj）是邊,則值為1，不是邊則值為0.無(wú)向圖的鄰接矩陣是按主對(duì)角線對(duì)稱的。若G是帶權(quán)圖，只要把1換成相應(yīng)邊上的權(quán)值即可,0的位置上可以不動(dòng)或?qū)⑵鋼Q成無(wú)窮大表示。無(wú)向圖的鄰接矩陣表示法可以僅存儲(chǔ)主對(duì)角線以下的元素，時(shí)間復(fù)雜度為O(n2)鄰接表表示法:鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。將無(wú)向圖的鄰接表稱為邊表，將有向圖的鄰接表稱為出邊表,將鄰接表的表頭向量稱為頂點(diǎn)表。若無(wú)向圖有n個(gè)頂點(diǎn)和e條邊,則它的鄰接表共有n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。建立鄰接表的時(shí)間復(fù)雜度是O（n+e).圖的鄰接表表示不是唯一的，這是因?yàn)樵诿總€(gè)頂點(diǎn)的鄰接表中,各邊結(jié)點(diǎn)的鏈接次序可以是任意的，其具體鏈接次序與邊的輸入次序和生成算法有關(guān)。3.圖的遍歷：遍歷圖的算法是求解圖的連通性、圖的拓?fù)渑判虻人惴ǖ幕A(chǔ)。圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法。深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。按訪問(wèn)頂點(diǎn)的先后次序得到的頂點(diǎn)序列稱為圖的深度優(yōu)先遍歷序列，或簡(jiǎn)稱為DFS序列。共需要搜索n2個(gè)矩陣元素，時(shí)間復(fù)雜度為鄰接矩陣O(n2）或鄰接表O（n+e)。廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷，先被訪問(wèn)的頂點(diǎn),其鄰接點(diǎn)也先被訪問(wèn)，就是先進(jìn)先出。時(shí)間復(fù)雜度為鄰接矩陣O(n2）或鄰接表O(n+e），空間復(fù)雜度都是O(n)。4.生成樹是連通圖的包含圖中所有頂點(diǎn)的一個(gè)極小連通子圖,一個(gè)圖的極小連通子圖恰為一個(gè)無(wú)回路的連通圖，也就是說(shuō)，若圖中任意添加一條邊，就會(huì)出現(xiàn)回路，若去掉任意一條邊，都會(huì)使之成為非連通圖。因此，一個(gè)具有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊，但有n-1條邊的圖不一定是生成樹，同一個(gè)圖可以有不同的生成樹.生成樹定義為：若從圖的某頂點(diǎn)出發(fā)，可以系統(tǒng)的訪問(wèn)到圖的所有頂點(diǎn)，則遍歷時(shí)經(jīng)過(guò)的邊和圖的所有頂點(diǎn)所構(gòu)成的子圖，稱為該圖的生成樹.最小生成樹：圖的生成樹不唯一，把權(quán)值最小的生成樹稱為最小生成樹（MST）。構(gòu)造最小生成樹的算法：普里姆Prim算法的時(shí)間復(fù)雜度為O(n2）與網(wǎng)中邊數(shù)無(wú)關(guān)適于稠密圖?？唆斔箍朘ruskal算法的時(shí)間復(fù)雜度為O（eloge），主要取決于邊數(shù)，較適合于稀疏圖。5。最短路徑：Dijkstra迪杰斯特拉算法,提出了按路徑長(zhǎng)度遞增的順序產(chǎn)生諸頂點(diǎn)的最短路徑算法。拓?fù)渑判颍鹤庸こ谭Q為活動(dòng)，頂點(diǎn)代表活動(dòng)，有向邊代表活動(dòng)的先后關(guān)系。這樣的有向無(wú)環(huán)圖DAG稱為頂點(diǎn)活動(dòng)網(wǎng),簡(jiǎn)稱為AOV網(wǎng)。將有向無(wú)環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列,若〈u，v〉∈E（G），則在線性序列u在v之前,這種線性序列稱為拓?fù)湫蛄?。由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判?。檢測(cè)的方法是:對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)湫蛄?，若網(wǎng)中所有頂點(diǎn)都在他的拓?fù)湫蛄兄?，則AOV網(wǎng)必定不存在環(huán).AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?。拓?fù)渑判虻拿枋鏊枷?a、在有向圖中選一個(gè)沒(méi)有前趨(入度為零）的頂點(diǎn),且輸出之。b、從有向圖中刪除該頂點(diǎn)及其與該頂點(diǎn)有關(guān)的所有邊.c、重復(fù)上述步驟，直到全部頂點(diǎn)都已輸出或圖中剩余的頂點(diǎn)中沒(méi)有前趨頂點(diǎn)為止。d、輸出剩余的無(wú)前趨結(jié)點(diǎn).拓?fù)渑判驅(qū)嶋H上是對(duì)鄰接表表示的圖G進(jìn)行遍歷的過(guò)程。時(shí)間復(fù)雜度是O（n+e)。第七章排序1。如果待排序文件中存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)過(guò)排序后,這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變,該排序方法是穩(wěn)定的；反之，則是不穩(wěn)定的。排序在內(nèi)存中處理，不涉及數(shù)據(jù)的內(nèi)外存交換，稱為內(nèi)部排序，反之為外部排序。內(nèi)部排序又分為五類:插入、選擇、交換、歸并和分配排序。在排序過(guò)程中需進(jìn)行兩種操作：比較兩個(gè)關(guān)鍵字的大小、改變指向記錄的指針或移動(dòng)記錄本身，而待排序記錄的存儲(chǔ)形式一般有三種：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)和輔助表。評(píng)價(jià)排序算法的標(biāo)準(zhǔn)：執(zhí)行算法需要的時(shí)間,以及算法所需要的附加空間。還有算法本身的復(fù)雜度。排序的時(shí)間開銷，一般情況下可用算法中關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)來(lái)衡量。2。插入排序：每次將一個(gè)待排序記錄按其關(guān)鍵字大小插入到前面已排好序的文件中的適當(dāng)位置.直接插入排序:每次從無(wú)序區(qū)取出第一個(gè)元素把它插入到有序區(qū)的適當(dāng)位置，使之成為新的有序區(qū)，經(jīng)過(guò)n-1次插入后完成.算法中R［0］作用:保存R[i]副本，監(jiān)視數(shù)組下標(biāo)變量j是否越界.所以R[0]稱為哨兵。每次的比較是從后往前比較的。時(shí)間復(fù)雜度最好是O（n)，最壞是O(n2），所以是O（n2）?？臻g復(fù)雜度O(1)，所以是就地排序。是穩(wěn)定的算法.初始情況是有序區(qū)中只有一個(gè)元素R[1］，無(wú)序區(qū)中R[2.。n]。希爾排序（縮小增量排序）：算法不穩(wěn)定.記錄的總比較次數(shù)和總移動(dòng)次數(shù)都要比直接插入排序少得多，特別是當(dāng)n越大越明顯。希爾排序的時(shí)間依賴于增量序列，最后一個(gè)增量必須是1，盡量避免增量互為倍數(shù)的情況.3.交換排序：兩兩比較待排序記錄的關(guān)鍵字，如果發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序位置。冒泡排序（起泡排序)：通過(guò)相鄰元素之間比較和交換,使較小移向頂部，從后往前兩兩比較。時(shí)間復(fù)雜度最好是O(n)，最壞是O（n2)，所以是O（n2).是穩(wěn)定的排序算法。快速排序（劃分交換排序)：是冒泡排序的改進(jìn)。比較和交換從兩端向中間進(jìn)行。一趟快速排序步驟：設(shè)兩個(gè)指針i和j，初值分別為low和high，基準(zhǔn)為x=R[i］,首先從j位置開始向前搜索第一個(gè)小于基準(zhǔn)x.key的記錄存入i所指位置上，i自增1，然后從i所指位置向后搜索找到第一個(gè)大于基準(zhǔn)x.key的記錄存入j所指位置上，j自減1，重復(fù)直至i=j為止。快速排序是不穩(wěn)定的。有非常好的時(shí)間復(fù)雜度,優(yōu)于其他各種排序算法，O（nlog2n)，但是當(dāng)記錄關(guān)鍵字有序或基本有序時(shí)復(fù)雜度反而大了使之轉(zhuǎn)變成冒泡排序?yàn)镺（n2)。快速排序是遞歸的，需要一個(gè)棧空間，空間復(fù)雜度O（log2n）。4.選擇排序：每一趟在待排序的記錄中選出關(guān)鍵字最小的記錄,依次存放在已排序好的記錄序列的最后。直接選擇排序：初始時(shí)，R［1.。n]為無(wú)序區(qū)，R[1]為空；第一趟是在R[1。.n]中選出最小的記錄與R[1］交換，R［1］為有序區(qū)；第二趟是在R［2..n］中選出最小的記錄與R［2］交換，R［1。.2］為有序區(qū)。時(shí)間復(fù)雜度O(n2)，是不穩(wěn)定的。初始情況是有序區(qū)為空，無(wú)序區(qū)中R［1..n]，第一趟從R［1。.n］選擇最小記錄與R［1］交換.堆排序：是對(duì)直接選擇排序的改進(jìn)，是一種樹形選擇排序?；舅枷耄涸谂判蜻^(guò)程中，將記錄數(shù)組R[1.。n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系,在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大或最小記錄。每一趟排序：將當(dāng)前無(wú)序區(qū)調(diào)整為一個(gè)大根堆，選取關(guān)鍵字最大的堆頂記錄，將他和無(wú)序區(qū)中最后一個(gè)記錄交換.堆排序是一個(gè)不斷建堆的過(guò)程。構(gòu)造堆的過(guò)程：R[1］作為二叉樹的根，R[2。.n]依次逐層從左到右順序排列，構(gòu)成一棵完全二叉樹，任意結(jié)點(diǎn)R[i]的左孩子是R［2i］,右孩子是R［2i+1],雙親是R?i/2?,此稱為篩選法。從?n/2?開始。每一趟的時(shí)間復(fù)雜度是O(log2n)，整個(gè)堆排序的時(shí)間復(fù)雜度是O（nlog2n).5。歸并排序:首先將待排序文件看成n個(gè)長(zhǎng)度為1的有序子文件，把這些子文件兩兩歸并，得到?n/2?個(gè)長(zhǎng)度為2的有序子文件,然后再將他們兩兩歸并，如此反復(fù),直到得到一個(gè)長(zhǎng)度為n的有序文件，此稱為二路歸并排序。每一趟歸并排序的時(shí)間復(fù)雜度是O（n），所以總的時(shí)間復(fù)雜度是O(nlog2n）。6。分配排序：前面方法都至少需要進(jìn)行?nlogn?次比較，而分配排序?qū)r(shí)間復(fù)雜度降為O（n）。箱排序(桶排序)：基數(shù)排序：是對(duì)箱排序的改進(jìn)和推廣。箱排序只適用于關(guān)鍵字取值范圍較小的情況，否則所需箱子數(shù)目太多。每個(gè)分量可能取值的個(gè)數(shù)rd稱為基數(shù)，基數(shù)的選擇和關(guān)鍵字的分解因關(guān)鍵字的類型而異。d趟箱排序?；鶖?shù)排序中，沒(méi)有進(jìn)行關(guān)鍵字的比較和記錄的移動(dòng)，而只是掃描鏈表和進(jìn)行指針賦值,所以排序的時(shí)間主要用在修改指針上，初始化鏈表時(shí)間為O（n）。7。內(nèi)部排序方法分析比較:本章除基數(shù)排序外，都是在順序表上實(shí)現(xiàn)的.時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性插入直接插入O（n2)O(1）穩(wěn)定希爾排序O（nlog2n）或O（n1.25)O（1）不穩(wěn)定交換冒泡排序O(n2)O(1)穩(wěn)定快速排序O(nlog2n)O(log2n)不穩(wěn)定選擇直接選擇O（n2)O(1)不穩(wěn)定堆排序O（nlog2n）O(1)不穩(wěn)定歸并排序歸并排序O（nlog2n)O（n)穩(wěn)定分配排序基數(shù)排序O（d*(rd+n））rd是基數(shù)，d是關(guān)鍵字位數(shù).n是元素個(gè)數(shù)O（rd+n)穩(wěn)定箱排序選取排序方法時(shí)需要考慮的主要因素:a、待排序的記錄個(gè)數(shù)，b、記錄本身的大小和存儲(chǔ)結(jié)構(gòu)，c、關(guān)鍵字的分布情況,d、對(duì)排序穩(wěn)定性的要求，e、時(shí)間和空間復(fù)雜度要等排序方法的選取:a、若待排序的一組記錄數(shù)目n較小(如n≤50)時(shí),可采用插入排序或選擇排序；b、n較大時(shí)，則應(yīng)采用快速排序、堆排序或歸并排序;c、若待排序記錄按關(guān)鍵字基本有序時(shí)，則宜選用直接插入排序或冒泡排序；d、當(dāng)n很大,而且關(guān)鍵字位數(shù)較少時(shí)，采用鏈?zhǔn)交鶖?shù)排序較好；e、關(guān)鍵字比較次數(shù)與記錄的初始排列順序無(wú)關(guān)的排序方法是選擇排序。一般的排序方法都可以在順序結(jié)構(gòu)上實(shí)現(xiàn)，當(dāng)記錄本身信息量較大時(shí)，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。插入、歸并、基數(shù)排序易于在鏈表上實(shí)現(xiàn);快速排序和堆排序可以提取關(guān)鍵字建立索引表，然后對(duì)索引表進(jìn)行排序.第八章：查找1.查找又稱檢索，是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。查找也分為內(nèi)查找和外查找。運(yùn)算查找的主要操作是關(guān)鍵字的比較,因此把查找過(guò)程中的平均比較次數(shù)（也稱為平均查找長(zhǎng)度)作為衡量算法效率優(yōu)劣的標(biāo)準(zhǔn).2.順序表的查找：順序查找和二分查找順序查找又稱線性查找：查找成功的平均查找長(zhǎng)度(n+1）/2，即約為表長(zhǎng)的一半.如果查找成功和不成功機(jī)會(huì)相等,那么平均查找長(zhǎng)度3(n+1）/4。優(yōu)點(diǎn)是簡(jiǎn)單，對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論是順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)、無(wú)論是否有序,都同樣適用，缺點(diǎn)是效率低。對(duì)于有序表來(lái)說(shuō)，該算法的平均查找長(zhǎng)度是（n+1)/2。二分查找(折半查找)：要求查找對(duì)象的線性表必須是順序存儲(chǔ)結(jié)構(gòu)的有序表。查找過(guò)程是遞歸的。樹中每個(gè)子樹的根節(jié)點(diǎn)對(duì)應(yīng)當(dāng)前查找區(qū)間的中位記錄R［mid]，它的左子樹和右子樹分別對(duì)應(yīng)區(qū)間的左子表和右子表，通常將此樹稱為二叉判定樹。由于二分查找是在有序表上進(jìn)行的，所以其對(duì)應(yīng)的判定樹必定是一棵二叉排序樹。二叉判定樹一定是二叉排序樹,二叉排序樹又稱為二叉查找樹。從判定樹上可見,關(guān)鍵字比較的次數(shù)恰好為該結(jié)點(diǎn)在樹中的層數(shù)。因此，二分查找算法在查找成功時(shí)進(jìn)行關(guān)鍵字比較的次數(shù)最多不超過(guò)判定樹的深度。查找成功時(shí)的平均查找長(zhǎng)度（n+1）/nlog2(n+1)-1,當(dāng)n很大時(shí)，可近似用log2（n+1)-1表示。因?yàn)榕卸涠葦?shù)小于2的結(jié)點(diǎn)只可能在最下面的兩層，所以n個(gè)結(jié)點(diǎn)的判定樹的深度和n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同，即為?log2(n+1)??？梢姡植檎业淖顗男阅芎推骄阅芟喈?dāng)接近。二叉判定樹的輸出：每次以?(low+high）/2?為根建樹.3.索引順序查找（分塊查找):是一種介于順序查找和二分查找之間的查找方法。要求分塊有序，前一塊的最大關(guān)鍵字小于后一塊的最小關(guān)鍵字，抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成索引表.分塊查找的基本思想是：首先查找索引表,可用二分查找或順序查找，然后在確定的塊中進(jìn)行順序查找。平均查找長(zhǎng)度：二分查找log(n/s+1）+s/2,順序查找(s2+2s+n)/2s。4。三種查找方法比較順序查找缺點(diǎn)是n較大時(shí),查找成功約為（n+1)/2，失敗需要比較n+1次.二分查找成功時(shí)約為log2（n+1）-1，但是他要求表以順序存儲(chǔ)且按關(guān)鍵字有序，適用于表不易變動(dòng)且又經(jīng)常查找的情況.分塊查找的優(yōu)點(diǎn)是，在表中插入或刪除一個(gè)記錄時(shí)，只要找到該記錄所屬的塊，就可以在該塊內(nèi)進(jìn)行插入或刪除操作，因?yàn)閴K內(nèi)記錄是無(wú)序的，所以插入或刪除比較容易，無(wú)需移動(dòng)大量記錄。主要缺點(diǎn)是需要增加一個(gè)輔助數(shù)組的存儲(chǔ)空間和將初始表塊排序的運(yùn)算，它也不適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。上述三種查找的時(shí)間復(fù)雜度分別是O（n）、O(log2n)和O(n的平方根)5.二叉排序樹(二叉查找樹)：或者是一棵空樹,或者具有下面性質(zhì)：a、若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值。b、若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值.c、左右子樹本身又各是一棵二叉排序樹。由此可得，按中序遍歷二叉排序樹所得到的遍歷序列是一個(gè)遞增有序序列。同樣一組關(guān)鍵字序列,由于其輸入順序不同,所得到的二叉排序樹也有所不同，含有n個(gè)結(jié)點(diǎn)的二叉排序樹不是唯一的。構(gòu)造二叉排序樹的真正目的并不是為了排序，而是為了更好地查找，又稱為二叉查找樹.二叉排序樹的查找與給定值的比較次數(shù)不會(huì)超過(guò)樹的深度。若二叉排序樹是一顆理想的平衡樹或接近理想的平衡樹,則時(shí)間復(fù)雜度為O(log2n）,若退化為一棵單支樹,則時(shí)間復(fù)雜度為O(n）。二叉排序樹的刪除：被刪除結(jié)點(diǎn)為p，其父結(jié)點(diǎn)為f.具體操作為：a、若p是葉子結(jié)點(diǎn),直接刪除p；b、若p只有一棵子樹（左子樹或右子樹），直接用p的左子樹（或右子樹）取代p的位置而成為f的一棵子樹.即p是左子樹則p的子樹變?yōu)閒的左子樹；c、若p既有左子樹又有右子樹，任選一種方法：(1）、用p的直接前驅(qū)結(jié)點(diǎn)代替p，即從p的左子樹中選擇值最大的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容），然后刪除結(jié)點(diǎn)s。s是p的左子樹中最右邊的結(jié)點(diǎn)且沒(méi)有右子樹；（2)、用p的直接后繼結(jié)點(diǎn)代替p，即從p的右子樹中選擇值最小的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容），然后刪除結(jié)點(diǎn)s.s是p的右子樹中最左邊的結(jié)點(diǎn)且沒(méi)有左子樹。在二叉排序樹上實(shí)現(xiàn)插入和查找操作的平均時(shí)間復(fù)雜度為O（log2n）,但在最壞得情況下，會(huì)變成O（n)。平衡二叉樹：既能滿足BST性質(zhì)又能保證二叉排序樹的深度在任何情況下均為O（log2n）。6。B樹是一種平衡的多路查找樹。一棵m(m≥3)階的B樹,或?yàn)榭諛?，或?yàn)闈M足下列性質(zhì)的m叉樹a、每個(gè)結(jié)點(diǎn)至少包含下列信息域；b、每個(gè)結(jié)點(diǎn)至多有m棵子樹;c、若樹為非空,則根結(jié)點(diǎn)至少有1個(gè)關(guān)鍵字,至多有m—1個(gè)關(guān)鍵字。因此,若根結(jié)點(diǎn)不是葉子，則它至少有兩顆子樹.d、每個(gè)非根結(jié)點(diǎn)中所含的關(guān)鍵字個(gè)數(shù)滿足：?m/2?-1≤n≤m-1，因?yàn)槊總€(gè)內(nèi)部結(jié)點(diǎn)的度數(shù)正好是關(guān)鍵字總數(shù)加1，所以處根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有?m/2?棵子樹，至多有m棵子樹。在B樹上插入和刪除元素的運(yùn)算比較復(fù)雜，它要求進(jìn)行運(yùn)算后的結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)≥?m/2?—1,在B樹進(jìn)行查找包括兩種基本操作：在B樹中查找結(jié)點(diǎn)、在結(jié)點(diǎn)中查找關(guān)鍵字。7.B+樹是一種文件組織的B樹的變形樹，通常有兩個(gè)頭指針root和sqt，前者指向根結(jié)點(diǎn)，后者指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。因此可對(duì)B+樹進(jìn)行兩種查找運(yùn)算：一種是從最小關(guān)鍵字起進(jìn)行順序查找,一種是從根結(jié)點(diǎn)開始進(jìn)行隨機(jī)查找.8。散列表查找是通過(guò)對(duì)記錄的關(guān)鍵字值進(jìn)行某種運(yùn)算直接求出記錄的地址，是一種由關(guān)鍵字到地址的直接轉(zhuǎn)換方法。散列存儲(chǔ)中使用的函數(shù)稱為散列函數(shù)或哈希函數(shù)，散列地址或哈希地址，散列表或哈希表.具有相同散列地址的關(guān)鍵字稱為同義詞。沖突的頻度除了與散列函數(shù)H相關(guān)外,還與散列表的填滿程度相關(guān)。如何盡量避免沖突和沖突發(fā)生后如何解決沖突,就成了散列存儲(chǔ)的兩個(gè)關(guān)鍵問(wèn)題。散列函數(shù)的目標(biāo)是使散列地址盡可能均勻的分布在散列空間上，同時(shí)使計(jì)算盡可能簡(jiǎn)單。直接地址法:計(jì)算簡(jiǎn)單，并且沒(méi)有沖突。適合于關(guān)鍵字的分布基本連續(xù)的情況。數(shù)字分析法：從中提取數(shù)字分布比較均勻的若干位作為散列地址.除余數(shù)法：p最好取小于或等于表長(zhǎng)m的最大素?cái)?shù)。這是一種最簡(jiǎn)單也最常用的方法。平方取中法：折疊法：把關(guān)鍵字分割成位數(shù)相同的幾段，分為移位疊加和邊界疊加。9.處理沖突的方法：開放定址法和拉鏈法。開放定址法：線性探查法、二次探查法和雙重散列法（幾種方法中最好的方法)。二次探查法：d+12,d—12，d+22,d—22拉鏈法：存儲(chǔ)結(jié)構(gòu)是鏈表時(shí)常用.把具有相同散列地址的關(guān)鍵字值放在同一個(gè)單鏈表中，稱為同義詞鏈表.有m個(gè)散列地址就有m個(gè)鏈表.用拉鏈法處理沖突比開放定址法多占用一些存儲(chǔ)空間用作鏈表指針，但它可以減少在插入和查找過(guò)程中關(guān)鍵字的平均比較次數(shù)(平均查找長(zhǎng)度）。10。查找不成功時(shí)，順序查找和二分查找所需要進(jìn)行的關(guān)鍵字僅取決于表長(zhǎng)，而散列表查找所需要進(jìn)行的比較次數(shù)和待查結(jié)點(diǎn)有關(guān)。散列表查找，計(jì)算查找成功的平均查找長(zhǎng)度時(shí)，除數(shù)是結(jié)點(diǎn)的個(gè)數(shù),而在計(jì)算查找不成功的平均查找長(zhǎng)度時(shí),除數(shù)卻是表長(zhǎng)。開放定址法：裝填因子α≤1，實(shí)用中一般取0.65-0.9之間的某個(gè)值。拉鏈法：α可以大于1，但一般取α≤1。會(huì)計(jì)制度設(shè)計(jì)概述一、名詞解析會(huì)計(jì)制度:是由政府部門和企業(yè)單位對(duì)會(huì)計(jì)工作的規(guī)則、方法、程序所制定的規(guī)范性文件。會(huì)計(jì)制度設(shè)計(jì)：是以會(huì)計(jì)法律、法規(guī)為依據(jù)，用系統(tǒng)控制的理論和技術(shù),把單位的會(huì)計(jì)組織機(jī)構(gòu)、會(huì)計(jì)核算與監(jiān)督和會(huì)計(jì)業(yè)務(wù)處理程序等加以具體化、規(guī)范化、文件化,以便具體指導(dǎo)和處理會(huì)計(jì)工作的過(guò)程。08年內(nèi)部控制制度：是指單位或組織內(nèi)部各能部門、各有關(guān)工作人員之間,在處理經(jīng)濟(jì)業(yè)務(wù)過(guò)程中相互聯(lián)系、相互制約的管理制度.08年預(yù)算會(huì)計(jì)制度：是規(guī)范各級(jí)政府、使用預(yù)算資金的各級(jí)行政單位和各類事業(yè)單位收入、分配、使用和報(bào)告情況的會(huì)計(jì)制度。它包括：行政總預(yù)算（政府）會(huì)計(jì)制度、行政單位預(yù)算會(huì)計(jì)制度、事業(yè)單位會(huì)計(jì)制度；09年會(huì)計(jì)核算制度：是指以貨幣為統(tǒng)一計(jì)量單位對(duì)會(huì)計(jì)對(duì)象進(jìn)行確認(rèn)、計(jì)量、記錄和報(bào)告的各種規(guī)范。會(huì)計(jì)分析制度：是指如何利息現(xiàn)有會(huì)計(jì)信息對(duì)相關(guān)會(huì)計(jì)對(duì)象進(jìn)行分析和考核,以比較不同實(shí)際或不同單位之間的財(cái)務(wù)狀況和經(jīng)營(yíng)成果的會(huì)計(jì)規(guī)范。會(huì)計(jì)控制：是按照既定的會(huì)計(jì)目標(biāo)，對(duì)會(huì)計(jì)行為和企業(yè)經(jīng)濟(jì)活動(dòng)所進(jìn)行的制約.二、簡(jiǎn)答題1、會(huì)計(jì)制度設(shè)計(jì)的原則？合規(guī)性、真實(shí)性、科學(xué)性、針對(duì)性、內(nèi)部控制性、效益型、適應(yīng)性。2、會(huì)計(jì)制度設(shè)計(jì)的方法?實(shí)地調(diào)查法，包括實(shí)地觀察、崗位訪問(wèn)、開座談會(huì)、問(wèn)卷測(cè)試、所要文檔。分析研究方法，包括文字說(shuō)明法、表格法、流程圖法。3、內(nèi)部控制的目標(biāo)與內(nèi)部會(huì)計(jì)控制的方法？目標(biāo)：維護(hù)財(cái)產(chǎn)物資的完整性、保證會(huì)計(jì)信息的準(zhǔn)確性、保證財(cái)務(wù)活動(dòng)的合法性、保證經(jīng)營(yíng)決策的貫徹執(zhí)行、保證生產(chǎn)經(jīng)營(yíng)活動(dòng)的經(jīng)濟(jì)型、效率性和效果性、保證國(guó)家法律法規(guī)的遵守執(zhí)行。方法：不相容職務(wù)相互分離控制；授權(quán)批準(zhǔn)控制；會(huì)計(jì)系統(tǒng)控制；預(yù)算控制；財(cái)產(chǎn)保全控制；風(fēng)險(xiǎn)控制;內(nèi)部報(bào)告控制；電子信息技術(shù)控制。4、會(huì)計(jì)制度設(shè)計(jì)與內(nèi)部控制制度的關(guān)系?會(huì)計(jì)制度與內(nèi)部控制制度有著密切的關(guān)系，會(huì)計(jì)制度設(shè)計(jì)的哥哥環(huán)節(jié)都必須貫徹內(nèi)部控制精神,因?yàn)閮?nèi)部控制制度既是企業(yè)各種規(guī)章制度控制手段的總稱，又是有限的執(zhí)行會(huì)計(jì)制度的保護(hù)性措施.內(nèi)部控制范圍極廣，內(nèi)容及其豐富，其中包括內(nèi)部開機(jī)控制，內(nèi)部管理控制，內(nèi)部會(huì)計(jì)控制包裹8個(gè)主要方法：不相容職務(wù)相互分離控制，授權(quán)批準(zhǔn)控制、會(huì)計(jì)系統(tǒng)控制、預(yù)算控制、財(cái)產(chǎn)保全控制、風(fēng)險(xiǎn)控制、內(nèi)部報(bào)告控制和電子信息技術(shù)控制.這些方法與會(huì)計(jì)制度設(shè)計(jì)緊密相關(guān)，也是企業(yè)進(jìn)行會(huì)計(jì)制度設(shè)計(jì)必須把握的核心內(nèi)容.09年第二章企業(yè)會(huì)計(jì)制度的總體設(shè)計(jì)一、名詞解釋設(shè)計(jì)方案:是指根據(jù)企業(yè)會(huì)計(jì)涉及的范圍，所形成的系統(tǒng)、框架和規(guī)劃。具體分為全面設(shè)計(jì)和局部設(shè)計(jì)。設(shè)計(jì)類型與方式：設(shè)計(jì)類型由企業(yè)所在行業(yè)特點(diǎn)、企業(yè)經(jīng)濟(jì)性質(zhì)、企業(yè)規(guī)模來(lái)確定.設(shè)計(jì)方式包括：?jiǎn)为?dú)設(shè)計(jì)、共同設(shè)計(jì)、集體設(shè)計(jì)、會(huì)議設(shè)計(jì)。總體設(shè)計(jì)：是對(duì)所設(shè)計(jì)的會(huì)計(jì)制度內(nèi)容及設(shè)計(jì)工作作出全面安排及規(guī)劃，即事先有一個(gè)提綱性規(guī)劃和指南.08年全面設(shè)計(jì):是指為企業(yè)設(shè)計(jì)一整套會(huì)計(jì)制度,一般在新建的企業(yè)或改制、兼并與收購(gòu)后的企業(yè)里，需要進(jìn)行全面性會(huì)計(jì)制度設(shè)計(jì)。局部設(shè)計(jì)：是指對(duì)個(gè)別部門的組織機(jī)構(gòu)和會(huì)計(jì)核算資料，或部分經(jīng)濟(jì)業(yè)務(wù)的會(huì)計(jì)處理所進(jìn)行的設(shè)計(jì)，又可分為補(bǔ)充性設(shè)計(jì)和修訂性設(shè)計(jì)。09年二、簡(jiǎn)答題1、企業(yè)總體會(huì)計(jì)設(shè)計(jì)的內(nèi)容?提高企業(yè)經(jīng)營(yíng)管理水平建議的設(shè)計(jì)；會(huì)計(jì)機(jī)構(gòu)和人員配備的設(shè)計(jì)；會(huì)計(jì)核算形式的設(shè)計(jì);財(cái)產(chǎn)核算及其管理制度的設(shè)計(jì)；成本費(fèi)用核算及其管理制度的設(shè)計(jì).2、企業(yè)總體設(shè)計(jì)的程序？調(diào)查研究收集資料；確定設(shè)計(jì)類型和設(shè)計(jì)方案；選擇會(huì)計(jì)政策和設(shè)計(jì)手段；制定涉及策略和設(shè)計(jì)驗(yàn)收標(biāo)準(zhǔn)；編制會(huì)計(jì)制度總體設(shè)計(jì)和具體設(shè)計(jì).3、企業(yè)總體設(shè)計(jì)的含義與作用？08年含義如上。作用如下：總體設(shè)計(jì)是進(jìn)行具體設(shè)計(jì)的基礎(chǔ);保證會(huì)計(jì)制度具體設(shè)計(jì)的適用性和可行性；保證會(huì)計(jì)制度的具體設(shè)計(jì)有序進(jìn)行第三章企業(yè)會(huì)計(jì)組織機(jī)構(gòu)與崗位職責(zé)的設(shè)計(jì)一、名詞解釋責(zé)權(quán)對(duì)等原則：是指在設(shè)計(jì)會(huì)計(jì)崗位責(zé)任制時(shí),必須明確規(guī)定每一管理者應(yīng)付的職責(zé),并相應(yīng)的賦予其一定的權(quán)利,做到有職必有權(quán),有權(quán)必有責(zé)，權(quán)責(zé)對(duì)等.企業(yè)內(nèi)部銀行:是相對(duì)獨(dú)立于企業(yè)會(huì)計(jì)部門的管理機(jī)構(gòu)，它將商業(yè)銀行的信貸結(jié)算職能和方式引入企業(yè)內(nèi)部來(lái)充實(shí)和完善企業(yè)內(nèi)部經(jīng)濟(jì)核算。會(huì)計(jì)與財(cái)務(wù)合并：是將會(huì)計(jì)對(duì)資金運(yùn)動(dòng)的核算、監(jiān)督職能與財(cái)務(wù)管理對(duì)資金的籌集、調(diào)度與分配職能統(tǒng)一由一個(gè)部門來(lái)履行的一種機(jī)構(gòu)設(shè)置形式.08年會(huì)計(jì)崗位責(zé)任制：是指明確各項(xiàng)會(huì)計(jì)工作的職責(zé)范圍、具體內(nèi)同和要求,并落實(shí)到每個(gè)會(huì)計(jì)工作崗位或會(huì)計(jì)人員的一種會(huì)計(jì)工作責(zé)任制度。09年上會(huì)計(jì)與財(cái)務(wù)分設(shè)：是將會(huì)計(jì)對(duì)資金運(yùn)動(dòng)的反映、監(jiān)督職能與財(cái)務(wù)管理對(duì)資金的籌集、調(diào)度與分配職能分別有會(huì)計(jì)部和財(cái)務(wù)部來(lái)履行的一種機(jī)構(gòu)設(shè)置形式。二、簡(jiǎn)答題1、企業(yè)會(huì)計(jì)組織機(jī)構(gòu)的設(shè)計(jì)形式會(huì)計(jì)與財(cái)務(wù)合并的形式，適合中小企業(yè)，業(yè)務(wù)簡(jiǎn)單，會(huì)計(jì)業(yè)務(wù)不多。會(huì)計(jì)與財(cái)務(wù)分別設(shè)置的形式，適合大中型企業(yè),業(yè)務(wù)繁多，經(jīng)營(yíng)范圍廣泛。2、企業(yè)會(huì)計(jì)組織機(jī)構(gòu)及其崗位職責(zé)設(shè)計(jì)的原則？適應(yīng)性;系統(tǒng)性;責(zé)權(quán)對(duì)等；控制性；效率性。3、企業(yè)會(huì)計(jì)組織機(jī)構(gòu)內(nèi)部分工的設(shè)計(jì)模式有哪些？總會(huì)計(jì)師領(lǐng)導(dǎo)下的集中核算模式:它是以會(huì)計(jì)師為領(lǐng)導(dǎo)，以會(huì)計(jì)部經(jīng)理為主管,以審計(jì)部為專職監(jiān)督部門的一種會(huì)計(jì)工作分工模式，一般適用于大中型、單獨(dú)設(shè)置總會(huì)計(jì)師崗位、會(huì)計(jì)與財(cái)務(wù)分設(shè)的企業(yè)。會(huì)計(jì)部經(jīng)理領(lǐng)導(dǎo)下的集中核算模式：它是以會(huì)計(jì)部經(jīng)理為領(lǐng)導(dǎo)，一般適用于中小型、不設(shè)置總會(huì)計(jì)師崗位、會(huì)計(jì)與財(cái)務(wù)分設(shè)的企業(yè)。財(cái)會(huì)主管領(lǐng)導(dǎo)下的集中核算模式：以財(cái)務(wù)與會(huì)計(jì)主管為領(lǐng)導(dǎo)，并通常只設(shè)財(cái)會(huì)主管、會(huì)計(jì)、出納等少數(shù)幾個(gè)崗位，適合小企業(yè)?？倳?huì)計(jì)師（會(huì)計(jì)部經(jīng)理）領(lǐng)導(dǎo)下的分散核算模式：以總會(huì)計(jì)師為領(lǐng)導(dǎo)下設(shè)財(cái)務(wù)、會(huì)計(jì)、審計(jì)部主管，并將一些成本業(yè)務(wù)核算或明細(xì)核算工作交分廠完成的一種模式。4、企業(yè)集團(tuán)會(huì)計(jì)組織機(jī)構(gòu)設(shè)計(jì)的特點(diǎn)與崗位職責(zé)設(shè)計(jì)的內(nèi)容？特點(diǎn)：規(guī)模大型化、經(jīng)營(yíng)多樣化，設(shè)計(jì)上考慮資本國(guó)際化的特點(diǎn)，與大中型企業(yè)會(huì)計(jì)組織相同點(diǎn)企業(yè)集團(tuán)的母公司和子公司也應(yīng)根據(jù)其經(jīng)營(yíng)規(guī)模和范圍大小、經(jīng)營(yíng)過(guò)程和企業(yè)組織形式的特點(diǎn)及管理要求,采取會(huì)計(jì)月財(cái)務(wù)分設(shè)模式或合并模式,并在其內(nèi)部設(shè)置相應(yīng)的機(jī)構(gòu)，還需在母公司的下屬分公司和分支機(jī)構(gòu)設(shè)置財(cái)務(wù)會(huì)計(jì)部門。內(nèi)容：日常會(huì)計(jì)核算和合并財(cái)務(wù)報(bào)表方面;稅務(wù)籌劃方面;預(yù)算管理方面;投資管理方面；資金調(diào)度、監(jiān)督和其他財(cái)務(wù)分析方面。5、內(nèi)部銀行崗位職責(zé)設(shè)計(jì)？結(jié)算存款崗位職責(zé)設(shè)計(jì)；資金投資崗位職責(zé)的設(shè)計(jì)；儲(chǔ)蓄崗位職責(zé)設(shè)計(jì)；管理崗位職責(zé)設(shè)計(jì)6、小型企業(yè)會(huì)計(jì)機(jī)構(gòu)運(yùn)作的要求？08年分清出納與總賬、總賬與明細(xì)帳、應(yīng)收應(yīng)付往來(lái)帳與總賬、管理庫(kù)存現(xiàn)金、銀行存款的人與編制銀行存款調(diào)節(jié)表的人的職責(zé)范圍,并有專人分別擔(dān)任。設(shè)定會(huì)計(jì)憑證的傳遞順序;要配備代職人員；要經(jīng)常進(jìn)行賬冊(cè)記錄的核對(duì)工作；要由精通會(huì)計(jì)業(yè)務(wù)的人擔(dān)任管理部門主管。7、大型企業(yè)會(huì)計(jì)機(jī)構(gòu)運(yùn)作的要求？總會(huì)計(jì)師職責(zé)制，由總會(huì)計(jì)師領(lǐng)導(dǎo)下的分散核算模式，并組織領(lǐng)導(dǎo)本企業(yè)的財(cái)務(wù)與會(huì)計(jì)管理工作；財(cái)會(huì)主管責(zé)任制，在總會(huì)計(jì)師領(lǐng)導(dǎo)下，負(fù)責(zé)本企業(yè)的具體財(cái)會(huì)工作，組織開展會(huì)計(jì)核算和會(huì)計(jì)監(jiān)督第四章會(huì)計(jì)科目、會(huì)計(jì)核算形式的設(shè)計(jì)一、名詞解釋會(huì)計(jì)科目：是按經(jīng)濟(jì)內(nèi)容對(duì)會(huì)計(jì)要素的具體內(nèi)容進(jìn)行分類核算的項(xiàng)目，它是以會(huì)計(jì)要素的具體內(nèi)容為基礎(chǔ)、按照管理和核算的要求而設(shè)計(jì).即根據(jù)會(huì)計(jì)核算的要求,對(duì)資產(chǎn)、負(fù)債、所有者權(quán)益、收入、費(fèi)用利潤(rùn)六大會(huì)計(jì)要素的具體內(nèi)容進(jìn)行科學(xué)的分類,給會(huì)計(jì)要素的具體內(nèi)容設(shè)計(jì)一個(gè)合適的名稱，這就是會(huì)計(jì)科目。會(huì)計(jì)憑證：是用來(lái)記錄經(jīng)濟(jì)業(yè)務(wù)的發(fā)生和完成情況,明確經(jīng)濟(jì)責(zé)任,并據(jù)以登記賬簿的書面文件。08記賬憑證：是指會(huì)計(jì)人員根據(jù)審核后的原始憑證確定會(huì)計(jì)分錄并作為記賬依據(jù)的會(huì)計(jì)憑證。填制記賬憑證是會(huì)計(jì)核算的一種基本方法.會(huì)計(jì)賬簿：企業(yè)經(jīng)濟(jì)信息絕大部分分散于會(huì)計(jì)憑證中，相互獨(dú)立的會(huì)計(jì)憑證無(wú)法連續(xù)、系統(tǒng)、完整的提供某一會(huì)計(jì)事項(xiàng)的全部信息，也就無(wú)法為企業(yè)決策服務(wù),因此需要設(shè)計(jì)一定格式、相互聯(lián)系的帳頁(yè)，即賬簿，用來(lái)序時(shí)的、分類的記錄和反應(yīng)有關(guān)經(jīng)濟(jì)業(yè)務(wù),把會(huì)計(jì)報(bào)表和會(huì)計(jì)憑證有機(jī)的聯(lián)系在一起.賬簿體系為核心、將會(huì)計(jì)憑證、賬簿組織、記賬方法和記賬程序有機(jī)結(jié)合的形式，或稱虧啊及核算組織程序。會(huì)計(jì)核算形式：是指在會(huì)計(jì)核算中，以賬簿體系為核心，將會(huì)計(jì)憑證、賬簿組織、記賬方法和記賬程序有機(jī)結(jié)合的形式,或成為會(huì)計(jì)核算組織程序序時(shí)賬：（日記賬)是指按照經(jīng)濟(jì)業(yè)務(wù)發(fā)生時(shí)間的先后順序逐日逐筆登記經(jīng)濟(jì)業(yè)務(wù)的賬簿.分類賬：是指對(duì)全部經(jīng)濟(jì)業(yè)務(wù)按照總分類賬戶和明細(xì)分類賬戶進(jìn)行分類登記的賬簿。有總分類和明細(xì)分類賬。備查賬簿：是指對(duì)某些在序時(shí)賬簿和分類賬簿中未能記載的經(jīng)濟(jì)業(yè)務(wù)事項(xiàng)進(jìn)行補(bǔ)充登記的賬簿。聯(lián)合賬簿：將序時(shí)賬和分類賬結(jié)合在一起的賬簿，如日記總賬二、簡(jiǎn)答題1、會(huì)計(jì)科目設(shè)計(jì)的原則？統(tǒng)一性和靈活性相結(jié)合的原則；內(nèi)外兼顧的原則;簡(jiǎn)明實(shí)用原則;相對(duì)穩(wěn)定原則；符合會(huì)計(jì)電算化原則;2、原始憑證的設(shè)計(jì)內(nèi)容？按憑證的來(lái)源:外來(lái)原始憑證，自制原始憑證(一次憑證、累計(jì)憑證、匯總憑證）按憑證格式內(nèi)容:通用憑證、專業(yè)憑證按憑證的用途：通知憑證；執(zhí)行憑證；計(jì)算憑證；按業(yè)務(wù)類別：貨幣資金收付業(yè)務(wù)憑證；存貨業(yè)務(wù)收發(fā)憑證;職工薪酬業(yè)務(wù)憑證；購(gòu)銷業(yè)務(wù)憑證;固定資產(chǎn)業(yè)務(wù)憑證;成本核算業(yè)務(wù)憑證;投資與籌資業(yè)務(wù)憑證。3、會(huì)計(jì)賬簿設(shè)計(jì)的范圍？按賬簿用途分:序時(shí)賬簿（普通日記賬、特種日記賬）、分類賬簿（總分類帳、明細(xì)分類賬）、備查賬簿;按賬簿外表形式分：訂本式賬簿；活頁(yè)式賬簿；卡片式賬簿按賬簿的格式分：三欄式賬簿（如明細(xì)賬）；多欄式賬簿；數(shù)量金額式賬簿4、會(huì)計(jì)核算形式的種類和內(nèi)容？會(huì)計(jì)核算形式種類：逐筆記賬型核算形式（適合小企業(yè)）:記賬憑證核算形式；日記總賬核算形式.匯總記賬型核算形式（適合大中企業(yè))：憑證匯總核算形式（科目匯總表核算形式在我國(guó)廣泛使用、匯總記賬憑證核算形式);賬簿匯總核算形式(多欄日記賬核算形式、憑單日記賬核算形式）5、簡(jiǎn)述設(shè)計(jì)會(huì)計(jì)憑證的主要內(nèi)容？07年明確所要設(shè)計(jì)會(huì)計(jì)憑證的種類和范圍;確定會(huì)計(jì)憑證的設(shè)計(jì)原則;制定會(huì)計(jì)憑證設(shè)計(jì)的方法；規(guī)定會(huì)計(jì)憑證的傳遞程序；建立會(huì)計(jì)憑證的保管制度第五章貨幣資金業(yè)務(wù)會(huì)計(jì)制度的設(shè)計(jì)一、名詞解釋其他貨幣資金：是指企業(yè)的銀行匯票存款、銀行本票存款、信用卡存款、信用證保證金存款、存出投資款、外埠存款等其他貨幣資金。二、簡(jiǎn)答題1、貨幣資金業(yè)務(wù)內(nèi)部會(huì)計(jì)控制制度設(shè)計(jì)？職責(zé)分工控制制度的設(shè)計(jì);授權(quán)審批；貨幣資金審核；貨幣資金監(jiān)督檢查2、貨幣資金業(yè)務(wù)會(huì)計(jì)制度設(shè)計(jì)的目標(biāo)和要求？目標(biāo)：保證貨幣資金的安全性和完整性;保證貨幣資金的合規(guī)性和合法性；保證貨幣資金業(yè)務(wù)會(huì)計(jì)核算資料的準(zhǔn)確和可靠；保證貨幣資金業(yè)務(wù)結(jié)算的及時(shí)性和正確性。要求：合法性；規(guī)范性；效率性；及時(shí)性；3、設(shè)計(jì)貨幣資金內(nèi)部控制制度的核心,制度的基本要求和具體要求？核心：是建立貨幣資金的職務(wù)分離制度、控制程序、稽核制度與其相關(guān)的崗位職責(zé)制度?；疽螅贺泿刨Y金首付業(yè)務(wù)的人員與記賬人員和負(fù)責(zé)審批的人員相分離。具體要求:貨幣資金的首付與保管應(yīng)有被授權(quán)批準(zhǔn)的專職出納人員負(fù)責(zé)，其他人員不得接觸；出納人員不能同時(shí)負(fù)責(zé)總分類帳的登記與保管；出納人員不能同時(shí)負(fù)責(zé)非貨幣資金賬戶的記賬工作；出納人員影單與貨幣資金審批人員相分離，實(shí)施嚴(yán)格的審批制度；貨幣資金的收付與控制貨幣資金收支的專用章不得由一人兼管;出納人員應(yīng)該與貨幣資金的稽核、會(huì)計(jì)檔案的保管人員相分離；負(fù)責(zé)貨幣資金收付的人員應(yīng)當(dāng)與負(fù)責(zé)現(xiàn)金清點(diǎn)的人員和負(fù)責(zé)銀行對(duì)賬的人員相分離；建立出納人員，專用印章保管人員、會(huì)計(jì)人員、稽核人員、會(huì)計(jì)檔案保管人員以及貨幣資金清查人員責(zé)任制度。07年4、企業(yè)在設(shè)計(jì)庫(kù)存現(xiàn)金會(huì)計(jì)控制制度時(shí)應(yīng)采取的做法？加強(qiáng)現(xiàn)金庫(kù)存限額的管理，超過(guò)庫(kù)存限額的現(xiàn)金應(yīng)當(dāng)及時(shí)存入開戶銀行；根據(jù)《現(xiàn)金管理暫行條例》的規(guī)定,結(jié)合本企業(yè)的實(shí)際情況，確定本企業(yè)的現(xiàn)金開支范圍和現(xiàn)金支付限額；庫(kù)存現(xiàn)金收入要及時(shí)存入銀行，不得坐支庫(kù)存現(xiàn)金；接觸款項(xiàng)必須執(zhí)行嚴(yán)格的審批核準(zhǔn)程序，嚴(yán)謹(jǐn)擅自挪用借出貨幣資金;取得的貨幣資金必須及時(shí)入賬,不得賬外設(shè)賬，嚴(yán)禁收款不入賬。09年第六章存貨業(yè)務(wù)會(huì)計(jì)制度的設(shè)計(jì)存貨：企業(yè)在日常經(jīng)營(yíng)活動(dòng)中持有以備出售的庫(kù)存商品、商品，處在生產(chǎn)過(guò)程中的在產(chǎn)品，在生產(chǎn)過(guò)程和提供勞務(wù)過(guò)程中消耗的材料和物料.二、簡(jiǎn)答題1、存貨的基礎(chǔ)工作設(shè)計(jì)？存貨編號(hào)設(shè)計(jì)（多好定位法,四號(hào)定位法）；存貨的計(jì)量（先進(jìn)先出法,加權(quán)平均法,移動(dòng)加權(quán)平均法，個(gè)別計(jì)價(jià)法）；存貨盤存制度的確定（永續(xù)盤存制，實(shí)地盤存制）2、存貨業(yè)務(wù)會(huì)計(jì)制度設(shè)計(jì)的目標(biāo)和要求?目標(biāo)：提供存貨的各種真實(shí)完整有用的信息;保證存貨的安全；控制存貨的流動(dòng);監(jiān)督落實(shí)存貨的經(jīng)營(yíng)責(zé)任；加強(qiáng)存貨資金周轉(zhuǎn)，考核存貨的經(jīng)濟(jì)效益。要求：嚴(yán)格各種存貨的收發(fā)手續(xù)的規(guī)定,保護(hù)實(shí)物財(cái)產(chǎn)的安全；正確反映各種存貨增減變動(dòng)和結(jié)存情況，保證企業(yè)生產(chǎn)活動(dòng)的正常進(jìn)行.正確計(jì)算物化勞動(dòng),考核存貨資金以及防止存貨超儲(chǔ)積壓.3、采購(gòu)與付款業(yè)務(wù)各種憑證傳遞程序的設(shè)計(jì)?指定專人填制有關(guān)