數(shù)據(jù)結構復習題-有答案的打印版

一、選擇題1．下面關于線性表的表達中，錯誤的選項是哪一個？〔B〕A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。3．線性表是具有n個〔C〕的有限序列〔n>0〕。A．表元素B．字符C．數(shù)據(jù)元素D．數(shù)據(jù)項E．信息項2．假設某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，那么利用〔A〕存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．帶頭結點的雙循環(huán)鏈表D．單循環(huán)鏈表3．某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用〔D〕存儲方式最節(jié)省運算時間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表4.靜態(tài)鏈表中指針表示的是〔C〕.A．內存地址B．數(shù)組下標C．下一元素地址D．左、右孩子地址5.鏈表不具有的特點是〔B〕A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比1.對于棧操作數(shù)據(jù)的原那么是〔B〕。A.先進先出B.后進先出C.后進后出D.不分順序2.有六個元素6，5，4，3，2，1的順序進棧，問以下哪一個不是合法的出棧序列？〔A〕A.543612B.453126C.346521D.2341563.設棧的輸入序列是1，2，3，4,那么〔D〕不可能是其出棧序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，4，1.數(shù)組A[0..9,0..9]的每個元素占5個存儲單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內存單元中，求A[6，8]的地址。13402.二維數(shù)組A[1..10，0..9]中每個元素占4個單元，在按行優(yōu)先方式將其存儲到起始地址為1000的連續(xù)存儲區(qū)域時，求A[5，9]的地址。11961．假設一棵二叉樹具有10個度為2的結點，5個度為1的結點，那么度為0的結點個數(shù)是〔B〕A．9B．11C．15D．不確定2．具有10個葉結點的二叉樹中有〔B〕個度為2的結點，A．8B．9C．10D．ll3.設給定權值總數(shù)有n個，其哈夫曼樹的結點總數(shù)為(D)A．不確定B．2nC．2n+1D．2n-14．假設度為m的哈夫曼樹中，其葉結點個數(shù)為n，那么非葉結點的個數(shù)為〔A〕。A．n-1B．n/m-1C．(n-1)/(m-1)D．n/(m-1)-1E．(n+1)/(m+1)-15.有關二叉樹以下說法正確的選項是〔B〕A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結點的度為2D．二叉樹中任何一個結點的度都為21．圖中有關路徑的定義是〔A〕。A．由頂點和相鄰頂點序偶構成的邊所形成的序列B．由不同頂點所形成的序列C．由不同邊所形成的序列D．上述定義都不是2．設無向圖的頂點個數(shù)為n，那么該圖最多有〔B〕條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n23．一個n個頂點的連通無向圖，其邊的個數(shù)至少為〔A〕。A．n-1B．nC．n+1D．nlogn；4．要連通具有n個頂點的有向圖，至少需要〔B〕條邊。A．n-lB．nC．n+lD．2n5．n個結點的完全有向圖含有邊的數(shù)目〔D〕。【中山大學1998二、9〔2分〕】A．n*nＢ．n〔n＋１〕C．n／2D．n*〔n－l〕6．一個有n個結點的圖，最少有〔B〕個連通分量，最多有〔D〕個連通分量。A．0B．1C．n-1D．n7．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)〔B〕倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的〔C〕倍。A．1/2B．2C．1D．48．用有向無環(huán)圖描述表達式(A+B)*〔〔A+B〕/A〕，至少需要頂點的數(shù)目為(A)。A．5B．6C．8D．99．用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應的頂點，那么輸出的頂點序列是(A)。A．逆拓撲有序B．拓撲有序C．無序的10．以下哪一種圖的鄰接矩陣是對稱矩陣？〔B〕A．有向圖B．無向圖C．AOV網(wǎng)D．AOE網(wǎng)1.假設查找每個記錄的概率均等，那么在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為(C)?！颈本┖娇蘸教齑髮W2000一、8〔2分〕】A．(n-1)/2B.n/2C.(n+1)/2D.n2.對N個元素的表做順序查找時，假設查找每個元素的概率相同，那么平均查找長度為(A)A．〔N+1〕/2B.N/2C.ND.[〔1+N〕*N]/23.下面關于二分查找的表達正確的選項是(D)A.表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B.表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型C.表必須有序，而且只能從小到大排列D.表必須有序，且表只能以順序方式存儲4.對線性表進行二分查找時，要求線性表必須〔B〕A.以順序方式存儲B.以順序方式存儲,且數(shù)據(jù)元素有序C.以鏈接方式存儲D.以鏈接方式存儲,且數(shù)據(jù)元素有序5．適用于折半查找的表的存儲方式及元素排列要求為(D)A．鏈接方式存儲，元素無序B．鏈接方式存儲，元素有序C．順序方式存儲，元素無序D．順序方式存儲，元素有序6.用二分〔對半〕查找表的元素的速度比用順序法(D)A.必然快B.必然慢C.相等D.不能確定7．當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度(C)A．必定快B.不一定C.在大局部情況下要快D.取決于表遞增還是遞減8.具有12個關鍵字的有序表，折半查找的平均查找長度〔A〕A.3.1B.4C.2.5D.59.折半查找的時間復雜性為〔D〕A.O〔n2〕B.O〔n〕C.O〔nlogn〕D.O〔logn〕10．當采用分快查找時，數(shù)據(jù)的組織方式為(B)A．數(shù)據(jù)分成假設干塊，每塊內數(shù)據(jù)有序B．數(shù)據(jù)分成假設干塊，每塊內數(shù)據(jù)不必有序，但塊間必須有序，每塊內最大〔或最小〕的數(shù)據(jù)組成索引塊C.數(shù)據(jù)分成假設干塊，每塊內數(shù)據(jù)有序，每塊內最大〔或最小〕的數(shù)據(jù)組成索引塊D.數(shù)據(jù)分成假設干塊，每塊〔除最后一塊外〕中數(shù)據(jù)個數(shù)需相同11．如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，那么可采用(A)查找法。A.分快查找B.順序查找C.折半查找D.基于屬性12.既希望較快的查找又便于線性表動態(tài)變化的查找方法是(C)A．順序查找B.折半查找C.索引順序查找D.哈希法查找13．分別以以下序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是(C)A．〔100，80，90，60，120，110，130〕B.〔100，120，110，130，80，60，90〕C.〔100，60，80，90，120，110，130〕D.(100，80，60，90，120，130，110)1．某內排序方法的穩(wěn)定性是指(D)。A．該排序算法不允許有相同的關鍵字記錄B．該排序算法允許有相同的關鍵字記錄C．平均時間為0〔nlogn〕的排序方法D．以上都不對2．下面給出的四種排序法中(D)排序法是不穩(wěn)定性排序法。A.插入B.冒泡C.二路歸并D.堆積3．以下排序算法中，其中〔D〕是穩(wěn)定的?！靖Ｖ荽髮W1998一、3(2分)】A.堆排序，冒泡排序B.快速排序，堆排序C.直接選擇排序，歸并排序D.歸并排序，冒泡排序4．穩(wěn)定的排序方法是〔B〕A．直接插入排序和快速排序B．折半插入排序和起泡排序C．簡單項選擇擇排序和四路歸并排序D．樹形選擇排序和shell排序5．以下排序方法中，哪一個是穩(wěn)定的排序方法？〔B〕A．直接選擇排序B．二分法插入排序C．希爾排序D．快速排序6．假設要求盡可能快地對序列進行穩(wěn)定的排序，那么應選B〔A．快速排序B．歸并排序C．冒泡排序〕。7．假設要求排序是穩(wěn)定的，且關鍵字為實數(shù)，那么在以下排序方法中應選〔A〕排序為宜。A．直接插入B．直接選擇C．堆D．快速E．基數(shù)8．假設需在O(nlog2n)的時間內完成對數(shù)組的排序，且要求排序是穩(wěn)定的，那么可選擇的排序方法是〔C〕。A.快速排序B.堆排序C.歸并排序D.直接插入排序9．下面給出的四種排序方法中，排序過程中的比擬次數(shù)與排序方法無關的是。(A)A．選擇排序法B.插入排序法C.快速排序法D.堆積排序法10．對以下四種排序方法，在排序中關鍵字比擬次數(shù)同記錄初始排列無關的是(D)。A．直接插入B.二分法插入C.快速排序D.歸并排序11．在以下排序算法中,哪一個算法的時間復雜度與初始排序無關〔D〕。A．直接插入排序B.氣泡排序C.快速排序D.直接選擇排序12．比擬次數(shù)與排序的初始狀態(tài)無關的排序方法是(D)。A．直接插入排序B．起泡排序C．快速排序D．簡單項選擇擇排序13．數(shù)據(jù)序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中的(C)的兩趟排序后的結果。A．選擇排序B.冒泡排序C.插入排序D.堆排序14．數(shù)據(jù)序列〔2，1，4，9，8，10，6，20〕只能是以下排序算法中的(A)的兩趟排序后的結果。A.快速排序B.冒泡排序C.選擇排序D.插入排序15．對一組數(shù)據(jù)〔84，47，25，15，21〕排序，數(shù)據(jù)的排列次序在排序的過程中的變化為A.8447251521B.1547258421C.1521258447D.1521254784那么采用的排序是(A)。A.選擇B.冒泡C.快速D.插入16．對序列{15，9，7，8，20，-1，4}進行排序，進行一趟后數(shù)據(jù)的排列變?yōu)閧4，9，-1，8，20，7，15}；那么采用的是〔C〕排序。A.選擇B.快速C.希爾D.冒泡1．一個堆棧的入棧序列為A、B、C、D、E，那么可能的出棧序列是〔〕。A.DCEABB.DECBAC.EDCBAD.ABCDE2.〔〕屬于不穩(wěn)定的排序算法。希爾排序B.堆排序C.快速排序D.基數(shù)排序3.向單鏈表中指針hs指向的結點后插入一個新節(jié)點s，應執(zhí)行〔〕。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;4.一個n個頂點的連通有向圖，其邊的數(shù)量至少為〔〕。A．n-1B．nC．n+1D．nlogn；5.設圖如下所示，在下面的5個序列中，不符合深度優(yōu)先遍歷的序列有〔〕種。aebdfcacfdebaedfcbaefdcbaefdbcA．2B．3C．4D．以上均不正確6．一個具有1026個結點的二叉樹的高h為〔〕。A．11B．12C．11至1026之間D．10至1024之間7．某二叉樹中序遍歷序列為ABCDEFG，后序遍歷序列為BDCAFGE，那么其先序序列不是〔〕。A．EACBDGFB．EFGACBDC．EAGCFBDD．EGFACDB8．不適用于折半查找的表的存儲方式及元素排列要求為〔〕。A．鏈接方式存儲，元素無序B．鏈接方式存儲，元素有序C．順序方式存儲，元素無序D．順序方式存儲，元素有序9.設n,m為一棵二叉樹上的兩個結點，在中序遍歷序列中n在m前的條件是〔〕。A.n在m右方B.n在m左方C.n是m的祖先D.n是m的子孫10．用戶依次輸入如下一組查詢關鍵字：70、50、30、60、66、56、80。請問最后建立的平衡二叉樹樹根是〔〕。A.50B.56C.60D.70二、填空題1．當線性表的元素總數(shù)根本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用__順序_____存儲結構。2．線性表L=〔a1,a2,…,an〕用數(shù)組表示，假定刪除表中任一元素的概率相同，那么刪除一個元素平均需要移動元素的個數(shù)是__〔n-1〕/2______?！颈狈浇煌ù髮W2001二、9】3．設單鏈表的結點結構為(data,next)，next為指針域，指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點,假設將結點y插入結點x之后，那么需要執(zhí)行以下語句:_______；py->next=px->next;px->next=py______;4．在一個長度為n的順序表中第i個元素〔1<=i<=n〕之前插入一個元素時，需向后移動_n-i+1_______個元素。5．對于一個具有n個結點的單鏈表，在的結點*p后插入一個新結點的時間復雜度為_O(1)，_______,在給定值為x的結點后插入一個新結點的時間復雜度為__O(n)______6．根據(jù)線性表的鏈式存儲結構中每一個結點包含的指針個數(shù)，將線性鏈表分成________和_______；而又根據(jù)指針的連接方式，鏈表又可分成________和________。7．在雙向循環(huán)鏈表中,向p所指的結點之后插入指針f所指的結點，其操作是_______、f->next=p->next;f->prior=p;p->next->prior=f;p->next=f;_______、_______、________。8.在雙向鏈表結構中，假設要求在p指針所指的結點之前插入指針為s所指的結點，那么需執(zhí)行以下語句：s^.next:=p；s^.prior:=_p^.prior_______；p^.prior:=s；__s^.prior^.next______:=s；9．鏈接存儲的特點是利用__指針______來表示數(shù)據(jù)元素之間的邏輯關系。10.順序存儲結構是通過__物理上相鄰_____表示元素之間的關系的;鏈式存儲結構是通過__指針_______表示元素之間的關系的。11.對于雙向鏈表,在兩個結點之間插入一個新結點需修改的指針共__4__個，單鏈表為____2___個。12.循環(huán)單鏈表的最大優(yōu)點是：_從任一結點出發(fā)都可訪問到鏈表中每一個元素。_______。13.指針p指向單鏈表L中的某結點，那么刪除其后繼結點的語句是：_u=p->next;p->next=u->next;free(u);_______14.帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是：__L->next->next==L______15.在單鏈表L中，指針p所指結點有后繼結點的條件是：_p->next!=null_16.帶頭結點的雙循環(huán)鏈表L為空表的條件是：____L->next==L&&L->prior==L____。17.在單鏈表p結點之后插入s結點的操作是：_s->next=p->next;p->next=s;______。1．棧是_操作受限〔或限定僅在表尾進行插入和刪除操作〕______的線性表，其運算遵循__后進先出_____的原那么。2．___棧____是限定僅在表尾進行插入或刪除操作的線性表。3.一個棧的輸入序列是：1，2，3那么不可能的棧輸出序列是_312______。4.設有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_______，而棧頂指針值是_______H。設棧為順序棧，每個元素占4個字節(jié)。5.當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top[1]與top[2]，那么當棧1空時，top[1]為__0，棧2空時，top[2]為___n+1____，棧滿時為__top[1]+1=top[2]_____。6．用下標0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標變量M加1后在數(shù)組有效下標范圍內循環(huán)，可采用的表達式是：M：=M=_(M+1)%N；_______。7．___隊列_____又稱作先進先出表。8.隊列的特點是__先進先出_____。9．隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是__先進先出_____。1.數(shù)組的存儲結構采用___順序存儲結構____存儲方式。2.設二維數(shù)組A[-20..30,-30..20],每個元素占有4個存儲單元,存儲起始地址為200.如按行優(yōu)先順序存儲,那么元素A[25,18]的存儲地址為__〔1〕9572_；如按列優(yōu)先順序存儲,那么元素A[-18,-25]的存儲地址為__〔2〕1228_。3.設數(shù)組a[1..50,1..80]的基地址為2000，每個元素占2個存儲單元，假設以行序為主序順序存儲，那么元素a[45,68]的存儲地址為_〔1〕9174_;假設以列序為主序順序存儲，那么元素a[45,68]的存儲地址為_〔2〕8788_。4.將整型數(shù)組A[1..8，1..8]按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內存單元中，那么元素A[7，3]的地址是：__1100_____。5.設有二維數(shù)組A[0..9,0..19],其每個元素占兩個字節(jié)，第一個元素的存儲地址為100，假設按列優(yōu)先順序存儲，那么元素A[6,6]存儲地址為__232_____。6.數(shù)組A[0..9,0..9]的每個元素占5個存儲單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內存單元中，那么元素A[6，8]的地址為__1340_____。7.二維數(shù)組A[1..10，0..9]中每個元素占4個單元，在按行優(yōu)先方式將其存儲到起始地址為1000的連續(xù)存儲區(qū)域時，A[5，9]的地址是：___1196____。8.用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8個元素是A中的第_1_行，第_3_列的元素。1．二叉樹由_(1)根結點(2)左子樹(3)右子樹(1)__，__(2)_，_(3)__三個根本單元組成。2．在二叉樹中，指針p所指結點為葉子結點的條件是_p->lchild==null&&p->rchlid==null_____。3．二叉樹中某一結點左子樹的深度減去右子樹的深度稱為該結點的__平衡因子__。4．具有256個結點的完全二叉樹的深度為__9____。5．一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，那么該樹有___12___個葉子結點。6．假設根結點的層數(shù)為１，具有ｎ個結點的二叉樹的最大高度是__n____。7．在一棵二叉樹中，度為零的結點的個數(shù)為N0,度為2的結點的個數(shù)為N2,那么有N0=__N2+1____8．設有N個結點的完全二叉樹順序存放在向量A[1:N]中，其下標值最大的分支結點為__N/2____。9．高度為K的完全二叉樹至少有__2k-2____個葉子結點。10．高度為8的完全二叉樹至少有___64___個葉子結點。11．二叉樹有50個葉子結點，那么該二叉樹的總結點數(shù)至少是_99_____。12．一個有2001個結點的完全二叉樹的高度為__11____。13．如某二叉樹有20個葉子結點，有30個結點僅有一個孩子，那么該二叉樹的總結點數(shù)為__69____。14．具有N個結點的二叉樹，采用二叉鏈表存儲，共有__N+1____個空鏈域。15．二叉樹的先序序列和中序序列相同的條件是_任何結點至多只有右子女的二叉樹。_____。16．二叉樹前序為ABDEGCF，中序為DBGEACF，那么后序一定是__DGEBFCA__。17．一個無序序列可以通過構造一棵___二叉排序樹___樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。18．利用樹的孩子兄弟表示法存儲，可以將一棵樹轉換為__二叉樹____。19．假設一個二叉樹的葉子結點是某子樹的中序遍歷序列中的最后一個結點，那么它必是該子樹的___前序___序列中的最后一個結點。20．哈夫曼樹是_帶權路徑長度最小的二叉樹，又稱最優(yōu)二叉樹_____。21．假設以{4，5，6，7，8}作為葉子結點的權值構造哈夫曼樹，那么其帶權路徑長度是__69____。22．有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，那么所建Huffman樹的樹高是_6__，帶權路徑長度WPL為_261__。23.給定一組數(shù)據(jù){6，2，7，10，3，12}以它構造一棵哈夫曼樹，那么樹高為__5,________，帶權路徑長度WPL的值為___96_______。1.判斷一個無向圖是一棵樹的條件是_有n個頂點，n-1條邊的無向連通圖_____。2．有向圖G的強連通分量是指__有向圖的極大強連通子圖____。3．一個連通圖的__生成樹____是一個極小連通子圖。4．具有10個頂點的無向圖，邊的總數(shù)最多為__45____。5．假設用n表示圖中頂點數(shù)目，那么有__n(n-1)/2_____條邊的無向圖成為完全圖。6．G是一個非連通無向圖，共有28條邊，那么該圖至少有__9____個頂點。7.在有n個頂點的有向圖中，假設要使任意兩點間可以互相到達，那么至少需要_n_____條弧。8．在有n個頂點的有向圖中，每個頂點的度最大可達__2(n-1)____。9．設G為具有N個頂點的無向連通圖，那么G中至少有_N-1_____條邊。10．n個頂點的連通無向圖，其邊的條數(shù)至少為__n-1____。11．如果含n個頂點的圖形形成一個環(huán)，那么它有__n____棵生成樹。12．N個頂點的連通圖的生成樹含有__N-1____條邊。13．構造n個結點的強連通圖，至少有__n____條弧。 14．有N個頂點的有向圖，至少需要量__N____條弧才能保證是連通的。15．右圖中的強連通分量的個數(shù)為〔3〕個。16．N個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有___2〔N-1〕____個非零元素。17．在圖G的鄰接表表示中，每個頂點鄰接表中所含的結點數(shù)，對于無向圖來說等于該頂點的__度____；對于有向圖來說等于該頂點的_出度_____。18.在有向圖的鄰接矩陣表示中，計算第I個頂點入度的方法是_第I列非零元素個數(shù)_____。19．構造連通網(wǎng)最小生成樹的兩個典型算法是__普里姆〔prim〕算法和克魯斯卡爾〔Kruskal〕算法____。20．求圖的最小生成樹有兩種算法，__克魯斯卡爾____算法適合于求稀疏圖的最小生成樹。21.Prim〔普里姆〕算法適用于求__邊稠密___的網(wǎng)的最小生成樹；kruskal〔克魯斯卡爾〕算法適用于求_邊稀疏______的網(wǎng)的最小生成樹。22.有向圖G可拓撲排序的判別條件是__不存在環(huán)____。23．求最短路徑的Dijkstra算法的時間復雜度為__O(n2〕____。24.上面的圖去掉有向弧看成無向圖那么對應的最小生成樹的邊權之和為__75____。25．設有向圖有n個頂點和e條邊，進行拓撲排序時，總的計算時間為__.O(n+e〕____。26．在AOE網(wǎng)中，從源點到匯點路徑上各活動時間總和最長的路徑稱為__關鍵路徑____。1．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比擬的元素下標依次為__6,9,11,12________。2.在有序表A[1..20]中，按二分查找方法進行查找，查找長度為5的元素個數(shù)是__5________3.在有序表A[1…20]中，按二分查找方法進行查找，查找長度為4的元素的下標從小到大依次是__1,3,6,8,11,13,16,19________4.己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當用二分法查找90時，需___2,_______次查找成功，47時_____4,____成功，查100時，需___3_______次才能確定不成功。哈希表是通過將查找碼按選定的__(1)__和__(2)__，把結點按查找碼轉換為地址進行存儲的線性表。哈希方法的關鍵是_(3)__和__(4)__。一個好的哈希函數(shù)其轉換地址應盡可能__(5)__，而且函數(shù)運算應盡可能__(6)__。5.平衡二叉樹又稱__________，其定義是__________。6.在哈希函數(shù)H〔key〕=key%p中，p值最好取__________。7.對于長度為255的表，采用分塊查找，每塊的最正確長度為___16_______。8.在n個記錄的有序順序表中進行折半查找，最大比擬次數(shù)是___．㏒2n」+1_______。9．假定有k個關鍵字互為同義詞，假設用線性探測再散列法把這k個關鍵字存入散列表中，至少要進行__k(k+1)/2________次探測。10.如果按關鍵碼值遞增的順序依次將關鍵碼值插入到二叉排序樹中，那么對這樣的二叉排序樹檢索時，平均比擬次數(shù)為___(n+1)/2_______。11.如果關鍵碼按值排序，而后用二分法依次檢索這些關鍵碼，并把檢索中遇到的在二叉樹中沒有出現(xiàn)的關鍵碼依次插入到二叉排序樹中，那么對這樣的二叉排序樹檢索時，平均比擬次數(shù)為__(n+1)/n*log2(n+1)-1________。12.平衡因子的定義是__結點的左子樹的高度減去結點的右子樹的高度________13.___．直接定址法_______法構造的哈希函數(shù)肯定不會發(fā)生沖突。14.在一棵有N個結點的非平衡二叉樹中進行查找，平均時間復雜度的上限〔即最壞情況平均時間復雜度〕為___O(N)_____。15.假設有n個關鍵字，它們具有相同的Hash函數(shù)值，用線性探測方法解決沖突，把這n個關鍵字散列到大小為n的地址空間中，共計需要做___n(n+1)/2___次插入和探測操作。16.高度為8的平衡二叉樹的結點數(shù)至少有___54_______個。17.高度為5〔除葉子層之外〕的三階B-樹至少有___31_______個結點。18.假定查找有序表A[1..12]中每個元素的概率相等，那么進行二分查找時的平均查找長度為___37/12_______19.可以唯一的標識一個記錄的關鍵字稱為___主關鍵字_______。20.二叉排序樹的左右子樹均不為空，那么___126_____上所有結點的值均小于它的根結點值，__64__________上所有結點的值均大于它的根結點的值。21.動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有____插入______和____刪除______運算，而后者不包含這兩種運算。1．假設不考慮基數(shù)排序，那么在排序過程中，主要進行的兩種根本操作是關鍵字的_比擬,_____和記錄的_移動____。2.屬于不穩(wěn)定排序的有_希爾排序、簡單項選擇擇排序、快速排序、堆排序等_________。3．分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表，那么最省時間的是_冒泡,____算法，最費時間的是__快速____算法。4.不受待排序初始序列的影響，時間復雜度為O(N2)的排序算法是_(1)簡單項選擇擇排序____，在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是_(2)直接插入排序〔最小的元素在最后時〕____。5．直接插入排序用監(jiān)視哨的作用是_______。6．對n個記錄的表r[1..n]進行簡單項選擇擇排序，所需進行的關鍵字間的比擬次數(shù)為_n(n-1)/2______。7．從平均時間性能而言，__快速________排序最正確。8．對于7個元素的集合{1，2，3，4，5，6，7}進行快速排序，具有最小比擬和交換次數(shù)的初始排列次序為_(4,1,3,2,6,5,7)____。9．快速排序在_____的情況下最易發(fā)揮其長處。10．在數(shù)據(jù)表有序時，快速排序算法的時間復雜度是_.O(n2)___。11．堆排序的算法時間復雜度為：__O(nlog2n)___。12．堆是一種有用的數(shù)據(jù)結構。試判斷下面的關鍵碼序列中哪一個是堆___④_______。①16，72，31，23，94，53②94，53，31，72，16，23③16，53，23，94，13，72④16，31，23，94，53，72⑤94，31，53，23，16，72下面程序段中，帶波浪線語句的執(zhí)行頻度為。i=1；while(i<=n)i=i*4;設有一空棧，現(xiàn)有輸入序列e，d，c，b，a，經(jīng)過push,push,push,pop,pop,push,push,pop操作后，輸出序列是______。長為n的循環(huán)隊列滿時，隊頭指針front和隊尾指針rear須滿足以下關系:。在字符串的模式匹配算法中，模式串“aaabcaaabcad”第7個字符〔帶下劃線〕的next[j]值為：______。數(shù)組A中每個元素的長度為3字節(jié)，行下標i從1到18，列下標j從1到30，從首地址1000開始連續(xù)存放在存儲器內，該數(shù)組按行存放時，元素A[8][5]的起始地址為。二叉樹的先序序列和中序序列相同的條件是：___。廣義表A=(x,((a,b),z),y)，那么運算tail(head(tail(A)))的結果為。具有四個結點的二叉樹有種不同形態(tài)。一棵完全二叉樹的結點總數(shù)為60個，那么最后一層的結點數(shù)為。在一棵度為3的樹中，度為3的結點數(shù)為3個，度為2的結點數(shù)為1個，度為1的結點數(shù)為20個，那么葉子結點數(shù)為個。高度為h的二叉樹中只有度為0和2的結點，那么此二叉樹中包含的結點數(shù)至少為。具有11個頂點的無向圖，邊的總數(shù)最多為______。以下圖所示無向網(wǎng)的最小生成樹各邊權值之和為。在伙伴系統(tǒng)中，起始地址為320，大小為8的塊，其伙伴塊的起始地址是。具有15個關鍵字的有序表，折半查找的平均查找長度為。哈希表的平均檢索長度不隨表中結點數(shù)目的增加而增加，而是隨的增大而增大。三、應用題1請按照迪杰斯特拉算法的思想填寫下表，并依此列出從頂點A到圖中所有其它頂點的最短路徑〔要求寫出每條最短路徑經(jīng)過的頂點序列，并指出該路徑長度〕。從A到所有其它頂點的最短路徑如下：2請?zhí)顚懴卤恚蟪鱿旅鍭OE-網(wǎng)中各個活動的最早和最遲開始時間，并據(jù)此求出該圖的關鍵路徑和工程的工期，指出哪些活動是關鍵活動。1234567VeVl關鍵路徑是：工程工期〔即關鍵路徑長度〕為：關鍵活動是：3ABCDEFG在報文中出現(xiàn)的概率分別為：5、20、16、37、12、8、7；請為這7種字符設計相應的赫夫曼編碼。要求：①畫出用于編碼的赫夫曼樹；②給出各字符編碼結果。4使用哈希函數(shù)hashf(x)=xmod13，現(xiàn)要把數(shù)據(jù)：1，13，12，34，38，33，27，22依次插入到哈希表中。要求：〔1〕使用線性探查再散列法來構造哈希表?！?〕使用鏈地址法構造哈希表?！?〕針對這兩種情況，確定其裝填因子，計算查找成功所需的平均比擬次數(shù)。5一待排序記錄關鍵字序列如下：〔17、89、46、35、49、96、13、5、22〕。寫出利用快速排序法對其進行第一趟排序后所得的序列：畫出由原始關鍵字序列篩選后建立的堆結構：6畫出該森林對應的二叉樹結構，寫出該二叉樹的中序遍歷結點序列。1.對下面過程寫出調用P(3)的運行結果。PROCEDUREp〔w：integer〕;BEGINIFw>0THENBEGINp(w-1);writeln(w);{輸出W}p(w-1〕END；END；解：運行結果為：1213121〔注：運行結果是每行一個數(shù)，為節(jié)省篇幅，放到一行。〕1.設一棵二叉樹的前序序列為ABDGECFH，中序序列為：DGBEAFHC。試畫出該二叉樹。2．一棵二叉樹的中序序列和后序序列分別為DBEAFIHCG和DEBHIFGCA，畫出這棵二叉樹。3．假定用于通訊的電文僅有8個字母C1，C2，…，C8組成，各個字母在電文中出現(xiàn)的頻率分別為5，25，3，6，10，11，36，4，試為這8個字母設計哈夫曼編碼樹。4．設通信中出現(xiàn)5中字符A、B、C、D、E對應的頻率為0.2,0.1,0.5,0.15,0.25構造哈夫曼樹，并給出對應字符的哈夫曼編碼。5．假設用于通訊的電文由8個字符組成，其出現(xiàn)的頻率為5,29,7,8,14,23,3,11。試為這8個字符設計哈夫曼編碼。6．假設用于通信的電文由字符集{a,b,c,d,e,f,g}中的字母構成。它們在電文中出現(xiàn)的頻度分別為{0.31,0.16,0.10,0.08,0.11,,0.20,0.04},為這7個字母設計哈夫曼編碼。7．試構造一棵二叉樹,包含權為1,4,9,16,25,36,49,64,81,100等10個終端結點,且具有最小的加權路徑長度WPL?！?0〕以數(shù)據(jù)集{2,5,7,9,13}為權值構造一棵哈夫曼樹，并計算其帶權路徑長度。以右圖為例，按Dijkstra算法計算得到的從頂點①(A)到其它各個頂點的最短路徑和最短路徑長度。2.試對右圖所示的AOE網(wǎng)絡，解答以下問題。 (1)這個工程最早可能在什么時間結束。(2)求每個事件的最早開始時間Ve[i]和最遲開始時間Vl[I]。(3)求每個活動的最早開始時間e()和最遲開始時間l()。 (4)確定哪些活動是關鍵活動。畫出由所有關鍵活動構成的圖，指出哪些活動加速可使整個工程提前完成。按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據(jù)l-e=0?來確定關鍵活動，從而確定關鍵路徑。 此工程最早完成時間為〔〕。關鍵路徑為：〔〕 此工程最早完成時間為43。關鍵路徑為<1,3><3,2><2,5><5,6>3．一個無向圖如以下圖所示，要求分別用Prim和Kruskal算法生成最小樹〔假設以①為起點，試畫出構造過程〕。1212654320101166181014594．試寫出用克魯斯卡爾〔Kruskal〕算法構造以下圖的一棵最小生成樹的過程。112564318412810202515523767第29圖解：V〔G〕={1，2，3，4，5，6，7}E〔G〕={〔1，6，4〕，〔1，7，6〕，〔2，3，5〕，〔2，4，8〕，〔2，5，12〕，〔1，2，18〕}設有一組關鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H〔key〕=keymod7，表長為10，用開放地址法的二次探測再散列方法Hi=(H(key)+di)mod10(di=12,22,32,…,)解決沖突。要求：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度。解：平均查找長度：ASLsucc=〔1+1+1+2+3+4+1+2〕/8=15/8以關鍵字27為例：H〔27〕=27%7=6〔沖突〕H1=〔6+1〕%10=7〔沖突〕H2=〔6+22〕%10=0〔沖突〕H3=〔6+33〕%10=5所以比擬了4次。設哈希表a、b分別用向量a[0..9],b[0..9]表示，哈希函數(shù)均為H〔key〕=keyMOD7,處理沖突使用開放定址法，Hi=[H(key)+Di]MOD10,在哈希表a中Di用線性探測再散列法，在哈希表b中Di用二次探測再散列法,試將關鍵字{19,24,10,17,15,38,18,40}分別填入哈希表a,b中,并分別計算出它們的平均查找長度ASL。解：哈希表a:ASLsucc=24/8=3；哈希表b:ASLsucc=18/83.采用哈希函數(shù)Ｈ〔k〕=3*kmod13并用線性探測開放地址法處理沖突，在數(shù)列地址空間［0..12］中對關鍵字序列22,41,53,46,30,13,1,67,51〔1〕構造哈希表〔畫示意圖〕；〔2〕裝填因子；等概率下〔3〕成功的和〔4〕不成功的平均查找長度。4.長度為12的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)試按表中元素的順序依次插入一棵初始為空的分類二叉樹，試畫出插入完成之后的分類二叉樹并計算其在等概率查找情況下，查找成功的平均查找長度。試用以下兩種方法構造兩個Hash表，Hash函數(shù)H(K)=[i/2],其中i為關鍵字K中第一個字母在字母表中的序號，[x]表示取整數(shù)。a.用線性探測開放定址法處理沖突(散列地址空間為0～16);b.用鏈地址法處理,然后分別求出這兩個Hash表在等概率查找情況下，查找成功的平均查找長度。5.一棵二叉排序樹結構如下,各結點的值從小到大依次為1-9，請標出各結點的值。6.長度為11的表〔xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon〕，按表中元素順序依次插入一棵初始為空的平衡二叉排序樹，畫出插入完成后的平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。7.用序列(46,88,45,39,70,58,101,10,66,34)建立一個排序二叉樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度.【北京郵電大學1999七〔10分〕】49.依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹。(1)試畫出生成之后的二叉排序樹;(2)對該二叉排序樹作中序遍歷，試寫出遍歷序列;(3)假定每個元素的查找概率相等，試計算該二叉排序樹的平均查找長度。8.關鍵字序列R={11,4,3,2,17,30,19}，請按算法步驟：〔1〕構造一棵哈夫曼樹，并計算出它的帶權路徑長度WPL〔2〕構造一棵二叉排序樹，如果對每個關鍵字的查找概率相同，求查找成功時的平均查找長度ASL。9.輸入一個正整數(shù)序列〔53,17,12,66,58,70,87,25,56,60〕，試完成以下各題。按次序構造一棵二叉排序樹BS。(2)依此二叉排序樹，如何得到一個從大到小的有序序列？畫出在此二叉排序樹中刪除“66”后的樹結構。10.設二叉排序樹中關鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關鍵字為363的結點，下述關鍵字序列哪一個不可能是在二叉排序樹中查到的序列？說明原因?！?〕51，250，501，390，320，340，382，363〔2〕24，877，125，342，501，623，421，3631．寫出以下排序算法的根本思想，并寫出對序列〔23，12，35，47，16，25，36，19，21，16〕進行排序時每一趟的結果。PROCbbsort(VARr:sequence;n:integer);{r是一個數(shù)組}d:=1;pos[-1]:=1;pos[1]:=n;i:=1;exchanged:=true;WHILEexchangedDO[exchanged:=false;WHILEi<>pos[d]DO[IF(r[i]-r[i+d])*d>0THEN[r[i]與r[i+d]交換;exchanged:=true;];i:=i+d;]pos[d]:=pos[d]-d;i:=pos[d];d:=-d;]ENDP;答：此排序為雙向起泡排序：從前向后一趟排序下來得到一個最大值，假設其中發(fā)生交換，那么再從后向前一趟排序，得到一個最小值。 一趟：12,23,35,16,25,36,19,21,16,47 二趟：12,16,23,35,16,25,36,19,21,47 三趟：12,16,23,16,25,35,19,21,36,47 四趟：12,16,16,23,19,25,35,21,36,47 五趟：12,16,16,19,23,25,21,35,36,47 六趟：12,16,16,19,21,23,25,35,36,47七趟：12,16,16,19,21,23,25,35,36,472．設待排序的關鍵碼分別為28，13，72，85，39，41，6，20。按二分法插入排序算法已使前七個記錄有序，中間結果如下:613283941728520i=1m=4r=7試在此根底上，沿用上述表達方式，給出繼續(xù)采用二分法插入第八個記錄的比擬過程。(1)使用二分法插入排序所要進行的比擬次數(shù)，是否與待排序的記錄的初始狀態(tài)有關？(2)在一些特殊情況下，二分法插入排序比直接插入排序要執(zhí)行更多的比擬。這句話對嗎？解：6,13,28,39,41,72,85,20i=1↑m=4↑r=7↑20<39i=1↑m=2↑r=3↑20>13i=3r=3m=320<28r=2i=3將r+1(即第3個)后的元素向后移動，并將20放入r+1處，結果為6,13,20,28,39,41,72,85?！?〕使用二分法插入排序所要進行的比擬次數(shù)，與待排序的記錄的初始狀態(tài)無關。不管待排序序列是否有序，已形成的局部子序列是有序的。二分法插入首先查找插入位置，插入位置是判定樹查找失敗的位置。失敗位置只能在判定樹的最下兩層上?！?〕一些特殊情況下，二分法插入排序要比直接插入排序要執(zhí)行更多的比擬。例如，在待排序序列已有序的情況下就是如此。3．算法模擬設待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。(1)用直接插入排序。試以排序碼序列的變化描述形式說明排序全過程〔動態(tài)過程求按遞減順序排序。(2)用直接選擇排序。試以排序碼序列的變化描述形式說明排序全過程〔動態(tài)過程〕要求按遞減順序排序。(3)直接插入排序算法和直接選擇排序算法的穩(wěn)定性如何？解：.(1)直接插入排序第一趟 (3)[8,3],2,5,9,1,6第二趟 (2)[8,3,2],5,9,1,6第三趟 (5)[8,5,3,2],9,1,