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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、查找成功查找到元素120需要進行多少次元素間的比較？(2) 為了折半查找元素95，經(jīng)過多少次元素間的比較才能確定不能查到？（3）畫出對上述有序表進行折半查找所對應的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點)四、程序填空題1以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針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é)點且有n個結(jié)點的單向鏈表的程序，結(jié)點中的數(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é)點*/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é)點的單向鏈表中刪除第i個結(jié)點， 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é)點）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 期末綜合練習一答案一、單項選擇題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后進先出、先進先出 3214圖狀 （網(wǎng)

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