2008-09(2)数据结构期末试卷(D

汕 头 职 业 技 术 学 院

2008-2009学年第二学期期末试卷（D）

课程名称 数据结构 学分_____ 拟题人 何汉阳 审题人___________ 系(校区) 计算机系 班级_____________ __ 学号_____ 姓名_ _________

题 号 得 分 一 二 三 四 五 六 七 八 总 分 评卷人

一、填空（26分，每空一分）

1. 在设计算法和程序时，不仅要考虑数据的____________及其_________，而且要考虑数据在存储器中

的____________。

2. 算法设计的基本要求是：_____________、_____________和_____________。

3. 估算算法运行时间的基本考虑是：确定问题的_______和确定算法执行基本操作的_______，在难以精

确计算基本执行次数的情况下，只考虑相对于问题规模N的_______。

4. 对于长度为n的顺序表的删除算法，它的最坏情况时间复杂性及其量级分别是______和______，平均

时间复杂性及其量级分别为________和________。

5. 串的堆型存储结构的特点是：仍以一组地址_______的存储单元存放串的字符序列，但其存储空间是

在算法执行过程中____________得到的。

6. 顺序队列存在假满现象，解决这个问题的常用方法是构建_______________。

7. 图的常用存储结构有__________和__________，Prim 算法是选用____________来存储图中的所有边。 8. 解决散列查找的两个主要问题是：(1)构造一个计算简单且冲突尽量少的、地址分布比较_______的

______________; (2)拟定解决__________的方案。

9. 假定一个顺序表的长度为50，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长

度_________，在查找不成功情况下的平均查找长度_________。

10. 关键字比较的次数与记录的初始排列次序无关的排序方法是_______排序；每次使两个相邻的有序表

合成一个有序表的排列方法叫做________排序。

二、选择题（在正确答案上打“√”，共20分，每小题2分） 1、下面关于线性表的叙述中，错误的是______。

A）线性表采用顺序存储，必须占用一片连续的存储单元 B）线性表采用链接存储，不必占用一片连续的存储单元 C）线性表采用链接存储，可以随机存取表中的任一结点

D）线性表采用顺序存储，无须为表示结点间的逻辑关系而增加额外的存储空间

2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_____存储方式最节省运算时间。

1

A）单链表 B）仅有头指针的单循环链表 C）双链表 D）仅有尾指针的单循环链表

3、下列排序算法中，______排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。 A）选择 B）冒泡 C）归并 D）堆

4、有一散列表，表长度m为100，采用除余法构造散列函数，即H(K)=K MOD P(P≤m)，为使散列函数具有较好的性能，P的选择应是______。

A）99 B）97 C）91 D）93

5、在包括n个键值的二叉排序树中查找一个键值，其平均比较次数的量级为________。 A）O(n） B）O(log2n） C）O(nlog2n) D）O(n2)

6、对有14个元素的有序表A［1..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］ C） A［7］，A［5］，A［3］，A［4］

7、假设一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是_______。 A）B，C，D，A，E B）E，D，A，C，B

C）B，C，A，D，E D）A，E，D，C，B

8、前序遍历序列和中序遍历序列相同的非空二叉树是：

A）任一结点均无右子树的非空二叉树 B）根结点无右子树的非空二叉树 C）任一结点均无左子树的非空二叉树 D）根结点无左子树的非空二叉树

9、图中有关路径的定义是______。

A）由顶点和相邻顶点序偶构成的边所形成的序列 B）由不同顶点所形成的序列 C）由不同边所形成的序列 D）上述定义都不是

10、下列说法不正确的是_________。

A）图的遍历是从给定的源点出发每一个顶点仅被访问一次 B）图的深度遍历不适用于有向图 C）遍历的基本算法有两种：深度遍历和广度遍历 D）图的深度遍历是一个递归过程

三、作图题（14分，每小题7分）

1. 先将下列树转化为二叉树，然后画出其二重链式结构图。

2

2. 写出下列图的邻接矩阵和邻接链表表示法。

四、已知一棵二叉树的先序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI，试画出这棵二叉树。

（10分）

五、在一个带头结点的单链表中，元素值递增有序，编写程序，在单链表中插入一元素后，表中元素值仍保持递增有序。（10分）

3

六、写出顺序表上实现顺序查找的算法，并将监视哨设在高端。（10分）

七、为了提高冒泡排序算法的效率，可在算法中设置一布尔变量noSwap来检查一次内循环中有无记录交换，若无交换算法即可中止结束，请用Ｃ语言编写改进后的冒泡排序算法。 （共10分）

4

2008-2009学年第二学期期末试卷（D）答案

课程名称 数据结构 拟题人 何汉阳

一、填空（每空一分，26分）

1、逻辑结构，运算，存储结构（物理结构） 2、易读性，健壮性，高效率 3、规模，次数，增长率 4、n-1, O(n), (n-1)/2, O(n) 5、连续，动态分配 6、循环队列

7、邻接矩阵，邻接链表，邻接矩阵 8、均匀，散列函数，冲突 9、51/2，50 10、冒泡，归并

二、选择题（每小题2分，共20分）

1～5、CDCBB 6～10、CBCAB

三、作图题（14分，每小题7分） 1、解：

2、解：

0111101010 10

四、解（10分）。

5

五、解：（10分）

∥L是带头结点的单链表，x是待插入的整数。

typedef struct node { int data;

struct node *next; }LINKLIST;

void LinkListInsertSort(LINKLIST *L, int x) { LINKLIST *pre,*p,*s;

s = (LINKLIST *)malloc(sizeof(LINKLIST)); s->data = x; s->next=NULL;

pre = L; p = L->next; //设置一前一后指针pre, p

while(p != NULL) //使p指向数据域不小于x的结点 if(p->data < x) //使pre指向数据域小于x的结点 { pre = p; p = p->next; } else

break;

pre->next = s; //在指针pre和p之间插入s结点 s->next = p; }

六、解（10分）。

/*数据结构按课本描述*/

int seq_search1(KEYTYPE k, SSTABLE st)

{ int i=0; /*假定从0号单元开始存放数据*/ st.r[st.len].key=k; /*监视哨设在高端*/ while(st.r[i].key != k) i++;

if(i==st.len) reture 0; else return i+1; }

七、解（10分）。

void Sort_Bubble1(RecordNode *r, int n) { int i, j;

int noswap =1; RecordNode temp;

for (i = n - 1; i >= 1 && noswap; i--) { noswap = 0;

for (j = 1; j < i + 1; j++) if (r[j].key > r[j+1].key)

{ temp = r[j];

r[j] = r[j+1]; r[j+1] = temp; noswap =1; } } }

6