上饒師范學(xué)院模擬試題一

PAGEPAGE1上饒師范學(xué)院模擬試題一課程名稱：數(shù)據(jù)結(jié)構(gòu)適用學(xué)期：第四學(xué)期適用專業(yè)：計算機科學(xué)與技術(shù)適用層次：本科班級：學(xué)號：姓名題號一二三四五六七總分得分得分一．選擇題(每小題2分，10小題共20分)1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分成。A．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B．線性結(jié)構(gòu)和非線性結(jié)構(gòu)C．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2．用鏈表表示線性表的優(yōu)點是。A．便于隨機存儲B．花費的存儲空間較順序存儲少C．便于插入和刪除操作D．?dāng)?shù)據(jù)元素的物理順序與邏輯順序相同3．已知兩個串為s1=“bccadcabcadf”，s2=“abc”，則s2在s1中的起始位置是。A．9B．8C．7D．64．若進棧序列為1，2，3，4，進棧過程中可以出棧，則不可能是一個出棧序列。A．1，4，3，2B．2，3，4，1C．3，1，4，2D．3，4，2，15．對圖(1)中的二叉樹,按先序遍歷得到的結(jié)點序列為。AA．ABCDHEIFGB．ABDHIECFGBCC．HDIBEAFCGD．HIDBEFGACDEFGHI圖(1)6．如下圖所示的4棵二叉樹中，不是完全二叉樹。A．B．C．D．7．進行二分法檢索，則線性表。A．必須以順序方式存儲B．必須以鏈式方式存儲，且數(shù)據(jù)元素按值排好序C．必須以鏈式方式存儲D．必須以順序方式存儲,且數(shù)據(jù)元素按值排好序8．一組記錄的排序碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為。A．38，40，46，56，79，84B．40，38，46，79，56，84C．40，38，46，56，78，84D．40，38，46，84，56，799．選擇排序和歸并排序的穩(wěn)定性分別是。A．都穩(wěn)定B．穩(wěn)定、不穩(wěn)定C．不穩(wěn)定、穩(wěn)定D．都不穩(wěn)定10．對如下無向圖2，若從頂點V1開始，按深度優(yōu)先搜索法進行遍歷，則可能訪問順序為。A．B．C．D．V1V2V3V4V5V6V7V8圖2得分二．填空題(每小題2分，8小題共16分)11．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)基本上可分為、。12．在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行操規(guī)作。13．設(shè)a=‘a(chǎn)Bc2*1XY+lq456XY’，則Length(a)為,SubStr(a,7,3)為。14．隊列是限制插入只能在表的一端、而刪除在表的另一端進行的線性表，其特點是。15．用順序方法將完全二叉樹的結(jié)點逐層存放在數(shù)組A[1．．n]中，結(jié)點A[i]若有左孩子，則該左孩子結(jié)點為，結(jié)點A[i]若有右孩子，則該右孩子結(jié)點為。16．順序檢索的平均檢索長度是。17．在一個具有n個頂點的無向圖中，要連通全部頂點至少需要條邊。18．在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用；若初始數(shù)據(jù)基本反序，則選用。得分三．概念簡答題(每小題3分，3小題共9分)19．試寫出在鏈接表示方法下，棧的基本運算。20．在所學(xué)的排序算法中，試分別給出時間復(fù)雜度是和排序算法。21．什么是樹?給出樹的四種表示形式。得分四．簡單解答題(每小題5分，4小題共20分)22．二叉樹結(jié)點采用順序存儲結(jié)構(gòu)，如下圖所示。1234567891011121314151617181920eafdgcjhib(1)．畫出該二叉樹；(2)．寫出該二叉樹的前序遍歷、中序遍歷和后序遍歷結(jié)果。(5分)23．設(shè)線性表的關(guān)鍵字集合Key={32,13,49,55,22,39,20},選用散列函數(shù)的方法為“除余法”，解決沖突的方法為“線性探查法”，請按上述條件求出Key中各值的地址。(5分)24．給出如圖(3)所示無向圖G(該題把圖3看成是無權(quán)圖)的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。(5分)A3B511C43D222E3F圖(3)25．對上題用圖示法畫出Prim算法構(gòu)造該網(wǎng)絡(luò)的最小生成樹步驟。(5分)得分五．程序閱讀理解填空題(4小題，共5+6+6=17分)26．[程序說明]：以下程序是將一個頭結(jié)點指針為a的單鏈表A分解成兩個單鏈表A和B，其中結(jié)點指針分別為a和b，使得Ａ鏈表中含有原鏈表Ａ中序號為奇數(shù)的結(jié)點，而Ｂ鏈表中含有原鏈表Ａ中序號為偶數(shù)的結(jié)點，且保持原來的相對順序，請?zhí)羁帐钩绦蛲瓿善涔δ堋?第一空1分，其余每空2分，共5分)voiddisa(a,b)LinkList*a，*b；{LinkList*p，*q，*r；p=a；b=a->link；r=b；while(p!=NULL&&p->link!=NULL){①；②；③；r=q；p=p->link；}r->link=NULL；}27．[程序說明]：以下程序是二分法插入排序算法，請?zhí)羁帐钩绦蛲暾?每空2分，共6分)voidbinSort(SordObject*pvector){inti,j,left,mid,right；RecordNodetemp;for(i=1；i<pvector->n；i++){①；left=0；right=i-1；while(left<=right){mid=(left+right)/2；if(②)right=mid-1；elseleft=mid+1；}for(j=i-1；j=left；j++)pvector->record[j+1]=pvector->record[j]；if(left!=i)③；}}28．[程序說明]：以下程序是用二分檢索算法在一個有序表中插入一個元素x，并保持表的有序性，請?zhí)羁帐钩绦蛲暾?每空2分，共6分)。(算法的思想是先在有序表r中用二分檢索算法檢索關(guān)鍵字值等于或小于x的結(jié)點，mid指向關(guān)鍵字值正好等于x的結(jié)點或low指向關(guān)鍵字值大于x的結(jié)點，然后采用移動法插入x結(jié)點。)bininsert(SeqDictionary*r，intx，intn){intlow=1；high=n；mid，inplace，i，find=0；while(low<=high&&!find){①；if(x<r[mid]．key)②；elseif(x>r[mid]．key)③；else{i=mid；find=1；}}if(find)inplace=mid；