《2019年電大本科數(shù)據(jù)結(jié)構(gòu)期末考試題庫及答案》由會員分享，可在線閱讀，更多相關(guān)《2019年電大本科數(shù)據(jù)結(jié)構(gòu)期末考試題庫及答案（21頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)（本）期末題庫及答案一、單項(xiàng)選擇題1數(shù)據(jù)的物理結(jié)構(gòu)（ D ）。 A與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) B僅僅包括數(shù)據(jù)元素的表示C只包括數(shù)據(jù)元素間關(guān)系的表示 D包括數(shù)據(jù)元素的表示和關(guān)系的表示2數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ C ）。A只能有一個(gè)數(shù)據(jù)項(xiàng)組成 B至少有二個(gè)數(shù)據(jù)項(xiàng)組成C可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成D至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型3從n個(gè)數(shù)中選取最大元素，（ C ）。 A基本操作是數(shù)據(jù)元素間的交換 B算法的時(shí)間復(fù)雜度是O(n2)C算法的時(shí)間復(fù)雜度是O(n) D需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較4線性表的順序結(jié)構(gòu)中，（ C ）。A邏輯上相鄰的元素在物理位置上不一定相鄰B數(shù)據(jù)元素是不能隨

2、機(jī)訪問的C邏輯上相鄰的元素在物理位置上也相鄰D進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高5以下表中可以隨機(jī)訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表6帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件是（ B ）（設(shè)頭指針為head）。Ahead = =NULL Bhead-next= =NULL Chead-next= =head Dhead!=NULL7 .設(shè)順序存儲的線性表長度為n，對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個(gè)元素平均移動元素的次數(shù)為（ A ）。A(n+1)/2 Bn C2n Dn-i8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ A ）的關(guān)系。 A一對一 B一對多 C多對多 D

3、每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼9設(shè)top是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則出棧操作為（ A ）。Ax=top-data;top=top-next; Btop=top-next;x=top-data; Cx=top- next;top=top- data; Dtop-next =top; x=top-data;10設(shè)順序存儲的線性表長度為n，要?jiǎng)h除第i個(gè)元素，按課本的算法，當(dāng)i=（ C ）時(shí)，移動元素的次數(shù)為3A3 Bn/2 Cn-3 D411以下說法正確的是（ C ）。A隊(duì)列是后進(jìn)先出 B棧的特點(diǎn)是后進(jìn)后出C棧的刪除和插

4、入操作都只能在棧頂進(jìn)行D隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行12 .以下說法不正確的是（ C ）。A棧的特點(diǎn)是后進(jìn)先出 B隊(duì)列的特點(diǎn)是先進(jìn)先出C棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行D隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行13串函數(shù)StrCmp(“abA”,”aba”)的值為（ D ）。A1 B0 C“abAaba” D-114一個(gè)棧的進(jìn)棧序列是a，b，c，d，則棧的不可能的出棧序列是（ A ）。Aadbc BbcadCcbad Ddcba15設(shè)有一個(gè)12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組b中（矩陣A的第一個(gè)元素為a1,1，數(shù)組b的下標(biāo)從1開始）

5、，則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有（ A ）。A7i10 B11i15 C9i14 D6i916已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（ A ）。A2m Bm C2m+1 Dm/217設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊(duì)列的頭指針和尾指針，要執(zhí)行出隊(duì)操作，用x保存出隊(duì)元素的值，p為指向結(jié)點(diǎn)類型的指針，可執(zhí)行如下操作：p=front-next;x=p-data; 然后執(zhí)行（ B ）。Afront=p-next; Bfront-next=p-next;Cfront=p; Dfront-next =

6、p;18以下說法不正確的是（ D ）。 A連通圖G一定存在生成樹B連通圖G的生成樹中一定包含G的所有頂點(diǎn)C連通圖G的生成樹中不一定包含G的所有邊D連通圖G的生成樹可以是不連通的19散列查找的原理是（ A ）。A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲C按關(guān)鍵字值的比較進(jìn)行查找D基于二分查找的方法20空串的長度為（ A ）。A0 B1 C2 D321排序過程中，每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹?，該排序算法? D )。 A選擇排序 B快速排序C冒泡排序 D直接插入排

7、序 22采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（ B ）次元素間的比較。 An+2 Bn Cn-1 Dn/223設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組b中。（矩陣A的第一個(gè)元素為a1,1，數(shù)組b的下標(biāo)從1開始），則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù)組元素是（ C ）。Ab18 Bb8 Cb13 Db1024如圖1若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為（ D ）。abecdhgf AacebdfghBaebcghdfCaedfbcghDabecdfgh 圖125已知如圖2所示的

8、一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ D ）。 Aabecdf Bacfebd Caebcfd Daedfcb bdfeca 圖226一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn)，該樹共有（ D ）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）。A10 B13 C11 D12二、填空題1通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性、_樹形_、_ 圖狀 四種類型。2通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成_圖狀 _結(jié)構(gòu)。3設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句_ p-next=head;_ _。4設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為

9、head，鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作_ _ p-next=head 。 5循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)_ r=f _時(shí)表明隊(duì)列已空。6在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，則插入一個(gè)s所指結(jié)點(diǎn)的操作為_ r-next=s _；r=s；7設(shè)有一個(gè)鏈棧，棧頂指針為hs，現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作_ s-next=hs 和hs=s；8循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)_ r= =f _時(shí)表明隊(duì)列為空。 9在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的

10、指針域?yàn)閚ext，則插入一個(gè)s所指結(jié)點(diǎn)的操作為_ r-next=s _；r=s；10“A”在存儲時(shí)占_2_個(gè)字節(jié)。11串的兩種最基本的存儲方式分別是_順序存儲_和 _鏈?zhǔn)酱鎯?_。12一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹總共有_11_個(gè)結(jié)點(diǎn)。13一棵二叉樹中順序編號為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號分別為_2i _、_2i+1_。14按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_先序 、_中序_、 _后序_三種。15兩個(gè)串相等的充分必要條件是 串長度相等且對應(yīng)位置的字符相等 。16把數(shù)據(jù)存儲到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_物理（存儲）_結(jié)構(gòu)。17一棵二叉

11、樹葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹共有_11_個(gè)結(jié)點(diǎn)。18如圖3所示的二叉樹，其后序遍歷序列為 gdbeihfca 。efgibachd 圖319根據(jù)搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷_、 _廣度優(yōu)先搜索遍歷 方法。20二叉樹為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是_錯(cuò)誤_的。(回答正確或不正確) 21一個(gè)有序表3，4，10，14，34，43，46，64，75，78，90，96，130用折半查找法查找值為90的結(jié)點(diǎn)，經(jīng)_4_次比較后查找成功。三、綜合題 1（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbe

12、ac，試畫出該二叉樹abced （2）若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系。答：dbeac （3）給出該樹的前序遍歷序列答：abdec2（1）一組記錄的關(guān)鍵字序列為45，40，65，43，35，95，寫出利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的 結(jié)果）答： 45 40 65 43 35 95 35 40 65 43 35 95 35 40 65 43 65 95 35 40 43 43 65 95 35 40 43 45 65 95 （2）對序列

13、45，40，65，43，35，95利用直接插入排序，寫出逐次插入過程（從第一個(gè)元素一直到第六個(gè)元素）。 答 40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 9540287231005463（1）設(shè)有一個(gè)整數(shù)序列40，28，6，72，100，3，54依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹 （2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度答：ASL=（1x1+2x2+3x3+4）/7=18/74 (1) 設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹.2461673185145（2）說明如

14、何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。答：中序遍歷16423252576782102 5（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程）初始樹 堆42826752573216102（2）寫出對上述堆對應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列答：102，52，42，82，16，67，32，57四、程序填空題1以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Sea

15、rch(NODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_low=high _) mid=(low+high)/2; if(amid.key=k) return _ mid _; else if(_amid.keydata=x; _ p-next=top _; _ top=p _; 3以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針struct node ElemType data;struct node *next;struct node *front，*re

16、ar; void InQueue(ElemType x) struct node *p; p= (struct node*) _ malloc(sizeof (struct node)_; p-data=x; p-next=NULL; _ rear-next=p _; rear= _ p _; 期末綜合練習(xí)二 一、單項(xiàng)選擇題1（ B ）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A數(shù)據(jù)元素 B數(shù)據(jù)對象 C數(shù)據(jù)結(jié)構(gòu) D數(shù)據(jù)項(xiàng)2同一種邏輯結(jié)構(gòu)（ B ）。 A只能有唯一的存儲結(jié)構(gòu) B可以有不同的存儲結(jié)構(gòu) C只能表示某一種數(shù)據(jù)元素之間的關(guān)系 D以上三種說法均不正確3設(shè)鏈表中的結(jié)點(diǎn)是NODE類型的結(jié)構(gòu)體變

17、量，且有NODE *p；為了申請一個(gè)新結(jié)點(diǎn)，并由p指向該結(jié)點(diǎn)，可用以下語句（ A ）。Ap=(NODE *)malloc(sizeof(NODE);Bp=(*NODE)malloc(sizeof(NODE);Cp=(NODE )malloc(sizeof(p);Dp=(NODE *)malloc(sizeof(p);4鏈表所具備的特點(diǎn)是（ C ）。A可以隨機(jī)訪問任一結(jié)點(diǎn) B占用連續(xù)的存儲空間C插入刪除元素的操作不需要移動元素結(jié)點(diǎn) D可以通過下標(biāo)對鏈表進(jìn)行直接訪問5設(shè)順序存儲的線性長度為n，要在第i個(gè)元素之前插入一個(gè)新元素，按課本的算法當(dāng)i= （ D ）時(shí)，移動元素次數(shù)為2An/2 Bn C1

18、Dn-1 6數(shù)據(jù)的物理結(jié)構(gòu)（ D ）。 A與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) B僅僅包括數(shù)據(jù)元素的表示C只包括數(shù)據(jù)元素間關(guān)系的表示 D包括數(shù)據(jù)元素的表示和關(guān)系的表示7一個(gè)棧的進(jìn)棧序列是1，2，3，4，則棧的不可能的出棧序列是（ B ）（進(jìn)出棧操作可以交替進(jìn)行）A3，2，4，1 B1，4，2，3C4，3，2，1 D3，2，1，48線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ A ）的關(guān)系。 A一對一 B一對多 C多對多 D每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 9設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊(duì)列的頭指針和尾指針。設(shè)p指向要入隊(duì)的新結(jié)點(diǎn)(

19、該結(jié)點(diǎn)已被賦值)，則入隊(duì)操作為（ A ）。Arear-next=p;rear=p; Brear-next=p; p = rear; Cp = rear-next;rear=p; Drear=p;rear-next=p;10以下表中可以隨機(jī)訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表11以下說法不正確的是（ C ）。 A順序棧中，棧滿時(shí)再進(jìn)行進(jìn)棧操作稱為“上溢”B順序棧中，?？諘r(shí)再作出棧棧操作稱為“下溢”C順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲空間的上界，則一定是隊(duì)列已滿D順序隊(duì)列中，隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲空間的上界，則隊(duì)列已空12算法的時(shí)間復(fù)雜度與（ C ）

20、有關(guān)。 A所使用的計(jì)算機(jī) B與計(jì)算機(jī)的操作系統(tǒng) C與算法本身 D與數(shù)據(jù)結(jié)構(gòu)13設(shè)有一個(gè)20階的對稱矩陣A，采用壓縮存儲方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組中（矩陣A的第一個(gè)元素為a11，數(shù)組b的下標(biāo)從1開始），則矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是（ D ）。A30 B28 C40 D3314設(shè)有一個(gè)長度為n的順序表，要?jiǎng)h除第i個(gè)元素需移動元素的個(gè)數(shù)為（ B ）。 An-i+1 Bn-i Cn-i-1 Di15深度為5的完全二叉樹第5層上有4個(gè)結(jié)點(diǎn)，該樹一共有（ D ）個(gè)結(jié)點(diǎn)。A28 B30 C31 D1916在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)

21、點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用的語句是（ C ）。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL17已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，則m一定不可能是（ D ）。A4 B8 C12 D918從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ A ）。 Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;19以下說法正確的是（ D ）。 A連通圖G的生成樹中可以包含回路B連通圖G的生成

22、樹可以是不連通的C連通圖G的生成樹一定是唯一的D連通圖G的生成樹一定是連通而不包含回路的20在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;21 對n個(gè)元素進(jìn)行冒泡排序，通常要進(jìn)行n-1趟冒泡，在第j趟冒泡中共要進(jìn)行（ C ）次元素間的比較。 Aj Bj-1 Cn-j Dn-j-122一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能輸出序列是（ A ）（進(jìn)棧出棧可以交替進(jìn)行）。Adceab Bedcba Cdecba Dabcde 23在排序過程中，可以有效地減少一趟排序過

23、程中元素間的比較次數(shù)的算法是（ D ）。 A冒泡 B選擇 C直接插入 D折半插入 24有一個(gè)長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。A26/10 B29/10 C29/9 D31/1025如圖1若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為（ B ）。abecdf AaebcfdBabedcfCacebdfDacfbde 圖1 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇

24、排序27一棵哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)），該樹總共有（ B ）個(gè)結(jié)點(diǎn)。A2n-2 B2n-1 C2n D2n+228設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹鞔鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是（ A ）。A33 B32 C85 D4129數(shù)據(jù)的（ A ）結(jié)構(gòu)與所使用的計(jì)算機(jī)無關(guān)。 A邏輯 B物理 C存儲 D邏輯與存儲30在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（ D ）倍。 A3 B2.5 C1.5 D2 二、填空題1通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成_樹形_結(jié)構(gòu)。2棧和隊(duì)列的操作特點(diǎn)分別是_先

25、進(jìn)后出_和 _先進(jìn)先出_。3要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行_ s-next= p-next；_和p-next=s;的操作。4結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_圖狀 （網(wǎng)狀）_結(jié)構(gòu)。5設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行x=hs-data; _ hs=hs-next;_ _。6根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通?？煞譃榧?、線性、樹形 、 圖狀 四類基本結(jié)構(gòu)。7在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚

26、ext，若要進(jìn)行出隊(duì)操作，并用變量x存放出隊(duì)元素的數(shù)據(jù)值，則相關(guān)操作為x=f-data; _ f=f-next;_ _。8要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為_和 _ n-1,O(n)_ 。9循環(huán)隊(duì)列的最大存儲空間為MaxSize=8，采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，若隊(duì)頭指針front=4，則當(dāng)隊(duì)尾指針rear= _ 4 _時(shí)，隊(duì)列為空，當(dāng)rear= _ 2 _時(shí)，隊(duì)列有6個(gè)元素。10稀疏矩陣存儲時(shí)，采用一個(gè)由_行號_ 、_列號 _ 、_非零元_3部分信息組成的三元組唯一確定矩陣中的一個(gè)非零元素。11在二叉樹的鏈?zhǔn)?/p>

27、存儲結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是值域 左指針 、 右指針 。12一棵二叉樹順序編號為6的結(jié)點(diǎn)（樹中各結(jié)點(diǎn)的編號與等深度的完全二叉中對應(yīng)位置上結(jié)點(diǎn)的編號相同），若它存在右孩子，則右孩子的編號為_13_。13向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行s-next=h;和_ h=s _。14在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為_ r-next=s _和r=s; (結(jié)點(diǎn)的指針域?yàn)閚ext)15如圖2所示的二叉樹，其前序遍歷序列為_ abdefcg _。gfabdec 圖2 16設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有_12_個(gè)結(jié)

28、點(diǎn)。（根所在結(jié)點(diǎn)為第1層）17在隊(duì)列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針的值增1，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)， 頭 指針的值增1。18對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個(gè)非零元素對應(yīng)的三元組包括該元素的_行下標(biāo)_、_列下標(biāo)_和_非零元素值_三項(xiàng)信息。19循環(huán)隊(duì)列的引入，目的是為了克服 假上溢 。20在對一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較_3_次。三、綜合題1（1）設(shè)head1和p1分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭指針和尾指針，head2和p2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針

29、，若要把B鏈表接到A鏈表之后，得到一個(gè)以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個(gè)關(guān)鍵的賦值語句（不用完整程序，結(jié)點(diǎn)的鏈域?yàn)閚ext）。 答：p1-next= head2；p2-next= head1； （2）單向鏈表的鏈域?yàn)閚ext，設(shè)指針p指向單向鏈表中的某個(gè)結(jié)點(diǎn)，指針s指向一個(gè)要插入鏈表的新結(jié)點(diǎn)，現(xiàn)要把s所指結(jié)點(diǎn)插入p所指結(jié)點(diǎn)之后，某學(xué)生采用以下語句： p-next=s; s-next=p-next; 這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫答：不對，s-next= p-next；p-next=s；2 (1)以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(

30、要求每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。33 (1)1518799854322：11103: 11114：1107：008：019：10 (2) 一棵哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡述理由？答: 2n-1個(gè)，因?yàn)榉侨~結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。3（1）畫出對長度為10的有序表進(jìn)行折半查找的判定樹（以序號1，2，10表示樹結(jié)點(diǎn)） 52849631071（2）對上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均查找長度答：ASL=（1x1+2x2+3x4+4x3）/10=29/104一組記錄的關(guān)鍵字序列為（46，79，56，38，40，

31、84）（1）利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次交換元素的過程，要求以升序排列）初始序列 46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8440，38，46，56，79，84（2）對上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過程。37776247522711 97113727475262779756793840844684793840465665679384046793840848456465（1）利用篩選法，把序列37，77

32、，62，97，11，27，52，47建成堆（小根堆），畫出相應(yīng)的完全二叉樹初始樹 堆 （2）寫出對上述堆所對應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列答：11，37，47，97，77，27，62，526設(shè)查找表為(50,60,75,85,96,98,105,110,120,130) (1) 說出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較？ 3次(2) 為了折半查找元素95，經(jīng)過多少次元素間的比較才能確定不能查到？4次96759813010585501100512060（3）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))四、程序填空題1以下函數(shù)為直接選擇排序算法，對

33、a1,a2,an中的記錄進(jìn)行直接選擇排序，完成程序中的空格typedef struct int key;NODE; void selsort(NODE a,int n)int i,j,k;NODE temp;for(i=1;i= _ n-1_;i+) k=i; for(j=i+1;j= _ n _;j+) if(aj.keyak.key) _ k=j _; if(i!=k) temp=ai;_ ai=ak_;_ ak=temp _;2以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3,n，完成程序中空格部分。NODE *create(n)NODE *

34、head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);head= p ; q=p ;pnext=NULL; /*建立頭結(jié)點(diǎn)*/for(i=1; ileft) ; printf(“%c”,BT-data) ; Inorder(BT-right) ; 期末綜合練習(xí)三一、單項(xiàng)選擇題1深度為5的完全二叉樹共有20個(gè)結(jié)點(diǎn)，則第5層上有（ C ）個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A3 B8 C5 D62在C語言中，順序存儲長度為3的字符串，需要占用（ A ）個(gè)字節(jié)。 A4 B3 C6 D123已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（ A ）。A2m

35、Bm C2m+1 Dm/24串函數(shù)StrCat（a,b）的功能是進(jìn)行串（ D ）。 A比較 B復(fù)制 C賦值 D連接5數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ D ）結(jié)構(gòu)。 A物理 B存儲 C邏輯與物理 D邏輯6一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有?A ）個(gè)指針域?yàn)榭铡?An+1 Bn Cn-1 Dn-27鏈表所具備的特點(diǎn)是（ C ）。A可以隨機(jī)訪問任一結(jié)點(diǎn) B占用連續(xù)的存儲空間C插入刪除不需要移動元素結(jié)點(diǎn) D可以通過下標(biāo)對鏈表進(jìn)行直接訪問8設(shè)一棵哈夫曼樹共有n個(gè)非葉結(jié)點(diǎn)，則該樹有（ B ）個(gè)葉結(jié)點(diǎn)。 An Bn+1 Cn-1 D2n9線性表只要以（ C ）方式存儲就能進(jìn)行折半查找。

36、A鏈接 B順序 C關(guān)鍵字有序的順序 D二叉樹10從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ A ）。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;11散列查找的原理是（ A ）。A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲C按關(guān)鍵字值的比較進(jìn)行查找D基于二分查找的方法12一棵完全二叉樹共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹共有（ C ）個(gè)結(jié)點(diǎn)。 A30 B20 C21 D2

37、313對n個(gè)元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（ C ）次元素間的交換，則表明序列已經(jīng)排好序。 A1 B2 C0 Dn-114在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（ D ）倍。 A3 B2.5 C1.5 D215排序過程中，每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹?，該排序算法? A )。 A直接插入排序 B快速排序C冒泡排序 D選擇排序 16已知如圖1所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ A ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7

38、CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5 圖117在對一組元素（64，48，106，33，25，82，70，55，93）進(jìn)行直接插入排序時(shí)，當(dāng)進(jìn)行到要把第7個(gè)元素70插入到已經(jīng)排好序的子表時(shí)，為找到插入位置，需進(jìn)行（ C ）次元素間的比較（指由小到大排序）。A6 B2 C3 D418已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ B ）。 Aabcedf Babcefd Caebcfd Dacfdebbdfeca 圖219采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方

39、法），最壞的情況下要進(jìn)行（ B ）次元素間的比較。 An+2 Bn Cn-1 Dn/220對二叉排序樹進(jìn)行（ C ）遍歷，可以使遍歷所得到的序列是有序序列。 A按層次 B后序 C中序 D前序21如圖3，若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為（ B ）。 Aacebdgf BabecdgfCacfedgbDabecfdg abecdfg 圖322在有序表2，4，7，14，34，43，47，64，75，80，90，97，120中，用折半查找法查找值80時(shí)，經(jīng)（ B ）次比較后查找成功。A4 B2 C3 D523元素2，4，6，8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ D

40、 ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A8，6，4，2 B2，4，6，8 C4，2，8，6 D8，6，2，424有一個(gè)長度為9的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。A25/10 B25/9 C20/9 D17/925排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ C ）排序。 A歸并 B插入 C選擇 D快速 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇排序

41、27一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn)，該樹共有（ D ）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）A10 B13 C11 D1228一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ B ）。 A40，38，46，79，56，84 B40，38，46，56，79，84C40，38，46，84，56，79 D38，40，46，56，79，8429隊(duì)列的插入操作在（ B ）進(jìn)行。 A隊(duì)頭 B隊(duì)尾 C隊(duì)頭或隊(duì)尾 D在任意指定位置 二、填空題（每小題2分，共24分）1一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹總共有_11_個(gè)結(jié)點(diǎn)。2在二叉樹的鏈?zhǔn)酱鎯?/p>

42、結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是_值域_、 左指針 、右指針。3設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10，該完全二叉樹一共有_21_個(gè)結(jié)點(diǎn)。4一棵二叉樹中順序編號為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號分別為_2i _、_2i+1_。5按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_先序_ 、_中序 _、 _后序_三種。6串的兩種最基本的存儲方式是_順序存儲_和 _鏈?zhǔn)酱鎯。7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_樹形_結(jié)構(gòu)。8一棵有2n-1個(gè)結(jié)點(diǎn)的二叉樹，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹共有_N_個(gè)葉結(jié)點(diǎn)。9把數(shù)據(jù)存儲到

43、計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_物理（存儲）_結(jié)構(gòu)。10對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有_ n+1_個(gè)指針域?yàn)榭铡?1結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_線性_結(jié)構(gòu)。12_中序_遍歷二叉排序樹可得到一個(gè)有序序列。13如圖4所示的二叉樹，其后序遍歷序列為 gdbeihfca 。efgibachd 圖4 14n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行_ n-1_趟冒泡。15如圖5所示的二叉樹，其先序遍歷序列為_ abdefcg _。gfabdec 圖5 16二叉樹為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是_不正確_的。(回答正確或不正確) 17圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_正確_的。(回答正確或不正確) 18根據(jù)搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷_、 _廣度優(yōu)先搜索遍歷_ 兩種方法19對記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按_主關(guān)鍵字_排序結(jié)果是唯一的。20按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字 相等 的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。16423252576782102三、綜合題1（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出該堆