數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題.docx

一、選擇題（每題2分共20分）1若長(zhǎng)度為n的線(xiàn)性表(a1, a2, an)采用順序存儲(chǔ)，刪除它的第i個(gè)數(shù)據(jù)元素，需要依次向前移動(dòng) 個(gè)數(shù)據(jù)元素。 A. n-i B. n+i C.n-i+1 D.n-i-12 在一個(gè)單鏈表head中，若要在指針p所指結(jié)點(diǎn)后插入一個(gè)q指針?biāo)附Y(jié)點(diǎn)，則執(zhí)行_。A. p-next=q-next; q-next=p;B. q-next=p-next; p=q;C. p-next=q-next; p-next=q;D. q-next=p-next; p-next=q;3棧是一種 的線(xiàn)性表。A. 只允許在一端進(jìn)行插入和在另一端進(jìn)行刪除 B. 只允許在一端進(jìn)行插入和刪除 C. 只允許在兩端進(jìn)行插入和刪除 D. 允許在中間部位進(jìn)行插入和刪除4算術(shù)表達(dá)式ab+c/d的逆波蘭式是_。 A. abcd+/ B. abc/d+ C. abcd/+ D. ab+cd/5循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）。A(rear-front+m)%mBread-front+1Cread-front-1 Dread-front6設(shè)二維數(shù)組a0m-10n-1按行優(yōu)先順序存儲(chǔ)在首地址為loc(a00)的存儲(chǔ)區(qū)域中，每個(gè)元素占d個(gè)單元，則aij的地址為_(kāi)。A. loc(a00) +( in+ j) d B. loc(a00) +(jm+i) d C. loc(a00) +(j-1)n+i-1) d D. loc(a00) +(j-1)m+i-1) d7對(duì)于二叉樹(shù)來(lái)說(shuō),第i層上至多有_個(gè)結(jié)點(diǎn)。 A2i B 2i-1 C2i-1 D2i-1-18有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，（ ）次比較后查找成功。A1 B2 C4 D89設(shè)哈希表長(zhǎng)m=11，哈希函數(shù)H（key）=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其余地址為空，如果線(xiàn)性探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)地址是 。 A3 B5 C8 D910用某種排序方法對(duì)線(xiàn)性表（25,84,21,47,15,27,68,35,20）進(jìn)行排序時(shí)，元素序列的變化情況如下：25,84,21,47,15,27,68,35,2015,84,21,47,25,27,68,35,2015,20,21,47,25,27,68,35,8415,20,21,25,47,27,68,35,84 15,20,21,25,27,35,47,68,84則采用的排序方法是（ ）。A冒泡排序 B快速排序 C歸并排序 D選擇排序二、求解題1已知二叉樹(shù)的擴(kuò)展前序序列：FKHBEGADC.請(qǐng)畫(huà)出該二叉樹(shù)并寫(xiě)出該樹(shù)的中序和后序序列。（12分）2畫(huà)出下列樹(shù)對(duì)應(yīng)的二叉樹(shù)。（10分）3.給定無(wú)向圖G=,其中V=a,b,c,d,e,E=(a,b),(a,e),(b,e),(b,c),(c,e),(e,d).請(qǐng)畫(huà)出圖G的鄰接矩陣,鄰接表。從結(jié)點(diǎn)a出發(fā),分別寫(xiě)出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法進(jìn)行遍歷的結(jié)點(diǎn)序列。(12分)4從空的二叉排序樹(shù)開(kāi)始依次插入30，18,11,17,7,5,13,41,29,37,23,19。畫(huà)出該二叉排序樹(shù)。（9分）5分別寫(xiě)出對(duì)序列 10,18,11,17,7,5,13,41,29,37,23,19,25進(jìn)行快速排序和冒泡排序的過(guò)程。(16分)三、寫(xiě)出下列算法的功能或輸出結(jié)果1.typedef struct List int number; struct List *next; Node，*Link;void func1(Link p)/p指向單鏈表 while(p!=NULL) printf(“%dn”,p-number);p=p-next;功能是 。2.寫(xiě)出下列程序段的運(yùn)行結(jié)果（棧中的元素類(lèi)型是char）： main() SEQSTACK s,*p; char x, y; p = &s; initstack(p); x = c; y = k; push(p,x); push(p,a); push(p,y); x = pop(p); push(p,t); push(p,s); while(!empty(p) y = pop(p); printf(%c,y); printf(%cn,x);運(yùn)行結(jié)果是 。 3int func3 (int r , int n, int k) int i,low=0, high=n-1, mid, find=0; while (low=high &find=0) mid=(low+high)/2; if (krmid) low=mid+1;else imid;find=1;if (!find) return -1;return i;功能是 。四、讀程填空1下列算法創(chuàng)建n個(gè)元素的帶頭單鏈表.typedef struct lnode int data; struct lnode *next; lnode,*linklist ; void create(linklist &head, int n) linklist p; int i; head=(linklist)malloc(sizeof(lnode); A ; for(i=n;i0;i-)p =(linklist)malloc(sizeof(lnode); scanf(“%d”,&p-data); B ; C ; 2完成下列插入排序算法。typedef struct nodeint key; int data;NODE;void insert(NODE