電大數(shù)據(jù)結(jié)構(gòu)(本科)考試題及答案

1、精選文檔一、單項(xiàng)選擇題1深度為5的完全二叉樹共有20個(gè)結(jié)點(diǎn)，則第5層上有（ ）個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A3 B8 C5 D62同一種邏輯結(jié)構(gòu)（ ）。 A只能有唯一的存儲(chǔ)結(jié)構(gòu) B可以有不同的存儲(chǔ)結(jié)構(gòu) C只能表示某一種數(shù)據(jù)元素之間的關(guān)系 D以上三種說(shuō)法均不正確3已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（ ）。A2m Bm C2m+1 Dm/24鏈表所具備的特點(diǎn)是（ ）。A可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn) B占用連續(xù)的存儲(chǔ)空間C插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn) D可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)5數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。 A物理 B存儲(chǔ) C邏輯與物理 D邏輯6數(shù)據(jù)

2、的物理結(jié)構(gòu)（ ）。 A與數(shù)據(jù)的邏輯結(jié)構(gòu)無(wú)關(guān) B僅僅包括數(shù)據(jù)元素的表示C只包括數(shù)據(jù)元素間關(guān)系的表示 D包括數(shù)據(jù)元素的表示和關(guān)系的表示7鏈表所具備的特點(diǎn)是（ ）。A可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn) B占用連續(xù)的存儲(chǔ)空間C插入刪除不需要移動(dòng)元素結(jié)點(diǎn) D可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A一對(duì)一 B一對(duì)多 C多對(duì)多 D每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 9線性表只要以（ ）方式存儲(chǔ)就能進(jìn)行折半查找。A鏈接 B順序 C關(guān)鍵字有序的順序 D二叉樹10以下表中可以隨機(jī)訪問(wèn)的是（ ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表11散列查找的原理是（ ）。A在待查

3、記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對(duì)應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C按關(guān)鍵字值的比較進(jìn)行查找D基于二分查找的方法12算法的時(shí)間復(fù)雜度與（ ）有關(guān)。 A所使用的計(jì)算機(jī) B與計(jì)算機(jī)的操作系統(tǒng) C與算法本身 D與數(shù)據(jù)結(jié)構(gòu)13對(duì)n個(gè)元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（ ）次元素間的交換，則表明序列已經(jīng)排好序。 A1 B2 C0 Dn-114設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。 An-i+1 Bn-i Cn-i-1 Di15排序過(guò)程中，每一趟從無(wú)序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹?，?/p>

4、排序算法是( )。 A直接插入排序 B快速排序C冒泡排序 D選擇排序 16在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用的語(yǔ)句是（ ）。 Ap=q->next Bp->next=q Cp->next=qànext Dq->next=NULL17在對(duì)一組元素（64，48，106，33，25，82，70，55，93）進(jìn)行直接插入排序時(shí)，當(dāng)進(jìn)行到要把第7個(gè)元素70插入到已經(jīng)排好序的子表時(shí)，為找到插入位置，需進(jìn)行（ ）次元素間的比較（指由小到大排序）。A6 B2 C3 D418從一個(gè)棧頂指針為top的鏈棧

5、中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ）。 Ax=top->data; top=top->next; Bx=top->data; Ctop=top->next; x=top->data; Dtop=top->next; x=data;19采用順序查找法對(duì)長(zhǎng)度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（ ）次元素間的比較。 An+2 Bn Cn-1 Dn/220在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ）。 Ar=f->next; Br=r->next; Cf=f->ne

6、xt; Df=r->next;21如圖1，若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為（ ）。abecdfg Aacebdgf BabecdgfCacfedgbDabecfdg 圖122一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。Adceab Bedcba Cdecba Dabcde 23元素2，4，6，8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出棧可以交替進(jìn)行）。 A8，6，4，2 B2，4，6，8 C4，2，8，6 D8，6，2，424有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成

7、功的平均比較次數(shù)為（ ）。A26/10 B29/10 C29/9 D31/1025排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。 A歸并 B插入 C選擇 D快速 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ ）。 A冒泡 B直接插入 C折半插入 D選擇排序27一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn)，該樹共有（ ）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）A10 B13 C11 D1228設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維

8、數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是（ ）。A33 B32 C85 D4129隊(duì)列的插入操作在（ ）進(jìn)行。 A隊(duì)頭 B隊(duì)尾 C隊(duì)頭或隊(duì)尾 D在任意指定位置30在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（ ）倍。 A3 B2.5 C1.5 D2二、填空題1一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹總共有_個(gè)結(jié)點(diǎn)。2棧和隊(duì)列的操作特點(diǎn)分別是_ _和 _ _。3設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹一共有_個(gè)結(jié)點(diǎn)。4結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_ _結(jié)構(gòu)。5按照二叉樹的遞歸定義，對(duì)二叉樹遍

9、歷的常用算法有_ _ _ 、_ _、 _ _三種。6根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常可分為集合、線性、 、 四類基本結(jié)構(gòu)。7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為_結(jié)構(gòu)。8要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為_和 _ 。9把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。10在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行_ _ _和p->next=s;的操作。11結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_結(jié)構(gòu)。12在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是值域 、 。13如圖2所

10、示的二叉樹，其后序遍歷序列為 。efgibachd14一棵二叉樹中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為_、_。15n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行_趟冒泡。16向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行s->next=h;和_。17二叉樹為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是_的。(回答正確或不正確) 18在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為_和r=s; (結(jié)點(diǎn)的指針域?yàn)閚ext)19圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_的。(回答正確或不正確

11、) 20設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有_個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）21根據(jù)搜索方法的不同，圖的遍歷有_ _、 _ _ 兩種方法22對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的_、_ _和_ _三項(xiàng)信息。23按某關(guān)鍵字對(duì)記錄序列排序，若關(guān)鍵字 的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。24在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較_次。三、綜合題1（1）利用篩選過(guò)程把序列42，82，67，102，16，32

12、，57，52建成堆（小根堆），畫出該堆（不要求中間過(guò)程）。 （2）寫出對(duì)上述堆對(duì)應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。2 (1)以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹( 要求每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2) 一棵哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡(jiǎn)述理由？3設(shè)查找表為(16,15,20,53,64,7), (1)用冒泡法對(duì)該表進(jìn)行排序（要求升序排列），要求寫出每一趟的排序過(guò)程。(2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(3)求在等概率條件下,對(duì)上述有序表

13、成功查找的平均查找長(zhǎng)度.4一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84）（1）利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次交換元素的過(guò)程，要求以升序排列）（2）對(duì)上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過(guò)程。5（1）設(shè)有一個(gè)整數(shù)序列50，38，16，82，110，13，64，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹 （2）利用上述二叉排序樹，為了查找110，經(jīng)多少次元素間的比較能成功查到，為了查找15，經(jīng)多少次元素間的比較可知道查找失敗6設(shè)查找表為(50,60,75,85,96,98,105,110,120,130) (1) 說(shuō)出進(jìn)行折半

14、查找成功查找到元素120需要進(jìn)行多少次元素間的比較？(2) 為了折半查找元素95，經(jīng)過(guò)多少次元素間的比較才能確定不能查到？（3）畫出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))四、程序填空題1以下函數(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，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) _(1)_; p-&g

15、t;data=x; p->next=NULL; _(2)_; rear= _(3)_; 2以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3,n，完成程序中空格部分。NODE *create(n)NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);head= （1） ; （2） ;pànext=NULL; /*建立頭結(jié)點(diǎn)*/for(i=1; i<=n; i+) p= （3） ; pàdata=i; pànext=NULL; qànext=

16、 （4） ; （5） ;return(head);3以下函數(shù)在head為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中刪除第i個(gè)結(jié)點(diǎn)， struct node int data;struct node *next;typedef struct node NODE int delete(NODE *head,int i )NODE *p,*q; int j; q=head;j=0; while(q!=NULL)&&( _(1)_) _(2)_;j+; if(q=NULL) return(0); p= _(3)_; _(4)_=p->next; free(_(5)_); return(1);

17、4以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 期末綜合練習(xí)一答案一、單項(xiàng)選擇題1C 2B 3 A 4C 5D 6D 7C 8A 9C 10D 11A 12C 13C 14B 15A 16C 17C 18A 19B 20C 21B 22A 23D 24B 25C 26C 27D 28A 29B 30D 二、填空題1112后進(jìn)先出、先進(jìn)先出 3214圖狀 （網(wǎng)

18、狀）5先序；中序；后序6樹形 圖狀 7樹形8n-1,O(n) 9物理（存儲(chǔ)） 10s->next=p->next;11線性 12左指針 右指針13gdbeihfca142i 2i+115n-116h=s; 17不正確18r->next=s; 19正確2012 21深度優(yōu)先搜索遍歷 廣度優(yōu)先搜索遍歷22行下標(biāo)、列下標(biāo)、非零元素值23相等243三、綜合應(yīng)用題1（1）16423252576782102 （2）102，52，42，82，16，67，32，57233 (1)151879985432 2：11103: 11114：1107：008：019：10（2）2n-1個(gè)，因?yàn)榉侨~結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。 3(1)原序列16 15 20 53 64 7 15 16 2