数据结构模拟题（开卷）.doc

中国地质大学（北京）继续教育学院 2012年09课程考试
《数据结构》模拟题（开卷）

一、单项选择题
1.分析下列算法suanfa1(n):
void suanfa1(int n)
{ int i,j,x=1；
for(i=0；i)。
A.(n*2)2 B.(n-1)2 C.(n+1)2 D.n2
2.折半查找有序表(16,20,30,35,40,46,60,80),若查找元素80,需依次与表元素( D )进行比较。
A.35,46,80 B.40,60 C.40,60,80 D.35,46,60,80
3.对长度为10的表作选择(简单选择)排序,共需比较( A )次关键字。
A.45 B.90 C.10 D.110
4下列算法suanfa2(n)的时间复杂度为( A )。
int suanfa1(int n)
{ int i,x=0；
for (i=0；i<5；i++)
for (j=1；j<=n；j++)
x+=2；
return x；
}
A.O(n) B.O(n5) C.O(5n) D.O(n2)
5.线性表在( B )时, 宜用顺序表作存储结构。
A.经常作插入、删除 B.经常随机存取
C.无足够连续存储空间 D.经常作动态查找
6.设广义表LS=((a,b),c,(d,e)),执行操作GetTail(GetHead(LS))后的结果是( A )。
A.(b) B.b C.(c,(d,e)) D.(a,b)
7.深度为k的满二叉树有( C )个叶子。
A.k2-1 B.2K-1-1 C.2K-1 D.k2
8.有16个顶点的无向图最多可能有( D )个连通分量。
A.32 B.8 C.256 D.16
9. ( C )是'Hua**Zhong**Da'的子串。
A.Hua B.zhong C.'*Da' D.'HuaZhongDa'
10.字符串的长度指的是串中( B )的个数。
A.不同字符 B.字符 C.字母 D.字母和数字

二、多项选择题
1.设哈希(Hash)函数为H(k)=k MOD 7,其中k是关键字,MOD为取模(求余)运算，
下列关键字( ACD )是同义词。
A.29,22,15 B.1,2,3,4 C.23,16,9 D.7,14,49
2.一个算法具有( AC )等特点。
A.可行性 B.健壮性
C.确定性 D.至少有一个输入量
3.对单链表可以进行( BCD )的操作
A.折半查找 B.顺序查找
C.删除结点 D.插入结点
4.若依次进栈的元素为a,b,c,d,可得到出栈的元素序列( ACD )。
A.a,b,c,d B.c,a,b,d
C.b,c,d,a D.d,c,b,a

三、填空题
1.有向图的存储结构有___邻接表、逆邻接表、十字链表__等表示法。
2.若7行6列的数组a以列序为主序顺序存储，基地址为1024,每个元素占2个存储单
元,则第3行第5列的元素(假定无第0行第0列)的存储地址是_1084_。
3.折半查找有序表(4,6,7,8,9,10,12,20,24,37,77,110),若查找值为9的元素,它
将依次与表中元素___10,7,8,9_比较大小；若查找值为80的元素,它将
依次与表中元素___10,24,77,110__比较大小。
4._____ 树中各结点的层的最大值___ 称为树的深度。
10.有n(n>0)个结点的完全二叉树的深度为élog2(n+1)ù或 ëlog2n+1û或 ëlog2nû+1。
5._______ 线性表中元素的数目______称为线性表的长度。
6.____ 限定在表头作删除,在表尾作插入_____的线性表称为队列。
7.设n个元素的线性表顺序存储,若在它的第i个(1≤i≤n)元素之后插入一个新元
素,共需移动____ n-i ___个元素。
8.构造Hash函数的方法有直接定址法、随机数法、_数字分析法、除留余数法
、平方取中法、折叠法
__等。
9.对n个记录的表进行简单选择排序,共计需要进行__ n(n-1)/2 _次比较关键字,
在最坏情况下,共计交换___ n-1___对记录。
10.字符串A中_连续字符组成子序列_称为串A的子串,_ 仅由空格字符组成的字符串称为空格串。
11.深度为k(k>0)的满二叉树共有_____2k-1-1__个非叶子。
12.在有向图G中,以顶点i为__弧尾的弧_的数目称为i的出度。

四、画图题
1.试画出下列稀疏矩阵以行序为主序的三元组表。

稀疏矩阵
参考答案：1.行序为主序的三元组表。
行号 列号 值
1
3
18
2
1
3
3
4
24
5
3
66
1
2
3
4

2.下列树的双亲表示法:

参考答案：2.下列树的双亲表示法

3.试画出下列有向图G的逆邻接表。

有向图G
参考答案：3.有向图的逆邻接表:

4.二叉树T的顺序存储结构:

参考答案：4.二叉树T的顺序存储结构:

5.已知二叉树的前序遍历序列和中序遍历序列分别是：
B,A,C,D,E,F和B,D,C,E,A,F
试画出该二叉树。
参考答案：5.前序遍历序列和中序遍历序列分别是：B,A,C,D,E,F和B,D,C,E,A,F,
对应的二叉树如下:

五、求解下列问题
1.依次输入元素10,6,8,3,7,42,25,30,27,60, 试生成一棵二叉排序树,(1)画出
生成之后的二叉排序树；(2)对该二叉排序树作中序、逆中序遍历，写出遍历序
列,(3)假定每个元素的查找概率相等,试计算查找成功时平均查找长度 。
参考答案：1.依次输入元素10,6,8,3,7,42,25,30,27,60, 试生成一棵二叉排序树,
(1)生成的二叉排序树是:

(2)中序遍历序列: 3,6,7,8,10,25,27,30,42,60
逆中序遍历序列: 60,42,30,27,25,10,8,7,6,3
(3)查找成功时平均查找长度:
ASL=(1+2+2+3+3+3+3+4+4+5)/10=3.0

2.试按表(30,11,18,4,55,19,15,70,58)
中元素的排列次序,将所有元素插入一棵
初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)画出插入完成之后的
二叉排序树；(2)假设每个元素的查找概率相等,计算该树的平均查找长度ASL。

参考答案： 2.解:(1)构造二叉排序树:

(2)平均查找长度: ASL=(1+2+2+3+3+3+4+4+4)/9=26/9≈2.9

3.试对下列网,(1)从顶点A出发,求(画)出一棵宽度优先生成树；
(2)从顶点D出发,用Prim(普里姆)算法求出一棵最小生成树，写出求解过程。

参考答案：3.(1)从顶点A出发,宽度优先生成树之一；


(1) 从顶点D出发,用Prim(普里姆)算法求出最小生成树之一:
(2)

六、设计题
1.设单链表的结点为(data,next),其中data为整型, next为指针型,试用C语言
类型定义分别写出结点类型和指针类型的定义。
参考答案：
1.设单链表的结点为(data,next),其中data为整型, next为指针型,试用C语言
类型定义分别写出结点类型和指针类型的定义。
typedef struct node
{ int data;
struct node *mext;
}node,*linklist;

七、简答题
1.二叉树有哪几种基本形态? 试举例说明。
参考答案：1.答:二叉树有5种基本形态,举例如下：

其中：
B1:为空二叉树；
B2:有根结点,左右子树均为空二叉树；
B3:有根结点,左子树为非空二叉树,右子树为空二叉树；
B4:有根结点,左子树为空二叉树,右子树为非空二叉树；
B5:有根结点,左右子树均为非空二叉树。

2.线性表的顺序存储结构和链式存储结构各有哪些优点和缺点?
参考答案：2.答:对于顺序存储结构:
(1)优点:是一种随机存取结构,存取任何元素的时间是一个常数,速度快；结构简单,逻辑上相邻的元素在物理上也是相邻的；不使用指针,节省存储空间。
(2)缺点:插入和删除元素,平均需要移动约半个表的元素,消耗大量时间；需要提供一个连续的存储空间；插入元素可能发生“溢出”；表尾之后的自由存储空间不能被其它表的数据占用(共享)。
对于链式存储结构:
(1)优点:插入和删除元素,不必移动元素,只需修改相关结点的指针；不需要一个连续的存储空间。
(2)缺点:不是随机存取结构,查找元素的时间与元素在表中位置有关,不是一个常数；使用指针,指针需占用一定的存储空间；系统需提供动态存储管理功能。

八、算法说明:输入一列整数,以0为结束标志,生成带头结点的递增有序单链表。结点类型定义和算法
struct Lnode
{ int data；
struct Lnode *next；
}；

struct Lnode *creat( )
{ struct Lnode *head,*f,*q,*p；int e；
head=(struct Lnode *)malloc(struct Lnode)；
head->next=NULL；
do{ f=_________
scanf("%d",&e)；f->data=e；
q=head；p=_______________；
while (p && e>p->data)
{ q=________； p=__________；}
f->next=____； q->next=_____；
}while(e)；
return head；
}

参考答案：八、算法填空
struct Lnode
{ int data；
struct Lnode *next；
}；

struct Lnode *creat( )
{ struct Lnode *head,*f,*q,*p；int e；
head=(struct Lnode *)malloc(struct Lnode)；
head->next=NULL；
do{ f=(struct Lnode *)malloc(structLnode)；
scanf("%d",&e)；f->data=e；
q=head；p=p->next；
while(p && e>p->data)
{ q=p； p=p->next ；} (* 或 q=q->next； p=q->next；*)
f->next=p； q->next=f；
}while(e)；
return head；
}
第8页（共8页）