電大數(shù)據(jù)結(jié)構(gòu)本小抄

1、中央電大開放本科計算機科學與技術(shù)數(shù)據(jù)結(jié)構(gòu)（本一、單項選擇題1數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ C ）。A只能有一個數(shù)據(jù)項組成 B至少有二個數(shù)據(jù)項組成C可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成 D至少有一個數(shù)據(jù)項為指針類型2 一種邏輯結(jié)構(gòu)（ A ）存儲結(jié)構(gòu)。A可以有不同的 B只能有唯一的C的數(shù)據(jù)元素在計算機中的表示稱為 D的數(shù)據(jù)元素之間的關(guān)系稱為3線性表的順序結(jié)構(gòu)中，（ C ）。A邏輯上相鄰的元素在物理位置上不一定相鄰 B數(shù)據(jù)元素是不能隨機訪問的C邏輯上相鄰的元素在物理位置上也相鄰 D進行數(shù)據(jù)元素的插入、刪除效率較高4以下說法中不正確的是（ B ）。A雙向循環(huán)鏈表中每個結(jié)點需要包含兩個指針域B已知

2、單向鏈表中任一結(jié)點的指針就能訪問到鏈表中每個結(jié)點C順序存儲的線性鏈表是可以隨機訪問的 D單向循環(huán)鏈表中尾結(jié)點的指針域中存放的是頭指針5以下表中可以隨機訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表6雙向循環(huán)鏈表結(jié)點的數(shù)據(jù)類型為：struct node int data;struct node *next; /*指向直接后繼*/struct node *prior;；設(shè)p指向表中某一結(jié)點，要顯示p所指結(jié)點的直接前驅(qū)結(jié)點的數(shù)據(jù)元素，可用操作（ B ）。Aprintf(“%d”,p->next->data); Bprintf(“%d”,p->prior-&g

3、t;data);Cprintf(“%d”,p->prior->next); Dprintf(“%d”,p->data);7 .設(shè)順序存儲的線性表長度為n，對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（ A ）。A(n+1)/2Bn C2nDn-i8一個棧的進棧序列是efgh，則棧的不可能的出棧序列是（ D ）（進出棧操作可以交替進行）。Ahgfe Bgfeh Cfgeh Dehfg9設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則出棧操作為（ A ）。Ax=top->data;top=t

4、op->next; Btop=top->next;x=top->data;Cx=top-> next;top=top-> data; Dtop->next =top; x=top->data; 10設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則取棧頂元素的操作為（ C ）。Atop->data= x; Btop=top->next;Cx=top->data; Dx=top->data; top= top->next;11以下說法正確的是（ C ）。A隊列是后進先出

5、 B棧的特點是后進后出C棧的刪除和插入操作都只能在棧頂進行 D隊列的刪除和插入操作都只能在隊頭進行13串函數(shù)StrCmp(“abA”,”aba”)的值為（ D ）。A1 B0 C“abAaba”D-114char *p; p=StrCat(“ABD”,”ABC”);Printf(“%s”,p); 的顯示結(jié)果為（ B ）。A-1 BABDABC CAB D115設(shè)有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為a1,1，數(shù)組b的下標從1開始），則矩陣A中第4行的元素在數(shù)組b中的下標i一定有（ A ）。A、7i10 B、11i15 C、9

6、i14 D、6i916深度為5的滿二叉樹至多有（ B ）個結(jié)點（根結(jié)點為第一層）A40 B31 C34 D3517已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ A ）。A2m Bm C2m+1 Dm/218已知一個圖的所有頂點的度數(shù)之和為m，則該圖的邊數(shù)為（ D ）。A2m Bm C2m+1 Dm/219以下說法不正確的是（ D ）。A連通圖G一定存在生成樹 B連通圖G的生成樹中一定包含G的所有頂點C連通圖G的生成樹中不一定包含G的所有邊 D連通圖G的生成樹可以是不連通的20以下說法不正確的是（ A ）。 A連通圖G的生成樹一定是唯一的 B連通圖G一定存在生成樹C連通圖G的生成樹中一定

7、要包含G的所有頂點D連通圖G的生成樹一定是連通而且不包含回路21散列查找的原理是（ A ）。A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲C按關(guān)鍵字值的比較進行查找 D基于二分查找的方法22有序表為1，2，4，6，10，18，20，32，用課本中折半查找算法查找值18，經(jīng)（ B ）次比較后成功查到。A3 B2 C4 D523排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當位置，直到全部排好序為止，該排序算法是( A )。A直接插入排序 B快速排序 C冒泡排序 D選擇排序24在排序過程中，可以通過

8、某一趟排序的相關(guān)操作所提供的信息，判斷序列是否已經(jīng)排好序，從而可以提前結(jié)束排序過程的排序算法是( A )。A冒泡 B選擇 C直接插入 D折半插入25采用順序查找法對長度為n的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進行（ B ）次元素間的比較。An+2 Bn Cn-1 Dn/226用折半查找法，對長度為12的有序的線性表進行查找，最壞情況下要進行（ A ）次元素間的比較A4 B3 C5 D627如圖若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ D ）。abecdhgf AacebdfghBaebcghdfCaedfbcghDabecdfgh 圖1 28如圖

9、若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ B ）。bcgdafe AacfgedbBaedbgfcCacfebdgDaecbdgf29一棵哈夫曼樹總共有23個結(jié)點，該樹共有（ D ）個葉結(jié)點（終端結(jié)點）A10 B13 C11 D1230一棵哈夫曼樹總共有25個結(jié)點，該樹共有（ A ）個非葉結(jié)點（非終端結(jié)點）。A12 B13 C14 D1531針對線性表，在存儲后如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用（ D ）存儲方式最節(jié)省時間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D順序表32線性表采用鏈式存儲時，其地址（ C ）。A一定是不連續(xù)的 B必須是連續(xù)的C可以連續(xù)也可以不

10、連續(xù) D部分地址必須是連續(xù)的33數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（ D ）結(jié)構(gòu)。 A物理 B存儲 C邏輯與物理 D邏輯34帶頭結(jié)點的單向鏈表的頭指針為head，該鏈表為空的判定條件是（ C ）的值為真。Ahead= = NULL Bhead->next= =headChead->next= = NULL Dhead = =head->next35以下特征中，（ D ）不是算法的特性。 A有窮性 B確定性 C可行性 D有0個或多個輸出 36設(shè)順序存儲的線性表長度為n，對于插入操作，設(shè)插入位置是等概率的，則插入一個元素平均移動元素的次數(shù)為（ A ）。An/2Bn Cn-

11、1Dn-i+137設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），則移動元素個數(shù)為（ A ）。 An-i+1 Bn-i Cn-i-1 Di38一個棧的進棧序列是5，6，7，8，則棧的不可能的出棧序列是（A ）（進出棧操作可以交替進行）A5，8，6，7 B7，6，8，5 C7，6，5，8 D8，7，6，539棧的插入刪除操作在（ D ）進行。 A棧底 B任意位置 C指定位置 D棧頂40棧和隊列的相同點是（ D ）。A都是后進先出 B都是后進后出C邏輯結(jié)構(gòu)與線性表不同 D邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表41以下說法正確的是（ C ）。 A棧的特

12、點是先進先出，隊列的特點是先進后出 B棧和隊列的特點都是先進后出C棧的特點是先進后出，隊列的特點是先進先出 D棧和隊列的特點都是先進先出42在C語言中，利用數(shù)組a存放字符串“Hello”，以下語句中正確的是（ A ）。Achar a10= “Hello”; Bchar a10; a=“Hello”;Cchar a10= Hello; Dchar a10=H,e,l,l,o;43元素2，4，6，8按順序依次進棧，則該棧的不可能輸出序列是（ D ）（進棧出?？梢越惶孢M行）。 A8，6，4，2 B2，4，6，8 C4，2，8，6 D8，6，2，444設(shè)有一個15階的對稱矩陣A，采用壓縮存儲方式將其下

13、三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為a1,1，數(shù)組b的下標從1開始），則數(shù)組元素b13對應(yīng)A的矩陣元素是（ A ）。Aa5,3Ba6,4Ca7,2Da6,845設(shè)有一個15階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素a7,6在一維數(shù)組B中的下標是（ C ）。A42 B13 C27 D3246一棵完全二叉樹共有30個結(jié)點，則該樹一共有（ D ）層(根結(jié)點所在層為第一層)。A6 B4 C3 D547串函數(shù)StrCmp（“d”，“D”）的值為（ B ）。 A0 B1 C-1 D348以下說法正確的是（ D

14、 ）。A連通圖G的生成樹中不一定包含G的所有頂點 B連通圖G的生成樹中一定要包含G的所有邊C連通圖G的生成樹一定是唯一的 D連通圖G一定存在生成樹49在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為（ D ）。 A2i B2i-1 C2i+2 D2i+150對二叉排序樹進行（ C ）遍歷，遍歷所得到的序列是有序序列。A按層次 B前序 C中序 D后序51設(shè)一棵有n個結(jié)點采用鏈式存儲的二叉樹，則該樹共有（ D ）個指針域為空。 A2n B2n+1 C2n+2 Dn+152以下排序算法中，在一趟排序過程中，除了其它相關(guān)操作外，只進行一次元素間的交換的算法是（ A ）。A直接選擇 B冒

15、泡 C直接插入 D折半插入bdfeca53已知如圖1所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ B ）。 Aabcedf Babcefd Caebcfd Dacfdeb 圖154對長度為n的線性表進行順序查找，在等概率情況下，平均查找長度為（ B ）。An B（n+1）/2 C2n Dn-155在有序表1，3，8，13，33，42，46，63，76，78，86，97，100中，用折半查找值86時，經(jīng)（ D ）次比較后查找成功。A6 B3 C8 D456如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ A ）。abecdfg Aacf

16、gedbBaedcbgfCacfebdgDaecbdgf57有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ A ）。A29/10 B31/10 C26/10 D29/958一棵哈夫曼樹有12個葉子結(jié)點（終端結(jié)點），該樹總共有（ C ）個結(jié)點。A22 B21 C23 D2459一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ A ）。 A31，29，37，47，70，85 B29，31，37，47，70，85C31，29，37，70，47，85 D31，29，37，85，47

17、，7060隊列的刪除操作在（ A ）進行。A隊頭 B隊尾 C隊頭或隊尾 D在任意指定位置61（ A ）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A數(shù)據(jù)對象 B數(shù)據(jù)元素 C數(shù)據(jù)結(jié)構(gòu) D數(shù)據(jù)項62設(shè)鏈表中的結(jié)點是NODE類型的結(jié)構(gòu)體變量，且有NODE *p；為了申請一個新結(jié)點，并由p指向該結(jié)點，可用以下語句（ D ）。Ap=(NODE *)malloc(sizeof(p); Bp=(*NODE)malloc(sizeof(NODE);Cp=(NODE )malloc(sizeof(p); Dp=(NODE *)malloc(sizeof(NODE);63設(shè)順序存儲的線性長度為n，要在第i個元素之前

18、插入一個新元素，按課本的算法當i=( C ）時，移動元素次數(shù)為2An/2 Bn Cn-1 C164一個棧的進棧序列是1，2，3，4，則棧的不可能的出棧序列是（D）（進出棧操作可以交替進行）A3，2，4，1 B3，2，1，4 C4，3，2，1 D1，4，2，365設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被賦值)，則入隊操作為（ A ）。Arear->next=p;rear=p; Brear->next=p; p = rear; Cp = rear->nex

19、t;rear=p; Drear=p;rear->next=p;66以下說法不正確的是（ D ）。 A順序棧中，棧滿時再進行進棧操作稱為“上溢”B順序棧中，?？諘r再作出棧棧操作稱為“下溢”C順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空D順序隊列中，當尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿67設(shè)有一個20階的對稱矩陣A，采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a11，數(shù)組b的下標從1開始），則矩陣元素a8,5在一維數(shù)組b中的下標是（ D ）。A30 B28 C40 D3368已知一個圖的所有頂點的度數(shù)之和為m，則m

20、一定不可能是（ D ）。A4 B8 C12 D969以下說法正確的是（ C ）。 A連通圖G的生成樹中可以包含回路 B連通圖G的生成樹可以是不連通的C連通圖G的生成樹一定是連通而不包含回路的D連通圖G的生成樹一定是唯一的70對n個元素進行冒泡排序，通常要進行n-1趟冒泡，在第j趟冒泡中共要進行（ C ）次元素間的比較。Aj Bj-1 Cn-j Dn-j-171在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是（C ）。A冒泡 B選擇 C折半插入 D直接插入 72一棵哈夫曼樹有n個葉子結(jié)點（終端結(jié)點），該樹總共有（ B ）個結(jié)點。A2n-2 B2n-1 C2n D2n+273數(shù)據(jù)

21、的（ A ）結(jié)構(gòu)與所使用的計算機無關(guān)。A邏輯 B物理 C存儲 D邏輯與存儲74從n個數(shù)中選取最大元素（ B ）。A基本操作是數(shù)據(jù)元素間的交換 B算法的時間復雜度是O(n) C算法的時間復雜度是O(n2) D需要進行(n+1)次數(shù)據(jù)元素間的比較75設(shè)head為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點，則滿足邏輯表達式（ B ）的值為真。Ap->next=NULL Bp->next= =head Cp->next=head Dp= =NULL76設(shè)順序存儲的線性表長度為n，要刪除第i個元素，按課本的算法，當i=（ C ）時，移動元素的次數(shù)為3。A3 Bn/2 Cn-3 D37

22、7一個棧的進棧序列是a，b，c，d，則棧的不可能的出棧序列是（ D ）。Adcba Bbcad Ccbad Dadbc 78設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作：p=front->next;x=p->data; 然后指行（ D ）。Afront=p->next; Bfront->next =p; Cfront=p; Dfront->next=p->next;79在C語言中，存儲字符串“AB

23、CD”需要占用（ C ）字節(jié)。A4 B2 C5 D380設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為a1,1，數(shù)組b的下標從1開始），則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù)組元素是（ C ）。Ab18 Bb8 Cb13 Db1081設(shè)有一個15階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為a1,1，數(shù)組b的下標從1開始），則數(shù)組元素b13對應(yīng)A的矩陣元素是（ A ）。Aa5,3Ba6,4Ca7,2Da6,882深度為5的完全二叉樹共有20個結(jié)點，則第5層上有（ C ）個結(jié)點(

24、根所在結(jié)點為第一層)。A3 B8 C5 D683已知一個圖的所有頂點的度數(shù)之和為m，且m是以下4中情況之一，則m只可能是（ D ）。A9 B7 C15 D884以下說法正確的是（ C ）。A連通圖G的生成樹中不一定包含G的所有頂點 B連通圖G的生成樹中一定要包含G的所有邊C連通圖G一定存在生成樹 D連通圖G的生成樹一定是唯一的85線性表只要以（ C ）方式存儲就能進行折半查找。A鏈接 B順序 C關(guān)鍵字有序的順序 D二叉樹86對二叉排序樹進行（ C ）遍歷，遍歷所得到的序列是有序序列。A按層次 B前序 C中序 D后序87對n個元素進行冒泡排序若某趟冒泡中只進行了（C ）次元素間的交換，則表明序列

25、已經(jīng)排好序。A1 B2 C0 Dn-188在對一組元素（64，48，106，33，25，82，70，55，93）進行直接插入排序時，當進行到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插入位置，需進行（ C ）次元素間的比較（指由小到大排序）。A6 B2 C3 D4abecdfg89如圖，若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ C ）。Aacebdgf BacfedgbCabecdgfDabecfdg 90一棵哈夫曼樹有10個非葉子結(jié)點（非終端結(jié)點），該樹總共有（ A ）個結(jié)點。A21 B20 C22 D1991一棵哈夫曼樹有12個葉子結(jié)點（終端結(jié)點），該樹總共

26、有（ C ）個結(jié)點。A21 B22 C23 D2492隊列的插入操作在（ B ）進行。A隊頭 B隊尾 C隊頭或隊尾 D在任意指定位置93隊列的刪除操作在（ B ）進行。 A隊尾 B隊頭 C隊頭或隊尾 D在任意指定位置94鏈表所具備的特點是（ C ）。A.可以隨機訪問任一結(jié)點 B.占用連續(xù)的存儲空間C.插人刪除元素的操作不需要移動元素結(jié)點 D.可以通過下標對鏈表進行直接訪問95線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在( C)的關(guān)系。A. 一對一 B. 一對多C. 多對多 D. 每一個元素都有一個直接前驅(qū)和一個直接后繼96算法的時間復雜度與(C )有關(guān)。A. 所使用的計算機 B.與計算機的操作系統(tǒng)C. 與

27、算法本身 D.與數(shù)據(jù)結(jié)構(gòu)974.在一個單鏈表中，p,q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用的語句是( )。A. p =q-> riext B.p->next=qC. p->next=q->next D.q->next=NULL98在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為( C )A. r=f->next;B. r=r->next;C. f=f->next;D. f=r->next;99.元素3,6,9按順序依次進棧，則該棧的不可能輸出序列是( B )(進棧出?？?/p>

28、以交替進行)A. 9，6，3B. 9，3，6C. 6，3，9D. 3，9，6100設(shè)有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組B中(數(shù)組下標從1開始)，則矩陣中元素戊.s在一維數(shù)組B中的下標是()A.33 B.32C. 85 D. 41101排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法，稱為( D )排序。A. 歸并 B.插人 C. 快速 D.選擇102排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空)中的元素進行比較(要求比較次數(shù)盡量少)，然后將其放入已排序序列的正確位置的方法是( C )。A.

29、冒泡 B. 直接插入 C. 折半插入 D. 選擇排序二、填空題1通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括 集合 、_線性_、_樹形_、 圖狀_四種類型。2通常可以把一本含有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成_樹形_結(jié)構(gòu)。3設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句_ p->next=head;_。4要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點，若鏈表中結(jié)點的指針域為next，可執(zhí)行_ s->next= p->next；_和p->next=s;的操作。5設(shè)有一個單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點的指

30、針域為next，p指向尾結(jié)點的直接前驅(qū)結(jié)點，若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作_ p->next=head； 。 6設(shè)有一個非空的鏈棧，棧頂指針為hs，要進行出棧操作，用x保存出棧結(jié)點的值，棧結(jié)點的指針域為next，則可執(zhí)行x=hs->data; _ hs=hs->next; _。7在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入一個s所指結(jié)點的操作為_ r->next=s _；r=s；8在一個不帶頭結(jié)點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為data，指針域為next，若要進行出隊操作，并用變量x存放出隊元

31、素的數(shù)據(jù)值，則相關(guān)操作為x=f->data;f=f->next; 。9循環(huán)隊列的隊頭指針為f，隊尾指針為r，當_ r= =f _時表明隊列為空。 10循環(huán)隊列的最大存儲空間為MaxSize=8，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=4，則當隊尾指針rear= _4 _時，隊列為空，當rear= _2 _時，隊列有6個元素。11稀疏矩陣存儲時，采用一個由_行號_ 、_列號_、_非零元_3部分信息組成的三元組唯一確定矩陣中的一個非零元素。12一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有_11_個結(jié)點。13一棵二叉樹順序編號為6的結(jié)點（樹中各結(jié)點的編號

32、與等深度的完全二叉樹中對應(yīng)位置上結(jié)點的編號相同），若它存在右孩子，則右孩子的編號為_13_。14按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_先序 _、_中序 _、_后序_三種。15結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_圖狀_結(jié)構(gòu)。16把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_物理（存儲）_結(jié)構(gòu)。17結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_樹形_結(jié)構(gòu)。efgibachd18如圖3所示的二叉樹，其后序遍歷序列為gdbeihfca。 圖3gfabdec19如圖4所示的二叉樹，其前序遍歷序列為_ abdefcg_。 圖420二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的

33、值、小于其右孩子的值。這種說法是_錯誤_的。(回答正確或不正確) 21在隊列的順序存儲結(jié)構(gòu)中，當插入一個新的隊列元素時， 尾 指針的值增1，當刪除一個元素隊列時， 頭 指針的值增1。22根據(jù)搜索方法的不同，圖的遍歷有_深度優(yōu)先 、 _ 廣度優(yōu)先 _兩種方法。23循環(huán)隊列的引入，目的是為了克服 假上溢 。24通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成_圖狀_結(jié)構(gòu)。25結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為_圖狀_結(jié)構(gòu)。26要在一個單向鏈表中刪除p所指向的結(jié)點，已知q指向p所指結(jié)點的直接前驅(qū)結(jié)點，若鏈表中結(jié)點的指針域為next，則可執(zhí)行_ q->next= p->next； _。27設(shè)

34、有一個單向循環(huán)鏈表，結(jié)點的指針域為next，頭指針為head，指針p指向表中某結(jié)點，若邏輯表達式_ p->next= =head;_的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。28設(shè)有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作_ s->next=hs; 和hs=s；29順序存儲字符串“ABCD”需要占用_5_個字節(jié)。30循環(huán)隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效地判斷?？栈驐M，若隊頭指針front=4，當隊尾指針rear= _3_時隊滿，隊列中共有_5_個元素。31一棵二叉樹葉結(jié)點（終端結(jié)點）數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有_11_個

35、結(jié)點32設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉節(jié)點的雙親結(jié)點的編號為10，該完全二叉樹一共有_21_個結(jié)點。33一棵二叉樹中順序編號為5的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中對應(yīng)位置上結(jié)點的編號相同），若它存在左孩子，則左孩子的編號為_10 _。34結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_線性_結(jié)構(gòu)。35一棵有n個葉結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2，則該樹共有_2n-1_個結(jié)點。36圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_正確_的。(回答正確或不正確) 37串的兩種最基本的存儲方式分別是_順序存儲_和 _鏈式存儲_ _。38按某關(guān)鍵字對記

36、錄序列排序，若關(guān)鍵字關(guān)鍵字相等的記錄的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。39設(shè)有一個不帶頭結(jié)點的單向循環(huán)鏈表，結(jié)點的指針域為next，指針p指向尾結(jié)點，現(xiàn)要使p指向第一個結(jié)點，可用語句_ p=p->next; _。40要在一個帶頭結(jié)點的單向循環(huán)鏈表中刪除頭結(jié)點，得到一個新的不帶頭結(jié)點的單向循環(huán)鏈表，若結(jié)點的指針域為next，頭指針為head，尾指針為p，則可執(zhí)行head=head-> next; _ p->next=head；_。41在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向_結(jié)點的直接后繼，另一個指向_結(jié)點的直接前驅(qū) 。42設(shè)有

37、一個頭指針為head的單向鏈表，p指向表中某一個結(jié)點，且有p->next= =NULL,通過操作_ p->next=head;_，就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。43循環(huán)隊列的最大存儲空間為MaxSize，隊頭指針為f，隊尾指針為r，當_（r+1）%MaxSize=f _時表明隊列已滿。44從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，可執(zhí)行x=h->data;和_h=h->next; 。(結(jié)點的指針域為next)45程序段 int count=0; char *s=” ABCD”;while(*s!=0)s+;count+; 執(zhí)行后count=

38、_ 4 _。46兩個串相等的充分必要條件是_串長度相等且對應(yīng)位置的字符相等。47一棵二叉樹總結(jié)點數(shù)為11，葉結(jié)點數(shù)為5，該樹有_4_個雙分支結(jié)點，_2_個單分支結(jié)點。48對二叉樹的遍歷可分為_先序、中序、后序、層次四種不同的遍歷次序。49設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為偶數(shù)，該葉節(jié)點的雙親結(jié)點的編號為9，該完全二叉樹一共有_18_個結(jié)點。50雙向循環(huán)鏈表中，p指向表中某結(jié)點，則通過p可以訪問到p所指結(jié)點的直接后繼結(jié)點和直接前驅(qū)結(jié)點，這種說法是_正確_的（回答正確或不正確）。51棧和隊列的操作特點分別是_先進后出（后進先出）_和_先進先出 （后進后出）_。52一棵有14個結(jié)點的

39、完全二叉樹，則它的最高層上有_7_個結(jié)點。efgibachd53如圖2所示的二叉樹，其先序遍歷序列為_ abdgcefhi。 圖254折半查找只適用于 順序存儲結(jié)構(gòu) 存儲的有序表 。55哈希函數(shù)是記錄關(guān)鍵字值與該記錄_存儲地址_之間所構(gòu)造的對應(yīng)關(guān)系。56深度為k的二叉樹最多有 2k-1 結(jié)點。57二叉樹排序中任一棵子樹都是二叉排序樹，這種說法是_正確_的。(回答正確或不正確)58串的兩種最基本的存儲方式是_順序存儲 _和 鏈式存儲_59結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為_圖狀_結(jié)構(gòu)。60設(shè)有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作s-> next=hs; _

40、 hs=s；。61循環(huán)隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效地判斷棧空或棧滿，若隊頭指針front=4，當隊尾指針rear= _3_時隊滿，隊列中共有_5_個元素。62A在存儲時占_1_個字節(jié)?！癆”在存儲時占_2_個字節(jié)。63程序段 char *s=”aBcD”;n=0;while(*s!=0) if(*s>a&&*s<z)n+;s+;執(zhí)行后n= _2_三、綜合題 1（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹 （2）若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹

41、成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系abced （3）給出該樹的前序遍歷序列答：（1）（2）d<b<e<a<c（3）abdec2（1）設(shè)head1和p1分別是不帶頭結(jié)點的單向鏈表A的頭指針和尾指針，head2和p2分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關(guān)鍵的賦值語句（不用完整程序，結(jié)點的鏈域為next）。 （2）單向鏈表的鏈域為next，設(shè)指針p指向單向鏈表中的某個結(jié)點，指針s指向一個要插入鏈表的新結(jié)點，現(xiàn)要把s所指結(jié)點插入p所指結(jié)點之后，某學生采用以下語句：

42、p->next=s; s->next=p->next;這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫答：（1）p1->next= head2；p2->next= head1；（2）不對，s->next= p->next；p->next=s；3（1）設(shè)有一個整數(shù)序列40，28，6，72，100，3，54依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹4028723100546 （2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度答：（1）（2）ASL=（1x1+2x2+3x3+4）/7=18/74（1）畫出對長度為10的有序表進行折半查

43、找的判定樹（以序號1，2，10表示樹結(jié)點） （2）對上述序列進行折半查找，求等概率條件下，成功查找的平均查找長度52849631071答：（1）（2）ASL=（1x1+2x2+3x4+4x3）/10=29/105（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程） （2）寫出對上述堆對應(yīng)的完全二叉樹進行中序遍歷得到的序列1642325257678210242826752573216102答：（1）初始樹 堆（2）102，52，42，82，16，67，32，576（1）利用篩選法，把序列37，77，62，97，11，27

44、，52，47建成堆（小根堆），畫出相應(yīng)的完全二叉樹 （2）寫出對上述堆所對應(yīng)的二叉樹進行前序遍歷得到的序列初始樹 堆答：（1）37776247522711 97（2）11，37，47，97，77，27，62，527（1）一組記錄的關(guān)鍵字序列為45，40，65，43，35，95寫出利用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的結(jié)果） （2）同樣對序列45，40，65，43，35，95利用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）。答：（1）45 40 65 43 35 95 （2） 40 45 65 43 35 95 35 40

45、 65 43 35 95 40 43 45 65 35 95 35 40 65 43 65 95 35 40 43 45 65 95 35 40 43 43 65 958設(shè)有一個不帶頭結(jié)點的單向鏈表，頭指針為head，結(jié)點類型為NODE，每個結(jié)點包含一個數(shù)據(jù)域data和一個指針域next，該鏈表有兩個結(jié)點，p指向第二個結(jié)點（尾結(jié)點），按以下要求寫出相應(yīng)語句（不要求完整程序，（1）、（2）、（3）、（4）是一個連續(xù)的過程）。 （1）新開辟一個結(jié)點，使指針s指向該結(jié)點，結(jié)點的數(shù)據(jù)成員data賦值為1 （2）把該結(jié)點插入鏈表的尾部，釋放指針s的指向 （3）刪除鏈表的第一個結(jié)點 （4）已知p1指向另一個新結(jié)點，把它插入到p所指結(jié)點和尾結(jié)點之間答：（1）s=（NODE*）malloc(sizeof(NODE);s->data=1;（2）p->next