东南大学十套数据结构试题及答案

数据结构试卷（五）

1. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

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； } }

2. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。

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); }

三、应用题(32分)

1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，

要求给出该二叉树的的后序遍历序列。 2. 设无向图G（如右图所示），给出该图的最小生成树上边的集合并

计算最小生成树各边上的权值之和。

3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，

要求计算出成功查找时的平均查找长度。 4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，

13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

四、算法设计题(28分)

1． 设计判断两个二叉树是否相同的算法。 2． 设计两个有序单链表的合并排序算法。

6

数据结构试卷（六）

四、算法设计题(20分)

１．设计在顺序有序表中实现二分查找的算法。 ２．设计判断二叉树是否为二叉排序树的算法。 ３．在链式存储结构上设计直接插入排序算法

7

数据结构试卷（七）

三、填空题(30分)

1. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。

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

_________________; }

四、算法设计题(20分)

1. 设计在链式结构上实现简单选择排序算法。 2. 设计在顺序存储结构上实现求子串算法。 3. 设计求结点在二叉排序树中层次的算法。

8

数据结构试卷（八）

三、填空题(30分)

1． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的

一趟希尔排序结束后的结果为_____________________________。 2． 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内

容。

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． 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后

面插入结点X需要执行的语句序列：s->next=p->next; _________________;。 4． 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，

则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。

5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为

__________。

6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。

7． 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素A[i][j]的值等

于____________。

8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择

排序结束后的结果为_____________________________。

9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。 10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成

初始堆只需把16与___________相互交换即可。

四、算法设计题(20分)

1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

9

数据结构试卷（九）

五、算法设计题(20分)

1． 设计计算二叉树中所有结点值之和的算法。 2． 设计将所有奇数移到所有偶数之前的算法。 3． 设计判断单链表中元素是否是递增的算法。

10