電大數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)小抄參考

1、專業(yè)好文檔數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)期末綜合練習(xí)一一、單項(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邏輯上相鄰的元素在物理位置上不一定

2、相鄰b數(shù)據(jù)元素是不能隨機(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è)順序存儲(chǔ)的線性表長度為n，對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個(gè)元素平均移動(dòng)元素的次數(shù)為（ a ）。a(n+1)/2 bn c2n dn-i8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ a ）的關(guān)系。 a一對一

3、b一對多 c多對多 d每一個(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è)順序存儲(chǔ)的線性表長度為n，要?jiǎng)h除第i個(gè)元素，按課本的算法，當(dāng)i=（ c ）時(shí)，移動(dòng)元素的次數(shù)為3a3 bn/2 cn-3 d411以下說法正確的是（ c ）。a隊(duì)列是后進(jìn)先出 b棧的特點(diǎn)是

4、后進(jìn)后出c棧的刪除和插入操作都只能在棧頂進(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，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（矩陣a的第一個(gè)元素為a1,1，

5、數(shù)組b的下標(biāo)從1開始），則矩陣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; df

6、ront-next =p;18以下說法不正確的是（ d ）。 a連通圖g一定存在生成樹b連通圖g的生成樹中一定包含g的所有頂點(diǎn)c連通圖g的生成樹中不一定包含g的所有邊d連通圖g的生成樹可以是不連通的19散列查找的原理是（ a ）。a在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對應(yīng)關(guān)系b按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)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

7、冒泡排序 d直接插入排序 22采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（ b ）次元素間的比較。 an+2 bn cn-1 dn/223設(shè)有一個(gè)10階的對稱矩陣a，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(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 圖

8、125已知如圖2所示的一個(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通常可以把某城市中各公交站點(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è)

9、單向循環(huán)鏈表，頭指針為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ì)

10、頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，則插入一個(gè)s所指結(jié)點(diǎn)的操作為_ r-next=s _；r=s；10“a”在存儲(chǔ)時(shí)占_2_個(gè)字節(jié)。11串的兩種最基本的存儲(chǔ)方式分別是_順序存儲(chǔ)_和 _鏈?zhǔn)酱鎯?chǔ) _。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ù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_物理（存儲(chǔ)

11、）_結(jié)構(gòu)。17一棵二叉樹葉結(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

12、，中序遍歷序列是dbeac，試畫出該二叉樹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 6

13、5 95 （2）對序列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)造一棵二叉排序樹.24616731

14、85145（2）說明如何通過序列的二叉排序樹得到相應(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

15、 binary_search(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

16、 *front，*rear; 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只能有唯一的存儲(chǔ)結(jié)構(gòu) b可以有不同的存儲(chǔ)結(jié)構(gòu) c只能表示某一種數(shù)據(jù)元素之間的關(guān)系 d以上三種說法均不正確3設(shè)鏈表中的結(jié)點(diǎn)是

17、node類型的結(jié)構(gòu)體變量，且有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ù)的存儲(chǔ)空間c插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn) d可以通過下標(biāo)對鏈表進(jìn)行直接訪問5設(shè)順序存儲(chǔ)的線性長度為n，要在第i個(gè)元素之前插入一個(gè)新元素，按課本的算法當(dāng)i= （ d ）時(shí)，移動(dòng)元素次數(shù)為2

18、an/2 bn c1 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è)

19、p指向要入隊(duì)的新結(jié)點(diǎn)(該結(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順序棧中，棧空時(shí)再作出棧棧操作稱為“下溢”c順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲(chǔ)空間的上界，則一定是隊(duì)列已滿d順序隊(duì)列中，隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲(chǔ)空間的上界，則隊(duì)列已空12算法的

20、時(shí)間復(fù)雜度與（ c ）有關(guān)。 a所使用的計(jì)算機(jī) b與計(jì)算機(jī)的操作系統(tǒng) c與算法本身 d與數(shù)據(jù)結(jié)構(gòu)13設(shè)有一個(gè)20階的對稱矩陣a，采用壓縮存儲(chǔ)方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(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è)元素需移動(dòng)元素的個(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)，

21、且q所指結(jié)點(diǎn)是p所指結(jié)點(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的生成樹中可以包

22、含回路b連通圖g的生成樹可以是不連通的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)棧出?？梢越惶孢M(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直接插

24、入 c折半插入 d選擇排序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，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(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存儲(chǔ) d邏輯與存儲(chǔ)30在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（ d ）倍。 a3 b2.5 c1.5 d2 二、填空題1通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成_樹形_結(jié)構(gòu)。2棧和隊(duì)

25、列的操作特點(diǎn)分別是_先進(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ù)域

26、為data，指針域?yàn)閚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ì)列的最大存儲(chǔ)空間為maxsize=8，采用少用一個(gè)元素空間以有效的判斷?？栈驐M，若隊(duì)頭指針front=4，則當(dāng)隊(duì)尾指針rear= _ 4 _時(shí)，隊(duì)列為空，當(dāng)rear= _ 2 _時(shí)，隊(duì)列有6個(gè)元素。10稀疏矩陣存儲(chǔ)時(shí)，采用一個(gè)由_行號_ 、_列號 _ 、_非零元_3部分信息組成的三元組唯一確定矩陣中的一個(gè)非零元

27、素。11在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(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)

28、，該樹共有_12_個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）17在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針的值增1，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)， 頭 指針的值增1。18對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(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)的單向

29、鏈表b的頭指針和尾指針，若要把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)

30、，構(gòu)造一棵哈夫曼樹( 要求每個(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，7

31、9，56，38，40，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）利用篩

32、選法，把序列37，77，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 *crea

34、te(n)node *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語言中，順序存儲(chǔ)長度為3的字符串，需要占用（ a ）個(gè)字節(jié)。 a4 b3 c6 d123已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和

35、為（ a ）。a2m 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存儲(chǔ) c邏輯與物理 d邏輯6一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有（ a ）個(gè)指針域?yàn)榭铡?an+1 bn cn-1 dn-27鏈表所具備的特點(diǎn)是（ c ）。a可以隨機(jī)訪問任一結(jié)點(diǎn) b占用連續(xù)的存儲(chǔ)空間c插入刪除不需要移動(dòng)元素結(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 ）方式

36、存儲(chǔ)就能進(jìn)行折半查找。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)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對應(yīng)關(guān)系b按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)c按關(guān)鍵字值的比較進(jìn)行查找d基于二分查找的方法12一棵完全二叉樹共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹共有（ c ）個(gè)結(jié)點(diǎn)。 a30

37、 b20 c21 d2313對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 bv1v2v

38、4v5v8v3v6v7cv1v2v4v8v3v5v6v7 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)行查找（

39、不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(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 ）（進(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排序方法中，從未排序序列中挑選元素，并將其依次放