自考數(shù)據(jù)結(jié)構(gòu) 歷年試題及答案

1、自考數(shù)據(jù)結(jié)構(gòu)02331歷年試題及答案(2009-2015個人整理版)全國2009年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.下列程序段的時間復(fù)雜度為( )9 s=0； for(i=1；i<n；i+) for(j=1；j<n；j+) s+=i*j；A.O(1)B.O(n)C.O(2n)D.O(n2)2.假設(shè)某個帶頭結(jié)點的單鏈表的頭指針為head，則判定該表為空表的條件是( )22A.head=NULL；B.head->next=NU

2、LL；C.head!=NULL；D.head->next=head；3.棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特征是( )32A.先進(jìn)先出B.后進(jìn)先出C.進(jìn)優(yōu)于出D.出優(yōu)于進(jìn)4.假設(shè)以數(shù)組An存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設(shè)定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當(dāng)前存于隊列中的元素個數(shù)為( )A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n5.判斷兩個串大小的基本準(zhǔn)則是( )52A.兩個串長度的大小B.兩個串中首字符的大小C.兩個串中大寫字

3、母的多少D.對應(yīng)的第一個不等字符的大小6.二維數(shù)組A45按行優(yōu)先順序存儲，若每個元素占2個存儲單元，且第一個元素A00的存儲地址為1000，則數(shù)組元素A32的存儲地址為( )60A.1012B.1017C.1034D.1036a00a01a02a03a04a327.高度為5的完全二叉樹中含有的結(jié)點數(shù)至少為( )72A.16B.17C.31D.328.已知在一棵度為3的樹中，度為2的結(jié)點數(shù)為4，度為3的結(jié)點數(shù)為3，則該樹中的葉子結(jié)點數(shù)為( )A.5B.8C.11D.189.下列所示各圖中是中序線索化二叉樹的是( A )81A10.已知含6個頂點(v0，v1，v2，v3，v4，v5)的無向圖的鄰接

4、矩陣如圖所示，則從頂點v0出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的頂點訪問序列為( )108A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)11.如圖所示有向圖的一個拓?fù)湫蛄惺? )A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF12.下列關(guān)鍵字序列中，構(gòu)成大根堆的是( )A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，313.對長度為15的有序順序表進(jìn)行二分查找，在各記錄的查找概率

5、均相等的情況下，查找成功時所需進(jìn)行的關(guān)鍵字比較次數(shù)的平均值為( )172A.B.C.D.14.已知一個散列表如圖所示，其散列函數(shù)為H(key)=key11，采用二次探查法處理沖突，則下一個插入的關(guān)鍵字49的地址為( D )d 19715.數(shù)據(jù)庫文件是由大量帶有結(jié)構(gòu)的( )206A.記錄組成的集合B.字符組成的集合C.數(shù)據(jù)項組成的集合D.數(shù)據(jù)結(jié)構(gòu)組成的集合二、填空題(本大題共10小題，每小題2分，共20分)請在每小題的空格中填上正確答案。錯填、不填均無分。16.估算算法時間復(fù)雜度時考慮的問題規(guī)模通常是指算法求解問題的_輸入量_。 817.在雙向循環(huán)鏈表中插入一個新的結(jié)點時，應(yīng)修改_4_個指針域的

6、值。 2818.若進(jìn)棧序列為a，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)_5_個不同的出棧序列。519.鏈串的結(jié)點大小定義為結(jié)點的_數(shù)據(jù)域_中存放的字符個數(shù)。 5420.廣義表(a，(d，(c)的深度為_3 _。6721.在含有3個結(jié)點a，b，c的二叉樹中，前序序列為abc且后序序列為cba的二叉樹有_4_棵。422.若用鄰接矩陣表示有向圖，則頂點i的入度等于矩陣中_。第i列非零元素的個數(shù)10723.對關(guān)鍵字序列(15，18，11，13，19，16，12，17，10，8)進(jìn)行增量為5的一趟希爾排序的結(jié)果為_。 15，12，11，10，8，16，18，1724.索引順序查找的索引表由各分塊中

7、的最大關(guān)鍵字及各分塊的_起始位置_構(gòu)成。17325.VSAM文件的實現(xiàn)依賴于操作系統(tǒng)中的_分頁_存取方法的功能。 215三、解答題(本大題共4小題，每小題5分，共20分)26.假設(shè)有一個形如的8×8矩陣，矩陣元素都是整型量(次對角線以上的元素都是0)。若將上述矩陣中次對角線及其以下的元素按行優(yōu)先壓縮存儲在一維數(shù)組B中，請回答下列問題：(1)B數(shù)組的體積至少是多少?(2)若a18存儲在B0中，a56存儲在Bk中，則k值為多少?(1) （1+8）*8/2=36 存放次對角線以上的零為37(2) 1227.對關(guān)鍵字序列(5，8，1，3，9，6，2，7)按從小到大進(jìn)行快速排序。(1)寫出排序

8、過程中前兩趟的劃分結(jié)果；(2)快速排序是否是穩(wěn)定的排序方法?(1)第一趟劃分結(jié)果；(2，3，1)，5，(9，6，8，7)第二趟劃分結(jié)果；(1，2，3)，5，(9，6，8，7)第三趟劃分結(jié)果；(1，2，3)，5，(7，6，8，9)第四趟劃分結(jié)果； 1，2，3，5，6，7，8，9第一趟劃分過程2315968712359687 1235768912356789ji(5，8，1，3，9，6，2，7)1(2，8，1，3，9，6，5，7)2(2，5，1，3，9，6，8，7)3(2，3，1，5，9，6，8，7)4(2，3，1，5，9，6，8，7)第二趟劃分過程(2，3，1，5，9，6，8，7)1(1，2，3

9、，5，7，6，8，9) (2)非穩(wěn)定2315968712355768956789ji第一趟：（2，3，1）5 （9，6，8，7）第二趟： 1，2，3，5 （9，6，8，7）第三趟：1，2，3，5，（7，6，8），9第四趟：1，2，3，5，6，7，8，928.假設(shè)通信電文使用的字符集為a，b，c，d，e，f，g，h，各字符在電文中出現(xiàn)的頻度分別為：7，26，2，28，13，10，3，11，試為這8個字符設(shè)計哈夫曼編碼。要求：(1)畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點的權(quán)值不大于右孩子結(jié)點的權(quán)值)； (2)按左分支為0和右分支為1的規(guī)則，分別寫出與每個字符對應(yīng)的編碼。(1)(2)29.已知3

10、階B樹如圖所示，非根 【1，2】P184根 【1，2】(1)畫出將關(guān)鍵字6插入之后的B樹；1,3695,8(2)畫出在(1)所得樹中插入關(guān)鍵字2之后的B樹。1,2,3695,81,3695,81,2,3692,5,81692,5,831692358四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.假設(shè)以帶頭結(jié)點的單鏈表表示線性表，單鏈表的類型定義如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;閱讀下列算法，并回答問題：(1)已知初始鏈

11、表如圖所示，畫出執(zhí)行f30(head)之后的鏈表；題30圖(2)簡述算法f30的功能。void f30( LinkList head) LinkList p,r, s; if (head - > next) r = head - > next; p = r->next; r - > next = NULL; while (p) s =p; p = p->next; if ( s - > data% 2 = = 0) s - > next = head - > next; head - > next = s; else s - > ne

12、xt = r - > next; r->next = s; r =s; (1)2857(2)31.假設(shè)以二叉鏈表表示二叉樹，其類型定義如下：typedef struct node DataType data; struct node * lchild, * rchild; /左右孩子指針 * BinTree ;閱讀下列算法，并回答問題：(1)已知以T為根指針的二叉樹如圖所示， 寫出執(zhí)行f31(T)之后的返回值；(2)簡述算法f31的功能。int f31 ( BinTree T) int d; if ( ! T) return 0; d = f31 ( T - > lchild

13、) + f31 ( T - > rchild) ; if (T - > lchild && T - > rchild) return d + 1 ; else return d;(1)3(2)統(tǒng)計度為2的結(jié)點個數(shù)32.設(shè)有向圖鄰接表定義如下：typedef struct VertexNode adjlist MaxVertexNum ; int n，e； 圖的當(dāng)前頂點數(shù)和弧數(shù)ALGraph； 鄰接表類型其中頂點表結(jié)點VertexNode邊表結(jié)點EdgeNode結(jié)構(gòu)為：閱讀下列算法，并回答問題：(1)已知某有向圖存儲在如圖所示的鄰接 表G中，寫出執(zhí)行f32(G)

14、的輸出；(2)簡述算法f32的功能。int visited MaxNum ;void DFS(ALGraph * G, int i) EdgeNode * p; visited i = TRUE ; if (G - > adjlist i. firstedge = = NULL) printf( "% c ", G - > adjlist i. vertex)； else p = G - > adjlist i. firstedge; while (p ! = NULL) if ( ! visitedp -> adjvex ) DFS( G, p -

15、 > adjvex) ; p = p->next;void f32 ( ALGraph * G) int i; for (i = 0; i < G->n; i +) visited i = FALSE ; for (i = 0; i < G->n; i+) if ( ! visitedi ) DFS(G, i) ;(1)ABECD(2)圖的深度優(yōu)先搜尋ABCDE33.下列算法f33的功能是對記錄序列進(jìn)行雙向冒泡排序。算法的基本思想為，先從前往后通過交換將關(guān)鍵字最大的記錄移動至后端，然后從后往前通過交換將關(guān)鍵字最小的記錄移動至前端，如此反復(fù)進(jìn)行，直至整個序列按

16、關(guān)鍵字遞增有序為止。請在空缺處填入合適的內(nèi)容，使其成為完整的算法。#define MAXLEN 100typedef int KeyType;typedef struct KeyType key; InfoType otherinfo; NodeType ;typedef NodeType SqList MAXLEN ;void f33 ( SqList R, int n) int i,j,k; NodeType t; i =0; j =n-l; while (i < j) for ( (1) ) k=i;k<j;k+ if (Rk.key > Rk +l.key) t =

17、Rk; Rk = Rk +1; Rk +1 = t; j-; for (k =j; k > i; k - ) if ( (2) ) Rk.key < Rk-l.key t = Rk; Rk = Rk-1; Rk-1 = t; (3) ; i+(1)(2)(3)五、算法設(shè)計題(本大題10分)34.假設(shè)以帶頭結(jié)點的單鏈表表示線性表，單鏈表的類型定義如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;編寫算法，刪除線性表中最大元素(假設(shè)最大值

18、唯一存在)。函數(shù)原型為：void f34(LinkList head) LinkNode *p,*max,*q;P=head->next;max=head->next;while(P)P=p->next;If(p->data>max->data) max=p;x=max->data;delete_L(Lnode *L,int i) Lnode *p,*q;int j;Elemtype x; P=L;j=0; While(p->next!=null&&j<=i-1) p=p->next;j+; If(! P->ne

19、xt|i<1) Printf("n刪除位置錯誤！");return(-1); Elseq=p->next;x=q->data; P->next=q->next;free(q); Return(x);/*delete_L*/全國2009年10月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)真題一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.按值可否分解，數(shù)據(jù)類型通?？煞譃閮深悾鼈兪?c)A.靜態(tài)類型和動態(tài)類型B.原子類型和表類型C.原子類型和結(jié)構(gòu)類型D.數(shù)組

20、類型和指針類型2. A.A f(n)是0(g(n)B.B g(n)是0(f(n)C.C h(n)是0(nlogn)D.D h(n)是0(n2)答案：C3.指針p、q和r依次指向某循環(huán)鏈表中三個相鄰的結(jié)點，交換結(jié)點*q和結(jié)點*r在表中次序的程序段是()A.p->next=r；q->next=r->next；r->next=q；B.p->next=r；r->next=q；q->next=r->next；C.r->next=q；q->next=r->next；p->next=r；D.r->next=q；p->next

21、=r；q->next=r->next；答案：A4.若進(jìn)棧次序為a，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的含3個元素的出棧序列個數(shù)是()A.3B.5C.6D.7答案：B5.假設(shè)以數(shù)組An存放循環(huán)隊列的元素，其頭指針front指向隊頭元素的前一個位置、尾指針rear指向隊尾元素所在的存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為()A.rear=frontB.(front+1)n=rearC.rear+1=frontD.(rear+1)n=front答案：D6.串的操作函數(shù)str定義為：A.3B.4C.5D.6答案：C7.二維數(shù)組A106采用行優(yōu)先的存儲方法，若每個

22、元素占4個存儲單元，已知元素A34的存儲地址為1000，則元素A43的存儲地址為()A.1020B.1024C.1036D.1240答案：A8.對廣義表L= (a，()執(zhí)行操作tail(L)的結(jié)果是()A.()B.()C.aD.(a)答案：B9.已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為()A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA答案：A10.已知森林F=T1，T2，T3，T4，T5，各棵樹Ti(i=1，2，3，4，5)中所含結(jié)點的個數(shù)分別為7，3，5，1，2，則與F對應(yīng)的二叉樹的右子樹中的結(jié)點個數(shù)為()A.2B.3C.8D.11答案：D11

23、.若非連通無向圖G含有21條邊，則G的頂點個數(shù)至少為()A.7B.8C.21D.22答案：B12.如圖所示的有向圖的拓?fù)湫蛄惺?)A.c，d，b，a，eB.c，a，d，b，eC.c，d，e，a，bD.c，a，b，d，e答案：B13.對關(guān)鍵字序列(6，1，4，3，7，2，8，5)進(jìn)行快速排序時，以第1個元素為基準(zhǔn)的一次劃分的結(jié)果為()A.(5，1，4，3，6，2，8，7)B.(5，1，4，3，2，6，7，8)C.(5，1，4，3，2，6，8，7)D.(8，7，6，5，4，3，2，1)答案：C14.分塊查找方法將表分為多塊，并要求()A.塊內(nèi)有序B.塊間有序C.各塊等長D.鏈?zhǔn)酱鎯Υ鸢福築15.便

24、于進(jìn)行布爾查詢的文件組織方式是()A.順序文件B.索引文件C.散列文件D.多關(guān)鍵字文件答案：D二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）請在每個空格中填上正確答案。錯填、不填均無分。1.數(shù)據(jù)的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是借助_指針_表示數(shù)據(jù)元素之間的邏輯關(guān)系。2.如果需要對線性表頻繁進(jìn)行_插入_或_刪除_操作，則不宜采用順序存儲結(jié)構(gòu)。3.如圖所示，可以利用一個向量空間同時實現(xiàn)兩個類型相同的棧。其中棧1為空的條件是top1=0，棧2為空的條件是top2=n-1，則“棧滿”的判定條件是_ top1>top2(或top2=top1-1或top1=top2+1)。4

25、.靜態(tài)存儲分配的順序串在進(jìn)行插入、置換和_聯(lián)接_等操作時可能發(fā)生越界。5.廣義表L=（a，（b，( )）的深度為_3_。6.任意一棵完全二叉樹中，度為1的結(jié)點數(shù)最多為_1_。7.求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中_邊_的數(shù)目正相關(guān)。8.在5階B樹中，每個結(jié)點至多含4個關(guān)鍵字，除根結(jié)點之外，其他結(jié)點至少含_2_個關(guān)鍵字。9.若序列中關(guān)鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是_穩(wěn)定_的。10.常用的索引順序文件是_ ISAM _文件和_ VSAM _文件。三、解答題(本大題共4小題，每小題5分，共20分)1.答案：2.由字符集s，t，a，e，i及其在電文

26、中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據(jù)該哈夫曼樹進(jìn)行譯碼，寫出原來的電文。答案：eatst(說明：每個字母1分)（5分）3.已知無向圖G的鄰接表如圖所示，(1)畫出該無向圖；(2)畫出該圖的廣度優(yōu)先生成森林。4.對序列(48，37，63，96，22，31，50，55，11)進(jìn)行升序的堆排序，寫出構(gòu)建的初始(大根)堆及前兩趟重建堆之后的序列狀態(tài)。初始堆：第1趟：第2趟：答案：初始堆：（96，55，63，48，22，31，50，37，11）（2分）第1趟：（63，55，50，48，22，31，11，37，96）（2分）第2趟：（55，48，5

27、0，37，22，31，11，63，96）（1分）四、算法閱讀題(本大題共4小題，每小題5分，共20分)1.閱讀下列算法，并回答問題：(1)無向圖G如圖所示，寫出算法f30(&G)的返回值；(2)簡述算法f30的功能。#define MaxNum 20int visitedMaxNum；void DFS(Graph *g，int i)；/*從頂點vi出發(fā)進(jìn)行深度優(yōu)先搜索，訪問頂點vj時置visitedj為1*/int f30(Graph *g)int i，k；for (i=0； i<g->n； i+)*g->n為圖g的頂點數(shù)目*visitedi=0；for (i=k=0

28、； i<g->n; i+)if (visitedi=0)k+；DFS(g，i)；return k；(1)(2)答案：（1）3（3分）（2）返回?zé)o向圖g中連通分量的個數(shù)。（2分）2.假設(shè)學(xué)生成績按學(xué)號增序存儲在帶頭結(jié)點的單鏈表中，類型定義如下：typedef struct Node int id;/*學(xué)號*/int score；/*成績*/struct Node *next； LNode， *LinkList；閱讀算法f31，并回答問題：(2)簡述算法f31的功能。void f31(LinkList A, LinkList B)LinkList p, q;p=A->next;q

29、=B->next;while (p && q)if (p->id<q->id)p=p->next;else if (p->id >q->id)q=q->next;else if (p->score <60)if (q->score <60)p->score=q->score;else p->score=60;p=p->next;q=q->next;(1)(2)答案：3.閱讀下列算法，并回答問題：(1)設(shè)串s=OneWorldOneDream，t=One，pos是一維整型數(shù)

30、組，寫出算法f32(s，t，pos)執(zhí)行之后得到的返回值和pos中的值；(2)簡述算法f32的功能。int strlen(char*s)； /*返回串s的長度*/int index(char*st，char*t)；*若串t在串st中出現(xiàn)，則返回在串st中首次出現(xiàn)的下標(biāo)值，否則返回-1*/int f32(char*s, char*t, int pos) int i, j, k, ls, lt;ls=strlen(s);lt=strlen(t);if (ls=0|lt=0) return-1;k=0;i=0;do j=index(s+i, t);if (j>=0) posk+=i+j;i+=

31、j+it;while(i+it<=is && j >=0return k;(1)(2)答案：（1）2；pos0=0,pos1=8(說明：每個值1分)（3分）（2）返回串t在s中出現(xiàn)的次數(shù)，并將每次出現(xiàn)的位置依次存放在數(shù)組pos中。（2分）4.二叉排序樹的存儲結(jié)構(gòu)定義為以下類型：typedef int KeyType;typedef struct node KeyType key;/*關(guān)鍵字項*/InfoType otherinfo;/*其它數(shù)據(jù)項*/struct node *lchild, *rchild;/*左、右孩子指針*/ BSTNode, *BSTree；閱

32、讀算法f33，并回答問題：(1)對如圖所示的二叉排序樹T，寫出f33(T，8)返回的指針?biāo)附Y(jié)點的關(guān)鍵字；(2)在哪些情況下算法f33返回空指針?(3)簡述算法f33的功能。BSTNode *f33(BSTree T, KeyType x) BSTNode *p;if (T=NULL) return NULL;p=f33(T->lchild, x);if (p!=NULL) return p;if (T->key >x) return T;return f33(T->rchild, x);(1)(2)(3)答案：（1）10（2分）（2）T是空樹或T中所有結(jié)點的關(guān)鍵字均不

33、大于給定值x時，返回空指針。（2分）（3）如果二叉排序樹T中存在含有關(guān)鍵字大于給定值x的結(jié)點，則返回指針指向它們中關(guān)鍵字最小的結(jié)點，否則返回空指針。（1分）五、算法設(shè)計題（本題10分）1.假設(shè)線性表采用順序存儲結(jié)構(gòu)，其類型定義如下：#define ListSize 100typedef struct int dataListSize;int length; SeqList, *Table;編寫算法，將順序表L中所有值為奇數(shù)的元素調(diào)整到表的前端。答案：參考答案一：void f34(Table L)(或者參數(shù)說明為：SeqList *L,1分) int i,j,t;i=0;（初始化，1分）j=L-

34、>length-1;while(i<j)(循環(huán)控制，1分) while(i<j&&L->datai%2)（1分）i+;while(i<j&&L->dataj%2=0)（1分）j-;if(i<j)(條件判斷，1分)t=L->datai;（交換，2分）L->datai=L->dataj;L->dataj=t;i+;(i和j,1分)j-;(其他，如“L->”表達(dá)，1分)參考答案二：void f34(SeqList*L)(或者參數(shù)說明為：Table L,1分) int i,j=0,t;(初始化，1分

35、)for(i=0;i<L->length;i+)(循環(huán)控制，2分)if(L->datai%2)/*奇數(shù)*/（奇數(shù)處理框架，1分） if(i!=j)(避免同一元素交換，1分) t=L->datai;(交換，2分)L->datai=L->dataj;L->dataj=t;j+;（1分）（其他，如“L->”表達(dá)，1分）全國2010年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1若一個算法的時間復(fù)雜度用T(n)表

36、示，其中n的含義是（ A ）A問題規(guī)模 B語句條數(shù)C循環(huán)層數(shù) D函數(shù)數(shù)量2具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ C ）線性結(jié)構(gòu)有：順序表、棧和隊列、串A樹 B圖C棧和隊列 D廣義表3將長度為n的單鏈表連接在長度為m的單鏈表之后，其算法的時間復(fù)雜度為（ B ）AO(1) BO(m)CO(n)DO(m+n)插入到長度為m的單鏈表，需找到表尾，時間復(fù)雜度為o(m)，連接的時間復(fù)雜度為0(1),所以總的時間復(fù)雜度為0(m)4在帶頭結(jié)點的雙向循環(huán)鏈表中插入一個新結(jié)點，需要修改的指針域數(shù)量是（ C ）A2個 B3個 C4個D6個void DInsertBefore(DListNode *p,DataType x)/

37、在帶頭結(jié)點的雙鏈表中，將值為x的新結(jié)點插入結(jié)點*p之前，設(shè)pNULL DListNode *s=malloc(sizeof(ListNode);s->data=x;s->prior=p->prior; s->next=p;p->prior->next=s;p->prior=s; 5假設(shè)以數(shù)組A60存放循環(huán)隊列的元素，其頭指針是front=47，當(dāng)前隊列有50個元素，則隊列的尾指針值為（ B ）A3 B37C50 D97對于循環(huán)向量中的循環(huán)隊列，寫出通過隊頭隊尾指針表示的隊列長度公式。（front指向?qū)嶋H隊頭，rear指向?qū)嶋H隊尾的下一元素位置。）當(dāng)re

38、arfront時，隊列長度L=rear-front；當(dāng)rear<front時，L=m+(rear-front)。這兩種情況可統(tǒng)一為L=(m+(rear-front)%m，這里m為向量的大小。本題中m=606若棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，則下列說法中正確的是（ B ） A需要判斷棧滿且需要判斷?？?B不需要判斷棧滿但需要判斷?？?C需要判斷棧滿但不需要判斷?？?D不需要判斷棧滿也不需要判斷?？找驗殒湕Ｖ械慕Y(jié)點是動態(tài)分配的，可以不考慮上溢，所以無需定義stackFull運算。7若串str=”Software”，其子串的數(shù)目是（ D ）A8 B9C36 D378設(shè)有一個10階的下三角矩陣A，采用行優(yōu)先

39、壓縮存儲方式，all為第一個元素，其存儲地址為1000，每個元素占一個地址單元，則a85的地址為 （ C ）A1012 B1017C1032 D1039在n階方陣A這個下三角矩陣中，第i（i從0開始）行（0i<n）有i+1個元素，元素總數(shù)為：n(n+1)/2，并將元素放在一個向量sa0. n(n+1)/2-1中。若ij，則aij在左下三角矩陣中，sak與aij的對應(yīng)關(guān)系是k=i(i+1)/2+j。若i<j，則aij在右上三角矩陣中，sak與aij的對應(yīng)關(guān)系是k=j(j+1)/2+i。若all為第一個元素， a85與a00為第一個元素時的a(85-(11-00)= a74位置一樣，k

40、=7*8/2+4=32，則a85的地址=1000+32=1032；若a44為第一個元素， a85與a00為第一個元素時的a(85-(44-00)= a41位置一樣，k=4*5/2+1=11，則a85的地址=1000+11=1011；9允許結(jié)點共享的廣義表稱為（ D ）A純表 B線性表C遞歸表 D再入表10下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（ A ）AB樹 B樹是一種平衡的多叉樹BAVL樹 AVL樹是自平衡二叉查找樹C二叉排序樹 D哈夫曼樹 哈夫曼樹是最優(yōu)二叉樹11對下面有向圖給出了四種可能的拓?fù)湫蛄校渲绣e誤的是（ C ）A1，5，2，6，3，4 B1，5，6，2，3，4C5，1，6，3，4，2

41、 D5，1，2，6，4，312以v1為起始結(jié)點對下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（ D ）Av1，v2，v3，v4，v5，v6，v7 Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4，v7，v5，v6 Dv1，v2，v5，v6，v7，v3，v4深度優(yōu)先遍歷類似于樹的前序遍歷。其特點是盡可能先對縱深方向進(jìn)行搜索。13下列排序算法中不穩(wěn)定的是（ A ）A快速排序 B歸并排序C冒泡排序 D直接插入排序穩(wěn)定：直接插入、冒泡、歸并、基數(shù) 不穩(wěn)定：直接選擇、希爾、快速、堆14一個有序表為(1，3，9，12，32，41，45，62，75，77，82，95，100)，當(dāng)采用折半查找方法

42、查找值32時，查找成功需要的比較次數(shù)是（ B ）mid1=45，mid2=9，mid3=32A2 B3C4 D815采用ISAM組織文件的方式屬于（ D ）A鏈組織 B順序組織C散列組織 D索引組織二、填空題(本大題共10小題，每小題2分，共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。16數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示稱為_存儲結(jié)構(gòu)_。17長度為n的線性表采用單鏈表結(jié)構(gòu)存儲時，在等概率情況下查找第i個元素的時間復(fù)雜度是_O（ n）_。18下面是在順序棧上實現(xiàn)的一個?；静僮?，該操作的功能是_取棧頂_。 typedef struct DataType data100； i

43、nt top； SeqStack； DataType f18(SeqStack*S) if(StackEmpty(S) Error(”Stack is empty”)； return S->dataS->top； 19在串匹配中，一般將主串稱為目標(biāo)串，將子串稱為_模式串_。20已知廣義表C=(a(b，c)，d)，則：tail(head(tail(C)= _()_。21用6個權(quán)值分別為6、13、18、30、7和16的結(jié)點構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長度為_221_。 WPL=30×1+18×2+16×3+13×4+6

44、15;5+7×5=30+36+48+52+30+35=23122已知有向圖如下所示，其中頂點A到頂點C的最短路徑長度是_35_。23對序列55，46，13，05，94，17，42進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是_42,13,94,55,05,46,17。24高度為3的3階B-樹最少的關(guān)鍵字總數(shù)是_5_。P182一顆m（m3）階的B-樹，每個非根結(jié)點中所包含的關(guān)鍵字個數(shù)j滿足： m/2 -1jm-1。即每個非根結(jié)點至少應(yīng)有 m/2 -1個關(guān)鍵字，至多有m-1個關(guān)鍵字。（注： m/2 是指不小于（即大于等于）m/2的最小整數(shù)。）一顆高度為h的m階B-樹中最少可容納的關(guān)鍵字總數(shù)為： m/

45、2 h-1，最少可容納的結(jié)點總數(shù)為 m/2 h-1 m/2 -1以h=3，m=3為例，相應(yīng)的B-樹最少可容納的關(guān)鍵字總數(shù)為 m/2 h-1=23-1=7個。25VSAM通常作為大型索引順序文件的標(biāo)準(zhǔn)組織，其動態(tài)索引結(jié)構(gòu)采用的是_B+_。三、解答題(本大題共4小題，每小題5分，共20分)26假設(shè)二叉樹的RNL遍歷算法定義如下： 若二叉樹非空，則依次執(zhí)行如下操作： (1)遍歷右子樹； (2)訪問根節(jié)點； (3)遍歷左子樹。已知一棵二叉樹如圖所示，請給出其RNL遍歷的結(jié)果序列。GCFABDC27已知一個無向圖G=(V，E)，其中V=A，B，C，D，E，F(xiàn)，鄰接矩陣表示如下所示。請回答下列問題：(1)

46、請畫出對應(yīng)的圖G。(2)畫出圖G的鄰接表存儲結(jié)構(gòu)。28已知一組待排記錄的關(guān)鍵字序列為(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆，請給出初始建堆后的序列。 29已知一棵二叉排序樹如圖所示。 請回答下列問題： (1)畫出插入元素23后的樹結(jié)構(gòu)；(2)請畫出在原圖中刪除元素57后的樹結(jié)構(gòu)。 四、算法閱讀題(本大題共4小題，每小題5分，共20分)30已知下列程序，Ls指向帶頭結(jié)點的單鏈表。 Typedefstruct node DataType data; struct node * next; * LinkList; void f30( LinkList L

47、s ) LinkList p, q; q = Ls->next; if ( q && q->next ) Ls->next = q->next; p=q while ( p->next ) p = p->next; p->next = q; q->next = NULL;請回答下列問題：(1)當(dāng)Ls指向的鏈表如下圖所示，請畫出執(zhí)行本函數(shù)之后的鏈表的結(jié)果。(2)請簡述算法的功能。刪除單鏈表的中間結(jié)點和尾結(jié)點。31已知字符串處理函數(shù)f31程序如下。 int f31(char*strl，char*str2) while(*strl=*s

48、tr2&&(*strl!=0) strl+； str2+； return(*strl-*str2 ? l0)； 請回答下列問題： (1)若調(diào)用語句是f31(”abcde”，”abcdf)，則函數(shù)的返回值是什么?若調(diào)用語句是 f31(”abcde”，”abcde”)，則函數(shù)的返回值是什么?由于'e '對應(yīng)的ASCII碼是101，'f'對應(yīng)的ASCII碼是102，則'e ''f'=101102=-1 函數(shù)的返回值是1。函數(shù)的返回值是0。 (2)簡述該函數(shù)的功能。答：如果兩個字符串結(jié)點*strl和*strl中的字符相等，且字符串結(jié)點*strl中的字符不等于字符串結(jié)束標(biāo)識'0'，則兩個字符串結(jié)點*strl和*strl中的字符指針自加運算。如果條件不滿足，則字符串結(jié)點*strl和*strl中的字符相減。若邏輯表達(dá)式的值為非零，則條件表達(dá)式的值等于1；若邏輯表達(dá)式的值為零，則條件表達(dá)式的值等于0。32數(shù)組A中存儲有n個整數(shù)，請閱讀下列程序。 void f32(intA，int n) inti，j，k，x； k=n-l； while(k>0) i=k； k=0； for(j=O；j&l