電大數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習一Word版

1、數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習一一、單項選擇題1數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ ）。A只能有一個數(shù)據(jù)項組成 B至少有二個數(shù)據(jù)項組成C至少有一個數(shù)據(jù)項為指針類型D可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成2（ ）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A數(shù)據(jù)對象 B數(shù)據(jù)元素 C數(shù)據(jù)結(jié)構(gòu) D數(shù)據(jù)項3線性表的順序結(jié)構(gòu)中，（ ）。A邏輯上相鄰的元素在物理位置上不一定相鄰B邏輯上相鄰的元素在物理位置上也相鄰C數(shù)據(jù)元素是不能隨機訪問的D進行數(shù)據(jù)元素的插入、刪除效率較高4設(shè)鏈表中的結(jié)點是NODE類型的結(jié)構(gòu)體變量，且有NODE *p；為了申請一個新結(jié)點，并由p指向該結(jié)點，可用以下語句（ ）。Ap=(NODE *)

2、malloc(sizeof(p);Bp=(*NODE)malloc(sizeof(NODE);Cp=(NODE )malloc(sizeof(p);Dp=(NODE *)malloc(sizeof(NODE);5以下表中可以隨機訪問的是（ ）。 A單向鏈表 B順序表 C單向循環(huán)鏈表 D雙向鏈表6設(shè)順序存儲的線性長度為n，要在第i個元素之前插入一個新元素，按課本的算法當i= （ ）時，移動元素次數(shù)為2An/2 Bn Cn-1 C17 .設(shè)順序存儲的線性表長度為n，對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（ ）。A(n+1)/2 Bn C2n Dn-i8一個棧的進棧序

3、列是1，2，3，4，則棧的不可能的出棧序列是（ ）（進出棧操作可以交替進行）A3，2，4，1 B3，2，1，4C4，3，2，1 D1，4，2，39設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則出棧操作為（ ）。Atop=top-next;x=top-data; Bx=top-data;top=top-next;Cx=top- next;top=top- data; Dtop-next =top; x=top-data; 10設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊

4、列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被賦值)，則入隊操作為（ ）。Arear-next=p;rear=p; Brear-next=p; p = rear; Cp = rear-next;rear=p; Drear=p;rear-next=p;11以下說法正確的是（ ）。A隊列是后進先出 B棧的特點是后進后出C棧的刪除和插入操作都只能在棧頂進行D隊列的刪除和插入操作都只能在隊頭進行12以下說法不正確的是（ ）。 A順序棧中，棧滿時再進行進棧操作稱為“上溢”B順序棧中，棧空時再作出棧棧操作稱為“下溢”C順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空D順序隊列中

5、，當尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿13串函數(shù)StrCmp(“abA”,”aba”)的值為（ ）。A1 B0 C“abAaba” D-114設(shè)有一個20階的對稱矩陣A，采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a11，數(shù)組b的下標從1開始），則矩陣元素a8,5在一維數(shù)組b中的下標是（ ）。A30 B28 C40 D3315設(shè)有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為a1,1，數(shù)組b的下標從1開始），則矩陣A中第4行的元素在數(shù)組b中的下標i一定有（ ）。A7i10 B11i

6、15 C9i14 D6i916深度為5的完全二叉樹第5層上有4個結(jié)點，該樹一共有（ ）個結(jié)點。A28 B30 C31 D1917已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ ）。A2m Bm C2m+1 Dm/2 18已知一個圖的所有頂點的度數(shù)之和為m，則m一定不可能是（ ）。A4 B8 C12 D919以下說法不正確的是（ ）。 A連通圖G一定存在生成樹B連通圖G的生成樹中一定包含G的所有頂點C連通圖G的生成樹中不一定包含G的所有邊D連通圖G的生成樹可以是不連通的20以下說法正確的是（ ）。 A連通圖G的生成樹中可以包含回路B連通圖G的生成樹可以是不連通的C連通圖G的生成樹一定是連通

7、而不包含回路的 D連通圖G的生成樹一定是唯一的21散列查找的原理是（ ）。A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲C按關(guān)鍵字值的比較進行查找D基于二分查找的方法22 對n個元素進行冒泡排序，通常要進行n-1趟冒泡，在第j趟冒泡中共要進行（ ）次元素間的比較。 Aj Bj-1 Cn-j Dn-j-123排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當位置，直到全部排好序為止，該排序算法是( )。 A直接插入排序 B快速排序C冒泡排序 D選擇排序 24在排序過程中，可以有效地減少一趟排序過程中

8、元素間的比較次數(shù)的算法是（ ）。 A冒泡 B選擇 C折半插入 D直接插入 25采用順序查找法對長度為n的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進行（ ）次元素間的比較。 An+2 Bn Cn-1 Dn/226如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ ）。 AaebcfdBabedcfCacebdfDacfbde 圖1 27如圖若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ ）。 AacebdfghBaebcghdfCaedfbcghDabecdfgh 圖228一棵哈夫曼樹有n個葉子結(jié)點（終端結(jié)點），該樹總共有（ ）個結(jié)點。A2n

9、-2 B2n-1 C2n D2n+229一棵哈夫曼樹總共有23個結(jié)點，該樹共有（ ）個葉結(jié)點（終端結(jié)點）A10 B11 C12 D13 30數(shù)據(jù)的（ ）結(jié)構(gòu)與所使用的計算機無關(guān)。 A邏輯 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)鏈表，可用語句_ _。4要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點，若鏈表中結(jié)點的指針域為next，可執(zhí)行_和p-next=s;

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

11、data; _ _。9循環(huán)隊列的隊頭指針為f，隊尾指針為r，當_ _時表明隊列為空。 10循環(huán)隊列的最大存儲空間為MaxSize=8，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=4，則當隊尾指針rear= _ _時，隊列為空，當rear= _ _時，隊列有6個元素。11“A”在存儲時占_個字節(jié)。12稀疏矩陣存儲時，采用一個由_ _ 、_ _ 、_ _3部分信息組成的三元組唯一確定矩陣中的一個非零元素。13一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有_個結(jié)點。14一棵二叉樹順序編號為6的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉樹中對應(yīng)位置上結(jié)點的編號相同），若它存在

12、右孩子，則右孩子的編號為_。15按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_ _ _ 、_ _、 _ _三種。16結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_結(jié)構(gòu)。17把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。18結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_結(jié)構(gòu)。19如圖3所示的二叉樹，其后序遍歷序列為 。efgibachd 圖320如圖4所示的二叉樹，其前序遍歷序列為_ _。gfabdec 圖421二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_的。(回答正確或不正確) 22在隊列的順序存儲結(jié)構(gòu)中，當插入一個新的隊列元素時， 指針的

13、值增1，當刪除一個元素隊列時， 指針的值增1。23根據(jù)搜索方法的不同，圖的遍歷有_ _、 _ _ 兩種方法24循環(huán)隊列的引入，目的是為了克服 。三、綜合題 1（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹 （2）若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系 （3）給出該樹的前序遍歷序列2（1）設(shè)head1和p1分別是不帶頭結(jié)點的單向鏈表A的頭指針和尾指針，head2和p2分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個以head1為頭

14、指針的單向循環(huán)鏈表，寫出其中兩個關(guān)鍵的賦值語句（不用完整程序，結(jié)點的鏈域為next）。 （2）單向鏈表的鏈域為next，設(shè)指針p指向單向鏈表中的某個結(jié)點，指針s指向一個要插入鏈表的新結(jié)點，現(xiàn)要把s所指結(jié)點插入p所指結(jié)點之后，某學生采用以下語句： p-next=s; s-next=p-next;這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫3（1）設(shè)有一個整數(shù)序列40，28，6，72，100，3，54依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹 （2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度4（1）畫出對長度為10的有序表進行折半查找的判定樹（以序號1，2，10表示樹結(jié)點）

15、 （2）對上述序列進行折半查找，求等概率條件下，成功查找的平均查找長度5（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程） （2）寫出對上述堆對應(yīng)的完全二叉樹進行中序遍歷得到的序列6（1）利用篩選法，把序列37，77，62，97，11，27，52，47建成堆（小根堆），畫出相應(yīng)的完全二叉樹 （2）寫出對上述堆所對應(yīng)的二叉樹進行前序遍歷得到的序列四、程序填空題1以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格typedef struct int

16、 key;NODE;int Binary_Search(NODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; 2以下函數(shù)為直接選擇排序算法，對a1,a2,an中的記錄進行直接選擇排序，完成程序中的空格typedef struct int key;NODE; void selsort(NODE a,int n)int i,j,k;N

17、ODE temp;for(i=1;i= _(1)_;i+) k=i; for(j=i+1;j= _(2)_;j+) if(aj.keydata=x; p-next=NULL; _(2)_; rear= _(3)_; 4以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 答案一、單項選擇題1D 2A 3B 4D 5B 6C 7A 8D 9B 10A 11C 12D

18、13D 14D 15A 16D 17A 18D 19D 20C 21A 22C23A 24C 25B 26B 27D 28B 29C 30A 二、填空題1集合；線性；樹形；圖狀2樹形3p-next=head;4s-next= p-next；5p-next=head；6hs=hs-next;7r-next=s8f=f-next;9r= =f104；2111；212行號；列號；非零元1311141315先序；中序；后序16圖狀17物理（存儲） 18樹形 19gdbeihfca20abdefcg21錯誤 22尾 頭23深度優(yōu)先 廣度優(yōu)先24假上溢 三、綜合應(yīng)用題1（1）（2）dbeanext= head2；p2-next= head1；（2）不對，s-next= p