数据结构与算法期末考试,数据结构与算法期末考试题及详解

数据结构与算法试题，高分，求答案啊

3?已知一株非空二元树，其先根与中根遍历的结果为：

先根：ABCDEFGHI ?

中跟：CBEDAGFHI

将此二元树构造出来。

答：????????????????? A

/???? \

B??????? F

/? ?\??????/? ?\

C?? ? D?? G??? H

/??????????? ??? \

I????????????????? E

4.分析下列程序的运行时间：

A)????? void? mystery(int n)

{int? i, j, k;

for(i=1; in; i++)

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

for(k=1; k=j; k++)

{some? statement? requiring? O(1)? time;}

}

我的答案是 n3 不过不是很确定

B）void? podd(int? n)

{int? I, j, x, y;

for(I=1; I=n; I++)

if( odd(I ) )

{for(j=I; j=n; j++)

x=x+1;

for(j=1; j=I; j++)

y=y+1;

}

}

n2 也不是很确定

5?已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。

表达式对应的二叉树为

所以对应的前缀为：-*+3bsin+x5/a*xx

后缀为：3b+x5+sin*axx*/-

三 实现下列算法

在指针实现的线性表L中，实现在线性表L中删除关键字为x的结点。

答：

int visited[n];

void dfs(Graph g, int i)

{edgeNode *t;

printf(“%4d”,i);

visited[i]=1;

t=g[i];

while(t!=NULL) {

if (visited[t-vno]= =0)

dfs(g,t-vno);

t=t-next;

}

}

在线索二元树中，由结点P求其中根顺序的后继。

答：

typedef enum {lLINK ,THREAD} PointerTag ;? // LINK==0; 指针，

THREAD==1；线索

typedef struct BinThrNode {

TElemType data；

struct BinThrNode *lchilid， *rchild；

PointerTag ltag， rtag；

}? BinThrNode,* BinThrTree;

中序遍历线索二叉树

p所指结点前驱的求法：

当p-ltag==THREAD时，前驱为p-lchild；

当p-ltag==LINK时，前驱为p-lchild的最右下方结点。

在二元查找树F中，实现插入记录R。

答：

Void INSERT(records R, BST F)

{if(F= =NULL)

{F=new celltype;

F- data=R;

F-lchild=NULL;

F-rchild=NULL;}

else if(R,keyF-data.key)

INSERT(R,F-lchild);

else if(R,keyF-data.key)

INSERT(R,F-rchild);

}

四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）

五 设要分类的数据存放在数组A

3 1 4 1 5 9 2 6 5 3

中，要进行堆分类，首先得为其建立一个初始堆，试画出初始建设堆过程中，二元树的变化和数组A的变化。

谁有数据结构的期末试题，借我参考下马上考试了

A：

06－07第一学期期末考试试卷

试卷代码：03266A 授课课时：112

课程名称：数据结构与算法 适用对象：本科

一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)

1.数据结构被形式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。

A.操作 B.映像 C.存储 D.关系

2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____。

A.必须连续的 B.部分地址必须连续的 C.一定是不续的 D.连续不连续都可以

3.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是____。

A.edcba B.decba C.dceab D.abcde

4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。

A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1

5.栈和队列的共同点是____。

A.都是先进后出 B.都是先进先出

C.只允许在端点处插入、删除元素 D.没有共同点

6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。

A. s-next = p-next; p-next=s; B. p-next = s-next; s-next = p;

C. q-next = s; s-next = p; D. p-next = s; s-next = q;

7.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是____。

A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF

8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。

A. 2h B. 2h-1 C. 2h +1 D. h +1

9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是____。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

10.具有6个顶点的无向图至少应有____条边才能确保是一个连通图。

A. 5 B. 6 C. 7 D. 8

11.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。

A. n B. n/2 C. (n+1)/2 D. (n-1)/2

12.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为____。

A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序

二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)

1.在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点。

2.对n个元素的序列进行起泡排序时，最少的比较次数是 。

3.空串是 ，其长度等于0。

4.一棵有n个结点的满二叉树共有 个叶子结点。

5.在散列函数H(key)=key % p中，p应取 。

6.已知模式串t=‘abcaabbabc’， 其用KMP法求得的每个字符对应的next函数值为 。

三、简答题(本大题共3小题，每小题5分，共15分)

1.在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述在什么情况下使用顺序表比链表好？

2.简述什么是稳定的排序，什么是不稳定的排序。

3.下列中缀表达式对应的后缀形式是什么？

(1) (A + B) * D + E / (F + A * D) + C

(2) A B|| ! (E F) {注：按C的优先级)

四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)

1.数据元素不是数据的最小单位( )。

2.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( )

3.AOE网是一种带权的无环连通图。( )

4.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的( )。

5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )

6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )

7.折半插入排序是稳定的。( )

8.在散列法中，使用双散列函数可保证绝对不产生冲突。( )

9.消除递归不一定需要使用栈( )

10.堆排序是交换排序的一种。( )

五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）

1．阅读后分析下面程序段的功能是什么? （6分）

SeqStack S1, S2, tmp;

DataType x; //设栈tmp和S2已做过初始化

while ( ! StackEmpty (S1))

{ x=Pop(S1) ;

Push(tmp,x);

}

while ( ! StackEmpty (tmp) )

{ x=Pop(tmp);

Push( S2, x);

}

2.某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。（7分）

3.设散列表为HT[13], 散列函数为 H (key) = key %13。用线性探测再散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）

4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试写出使用希尔排序(增量为5,2,1)方法每趟排序后的结果。（6分）

六、算法设计题（本题共18分，第1小题10分，第2小题8分）

1.编写一个算法frequency，统计在一个输入字符串中所含各个不同字符出现的频度。用适当的测试数据来验证这个算法。(10分)

2.在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，并统计树中具有度为1的结点数目的算法。要求给出二叉链表的类型定义。(8分)

答案：

06－07第一学期

期末考试参考答案与评分标准

试卷代码：03266A 授课课时：112

课程名称：数据结构与算法 适用对象：本科

一、单项选择题(每小题2分，共24分。)

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

7. D 8. B 9. D 10. A 11. C 12. D

二、填空题(每空1分，共7分。)

1.父(或前驱)， 1

2. n-1

3. 不包含任何字符的串

4. (n+1)/2

5. 素数

6. 0111223123

三、简答题(每小题5分，共15分)

1.答：① 顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小(1)，存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

2.答：在排序序列中，任何两个相等的关键字Ki=Kj,如果在排序前的序列中Ki领先于Kj，若在排序后的序列中Ki仍领先于Kj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Kj领先于Ki，则称所用的排序方法是不稳定的。

3.答：各中缀表达式的后缀形式如下：

(1)AB+D*EFAD*+/+C+

(2)ABEF!||

四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)

1.T 2.F 3.T 4.F 5.F

6.F 7.T 8.F 9.T 10.F

五、分析应用题（1、4小题各6分，2、3小题各7分）

1．（6分）

答：程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。

2．（7分）

答：为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：

赫夫曼编码为：概率为0.23的字符编码为：00

　概率为0.11的字符编码为：010

概率为0.05的字符编码为：0110

概率为0.03的字符编码为：0111

概率为0.29的字符编码为：10

概率为0.14的字符编码为：110

概率为0.07的字符编码为：1110

概率为0.08的字符编码为：1111

3.（7分）

答：使用散列函数H(key)=key mod 13 有：

H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10

利用线性探查法造表：

0 1 2 3 4 5 6 7 8 9 10 11 12

78 15 03 57 45 20 31 23 36 12

1 1 1 1 1 1 4 1 2 1

搜索成功的平均搜索长度为：

ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10

4.（6分）

答： 希尔排序(增量为5,2,1)

六、算法设计题（第1小题10分，第2小题8分）

1. (10分)

include iostream.h

include”string.h”

int charnumber=128;

void frequency(strings,int C[ ]){

for(int i=0;i charnumber;i++) C[i]=0;

for( i=0;i s.length();i++) C[atoi(s[i])]++;

for( i=0;i charnumber;i++)

if(C[i]0) cout”(”i”):\t”C[i]”\t”;

}

2. (8分)

类型定义（略）

int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数

{

int num=0; //num统计度为1的结点的个数

if(bt){

QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列

while(!QueueEmpty(Q))

{ p=QueueOut(Q); printf(p-data); //出队,访问结点

if(p-lchild !p-rchild ||!p-lchild p-rchild)

num++;//度为1的结点

if(p-lchild) QueueIn(Q,p-lchild); //非空左子女入队

if(p-rchild) QueueIn(Q,p-rchild); //非空右子女入队

}

}

return(num); //返回度为1的结点的个数

}

B：

06－07第一学期期末考试试卷

试卷代码：03266B 授课课时：112

课程名称：数据结构与算法 适用对象：本科

一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)

1.数据结构被形式地定义为 (K, R)，其中K是____的有限集，R是K上的关系有限集。

A.算法 B.数据元素 C.数据操作 D.逻辑结构

2.在数据结构中，从逻辑上可以把数据结构分成____。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构

C.线性结构和非线性结构 D.内部结构和外部结构

3.以下的叙述中，正确的是____。

A.线性表的存储结构优于链式存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

4.若一个栈的入栈序列是1、2、3、… 、n，其输出序列为p1、p2、p3、… 、pn，若p1=n，则pi为____。

A. i B. n = i C. n - i +1 D.不确定

5.判断一个循环队列QU (最多元素为m) 为空的条件是____。

A. QU-front == QU-rear B. QU-front != QU-rear

C. QU-front == (QU-rear+1)%m D. QU-front != (QU-rear+1)%m

6.在某单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行____。

A. s-next = p; p-next=s; B. s-next = p-next; p-next = s;

C. s-next = p-next; p = s; D. p-next = s; s-next = p;

7.串是一种特殊的线性表，其特殊性体现在____。

A.可以顺序存储 B.数据元素是一个字符

C.可以链接存储 D.数据元素可以是多个字符

8.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是____。

A. acbed B. decab C. deabc D. cedba

9.对于一个满二叉树，m个树叶，n个结点，深度为h，则____。

A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -1

10.一个有n个顶点的无向图最多有____条边。

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

11.顺序查找法适合于存储结构为____的线性表。

A. 散列存储 B. 顺序存储或链接存储

C. 压缩存储 D. 索引存储

12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。

A. 插入排序 B.选择排序 C.快速排序 D. 归并排序

二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)

1.在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点。

2.在无权图G的邻接矩阵中，若A[i][j]等于1，则等于A[j][i] = 。

3.根据二叉树的定义，具有三个结点的二叉树有 种不同的形态。

4.空格串是指 ，其长度等于 。

5.在散列存储中，装填因子α的值越大，则存储元素时发生冲突的可能性就 。

6.已知模式串t= ‘abacabaaad’， 其用KMP法求得的每个字符对应的next函数值为 。

三、简答题(本大题共3小题，每小题5分，共15分)

1.比较静态查找与动态查找的主要区别，它们的基本运算有哪些不同？

2.逻辑结构分哪几种，存储结构有哪几种？

3.在具有n(n1)个结点的各棵不同形态树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？

四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)

1.每种数据结构都应具备三种基本运算：插入、删除、搜索( )。

2.满二叉树不一定是完全二叉树。( )

3.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( )

4.任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。( )

5.线性链表中所有结点的类型必须相同。( )

6.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关( )。

7.在散列法中解决冲突时，其装载因子的取值一定在(0，1)之间。( )

8.任何一个关键活动延迟，那么整个工程将会延迟。( )

9.平衡二叉树的左右子树深度之差的绝对值不超过1。( )

10.n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。( )

五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）

1.下述算法的功能是什么? （6分）

LinkList Demo(LinkList L)

{ // L 是无头结点单链表

ListNode *Q,*P;

if(LL-next){

Q=L;

L=L-next;

P=L;

while (P-next) P=P-next;

P-next=Q; Q-next=NULL;

}

return L;

}

2.将给定的图简化为最小的生成树，要求从顶点1出发。（7分）

3.设散列表为HT[13], 散列函数为 H (key) = key %13。用双散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个地址的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）

4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},写出使用快速排序法每趟排序后的结果。（6分）

六、算法设计题（本题共18分，第1小题10分，第2小题8分）

1.试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。(10分)

2.设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。要求给出二叉链表的类型定义。(8分)

答案：

06－07第一学期

期末考试参考答案与评分标准

试卷代码：03266B 授课课时：112

课程名称：数据结构与算法 适用对象：本科

一、单项选择题(每小题2分，共24分。)

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

7. B 8. D 9. D 10.C 11. B 12. A

二、填空题(每空1分，共7分。)

1. 无

2. 1

3. 5

4. 串中字符全为空格 ， 空格的个数

5. 大

6. 0112123422 。

三、简答题(本大题共5小题，每小题5分，共15分)

1．答：两种查找方法最大的区别在于：

静态查找方法不修改查找表；动态查找在查找不成功时，将结点插入查找表中，即有可能修改查找表；

静态查找的基本运算有建表、查找和读表元；动态查找除上述基本操作外还有初始化、插入和删除操作；

2.答：根据数据元素之间关系的不同特性，通常有下列四类基本结构：(1)集合；(2)线性结构；(3)树形结构；(4)图状结构或网状结构。有两种不同的存储结构：顺序存储结构和链式存储结构。

3.答：深度最小的那棵树的深度为2。对于这n个结点，除了一个根结点之外，其余得n-1个结点均为叶子结点，故其深度为2。该树叶子结点数为n-1，非叶子结点数为1。

四、判断题(每小题1分，共10分)

1. (T) 2. (F) 3. (T) 4. (F) 5. (T)

6. (T) 7. (F) 8. (T) 9. (T ) 10.(T)

五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）

1.（6分）

答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。

2.（7分）

答:

3.（7分）

答：使用散列函数H(key)=key mod 13 有：

H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10

利用双散列法造表：Hi =（Hi-1+RH(key)）%13, Hi =H(key)

0 1 2 3 4 5 6 7 8 9 10 11 12

78 15 03 57 45 20 31 36 23 12

1 1 1 1 1 1 3 5 1 1

搜索成功的平均搜索长度为：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/10

4.（6分）

答：

六、算法设计题（第1小题10分，第2小题8分）

1.(10分)

答：

(1) 定义链表结构

struct DoubleListNode {

char data ;

int freq;

DoubleListNode * llink, *rlink ;

};

初始时，所有结点的freq域的值都为0。

(2) 定义函数

DoubleListNode * locate ( DoubleListNode *f ; char x ) {

DoubleListNode * p, *q;

p = f→rlink; /*跳过表头结点*/

while ( p != NULL p→data != x ) p = p→rlink; /*搜索*/

if ( p ) {

p→freq ++; q = p→llink;

p→rlink→llink = q; q→rlink = p→rlink; /*从链中摘下p*/

while ( q != f q→freq p→freq ) q =q→llink;

p→llink = q;

p→rlink = q→rlink; q→rlink→llink = p;

q→rlink = p; /*在q后面插入p*/

}

return p;

}

2． (8分)

答：类型定义（略）

void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换

{

if(bt)

{ BiTree s；

s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; //左右子女交换

exchange(bt-lchild); //交换左子树上所有结点的左右子树

exchange(bt-rchild); //交换右子树上所有结点的左右子树

}

}

求北邮 数据结构期末考试试题

（三）简答题

1．简述顺序存储结构和链式存储结构的特点

答：顺序存储结构的优点无需为表示元素间的逻辑关系而增加额外的指针空间；可以随机存取表中的任一元素。缺点是必须事先进行空间分配，表的容量难以扩充；插入和删除操作时需移动大量结点，效率较低。

链式存储结构的优点是结点的存储采用动态存储，表的容量很容易扩充；插入和删除操作方便，不必移动结点，只要修改结点中的指针即可。缺点是每个结点中需要有指针空间，比顺序存储结构的存储密度小；只能进行顺序查找结点。

2．链表中为何要引入头结点？

答：链表进行插入和删除操作时要判断是否在链表的首端操作，若在第一结点前插入新结点和删除第一个结点则会引起首指针head值的改变；否则head的值不会改变。在链表前加一个头结点（只用指针域指向链表的首结点）就避免了两种情况的判断，使程序设计简单了，程序的结构更清楚。

2． 简述由二叉树的前序、中序和后序遍历序列确定二叉树

答：在三种遍历序列中，前序序列和中序序列、中序序列和后序序列能唯一确定一棵二叉树，因为前序序列或后序序列能确定二叉树的根结点而中序序列能确定根的左、右子树。前序序列和后序序列不能唯一确定一棵二叉树，但注意树的先根序列和后根序列能唯一的确定该树，因为树的后根序列就是二叉树的中序序列。

4．快速排序最坏情况的改进

答：当待排序的序列为有序序列时快速排序的效率很低，蜕变为冒泡排序了，为了避免这种情况，选序列的首元素为枢轴元素（或称基准元素）改为选序列的首元素、中间元素和末元素三个元素中中间大的元素为基准元素（简单的就用中间元素为基准），这可大大改善快速排序的性能。例如：

8，0，4，9，6，3，5，2，7，1

以中间大元素6为基准，基准元素与最后元素交换后为：

8，0，4，9，1，3，5，2，7，6

↑ ↑

i j

将i,j指的内容比较，若i的内容比基准小，i推进，否则i停下，开始进行j的比较；若j的内容比基准大，j推进,，否则j停下，将i的内容与j的内容交换，重复上述过程，直至jI SPAN止，将基准与i的内容交换，一次分段完成。,如下所示：

8，0，4，9，1，3，5，2，7，6

2，0，4，9，1，3，5，8，7，6

2，0，4，5，1，3，9，8，7，6

2，0，4，5，1，3，6，8，7，9

5．简述动态规划法的基本思想

答：为了节约重复求相同子问题的时间，引入一个表（数组），不管它们是否对最终解有用，把新的子问题的解答存于该表中，待以后遇到同样子问题时，就不再重复求该子问题，而直接从表中取出该子问题的解答，这就是动态规划法所采用的基本思想。

（四）选择题

1．循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 。

A．(rear-front+m)% m B．read-front+1

C．read-front-1 D．read-front

n 参考答案 A

2．递归算法的执行过程一般来说，可分成 (1) 和 (2) 两个阶段。

(1)A．试探 B．递推 C．枚举 D．分析

(2)A．回溯 B．回归 C．返回 D．合成

n 参考答案 (1) B (2) B

3．设哈希表长m=11，哈希函数H（key）=key%11。表中已有4个结点：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其余地址为空，如果二次探测再散列处理冲突，关键字为49的结点地址是 。

A．8 B．3 C．5 D．9

n 参考答案 D

4．m阶B-树中所有非终端（除根之外）节点中的关键字个数必须大于或等于 。

A． －1 B． +1 C． －1 D．m

n 参考答案 C

5．一组记录的关键码为（46，79，56，38，40，84），则采用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。

A．38，40，46，56，79，84 B．40，38，46，79，56，84

C．40，38，46，56，79，84 D．40，38，46，84，56，79

n 参考答案 C

6．若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用 (1) 算法，因为 (2) 。

（1）A．先递归后递推 B．先递推后递归 C．递归 D．递推

（2）A．递推的效率比递归高 B．递归宜于问题分解

C．递归的效率比递推高 D．递推宜于问题分解

n 参考答案 （1）D （2）A

7．将一棵有100节点的完全二叉树从上到下、从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。

A． 99 B．98 C．50 D．48

n 参考答案 B

8．二叉树在线索化后，仍不能有效求解的问题是 。

A．前序线索二叉树中求前序后继 B．中序线索二叉树中求中序后继

C．中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继

n 参考答案 D

9．判断线索二叉树中某结点P有左孩子的条件是 （1） 。若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 （2） 。

（1）A．P！=null B．P-lchild！=null C．P-ltag=0 D．P-ltag=1

（2）A．根结点无右子树的二叉树 B．根结点无左子树的二叉树

C．根结点可能有左子树和右子树 D．各结点只有一个孩子的二叉树

n 参考答案 （1）C （2）C

10．在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行_____。

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;

n 参考答案 D

11．设二维数组a[0…m-1][0…n-1]按列优先顺序存储在首地址为loc(a[0][0])的存储区域中，每个元素占d个单元，则a[i][j]的地址为________。

A． loc(a[0][0]) +(j×n+i) ×d B． loc(a[0][0]) +(j×m+i) ×d

C．loc(a[0][0]) +((j-1)×n+i-1) ×d D． loc(a[0][0]) +((j-1)×m+i-1) ×d

n 参考答案 B

12．如果一个栈的进栈序列是1,2,3,4且规定每个元素的进栈和退栈各一次,那么不可能得到的退栈序列_____。

A 4,3,2,1 B 4,2,1,3 C 1,3,2,4 D 3,4,2,1

n 参考答案 B

13．对n个元素进行快速排序时，最坏情况下的时间复杂度为 。

A．O（log2n） B．O（n） C．O（nlog2n） D．O（n2）

n 参考答案 D

14．任何一个基于“比较”的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为 。

A．10 B．11 C ．21 D．36

n 参考答案 A

四、模拟试题

1．二叉树的前序、中序和后序遍历法最适合采用 （1） 来实现。

查找树中，由根结点到所有其它结点的路径长度的总和称为 （2） ，而使上述路径长度总和达到最小的树称为 （3） 。它一定是 （4） 。

在关于树的几个叙述中，只有 （5） 是正确的。

（1）A．递归程序 B．迭代程序 C．队列操作 D．栈操作

（2）A．路径和 B．内部路径长度 C．总深度 D．深度和

（3）A．B-树 B．B+树 C．丰满树 D．穿线树

（4）A．B-树 B．平衡树 C．非平衡树 D．穿线树

（5）A．用指针方式存储有n个结点的二叉树，至少要有n+1个指针

B．m阶B-树中，每个非叶子结点的后件个数≥

C．m阶B-树中，具有k个后件的结点，必含有k-1个键值

D．平衡树一定是丰满树

n 参考答案（1）A （2）B （3）C （4）B （5）C

2．一棵查找二叉树，其结点A、B、C、D、E、F依次存放在一个起始地址为n（假定地址以字节为单位顺序编号）的连续区域中，每个结点占4个字节：前二个字节存放结点值，后二个字节依次放左指针、右指针。若该查找二叉树的根结点为E，则它的一种可能的前序遍历为 （1） ，相应的层次遍历为 （2） 。在以上两种遍历情况下，结点C的左指针Lc的存放地址为 （3） ，Lc的内容为 （4） 。结点A的右指针Ra的内容为 （5） 。

（1）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF

（2）A．EAFCBD B．EFACDB C．EABCFD D．EACBDF

（3）A．n+9 B．n+10 C．n+12 D．n+13

（4）A．n+4 B．n+8 C．n+12 D．n +16

（5）A．n+4 B．n+8 C．n+12 D．n +16

n 参考答案 （1）D （2）A （3）B （4）A （5）B

3．对于给定的一组关键字（12，2，16，30，8，28，4，10，20，6，18），按照下列算法进行递增排序，写出每种算法第一趟排序后得到的结果：希尔排序（增量为5）得到 （1） ，快速排序（选第一个记录为基准元素）得到 （2） ，基数（基数为10）排序得到 （3） ，二路归并排序得到 （4） ，堆排序得到 （5） 。

（1）A．2,4,6,8,10,12,16,18,20,28,30 B．6,2,10,4,8,12,28,30,20,16,18

C．12,2,10,20,6,18,4,16,30,8,28 D．30,10,20,12,2,4,16,6,8,28,18

（2）A．10,6,18,8,4,2,12,20,16,30,28 B．6,2,10,4,8,12,28,30,20,16,18

C．2,4,6,8,10,12,16,18,20,28,30 D．6,10,8,28,20,18,2,4,12,30,16

（3）A．10,6,18,8,4,2,12,20,16,30,28 B．1,12,10,20,6,18,4,16,30,8,28

C．2,4,6,8,10,12,16,18,20,28,30 D．30,10,20,12,2,4,16,6,8,28,18

（4）A．2,12,16,8,28,30,4,6,10,18,20 B．2,12,16,30,8,28,4,10,6,20,18

C．12,2,16,8,28,30,4,6,10,28,18 D．12,2,10,20,6,18,4,16,30,8,28

（5）A．30,28,20,12,18,16,4,10,2,6,8 B．20,30,28,12,18,4,16,10,2,8,6

C．2,6,4,10,8,28,16,30,20,12,18 D．2,4,10,6,12,28,16,20,8,30,18

n 参考答案 （1）C （2）B （3）D （4）B （5）C

4．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （1） 。

从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 （2） 。设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 （3） 排序法。

（1）A．希尔排序 B．起泡排序 C．插入排序 D．选择排序

（2）A．希尔排序 B．起泡排序 C．插入排序 D．选择排序

（3）A．起泡排序 B．快速排序 C．堆排序 D．基数排序

n 参考答案 （1）D （2）C （3）C

5．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时,元素序列的变化情况如下：

①25,84,21,47,15,27,68,35,20 ②20,15,21,25,47,27,68,35,84

③15,20,21,25,35,27,47,68,84 ④15,20,21,25,27,35,47,68,84

则所采用的排序方法是 （1） 。下列（2）中不稳定的排序是 （2） 。

外排序是指 （3） 。

（1）A．选择排序 B．希尔排序 C．归并排序 D．快速排序

（2）A．直接插入排序 B．冒泡排序 C．Shell排序 D．归并排序

（3）A．用机器指令直接对硬盘中需排序数据排序

B． 把需排序数据，用其它大容量机器排序

C． 把外存中需排序数据一次性调入内存，排好序后再存储外存

D．对外存中大于内存允许空间的待排序的数据，通过多次内外间的交换实现排序。

n 参考答案 (1) D (2) C （3）D

6．在内部排序中，通常要对被排序数据进行多次扫描。各种排序方法有不同的排序实施过程和时间复杂性。对给定的整数数列（541,132,984,746,518,181,946,314,205,827）进行从小到大的排序时,采用冒泡排序和简单选择排序时,若先选出大元素,则第一次扫描结果分别是 （1） 采用快速排序（以中间元素518为基准）的第一次扫描结果是 （2） 。

设被排序的序列有n个元素，冒泡排序和简单选择排序的时间复杂度是 （3） ；快速排序的时间复杂度是 （4） 。

（1）

A．(181,132,314,205,541,518,946,827,746,984）和（541,132,827,746,518,181,946,314,205,984）

B．（132,541,746,518,181,946,314,205,827,984）和（541,132,827,746,518,181,946,314,205,984）

C．（205,132,314,181,518,746,946,984,541,827）和（132,541,746,518,181,946,314,205,827,984）

D．(541,132,984,746,827,181,946,314,205,518）和（132,541,746,518,181,946,314,205,827,984）

（2）A．（181,132,314,205,541,518,946,827,746,984）

B．（541,132,827,746,518,181,946,314,205,984）

C．（205,132,314,181,518,746,946,984,541,827）

D．(541,132,984,746,827,181,946,314,205,518）

（3）A．O(nlog2n) B．O(n) C．log2n D．O(n2)

（4）A．O(nlog2n) B．O(n2log2n) C．O(log2n) D．O(n2)

n 参考答案 （1）B （2）C （3）D （4）A

7．结定结点的关键字序列（F、B、J、G、E、A、I、D、C、H），对它按字母的字典顺序进行排列，采用不同方法，其最终结果相同。但中间结果是不同的。

Shell排序的第一趟扫描（步长为5）结果应为 （1） 。

冒泡排序（大数下沉）的第一趟冒泡的效果是 （2） 。

快速排序的第一次扫描结果是 （3）

二路归并排序的第一趟结局是 （4） 。

若以层次序列来建立对应的完全二叉树后，采用筛选法建堆，其第一趟建的堆是 （5） 。

（1）A．（B、F、G、J、A、D、I、E、H、C）

B．（B、F、G、J、A、E、D、I、C、H）

C．（A、B、D、C、E、F、I、J、G、H）

D．（C、B、D、A、E、F、I、G、J、H）

（2）A．（A、B、D、C、F、E、I、J、H、G）

B．（A、B、D、C、E、F、I、H、G、J）

C．（B、F、G、E、A、I、D、C、H、J）

D．（B、F、G、J、A、E、D、I、C、H）

（3）A．（C、B、D、A、F、E、I、J、G、H）

B．（C、B、D、A、E、F、I、G、J、H）

C．（B、A、D、E、F、G、I、J、H、C）

D．（B、C、D、A、E、F、I、J、G、H）

（4）A．（B、F、G、J、A、E、D、I、C、H）

B．（B、A、D、E、F、G、I、J、H、C）

C．（A、B、D、C、E、F、I、J、G、H）

D．（A、B、D、C、F、E、J、I、H、G）

（5）

n 参考答案 （1）C （2）C （3）B （4）A （5）B

8．二叉树 （1） 。在完全二叉树中，若一个结点没有 （2） ，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子树是N在原树里对应结点的 （3） ，而N的右子树是它在原树里对应结点的 （4） 。二叉排序树的平均检索长度为 （5） 。

（1）A．是特殊的树 B．不是树的特殊形式

C．是两棵树的总称 D．是只有二个根结点的树形结构

（2）A．左子树 B．右子树 C．左子树或没有右子树 D．兄弟

（3）～(4)A．最左子树 B．最右子树 C．最邻近的右兄弟 D．最邻近的左兄弟

（5）A．O(n2) B．O(n) C．O(log2n) D．O(nlog2n)

n 参考答案 （1）B （2）A （3）A （4）C （5）C

9．哈希存储的基本思想是根据 （1） 来决定 （2） ，冲突（碰撞）指的是 （3） ， __(4)___越大，发生冲突的可能性也越大。处理冲突的两种主要方法是 （5） 。

（1）～（2）A．存储地址 B．元素的序号 C．元素个数 D．关键码值

（3） A．两个元素具有相同序号 B．两个元素的关键码值不同，而非码属性相同

C．不同关键码值对应到相同的存储地址 D．数据元素过多

（4） A．非码属性 B．平均检索长度 C．负载因子 D．哈希表空间

（5） A．线性探查法和双散列函数法 B．建溢出区法和不建溢出区法

C．除余法和折叠法 D．拉链法和开放地址法

n 参考答案 （1）D （2）A （3）C （4）C （5）D

10． 设二维数组F的行下标为1至5，列下标为0至8，F的每个数据元素均占4个字节。在按行存储的情况下，已知数据元素F[2，2]的第一个字节的地址是1044，则F[3，4]和F[4，3]的第一个字节的地址分别为 （1） 和 （2） ，而数组的第一个数据元素的第一个字节和数组最后一个元素的最后一个字节的地址分别为 （3） 和 （4） 。

对一般的二维数组G而言，当 （5） 时，其按行存储的G[I，J]的地址与按列存储的G[J，I]的地址相同。

（1）A．1088 B． 1084 C．1092 D．1120

（2）A．1092 B． 1088 C．1120 D．1124

（3）A．1004 B． 1044 C．1000 D．984

（4）A．1183 B． 1179 C．1164 D．1187

（5）A．G的列数与行数相同

B．G的列的上界与G的行的上界相同

C．G的列的上界与G的行的下界相同

D．G的列的上下界与G的行的上下界相同

n 参考答案 （1）A （2）C （3）C （4）B （5）D

11．某顺序存储的表格，其中有90,000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。

用顺序查找法查找时，平均比较次数约为 (1) ，最大比较次数为 (2) 。

现把90,000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是 (3) ，此时的平均比较次数是 (4) 。当g的值大于等于90,000时，此方法的查找速度接近于 (5) 。

(1)～(2) A. 25,000 B. 30,000 C. 45,000 D. 90,000

(3)～(4) A. 100 B. 200 C. 300 D. 400

(5) A. 快速分类法 B. 斐波那契查找法 C. 二分法 D. 顺序查找法

n 参考答案 （1）C （2）D （3）C （4）C （5）D

12．已知无向图的邻接表如图2-35所示：

此邻接表对应的无向图为 (1) 。此图从F开始的深度优先遍历为 （2） 。从F开始的广度优先遍历为 （3） 。从F开始的深度优先生成树为 （4） 。从F开始的广度优先生成树为 （5） 。

（1）

（2）A. F G I L J M K H B. F G I L J K H M

C. F G I L J K M H D. F G H M I L J K

（3）A. F G I L J K M H B. F G H M I L J K

C. F G H I L J K M D. F G H M K I L J

（4）

（5）

n 参考答案 （1）C （2）B （3）B （4）A （5）B

13．图2-36是带权的有向图G的邻接表。以结点V1出发深度遍历图G所得的结点序列为 （1） ；广度遍历图G所得的结点序列为 （2） ；G的一种拓扑序列是 （3） ；从结点V1到V8结点的最短路径是 （4） ；从结点V1到V8结点的关键路径是 （5） 。

（1）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V3，V8，V4，V5，V6，V7

C. V1，V2，V3，V8，V4，V5，V7，V6 D. V1，V2，V3，V8，V5，V7，V4，V6

（2）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8

C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8

（3）A. V1，V2，V3，V4，V5，V6，V7，V8 B. V1，V2，V4，V6，V5，V3，V7，V8

C. V1，V2，V4，V6，V3，V5，V7，V8 D. V1，V2，V4，V6，V7，V3，V5，V8

(4)～(5)A.( V1，V2，V4，V5，V3，V8) B. (V1，V6，V5，V3，V8)

C.( V1，V6，V7，V8) D. ( V1，V2，V5，V7，V8)

n 参考答案 （1）D （2）C （3）B （4）D （5）B

类似于这个吧 这也只是一部分 全部已发到你的邮箱

算法与数据结构期末是笔考还是机考

都要考

数算传统上的期末会分为闭卷考试和机考两个部分,机考就是在onlinejudge网站里,在限定的时间内,做出几道算法编程题,让机器自动判断对错,并以此计分。

急需数据结构C语言版（清华大学出版社）的期末考试试题及答案

《数据结构》期末考试试卷（ A ）

一、 选择题（每小题2分，共24分）

1．计算机识别、存储和加工处理的对象被统称为( A )

A.数据 B.数据元素

C.数据结构 D.数据类型

2．栈和队列都是（ A ）

A．限制存取位置的线性结构 B．顺序存储的线性结构

C．链式存储的线性结构 D．限制存取位置的非线性结构

3．链栈与顺序栈相比，比较明显的优点是( D )

A.插入操作更加方便 B.删除操作更加方便

C.不会出现下溢的情况 D.不会出现上溢的情况

4．采用两类不同存储结构的字符串可分别简称为( B )

A.主串和子串 B.顺序串和链串

C.目标串和模式串 D.变量串和常量串

5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：B

A. 110 B .108

C. 100 D. 120

6．串是一种特殊的线性表，其特殊性体现在：B

A.可以顺序存储 B .数据元素是一个字符

C. 可以链接存储 D. 数据元素可以是多个字符

7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： C

A. 2h B .2h-1

C. 2h+1 D. h+1

软件开发网

8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ A

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同

C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D. 以上都不对

9．一个有n个顶点的无向图最多有多少边？C

A. n B .n(n-1)

C. n(n-1)/2 D. 2n

10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C

A. 1/2 B .1

C. 2 D. 4

11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）

A．左子树的叶子结点 B．左子树的分支结点

C．右子树的叶子结点 D．右子树的分支结点

软件开发网

12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )

A.35和41 B.23和39

C.15和44 D.25和51

二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）

原理见课本128页

三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分)

深度优先；C0-C1-C3-C4-C5-C2

宽度优先：C0-C1-C2-C3-C4-C5

四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）

原理见课本250页

五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）

0 1 2 3 4 5 6 7 8

12 23 45 66 76 88 93 103 166

过程：

mid=(0+8)/2=4

high=3,low=0 mid=1

high=0,low=0 mid=0（找到12）

high=8,low=5,mid=6（找到93）

high=8,low=7,mid=7

high=8 low=8 mid=8

算法：见课本84页上

六、知单链表的结点结构为

Data next

下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。

请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)

void SelectSort(LinkedList L)

{

LinkedList p,q,min;

DataType rcd;

p= (1) ;

while(p!=NULL) {

min=p;

q=p-next;

while(q!=NULL){

if( (2) )min=q;

q=q-next;

}

if( (3) ){

rcd=p-data;

p-data=min-data;

min-data=rcd;

}

(4) ;

}

}

本题不会。嘿嘿。。。。

七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)

输入：

四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入

2：输出：算法产生至少一个量作为输出

3.：确定性：组成算法的每条指令是清晰的，无歧异的。

4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的

八、何谓队列的"假溢"现象？如何解决？（5分）

队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。

九、说明并比较文件的各种物理结构。（6分）