第一篇：數(shù)據(jù)結(jié)構(gòu)試題大題編程及參考答案

數(shù)據(jù)結(jié)構(gòu)考試題參考答案

1、設(shè)順序表L中的數(shù)據(jù)元素遞增有序。試寫一算法，將數(shù)據(jù)元素x插入到順序表L的適當(dāng)位置，以保持該表的有序性。

解：存儲結(jié)構(gòu)為：

typedef struct

SeqList { DataType *data;

int MaxLen;

int len;}SeqList;算法如下：

void insertLx(SeqList &L, DataType x){ if(L.len==L.maxlen)return;int i=L.len-1;while(i>=0 && x

2、試寫一個算法，在帶頭結(jié)點(diǎn)的單鏈表L的元素x前插入一個結(jié)點(diǎn)y。解：存儲結(jié)構(gòu)如下： typedef

struct

Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下：

void insert_y_before_x(LinkList L, ElemType x, ElemType y){ Lnode *q, *p=L;

while(p->next && p->next->data!=x)p=p->next;//找x的前驅(qū)結(jié)點(diǎn)p;if(!p->next)return;// 若不存在結(jié)點(diǎn)x，則返回； q=new Lnode;q->data=y;q->next=p->next;p->next=q;}

3、試寫一個算法，統(tǒng)計帶頭指針的單鏈表L的元素個數(shù)。解：存儲結(jié)構(gòu)如下： typedef

struct

Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下： int length(LinkList L){ int len=0;Lnode *p=L;while(p){ len++;p=p->next;} return len;} 注：如果單鏈表是帶頭結(jié)點(diǎn)的，則算法如下： int length(LinkList L){ int len=0;Lnode *p=L->next;;while(p){ len++;p=p->next;} return len;}

4、試寫一個算法，在帶頭結(jié)點(diǎn)的單鏈表L的第k個結(jié)點(diǎn)后插入一個結(jié)點(diǎn)x。解：

存儲結(jié)構(gòu)如下： typedef

struct

Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下：

void insert_after_k(LinkList L, int k, ElemType x){ if(k<0)return;Lnode *q, *p=L;int i=0;while(p && inext;} //找到第k個結(jié)點(diǎn)p;if(!p)return;//若不存在第k個結(jié)點(diǎn)，則返回；

q=new Lnode;q->data=x;q->next=p->next;p->next=q;} 注：如果是在L的第k個結(jié)點(diǎn)前插入一個結(jié)點(diǎn)，則找第k-1個結(jié)點(diǎn)p，然后插入。５、試寫一個算法，在帶頭結(jié)點(diǎn)的單鏈表Ｌ中刪除所有的數(shù)據(jù)元素為x的結(jié)點(diǎn)。解：

存儲結(jié)構(gòu)如下： typedef

struct

Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下：

void Delete_all_x(LinkList L, Elemtype x){ Lnode *p, *q;p=L;while(p){ if(p->next && p->next->data==x){q=p->next;p->next=q->next;delete q;} else p=p->next;} } 注意：要刪除所有的值為x的結(jié)點(diǎn)。６、假設(shè)一個單循環(huán)鏈表Ｌ的數(shù)據(jù)域為整型，設(shè)計一個算法，求該表中所有結(jié)點(diǎn)的數(shù)據(jù)之和。解：

存儲結(jié)構(gòu)如下： typedef

struct

Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;

假設(shè)Ｌ帶頭結(jié)點(diǎn)，且Ｌ指向頭結(jié)點(diǎn)，則算法如下： int sum_Of_Data(LinkList L){ int s=0;Lnode *p=L->next;while(p!=L){s+=p->data;p=p->next;} return s;} 假設(shè)Ｌ不帶頭結(jié)點(diǎn)，且Ｌ指向循環(huán)鏈表中任何一個結(jié)點(diǎn)，則算法如下： int sum_of_data(LinkList L){ int s=0;Lnode *p=L;if(L){ s+=p->data;p=p->next;while(p!=L){ s+=p->data;p=p->next;} } return s;} 注：以上兩種情形，只要給出其中一種情形的解即可。

７、假設(shè)二叉樹用二叉鏈表存儲，設(shè)計一個算法，求二叉樹的結(jié)點(diǎn)個數(shù)。解：存儲結(jié)構(gòu)如下：

typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下： int nodes(bitree T){ if(!T)return 0;else return(1+nodes(T->lchild)+nodes(T->rchild));} ８、寫一個算法，建立二叉樹的二叉鏈表。解：存儲結(jié)構(gòu)如下： typedef char ElemType;typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下：

void creat_bitree(bitree &T){ //按擴(kuò)展的先序序列輸入結(jié)點(diǎn)，輸入‘?！硎究铡lemType ch;

cin>>ch;if(ch==’#’)T=0;else { T=new bitnode;T->data=ch;creat_bitree(T->lchuild);creat_bitree(T->rchild);} } 或者寫成以下算法：

bitree creat_bitree(void){ //按擴(kuò)展的先序序列輸入結(jié)點(diǎn)，輸入‘＃’表示空。bitree

T;ElemType ch;

cin>>ch;if(ch==’#’)T=0;else { T=new bitnode;T->data=ch;creat_bitree(T->lchuild);creat_bitree(T->rchild);} return T;}

9、假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹，并寫出后序序列。解：該二叉樹如下：

后序序列為：ACDBGJKIHFE。

10、假設(shè)一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列為DBGEHJACIF，請畫出該二叉樹，并寫出其先序序列和后序序列。解：該二叉樹如下：

先序序列為：ABDEGHJCFI；

后序序列為：DGJHEBIFCA。

11、編寫一個遞歸算法，將用二叉鏈表表示的二叉樹的所有結(jié)點(diǎn)的左、右子樹交換。解：存儲結(jié)構(gòu)如下： typedef char ElemType;typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下：

void exchange(bitree &T){if(!T)return;bitree temp;temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;exchange(T->lchild);exchange(T->rchild);}

12、試寫出二叉鏈表表示的二叉樹的先序遍歷的非遞歸算法。解：存儲結(jié)構(gòu)如下： typedef char ElemType;typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下：

void preorder(bitree T){ //先序遍歷，當(dāng)前結(jié)點(diǎn)入棧。#define MaxNum 20 bitree stack[MaxNum];int top=0;//指向棧頂?shù)南乱晃恢?。bitnode *p;p=T;while(p || top>0){while(p){cout<

data;stack[top++]=p;p=p->lchild;} if(top>0){ p=stack[--top];p=p->rchild;} } cout<

第二篇：數(shù)據(jù)結(jié)構(gòu)試題及答案

數(shù)據(jù)結(jié)構(gòu)試卷

（二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯誤的是（）。

(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間

(B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)

2．設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。

(A)2m-1(B)2m(C)2m+1(D)4m 3．設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）。

(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。

(A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有（）條邊。

(A)n(n-1)/2(B)n(n-1)(C)n

2(D)n2-1 6．設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為（）。

(A)9(B)10(C)11(D)12 7．設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點(diǎn)。

(A)n-1(B)n(C)n+1(D)2n-1 8．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。

(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8

二、填空題(24分)1.1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是____________________和__________________________。

2.2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。

typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”);

else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時間復(fù)雜度為___________，平均時間復(fù)雜度為__________。5.5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_______個空指針域。

6.6.設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_______。

7.7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。

v1??3??2??4v2??1??3v3??1??4??28.8.設(shè)某無向圖G的鄰接表為v4??1??3，則從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。

三、應(yīng)用題(36分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。

2． 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink）。

3． 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。

4． 4． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5． 5． 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。

6． 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。

數(shù)據(jù)結(jié)構(gòu)試卷

（二）參考答案

一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C

二、填空題

1.1.構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序

4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4)

三、應(yīng)用題

1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略

5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略

數(shù)據(jù)結(jié)構(gòu)試卷

（三）一、選擇題(30分)1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。

(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu) 2．下面程序的時間復(fù)雜為（）

for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。

(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；

(C)q=p->next；p->next=q->next；free(q)；

(D)q=p->next；p->data=q->data；free(q)；

4．設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。

(A)1(B)n(C)nlog2n(D)n2

5．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．設(shè)二叉排序樹中有n個結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設(shè)無向圖G中有n個頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為（）。

(A)n，e(B)e，n(C)2n，e(D)n，2e 8.設(shè)某強(qiáng)連通圖中有n個頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。

(A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。

(A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復(fù)雜度最大。

(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序

二、填空殖(48分，其中最后兩小題各6分)1.1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。

2.2.設(shè)一棵完全二叉樹中有500個結(jié)點(diǎn)，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。

3.3.設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。

4.4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。

5.5.設(shè)哈夫曼樹中共有n個結(jié)點(diǎn)，則該哈夫曼樹中有________個度數(shù)為1的結(jié)點(diǎn)。6.6.設(shè)有向圖G中有n個頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為_________。

7.7.__________遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。

8.8.設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。

9.9.不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為____________。

10.10.設(shè)有n個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為____________，右孩子結(jié)點(diǎn)的編號為___________。11.11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為___________________________。

12.12.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓?fù)湫蛄袨開___________________。

13.13.下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。

struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}

if(_______________________)return(j);else return(-1);} 14.14.下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。

typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){

if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;}

數(shù)據(jù)結(jié)構(gòu)試卷

（三）參考答案

一、選擇題

1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最后刪除結(jié)點(diǎn)B。

第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。

二、填空題

1.1.順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。

}

數(shù)據(jù)結(jié)構(gòu)試卷

（四）一、選擇題(30分)1．設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（）個結(jié)點(diǎn)。

(A)2k-1(B)2k(C)2k-1(D)2k-1 3．設(shè)某無向圖中有n個頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（）。

(A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為（）。

(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn)，則該圖中有（）條有向邊。

(A)n(B)n-1(C)m(D)m-1 6．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。

(A)3(B)4(C)5(D)8 7．設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。

(A)必須判別棧是否為滿(B)必須判別棧是否為空

(C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復(fù)雜度最大。

(A)快速排序(B)冒泡排序(C)希爾排序(D)堆

9．設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。

(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)

二、填空題(42分)1． 1． 設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為________，快速排序的平均時間復(fù)雜度為_________。

2． 2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為_________________________________________________________（設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink）。3． 3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結(jié)點(diǎn)。5． 5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進(jìn)行篩選。

6． 6． 設(shè)哈夫曼樹中共有99個結(jié)點(diǎn)，則該樹中有_________個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_____個空指針域。

7． 7． 設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當(dāng)前實(shí)際存儲________________個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置，尾指針指向當(dāng)前隊尾元素的位置）。

8． 8． 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。9． 9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。

10．10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為________________________。

11．11．設(shè)某無向圖G中有n個頂點(diǎn)，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。

12．12．設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。

13．13．設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。

14．14．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。

typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;ikey=a[i];k=a[i] % p;s->next=hashtable[k];_______________________;} }

數(shù)據(jù)結(jié)構(gòu)試卷

（四）參考答案

一、選擇題

1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A

二、填空題

1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s

數(shù)據(jù)結(jié)構(gòu)試卷

（五）一、選擇題(30分)

1．?dāng)?shù)據(jù)的最小單位是（）。

(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量

2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（）。

(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（）。

(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。

(A)“STRUCTURE”(B)“DATA”

(C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設(shè)一個有序的單鏈表中有n個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（）。

(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（）。

(A)Nl+N2+……+Nm

(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm

7．設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。

(A)25(B)10(C)7(D)1 8．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。

(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。

(A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。

(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80

二、填空題(共30分)1.1.設(shè)有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。

2.2.在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。

3.3.設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。

4.4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運(yùn)算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定先出隊列，所以又把隊列稱為_________表。

5.5.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。

6.6.設(shè)一棵完全二叉樹有128個結(jié)點(diǎn)，則該完全二叉樹的深度為________，有__________個葉子結(jié)點(diǎn)。

7.7.設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點(diǎn)i的________，第i列中所有非零元素個數(shù)之和等于頂點(diǎn)i的__________。

8.8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。

9.9.下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++)

if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實(shí)現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){

int low=0,mid,high=n-1;

while(low<=high){

________________________________;

if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1;

}

return(0);}

三、應(yīng)用題(24分)

1.1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。

3.3.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。

4.4.設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。

數(shù)據(jù)結(jié)構(gòu)試卷

（五）參考答案

一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C

二、填空題

1.1.top1+1=top2 2.2.可以隨機(jī)訪問到任一個頂點(diǎn)的簡單鏈表

3.3.i(i+1)/2+j-1 4.4.FILO，F(xiàn)IFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度

8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k

三、應(yīng)用題

1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3

數(shù)據(jù)結(jié)構(gòu)試卷

（六）一、選擇題(30分)1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。

(A)20(B)30(C)40(D)45 2．執(zhí)行一趟快速排序能夠得到的序列是（）。

(A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。

(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序

5．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。

(A)空或只有一個結(jié)點(diǎn)(B)高度等于其結(jié)點(diǎn)數(shù)

(C)任一結(jié)點(diǎn)無左孩子(D)任一結(jié)點(diǎn)無右孩子

6．一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（）。

(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設(shè)某棵三叉樹中有40個結(jié)點(diǎn)，則該三叉樹的最小高度為（）。

(A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（）。

21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結(jié)點(diǎn)。

(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔?，指針變量s指向?qū)⒁腙犃械慕Y(jié)點(diǎn)X，則入隊列的操作序列為（）。

(A)front->next=s；front=s；(B)s->next=rear；rear=s；

(C)rear->next=s；rear=s；(D)s->next=front；front=s；

12.設(shè)某無向圖中有n個頂點(diǎn)e條邊，則建立該圖鄰接表的時間復(fù)雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設(shè)某哈夫曼樹中有199個結(jié)點(diǎn)，則該哈夫曼樹中有（）個葉子結(jié)點(diǎn)。

(A)99(B)100(C)101(D)102 14.設(shè)二叉排序樹上有n個結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）。

(A)第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和

(C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和

二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（）

2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）

5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（）

7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（）

9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（）

三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復(fù)雜度為_________。

2．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語句序列為__________________________（設(shè)結(jié)點(diǎn)的指針域為next）。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。4．設(shè)無向圖G中有n個頂點(diǎn)，則該無向圖中每個頂點(diǎn)的度數(shù)最多是_________。5．設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有_______個結(jié)點(diǎn)數(shù)。

6．設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。

7．設(shè)二叉樹中結(jié)點(diǎn)的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為___________。

9．快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。

數(shù)據(jù)結(jié)構(gòu)試卷

（六）參考答案

一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B

二、判斷題

1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．錯 9．對 10．對

三、填空題

1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法

數(shù)據(jù)結(jié)構(gòu)試卷

（七）一、選擇題(30分)1．設(shè)某無向圖有n個頂點(diǎn)，則該無向圖的鄰接表中有（）個表頭結(jié)點(diǎn)。

(A)2n(B)n(C)n/2(D)n(n-1)2．設(shè)無向圖G中有n個頂點(diǎn)，則該無向圖的最小生成樹上有（）條邊。

(A)n(B)n-1(C)2n(D)2n-1 3．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。

(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹可以得到一個從小到大的有序序列。

(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷

5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（）。

(A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。

(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（）。

(A)20(B)256(C)512(D)1024 9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。

(A)1(B)2(C)3(D)4 10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。

(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;

三、填空題(30分)1.1.設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個指針域分別為left和right）。2.2.設(shè)完全有向圖中有n個頂點(diǎn)，則該完全有向圖中共有________條有向條；設(shè)完全無向圖中有n個頂點(diǎn)，則該完全無向圖中共有________條無向邊。

3.3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進(jìn)行篩選。

4.4.解決散列表沖突的兩種方法是________________和__________________。

5.5.設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點(diǎn)，21個度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有______個。

6.6.高度為h的完全二叉樹中最少有________個結(jié)點(diǎn)，最多有________個結(jié)點(diǎn)。7.7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。

8.8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。

9.9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。

10.10.下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。

struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){

int j=t;struct record x=r[s];i=s;

while(i

while(ix.key)j=j-1;if(i

while(____________________)i=i+1;if(i

}

_________________;}

數(shù)據(jù)結(jié)構(gòu)試卷

（七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B

三、填空題

1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i

5．B 10．D

數(shù)據(jù)結(jié)構(gòu)試卷

（八）一、選擇題(30分)1.1.字符串的長度是指（）。

(A)串中不同字符的個數(shù)(B)串中不同字母的個數(shù)

(C)串中所含字符的個數(shù)(D)串中不同數(shù)字的個數(shù) 2.2.建立一個長度為n的有序單鏈表的時間復(fù)雜度為（）

(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。

(A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)位置上的字符相等

(C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。

(A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設(shè)一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。

(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設(shè)一棵完全二叉樹中有65個結(jié)點(diǎn)，則該完全二叉樹的深度為（）。

(A)8(B)7(C)6(D)5 8.8.設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點(diǎn)，2個度數(shù)為2的結(jié)點(diǎn)，2個度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（）個度數(shù)為0的結(jié)點(diǎn)。

(A)5(B)6(C)7(D)8 9.9.設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。

(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊列是一種（）的線性表。

(A)先進(jìn)先出(B)先進(jìn)后出(C)只能插入(D)只能刪除

三、填空題(30分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_____________________________。

2． 2． 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個新結(jié)點(diǎn)，請在下劃線處填上正確的內(nèi)容。

typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：s->next=p->next;_________________。4． 4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink）。

5． 5． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。

6． 6． 完全二叉樹中第5層上最少有__________個結(jié)點(diǎn)，最多有_________個結(jié)點(diǎn)。7． 7． 設(shè)有向圖中不存在有向邊，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。

8． 8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。

9． 9． 設(shè)連通圖G中有n個頂點(diǎn)e條邊，則對應(yīng)的最小生成樹上有___________條邊。10． 10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。

數(shù)據(jù)結(jié)構(gòu)試卷

（八）參考答案

一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A

三、填空題

1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50

第三篇：2013臺灣省數(shù)據(jù)結(jié)構(gòu)試題及答案（推薦）

1、串的邏輯結(jié)構(gòu)與（D）的邏輯結(jié)構(gòu)不相同。A）線性表 B）棧 C）隊列 D）集合

2、廣義表head(((a,b),(c,d)))的運(yùn)算結(jié)果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)）

3、鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間（A）。

A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B）只有一部分，存放結(jié)點(diǎn)值

C）只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針

D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)

4、設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要刪除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為（A）。

A）p->next=p->next->next;B）p=p->next;C）p=p->next->next;D）p->next=p;

5、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為（C）。

A）top不變 B）top=0 C）top--D）top++

6、數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是（D）。

A）數(shù)據(jù)的邏輯結(jié)構(gòu) B）數(shù)據(jù)的存儲結(jié)構(gòu)

C）建立在相應(yīng)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)上的算法 D）包括以上三個方面

7、向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點(diǎn)時，應(yīng)執(zhí)行（D）。A)hs->next=s;

B)s->next=hs->next;hs->next=s;C)s->next=hs;hs=s;D)s->next=hs;hs=hs->next;

8、設(shè)一數(shù)列的順序為1，2，3，4，5，6，通過棧結(jié)構(gòu)不可能排成的順序數(shù)列為（B）。A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1

9、廣義表head(((a,b),(c,d)))的運(yùn)算結(jié)果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)）

10、若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個數(shù)是(B)。A）9 B）11 C）15 D）不能確定

11、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點(diǎn)的操作為（B）。A)rear=rear->next;B)front=front->next;C)rear=front->next;

D)front=rear->next;

12、n個頂點(diǎn)的圖的最小生成樹必定（D），是不正確的描述。A）不唯一 B）權(quán)的總和唯一 C）不含回路 D）有n條邊

13、串的邏輯結(jié)構(gòu)與（D）的邏輯結(jié)構(gòu)不同。A）線性表 B）棧 C）隊列 D）樹

第四篇：管理學(xué)原理試題和大題答案

管理學(xué)原理試題和大題答案

一、單項選擇[請從所給出的四個選項中，選擇一個正確答案的字母填入括號。1．關(guān)于管理的含義，下列詞語中()的表述不確切。A.激勵、約束 B．協(xié)調(diào)、溝通 C.放任、自由 D．理順、調(diào)整

2．在TL茨劃分的幾種主要的管理學(xué)理論流振中，()主張通過分析案例來研究管理學(xué)問題。A．管理過程學(xué)派 B.經(jīng)驗學(xué)派 C.系統(tǒng)管理學(xué)派 D．管理科學(xué)學(xué)派

3．管理學(xué)界對行為科學(xué)的研究是在()的基礎(chǔ)上發(fā)展起來的，并迅速成為影響巨大的理論流派。A.科學(xué)管理理論 B．人際關(guān)系學(xué)說 C.經(jīng)營管理理論 D.權(quán)變理論學(xué)派 4．下列關(guān)于計劃的描述正確的是()。

A．企業(yè)目標(biāo)是追逐利潤，因此計劃工作只需考慮經(jīng)濟(jì)效益 B．計劃工作至關(guān)重要，因此必須面面俱到 C.計劃與決策沒有什么必然的聯(lián)系 D．計劃工作在各級管理工作中普遍存在 5．銷售人員意見綜合預(yù)測方法主要適用于()。A.丸市場預(yù)測 B．技術(shù)預(yù)測 c．戰(zhàn)略規(guī)劃預(yù)測 D．財務(wù)預(yù)測

6．某企業(yè)生產(chǎn)同種產(chǎn)品有三種方案可供選擇，已知各方案的固定成本和單位變動成本分別為：甲方案5000 511 100；乙方案15000{r11 60；丙方案25000和 40，目前企業(yè)的產(chǎn)量可以達(dá)到610，那么企業(yè)應(yīng)該選擇()才能實(shí)現(xiàn)成本最低。A．甲方案 B.乙方案 C.丙方案 D．無法碗定

7．下列關(guān)于管理幅度與管理層次的描述正確的是()。A.管理幅度與管理層次共同決定組織規(guī)模 B．為了保證管理效果，管理幅度越大越好

c.當(dāng)組織規(guī)模一定時，管理幅度與管理規(guī)模成正比關(guān)系 D．管理幅度越窄，管理層次就越多，組織結(jié)構(gòu)就呈扁平型 8．領(lǐng)導(dǎo)是領(lǐng)導(dǎo)者向下屬施加影響的行為，領(lǐng)導(dǎo)的實(shí)質(zhì)在于()。A．影響 B．權(quán)利 C.職位 D.職責(zé)

9．控制系統(tǒng)是由控制主體、控制客體和控制媒體組成，符合控制目的，具有自身功能的管理系統(tǒng)，其中控制主體是指()。

A．具有上次之分的一個組織的全部行為活動 B.控制行為所需的媒介物或方式 C.控制活動所針對的人、財、物和信息

D．控制活動中的各級管理人員及其所屬的職能部門 10．下列對現(xiàn)代沖突理論的理解不確切的是()。A.沖突可以為組織帶來活力，因此管理者要制造各種沖突 B．管理者的任務(wù)主要是管理好沖突，減少不利影響 C.沖突具有正面和反面、建設(shè)性和破壞性兩種性質(zhì) D．適當(dāng)?shù)臎_突可以給組織帶來好處 11．管理的最終目的是()。

A.實(shí)現(xiàn)人與人之間關(guān)系的協(xié)調(diào) B．有效地組織資源和組織活動 C.以最少的投入獲得最大的產(chǎn)出 D.制定組織目標(biāo) 12．諸葛亮“借東風(fēng)”給周瑜的典故說明了()的重要性。A．預(yù)測 B．決策 C.計劃 D．聯(lián)合

13．激勵手段之一是“工作豐富化”，其含義是()。A.增加工作內(nèi)容 B．使工作具有挑戰(zhàn)性且富有意義 C.工作內(nèi)容更具挑戰(zhàn)性 D．消除工作的單調(diào)乏味 14．組織結(jié)構(gòu)設(shè)計的出發(fā)點(diǎn)和依據(jù)是()。A.企業(yè)目標(biāo) D．權(quán)責(zé)利關(guān)系 C.分工合作關(guān)系 D．一項管理職能

15．上級與下級的溝通中，如果上級發(fā)問：“你有意見嗎?”“你明白嗎?”這說明領(lǐng)導(dǎo)者在溝通中()。A.善于積極傾聽 B．比較謙虛 C.態(tài)度積極友好 D．善于運(yùn)用反饋

二、判斷正誤(下列各題有對有錯，對的劃√；錯的劃X并改正。每小 題2分，共20分)1．管理的一般職能來源于管理的科學(xué)性性質(zhì)，內(nèi)容是合理組織生產(chǎn)力和維護(hù)生產(chǎn)關(guān)系。()2．企業(yè)戰(zhàn)略管理的核心是對企業(yè)現(xiàn)在和未來的整體效益活動實(shí)行全局性管理。()3．計劃工作事關(guān)重大，因此，企業(yè)高層管理者一定要做好計劃工作，中下級管理人員不必做計劃。()4．頭腦風(fēng)暴法進(jìn)行預(yù)測關(guān)鍵是要取得參與人員的一致意見。()5．區(qū)分事業(yè)部制組織結(jié)構(gòu)和控股型組織結(jié)構(gòu)的最明顯特征是分支機(jī)構(gòu)(事業(yè)部和子公司)是否是獨(dú)立法人。()6．扁平型組織結(jié)構(gòu)有利于領(lǐng)導(dǎo)控制，但會影響下屬的工作積極性。()7．在一個組織中，領(lǐng)導(dǎo)的工作績效是由領(lǐng)導(dǎo)者個人的工作成績表現(xiàn)出來的。()8．根據(jù)期望理論，如果激勵的效價足夠大，則可以達(dá)到很高的激勵水平。()9．為了實(shí)現(xiàn)有效控制的要求，控制工作一定要嚴(yán)格按照計劃的標(biāo)準(zhǔn)來檢查，應(yīng)加強(qiáng)剛性原則，避免靈活性原則。()10．非正式溝通容易傳播小道消息，因此組織要極力避免。()

三、簡答題(每小題lo分，共30分。要點(diǎn)應(yīng)展開，否則酌情扣分)1．簡述泰羅科學(xué)管理理論的主要內(nèi)容。2．管理人員培訓(xùn)的內(nèi)容有哪些? 3．簡述馬斯洛的需要層次理論。

四、案例分析(20分)陳華已經(jīng)在一家IT公司工作了5個年頭。在這期間，他從普通編程員升到資深的編程分析員。他對自己所服務(wù)的這家公司相當(dāng)滿意，不管是工作職位還是收入，都讓陳華感到有成就感，而且他還為工作中的創(chuàng)造性要求所激勵。

一個周末的下午，陳華和他的朋友及同事王迪一起打高爾夫球。他了解到他所在的部門新雇了一位剛從大學(xué)畢業(yè)的編程分析員。盡管陳華是個好脾氣的人，但當(dāng)他聽說這位新來者的起薪僅比他現(xiàn)在的工資少30元時，不禁發(fā)火了。

下周一的早上，陳華找到了人事部主任李江林，問他自己聽說的事是不是真的，李江林帶有歉意地說，確有這么回事，但他試圖解釋公司的處境：“陳華，編程分析員的市場相當(dāng)緊俏，為使公司能吸引合格的人雖，我們不得不提供較高的起薪。我們非常需要增加一名編程分析員，因此我們只能這么做?！?/p>

陳華問能否相應(yīng)調(diào)高他的工資。李江林回答說：“你的工資需按照正常的績效評估時間評定后再調(diào)。你干得非常不錯!我相信老板到時會給你提薪的?！标惾A在向李扛林道了聲“打擾了!”便離開了他的辦公室，邊走邊不停地?fù)u頭，很對自己在公司的前途感到疑慮。問題：

1．本例描述的事件對陳華的工作動力會產(chǎn)生什么樣的影響?(4分)2．哪一種激勵理論可以更好地解釋陳華的困惑?簡述其理論內(nèi)容。(s分)3．你覺得李江林的解釋會讓陳華感到滿意嗎，請說明理由．(4分)4．你認(rèn)為公司應(yīng)當(dāng)對陳華采取什么措施?為什么?(4分)

管理學(xué)基礎(chǔ) 試題答案及評分標(biāo)準(zhǔn)

一、單項選擇(請從所給出的四個選項中，選擇一個正確答案的字母填入括號。每小題2分，共 30分)1．C 2．B 3．B 4．D 5．A 6．C 7．A 8．A 9，D 10．A 11．B 12．A 13．B 14．A 15．D

二、判斷正誤(下列各題有對有錯，對的劃√；錯的劃X并改正。每小題2分，共20分)1．(X)把“科學(xué)性”改為“二重性” 2．(√)

3．(X)計劃工作在各級管理人員的工作中普遍存在，均很重要 4．(X)關(guān)鍵是引起思維共振，產(chǎn)生創(chuàng)造性思維 5．(√)

6．(X)扁平型組織結(jié)構(gòu)有利于信息溝通，有利于調(diào)動下級人員的積極性 7．(X)是由被領(lǐng)導(dǎo)者的群體活動的成效表現(xiàn)出來的 8．(X)效價和期望值都較高時，才能取得較高的激勵水平

9．(X)控制工作應(yīng)該有一定的彈性，要遵循靈活性原則，及時糾正計劃中的疏忽，才可以適應(yīng)環(huán)境的變化。10．(X)非正式溝通是溝通的重要形式，充分利用可以成為正式溝通的重要補(bǔ)充。

三、簡答題(每小題10分，共30分。要點(diǎn)應(yīng)展開，否則酌情扣分)1．簡述泰羅科學(xué)管理理論的內(nèi)容。

科學(xué)管理理論是美國古典管理理論的代表，是由科學(xué)管理之父泰羅提出的。其主要內(nèi)容有：(1)制定科學(xué)的作業(yè)方法；(2)科學(xué)的選擇和培訓(xùn)工人；(3)實(shí)行有差別的計件工資制；(4)將計劃職能和執(zhí)行職能分開；(5)實(shí)行職能工長制；(6)在管理上實(shí)行例外原則。2．管理人員培訓(xùn)的內(nèi)容有哪些? 管理人員培訓(xùn)的內(nèi)容主要有：(1)業(yè)務(wù)培訓(xùn)；(2)管理理論；(3)管理能力；

(4)交際能力及心理素質(zhì)等方面。3．簡述馬斯洛的需要層次理論。馬斯洛把人類的需要分為五大層次：

第一層次的需要是生理上的需要。是為維持人類自身生命的基本需要，如食物、水、衣著、住所和睡眠。第二層次的需要是安全的需要。是有關(guān)人類避免危險的需要。

第三層次是友愛和歸屬的需要．當(dāng)生理及安全得到相當(dāng)?shù)臐M足，友愛和歸屬方面的需要 便占據(jù)主要地位。第四層次的需要是尊重的需要。人們一旦滿足了歸屬的需要，他們就會產(chǎn)生尊重的需要，即自尊和受到別人的尊重。

第五層次的需要是自我實(shí)現(xiàn)的需要，這是最高層次的需要。

馬斯洛認(rèn)為，一般的人都是按照這個層次從低級到高級，一層一層地去追求并使自己的需要得到滿足。

四、案例分析(20分)解答提示：

1．事件會對陳華的工作動力產(chǎn)生非常消極的影響，因為對于陳華來說，他在工作中所獲得的激勵主要來自于成就激勵和創(chuàng)造性激勵，而體現(xiàn)他的成就的重要表現(xiàn)或者說重要標(biāo)志之一就是薪水，當(dāng)他感覺自己的固成就感而帶來的自信受到打擊，處境很尷尬時，一個有成就需要的人就會有很強(qiáng)的受挫感，會影響其工作的動力。

2．亞當(dāng)斯的公平理論． 理論內(nèi)容；

公平理論是美國心理學(xué)家亞當(dāng)斯于20世紀(jì)60年代首先提出了一種激勵理論，又稱為社會比較理論。公平理論認(rèn)為，激勵中的一個重要因素是個人的報酬是否公平，個人主觀地將自己投入(諸如努力、經(jīng)濟(jì)、教育等許多因素)同別人相比，看自己所得的報酬是否公正或公平。如果認(rèn)為自己所獲得的報酬不公平，就可能產(chǎn)生不滿，降低產(chǎn)出的數(shù)量、質(zhì)量，甚至離開這個組織；如果認(rèn)為報酬是公平的，就會繼續(xù)在同樣的產(chǎn)出水平上工作；如果認(rèn)為個人報酬比認(rèn)為的公平報酬大，則會更加努力地工作。

該理論還指出，職工的某些不公平感雖然可以暫時忍耐，但如果長時間維持，將會帶來嚴(yán)重的后果。3．這種解釋不會讓陳華感到滿意，可以說沒有什么作用．因為陳華需要的不是對這件事本身給出一個復(fù)雜或簡單的理由，而是需要對這個事件所反映的深層次的問題給予解釋，即長久以來以及今后自己在公司中處于什么樣的地位的問題，李江華的解釋只能使陳華理解為“在公司里你無所謂，只是非常普通的一個成員”，同時還透露了一個更加不好的信息，“公司非常需要編程分析員，你不是公司可以依賴的力量，你還不如一個新人”，那么賴以支撐其努力工作的力量就不復(fù)存在了。4.如果重視老員工的作用，就不應(yīng)當(dāng)忽視他們的心理需求，公司有許多措施可以采取，最主要的是增加陳華的公平感。如果按照程序無法盡快增加陳華的薪水，那么就應(yīng)該采用其他方式提高其成就滿足感覺，讓其心理狀態(tài)至少感覺公平．比如職務(wù)提升、工作豐富化、委任陳華擔(dān)任新聘人員的指導(dǎo)教師等等。

四、簡答題(本大題共4小題，每小題5分，共20分)1.甲、乙兩人一同大學(xué)畢業(yè)后進(jìn)了同一家企業(yè)并同在一間科室工作，兩人的工資也被定在同一檔次：每月1000元。一年試用期過后，甲的工資被定為每月1200元，而乙的工資被定為每月1500元。甲拿到1200元工資后很高興，因為比原來工資增加了200元，但當(dāng)他得知乙的月工資是1500元后，則十分氣憤，工作積極性明顯下降。試通過公平理論分析甲的心理以及管理者的對策。答：（1）公平理論認(rèn)為，職工的工作動機(jī)主要受工資報酬的影響，包括絕對報酬（自己實(shí)際收入的數(shù)量）與相對報酬（自己實(shí)際收入與他人實(shí)際收入的比值）兩種。每個人都會自覺或不自覺地把自己付出的勞動和所得報酬與他人付出的勞動和所得報酬進(jìn)行橫向比較，也會把自己現(xiàn)在付出的勞動和所得報酬與自己過去付出的勞動和報酬進(jìn)行縱向比較。通過比較，如果發(fā)現(xiàn)自己的收支比例與他人的收支比例相等，便認(rèn)為是正常的、合理的，因而心情舒暢，安心工作；如果發(fā)現(xiàn)自己的收支比例低于他人的收支比例，或現(xiàn)在的收支比例低于過去的收支比例，就會產(chǎn)生不公平感，就會對工作態(tài)度、工作積極性產(chǎn)生消極影響。在本案例中，甲做縱向比較時的高興在于與過去比其工資增加了200元；但當(dāng)他與乙進(jìn)行橫向比較時，發(fā)覺自己的工資比乙少了300元，由此產(chǎn)生不公平感，導(dǎo)致工作積極性明顯下降。

（2）管理者應(yīng)對甲、乙兩人的工資差異進(jìn)行認(rèn)真分析，如果原因在于乙比甲能力強(qiáng)、貢獻(xiàn)大，應(yīng)時及對甲作出解釋，使甲重新認(rèn)定自我、找出差距所在、明確努力的方向，激發(fā)甲的工作積極性；如果原因在于管理者對甲、乙的能力與貢獻(xiàn)判斷失誤，應(yīng)及時、果斷的糾正失誤，重新制定甲、乙的工資標(biāo)準(zhǔn)。

2.俗話說“貨比三家”，消費(fèi)者購物時往往在心理上要經(jīng)歷一個復(fù)雜的過程。在購買商品時，消費(fèi)者首先借助感知與表象獲得感性認(rèn)識，再經(jīng)過思維獲得理性認(rèn)識，再加以反復(fù)比較，以決定是否購買。試由以上過程分析認(rèn)識中感知與思維的關(guān)系。答：（1）人們對事物的認(rèn)識過程，也就是人們對客觀事物個別屬性的各種不同感覺加以聯(lián)系和綜合的反映過程，這個過程主要是通過人的感覺、知覺、記憶、思維等心理活動來完成的。消費(fèi)者對商品的認(rèn)識過程，就是從感知到思維的過程，感知是形成表象并產(chǎn)生思維的直接基礎(chǔ)。

（2）感覺是對事物個別屬性的認(rèn)識，是認(rèn)識過程的開端；在感覺的基礎(chǔ)上，人們對事物的個別屬性加以綜合分析，形成知覺，對事物有了較完整的形象。感覺、知覺是認(rèn)識的初級階段――感性認(rèn)識階段。

（3）人們?yōu)榧訌?qiáng)對事物的認(rèn)識，還借助記憶把過去生活實(shí)踐感知過的東西、體驗過的情感或知識經(jīng)驗，在頭腦中重復(fù)反映出來。人們對事物的認(rèn)識過程，不僅通過感知去認(rèn)識事物的外在聯(lián)系，琮以表象的形式向思維過渡，進(jìn)一步認(rèn)識事物的一般特征和內(nèi)在聯(lián)系，全面地、本質(zhì)地把握事物的本質(zhì)。這個思維過程（包括記憶過程）是人們對客觀事物在頭腦中概括的、間接的反映，是認(rèn)識的高級階段――理性認(rèn)識階段。

3.心理學(xué)家曾作過一項實(shí)驗，這項實(shí)驗分兩段進(jìn)行：第一段，向四組大學(xué)生介紹一個陌生人。對第一組說，這是一個外傾型的人；對第二組說，這個人是內(nèi)傾型的；在第三組，先講述這個人的我外傾特征，后講述他的內(nèi)傾特征；在第四組，先講述這個人的內(nèi)傾特征，后講述他的外傾特征。然后，讓這四個組學(xué)生分別想象出對這個陌生人的印象。第一組和第二組學(xué)生得到的印象是顯然易見的。在第三和第四組中，關(guān)于這個陌生人的印象完全符合提供信息的順序，總是先提供的信息占優(yōu)勢。也就是說，第三組學(xué)生普遍把陌生人想象為外傾型，第四組普通把他想象為內(nèi)傾型。第二段，給另外兩級學(xué)生按上述第三和第四組同樣的順序描述一個人，所不同的是在先描述他的內(nèi)傾或外傾特征之后，中間插做其他事情，如讓學(xué)生作一些不太復(fù)雜的數(shù)學(xué)習(xí)題，然后再描述相反的性格特征。在這種情況下，最后描述的特征會使學(xué)生留下深刻的印象。試分析該實(shí)驗所提示的心理效應(yīng)。答：（1）該實(shí)驗證明了優(yōu)先效應(yīng)和近因效應(yīng)的客觀存在。其中，第一段實(shí)驗說明了優(yōu)先效應(yīng)的存在；第二段實(shí)驗說明了近因效應(yīng)的存在。優(yōu)先效應(yīng)是指一個人最先給人留下的印象有強(qiáng)烈的影響，它與第一印象的作用是相同的；近因效應(yīng)則是指最后給人留下的印象具有強(qiáng)烈的影響。

（2）該實(shí)驗不僅證明了優(yōu)先效應(yīng)和近因效應(yīng)的客觀存在，而且證明了兩種效應(yīng)發(fā)生作用的不同條件。一般來說，在感知陌生人時優(yōu)先效應(yīng)起著更大的作用；而在感知熟悉的人時，如果在熟悉的人的行為上出現(xiàn)某種新異的表現(xiàn)，則近因效應(yīng)起更大的作用。

4.當(dāng)我們看到教室的講臺時，我們幾乎在獲得該講臺的知覺的同時，賦予了這張講臺在教學(xué)工具方面的意義。這是思維的結(jié)果，講臺是直接的、具體的，但教學(xué)工具則是間接的，抽象的。試分析上述現(xiàn)象所表明的知覺與思維的關(guān)系。

答：該材料表明，在人的心理活動過程中，知覺與思維密不可分：知覺是思維的“窗口”，為思維提供感學(xué)信息；思維對感覺信息進(jìn)行加工處理，把知覺組織起來，使知覺獲得一定的意義。思維是對客觀事物間接的、抽象的反映，知覺則是對客觀事物直接的、具體的反映。

案例題2：

7.一企業(yè)有兩個生產(chǎn)同類產(chǎn)品的車間，A車間的凝聚力明顯弱于B車間，但A車間的生產(chǎn)效率又明顯高于B車間。

請分析以上現(xiàn)象的成因以及上級主管部門提高B車間生產(chǎn)效率的對策。答：（1）對群體凝聚力與群體生產(chǎn)效率之間的關(guān)系的研究表明，凝聚力的狀況對生產(chǎn)效率有著重大的影響，誘是除凝聚力外的另一重要變量，兩者共同影響生產(chǎn)效率。無論凝聚力強(qiáng)弱如何，積極誘導(dǎo)都能提高生產(chǎn)效率，并且在凝聚力強(qiáng)的組生產(chǎn)效率更高；而消極誘導(dǎo)則明顯降低了生產(chǎn)效率，并且在凝聚力強(qiáng)的組生產(chǎn)效率更低。此外，凝聚力強(qiáng)的群體比凝聚力弱的群體更易受誘導(dǎo)因素的影響，在積極誘導(dǎo)條件下凝聚力強(qiáng)的群體的生產(chǎn)效率更高，在消極誘導(dǎo)條件下凝聚力強(qiáng)的群體的生產(chǎn)效率反而更低。在本案例中，A車間雖然凝聚力弱于B車間，但車間主管理采取的是積極誘導(dǎo)方式；而B車間雖然凝聚力強(qiáng)于A車間，但車間主管采取的是消極誘導(dǎo)方式，而且正因為其凝聚力強(qiáng)，所以在消極誘導(dǎo)下，其生產(chǎn)效率則更低。（2）從管理角度講，上級主管部門應(yīng)對B車間主管的思想狀況、態(tài)度、動機(jī)等方面進(jìn)行了解，在此基礎(chǔ)上對其進(jìn)行教育，勸其糾正自己對車間群體的誘導(dǎo)方式；如拒不糾正，可考慮撤換其職務(wù)。

8.知識分子階層出身的人，舉止比較文雅、有修養(yǎng)，待人禮貌，但愛幻想，不大喜歡深交，遇事缺乏果斷性；農(nóng)民階層出身的人，作風(fēng)樸素，不怕苦和累，憨厚老實(shí)，但有時有自卑感，有點(diǎn)倔強(qiáng)固執(zhí)；工人階層出身的人，集體主義強(qiáng)、守紀(jì)律，情感較強(qiáng)烈直爽，講究實(shí)際。上述材料反映了什么現(xiàn)象？試分析其原因。答：（1）上述材料表明：不同階層的人具有明顯的個性差異。

（2）階級和階層因素是影響個性形成的重要因素。人總是生活在一定的社會中，在階級社會或有階級的社會里又必然是屬于一一的階級或階層的成員，作為階級或階層的成員，所形成的個性不可避免地要打上本階級或階層的烙印。

9.美國社會心理學(xué)家阿希做了一個實(shí)驗。他給被試者看一張列有聰明、靈巧、勤奮、堅定、熱情等五種品質(zhì)的表格，要求被試者想像一個具有這五種品質(zhì)的人。被試者普遍把具有這五種品質(zhì)的人想像為一個理想的友善的人。然后，他把這張表格中的熱情換為冷酷，再要求被試者根據(jù)這五種品質(zhì)想像出一個適合的人。結(jié)果發(fā)現(xiàn)，被試者普遍推翻了原來的形象，而產(chǎn)生了一個完全不同的形象。上述實(shí)驗說明了什么問題？如何克服該實(shí)驗所揭示的效應(yīng)？ 答：（1）該實(shí)驗表明：表格所列的最后那種品質(zhì)起著暈輪作用，影響了對一個人的總體印象。暈輪效應(yīng)是指我們在觀察某個人時，對于他的某種品質(zhì)或特征有清晰明顯的知覺，由于這一特征或品質(zhì)從觀察者的角度來看非常突出，從而掩蓋了對這個人其他特征和品質(zhì)的知覺，由一點(diǎn)作出對這個人整體面貌的判斷。

（2）暈輪效應(yīng)的產(chǎn)生，往往是個體在掌握有關(guān)知覺對象信息很少的情況下作出總體判斷的結(jié)果，或是只從自己的偏好出發(fā)，帶著個人偏見去衡量別人的結(jié)果。要克服暈輪效應(yīng)，必須在社會知覺過程中，堅持認(rèn)識人與事的全面性、動態(tài)性和客觀性。①要在深入了解和全面觀察、分析一個人的言行后，才對其作出評價；②要用發(fā)展的眼光看待人與事，切忌用靜止的眼光和成見去“蓋棺定論”；③要以客觀的標(biāo)準(zhǔn)評價人，不以自己的好惡為標(biāo)準(zhǔn)。

10.原蘇聯(lián)心理學(xué)家彼得羅夫斯基設(shè)計了一個實(shí)驗：被試者是一些四年級、七年級和九年級的學(xué)生。給學(xué)生一張問卷，其中有幾條關(guān)于道德問題的判斷，學(xué)生應(yīng)對這些判斷表示贊成或反對。問題很簡單，每個學(xué)生都能根據(jù)公認(rèn)的準(zhǔn)則作出回答。過了一段時間之后，把這些道德的判斷列入一張更長的項目單之中，而在學(xué)生回答之前給予暗示，指明其他人都贊成的錯誤的判斷。在這種情況下，只有極少接受暗示、屈從壓力而改變其原來的主意，絕大多數(shù)人并沒有改變主意。試分析這一實(shí)驗所揭示的問題。答：（1）該實(shí)驗表明，群體的壓力并不是人們改變主意的關(guān)鍵因素，在這種情況下關(guān)鍵因素是遵循集體的崇高思想、目的和價值觀念，具有“集體主義自決”品質(zhì)的人只在非原則性問題上表現(xiàn)出順從，而在原則性問題上則堅持已見。

（2）一個人接受多數(shù)人的意見，可能是屈服于壓力，怕被孤立；也可能是為了實(shí)現(xiàn)群體的理想和信念而采取與群體保持一致的措施，即“集體主義自決”?！凹w主義自決”指的是以集體主義思想為指導(dǎo)，對群體的意見經(jīng)過獨(dú)立分析之后所作出的行為瓜，當(dāng)認(rèn)為群體的意見正確時予以支持，并非由群體的壓力改變了他的意見；當(dāng)認(rèn)為群體的意見是一種原則性錯誤時，則抗拒群體的壓力，堅持不從眾。

31.指出管理過程學(xué)派的創(chuàng)始者，并簡要說明該學(xué)派的基本觀點(diǎn)。

答案：管理過程學(xué)派的創(chuàng)始者是法約爾。法約爾的著述很多，1916年出版的《工業(yè)管理和一般管理》是其最主要的代表作，標(biāo)志著一般管理理論的形成。他的研究則是從辦公桌前的總經(jīng)理出發(fā)的，把辦公桌前的總經(jīng)理當(dāng)作管理者作為研究對象。他認(rèn)為，管理理論是指有關(guān)管理的、得到普遍承認(rèn)的理論，是經(jīng)過普遍經(jīng)驗檢驗并得到論證的一套有關(guān)原則、標(biāo)準(zhǔn)、方法、程序等內(nèi)容的完整體系。

法約爾將管理活動分為計劃、組織、指揮、協(xié)調(diào)和控制等五大管理職能，并進(jìn)行了相應(yīng)的分析和討論。法約爾認(rèn)為管理的五大職能并不是企業(yè)管理者個人責(zé)任，它同企業(yè)經(jīng)營的其它五大活動一樣，是一種分配于領(lǐng)導(dǎo)人與整個組織成員之間的工作。

32.簡要說明例行問題及處理例行問題的特點(diǎn)。

答案：例行問題的特點(diǎn)：從根本上說，不是要每次都作決策，而是要建立某些制度、規(guī)則或政策，使得當(dāng)問題重復(fù)發(fā) 生時，不必再作決策，而只需根據(jù)已有的制度和規(guī)則按例行程序處理即可。

33.簡述管理工作中應(yīng)如何適當(dāng)?shù)叵拗坡毮苈殭?quán)。答案：適當(dāng)限制職能職權(quán)的使用：

限制使用范圍——限于解決如何做、何時做等方面的問題，再擴(kuò)大就會取消直線人員的工作； 限制使用級別——下一級職能職權(quán)不應(yīng)越過上一級直線職權(quán)

34.簡要說明主管間輪換的優(yōu)缺點(diǎn)。

答案：在主管職位間輪換。這種輪換是在組織的同一層次上的各個不同部門的主管職務(wù)上進(jìn)行的。這種輪換的目的是使將要提拔到較高層次的主管人員，在不同的職務(wù)上根據(jù)各部門的不同特點(diǎn)，學(xué)習(xí)實(shí)際的管理經(jīng)驗。這種方法不要求主管人員對部門活動有很深的了解，而是強(qiáng)調(diào)他們?nèi)婀芾砑寄艿奶岣撸顾麄兎e累在不同管理部門的經(jīng)驗，以勝任較高層次上的管理工作。這種輪換的優(yōu)點(diǎn)是可以開闊主管人員的視野，了解各部門的特點(diǎn)及其相互關(guān)系，培養(yǎng)全面綜合管理能力；同時，也可以從中考察他們的適應(yīng)能力和實(shí)際的管理能力。缺點(diǎn)則是這種輪換會影響各個部門的相對穩(wěn)定性。

2008—2009學(xué)第一學(xué)期《管理學(xué)基礎(chǔ)》試題及答案

1．關(guān)于管理的含義，下列選項中(C)的表述不確切。A.激勵、約束 B．協(xié)調(diào)、溝通 C．放任、自由 D.理順、調(diào)整

2．梅奧等人通過霍桑試驗提出了不同于古典管理理論的新觀點(diǎn)和新思想，創(chuàng)立了(B)A.人文關(guān)系學(xué)說 B．人際關(guān)系學(xué)說 C.行為科學(xué)學(xué)說 D．社會關(guān)系學(xué)說

3．下列關(guān)于計劃工作基本特征的描述不準(zhǔn)確的是(A)。A．計劃是高層管理者的職責(zé)范疇 B．計劃工作居首要地位 C.計劃工作是有目的的行為 D．計劃工作要講究效率

4．企業(yè)目標(biāo)并不是一成不變的，應(yīng)根據(jù)外部環(huán)境的變化及時調(diào)整與修正，使其更好 地實(shí)現(xiàn)企業(yè)的宗旨，這就是確定企業(yè)目標(biāo)的(C)原則。A．現(xiàn)實(shí)性 B．協(xié)調(diào)性 C.權(quán)變性 D．關(guān)鍵性

5．下面決策方法中，選項(D)具有“匿名性”的特點(diǎn)。A.群眾評議法 B．哥頓法 C.頭腦風(fēng)暴法 D．特爾菲法

6．銷售人員意見綜合預(yù)測方法主要適用于(A)。A．市場預(yù)測 B．長期預(yù)測 C．戰(zhàn)略規(guī)劃預(yù)測 D．財務(wù)預(yù)測

7．某產(chǎn)品有三個生產(chǎn)方案，其成本狀況為：甲方案固定成本為5000，單位變動成本為lOO；乙方案固定成本為12000，單位變動成本為60；丙方案固定成本為30000，單位變動成本為30。若丙方案為最佳方案，則產(chǎn)量為(D)。A．150 B．300 C.500 D．700

8．20世紀(jì)初期，有一位社會學(xué)家提出了建立“理想的組織模式”的設(shè)想，他就是(C)A.巴納德 B．孔茨 C.韋伯 D．厄威克

9．如果企業(yè)進(jìn)行小批量產(chǎn)品的生產(chǎn)，那么，它需要根據(jù)顧客的要求進(jìn)行設(shè)計、生產(chǎn)，對企業(yè)人員技術(shù)水平要求較高，這種企業(yè)適于采用(B)組織形式。A.集權(quán)式 B．分權(quán)式 C.均權(quán)式 D．不確定

lo．評價管理者的領(lǐng)導(dǎo)能力和影響能力，有關(guān)信息的獲得來源于(B)。A.上級人員 B．下屬人員 C.高層領(lǐng)導(dǎo) D．協(xié)作部門

11．領(lǐng)導(dǎo)理論的發(fā)展大致經(jīng)歷了三個階段，(A)側(cè)重于研究領(lǐng)導(dǎo)人的性格、素質(zhì)方面的特征。A．性格理論階段 B．行為理論階段 C.效用領(lǐng)導(dǎo)階段 D．權(quán)變理論階段

12．布萊克和莫頓在管理方格理論中對最具代表性的五種領(lǐng)導(dǎo)類型進(jìn)行了詳細(xì)分析，其中任務(wù)式領(lǐng)導(dǎo)的特點(diǎn)是(A)。A．對生產(chǎn)和工作的完成情況很關(guān)心，很少注意下屬的士氣、情緒和發(fā)展?fàn)顩r B．對生產(chǎn)和人的關(guān)心度都很小，領(lǐng)導(dǎo)僅扮演“信使”的角色 C.注重創(chuàng)造一種良好的人際環(huán)境，不關(guān)心任務(wù)完成情況 D．對人和任務(wù)都給予中等程度的關(guān)心，維持正常的生產(chǎn)效率和說得過去的土氣

13．控制系統(tǒng)是由控制主體、控制客體和控制媒體組成的具有自身目標(biāo)和功能的管理系統(tǒng)。其中控制主體是指(D)。A．具有主次之分的一個組織的全部行為活動 B．控制行為所需的媒介物或方式 C.控制活動所針對的人、財、物和信息 D．控制活動中的各級管理人員及其所屬的職能部門

14.下列對現(xiàn)代沖突理論的理解不確切的是(A)。A．沖突可以為組織帶來活力，因此管理者要制造各種沖突 B．管理者的任務(wù)主要是管理好沖突，減少不利影響 C．沖突具有正面和反面、建設(shè)性和破壞性兩種性質(zhì) D．適當(dāng)?shù)臎_突可以給組織帶來好處

15．下列關(guān)于管理幅度與管理層次的描述正確的是(A)。A．管理幅度與管理層次共同決定組織規(guī)模 B.為了保證管理效果，管理幅度越大越好 C．當(dāng)組織規(guī)模一定時，管理幅度與管理規(guī)模成正比關(guān)系 D。管理幅度越窄，管理層次就越多，組織結(jié)構(gòu)就呈扁平型

二、判斷并改錯(下列各題有對有錯，對的劃√；錯的劃X并改正。16．泰羅科學(xué)管理的中心問題就是提高勞動生產(chǎn)率。()

17，計劃工作是講求效率的。因此，制定計劃時必須考慮經(jīng)濟(jì)效益，其他的都是次要的。()18．組織作為人的集合，就是每個人的加總。()19．運(yùn)用頭腦風(fēng)暴法進(jìn)行預(yù)測關(guān)鍵是要取得參與人員的一致意見。()20．當(dāng)外部環(huán)境處于劇烈變化狀態(tài)時，企業(yè)可以通過建立一些臨時性的部門、通暢的信息傳遞、分權(quán)程度的提高，發(fā)揮員工的潛力，減少外部環(huán)境對企業(yè)造成的不利影響。()21．扁平型組織結(jié)構(gòu)有利于領(lǐng)導(dǎo)控制，但會影響下屬的工作積極性。()22．阿吉利斯認(rèn)為，領(lǐng)導(dǎo)方式會影響人的成熟過程，如果讓職工長期從事簡單的重 復(fù)性工作會造成依賴心理，從而阻礙其向成熟發(fā)展。()23．表彰和獎勵能起到激勵的作用，批評和懲罰不能起到激勵的作用。()24，全面質(zhì)量管理強(qiáng)調(diào)的是全員參與和全過程的質(zhì)量管理。()25．現(xiàn)代沖突理論認(rèn)為，管理者應(yīng)盡可能防止和消除沖突。()

一、單項選擇(請從四個選項中選擇一個最優(yōu)答案的字母填入括號。每小題2分，共30分)1．C 2．B 3．A 4．C 5．D 6．A 7．D 8．C 9．B 10．B 11．A 12．A 13．D 14．A 15．A

二、判斷并改錯(下列各題有對有錯，對的劃√；錯的劃X并改正。每小題2分，共20分)16．(√)。17．(X)制定計劃時除了考慮經(jīng)濟(jì)效益外，還要考慮非經(jīng)濟(jì)方面的因素。18．(X)組織作為人的集合，不是簡單的毫無關(guān)聯(lián)的個人的加總，而是為了實(shí)現(xiàn)一定目的，有意識地協(xié)同勞動而產(chǎn)生的群體。19．(X)運(yùn)用頭腦風(fēng)暴法進(jìn)行預(yù)測的關(guān)鍵是引起思想共振，產(chǎn)生創(chuàng)造性思維。20．(√)21．(X)扁平型組織結(jié)構(gòu)有利于信息溝通，有利于調(diào)動下級人員的積極性。22．(√)23．(X)獎勵和懲罰不一定能起到激勵作用，只有得當(dāng)?shù)莫剟詈蛻土P，才能起到有效的激勵作用。24．(√)25．(X)現(xiàn)代沖突理論認(rèn)為，管理者要管理好沖突，減少不利影響，充分發(fā)揮積極作用。

第五篇：數(shù)據(jù)結(jié)構(gòu)試題及答案10

《數(shù)據(jù)結(jié)構(gòu)》自考復(fù)習(xí)思考試題

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上（）

A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關(guān)系的有限集合

2.在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為（）A.n-i+1

B.i C.i+1

D.n-i 3.若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則該鏈表為空的判定條件是（）A.head==NULL

B.head->next==NULL C.head!=NULL

D.head->next==head 4.引起循環(huán)隊列隊頭位置發(fā)生變化的操作是（）A.出隊

B.入隊

C.取隊頭元素

D.取隊尾元素

5.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是（）A.2，4，3，1，5，6

B.3，2，4，1，6，5 C.4，3，2，1，5，6

D.2，3，5，1，6，4 6.字符串通常采用的兩種存儲方式是（）A.散列存儲和索引存儲

B.索引存儲和鏈?zhǔn)酱鎯?C.順序存儲和鏈?zhǔn)酱鎯?/p>

D.散列存儲和順序存儲

7.設(shè)主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進(jìn)行的無效位移次數(shù)為（）A.m

B.n-m C.n-m+1

D.n 8.二維數(shù)組A［12］［18］采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為（）A.429

B.432 C.435

D.438 9.對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是（）A.(e,f)

B.((e,f))C.(f)

D.()10.下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是（）11.n個頂點(diǎn)的強(qiáng)連通圖中至少含有（）A.n-1條有向邊

B.n條有向邊 C.n(n-1)/2條有向邊

D.n(n-1)條有向邊

12.對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為（）A.(19，23，56，34，78，67，88，92)

B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)

D.(19，23，67，56，34，78，92，88)13.若在9階B-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個數(shù)為（）

A.4

B.5 C.8

D.9 14.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹（）A.其形態(tài)不一定相同，但平均查找長度相同

B.其形態(tài)不一定相同，平均查找長度也不一定相同 C.其形態(tài)均相同，但平均查找長度不一定相同 D.其形態(tài)均相同，平均查找長度也都相同

15.ISAM文件和VSAM文件的區(qū)別之一是（）A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取 C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動態(tài)索引結(jié)構(gòu) D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤

二、填空題(本大題共10小題，每空2分，共20分)16.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的____________。17.刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(diǎn)(存在)應(yīng)執(zhí)行的語句是____________。18.棧下溢是指在____________時進(jìn)行出棧操作。

19.已知substr(s,i,len)函數(shù)的功能是返回串s中第i個字符開始長度為len的子串，strlen(s)函數(shù)的功能是返回串s的長度。若s=″ABCDEFGHIJK″,t=″ABCD″,執(zhí)行運(yùn)算substr(s,strlen(t), strlen(t))后的返回值為____________。

20.去除廣義表LS=(a1,a2,a3,??，an)中第1個元素，由其余元素構(gòu)成的廣義表稱為LS的____________。

21.已知完全二叉樹T的第5層只有7個結(jié)點(diǎn)，則該樹共有____________個葉子結(jié)點(diǎn)。22.在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的____________。

23.當(dāng)關(guān)鍵字的取值范圍是實(shí)數(shù)集合時，無法進(jìn)行箱排序和____________排序。24.產(chǎn)生沖突現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù)的____________。

25.假設(shè)散列文件中一個桶能存放m個記錄，則桶“溢出”的含義是，當(dāng)需要插入新的記錄時，該桶中____________。

三、解答題(本大題共4小題，每小題5分，共20分)26.假設(shè)以數(shù)組seqn［m］存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。(1)寫出隊滿的條件表達(dá)式；(2)寫出隊空的條件表達(dá)式；

(3)設(shè)m=40,rear=13,quelen=19,求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達(dá)式。

27.已知一棵二叉樹的中序序列為ABCDEFG，層序序列為BAFEGCD，請畫出該二叉樹。28.畫出下圖所示有向圖的所有強(qiáng)連通分量。

29.對7個關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。(1)假設(shè)關(guān)鍵字集合為{1,2,3,4,5,6,7}，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列；(2)對所舉序列進(jìn)行快速排序，寫出排序過程。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.閱讀下列算法，并回答問題：(1)設(shè)順序表L=(3,7,11,14,20,51)，寫出執(zhí)行f30(&L,15)之后的L；(2)設(shè)順序表L=(4,7,10,14,20,51)，寫出執(zhí)行f30(&L,10)之后的L；(3)簡述算法的功能。

void f30(SeqList*L, DataType x){

int i =0, j;

while(ilength && x>L->data［i］)i++;

if(ilength && x==L->data［i］){

for(j=i+1;jlength;j++)

L->data［j-1］=L->data［j］;

L->length--;

} else {

for(j=L->length;j>i;j--)

L->data［j］=L->data［j-1］;

L->data［i］=x;

L->length++;

} } 31.已知圖的鄰接表表示的形式說明如下：

#define MaxNum

//圖的最大頂點(diǎn)數(shù) typedef struct node {

int

adjvex;

//鄰接點(diǎn)域

struct node *next;

//鏈指針域

} EdgeNode;

//邊表結(jié)點(diǎn)結(jié)構(gòu)描述 typedef struct {

char vertex;

//頂點(diǎn)域

EdgeNode

*firstedge;

//邊表頭指針 } VertexNode;

//頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述 typedef struct {

VertexNode adjlist［MaxNum］;

//鄰接表

int n, e;

//圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù) } ALGraph;

//鄰接表結(jié)構(gòu)描述

下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。

typedef enum {FALSE, TRUE} Boolean;Boolean visited［MaxNum］;void DFSForest(ALGraph *G){

int i;

for(i=0;in;i++)visited［i］=

(1)

;

for(i=0;in;i++)if(!visited［i］)DFSTree(G,i);} void DFSTree(ALGraph *G, int i){

EdgeNode *p;

visited［i］=TRUE;

p=G->adjlist［i］.firstedge;

while(p!=NULL){

if(!visited［p->adjvex］){

printf(″<%c,%c>″,G->adjlist［i］.vertex，G->adjlist［p->adjvex］.vertex);

(2)

;

}

(3)

;

} } 32.閱讀下列算法，并回答問題：

(1)假設(shè)數(shù)組L［8］={3,0,5,1,6,4,2,7}，寫出執(zhí)行函數(shù)調(diào)用f32(L，8)后的L；(2)寫出上述函數(shù)調(diào)用過程中進(jìn)行元素交換操作的總次數(shù)。void f32(int R［］,int n){

int i,t;

for(i=0;i

while(R［i］!=i){

t=R［R［i］］;

R［R［i］］=R［i］;

R［i］=t;

} } 33.已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：。請在空缺處填入適當(dāng)內(nèi)容，使其成為一個完整算法。void f33(LinkList L, LinkList H［］, int m){//由帶頭結(jié)點(diǎn)的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在 int i,j;

LinkList p,q;

for(i=0;i

H［i］=

(1)

;

p=L->next;

while(p)

{

q=p->next;

j=p->key%m;

(2)

;

H［j］=p;

(3)

;

}

free(L);

}

五、算法設(shè)計題(本大題10分)34.假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)的類型說明如下所示： typedef char DataType;typedef struct node {

DataType data;

struct node *lchild, *rchild;

//左右孩子指針

struct node *parent;

//指向雙親的指針 } BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結(jié)點(diǎn)的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點(diǎn)在二叉樹的中序序列中的后繼。

(1)就后繼的不同情況，簡要敘述實(shí)現(xiàn)求后繼操作的方法；

(2)編寫算法求px所指結(jié)點(diǎn)的中序序列后繼，并在算法語句中加注注釋。數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)答案

一、單項選擇題 1.(B)2.(D)3.(A)4.(A)5.(D)6.(C)7.(C)8.(A)9.(B)10.(A)11.(B)12.(D)13.(C)14.(B)15.(C)

二、填空題(本大題共10小題，每空2分，共20分)16.存儲結(jié)構(gòu) 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.棧空

19.“DEFG” //注意雙引號不能少 20.表尾

21.２^(I-2)+M/2 葉子結(jié)點(diǎn)． 22.入度 23.基數(shù) 24.同義詞

25.已有m個同義詞記錄

三、解答題(本大題共4小題，每小題5分，共20分)26.(1)quelen == m(2)quelen == 0(3)(13quelen + m)% m 27.B

/

A F

/

E G

/

C

D 28.3個: a、bce、dfg 29.我們知道，對n個關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個關(guān)鍵字比較。

這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分(1)4 1 3 2 6 5 7

或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)自己列吧 :)

四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在順序表L中查找數(shù)x, 找到，則刪除x，沒找到，則在適當(dāng)?shù)奈恢貌迦離，插入后，L依然有序.31.(1)FALSE //初始化為未訪問

(2)DSFTree(G, p->adjvex);//從相鄰結(jié)點(diǎn)往下繼續(xù)深度搜索(3)p = p->next;//下一個未訪問的相鄰結(jié)點(diǎn)

32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次

33.(1)NULL

//初始化

(2)p->next = H[ j ] //和下面一句完成頭插法(3)p = q;

//繼續(xù)遍歷L

五、算法設(shè)計題(本大題10分)34.1)

a)*px 有右孩子，則其右孩子為其中序序列中的后繼

b)*px 無右孩子，從*px開始回溯其祖先結(jié)點(diǎn)，找到第1個身份為左孩子的結(jié)點(diǎn)，找到，則該結(jié)點(diǎn)的父結(jié)點(diǎn)為*px的中序序列中的后繼。找不到，則無后繼。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子

BinTNode *q, *qp;

q = px;while(qp = q->parent){ //未回溯到根結(jié)點(diǎn)

if(qp->lchild == q)return qp;//找到1)b)所述結(jié)點(diǎn)

q = qp;//往上回溯 }

return NULL;//未找到 }