-
数据结构试卷（一）
一、单选题（每题
2
分，共
20
分）
1.
栈和队列的共同特点是
(
)
。
A.
只允许在端点处插入和删除元素
B.
都是先进后出
C.
都是先进先出
D.
没有共同点
2.
用链接方式存储的队列，在进行插入运算时
( ).
A.
仅修改头指针
B.
头、尾指针都要修改
C.
仅修改尾指针
D.
头、尾指针可能都要修
改
3.
以下数据结构中哪一个是非线性结构？
( )
A.
队列
B.
栈
C.
线性表
D.
二
叉树
4.
设有一个二维数组
A[m][n]
，假设
A[0][0]
存放位置在
644(10)
，
A[2][2]
存放位置在
676(1 0)
，
每个元素占一个空间，
问
A[3][3]( 10)
存放在什么位置？脚注
(10)
表示用
< p>10进制表示。
A
．
688
B
．
678
C
．
692
D
．
696
5.
树最适合用来表示
(
)
。
A.
有序数据元素
B.
无序数据元素
C.
元素之间具有分支层次关系的数据
D.
元素之间无联
系的数据
6.
二叉树的第
k
层的结点数最多为
(
).
A
．
2
k
-1
B.2K+1 C.2K-1
D. 2
k-1
7.
若有
18
个元素的有序表存放在一维数组
A[19]< /p>
中，第一个元素
放
A[1]
中，现进行二分 查找，则查找
A
［
3
］的比较序列的下
< p>标依次为
(
)
A. 1
，
2
，
3
B. 9
，
5
，
2
，
3
C. 9
，
5
，
3
D. 9
，
4
，
2
，
3
8.
对
n
个记录的文件 进行快速排序，所需要的辅助存储空间大致
为
A.
O
（
1
）
B.
O
（
n
）
C.
O
（
1og
2
n
）
D.
O
（
n2
）
9.
对于线性表（
7
，
34
，
55
，
25
，
64
，
46
，
20
，
10
）进行
散列存储
时，若选用
H
（
K
）
=K %9
作 为散列函数，则散列地址为
1
的元
素有（
）个，
A
．
1 B
．
2 C
．
3 D
．
4
1
10.
设
有
6
个
结
点的无
向
图
，
该图
至少
应
有
(
)
条边才能确保是一个连通图。
A.5
B.6
C.7
D.8
二、填空
题（每空
1
分，共
26
分）
1.
通常从四个方面评价算法的质量：
_________
、
_________
、
_________
和
_________
。
2.
一个算法的时间复杂度为
(n3+ n2log2n+14n)/n2
，其数量级表示为
________<
/p>
。
3.
假定一棵树的广 义表表示为
A
（
C
，
D
< p>（E
，
F
，
G
）
，
H
（
I
，
J< /p>
）
）
，
则树中所含的结点数为
__________
个，树的深度为
___________
，
树的度为
_________
。
4.
后缀算式
9 2 3 +- 10 2 / -
的值为
__________
。
中缀算 式（
3+4X
）
-2Y/3
对应的后缀算 式为
_______________________________
。
5.
若用链表存储一棵二叉树时，每个结 点除数据域外，还有指向左
孩子和右孩子的两个指针。在这种存储结构中，
n
个结点的二叉
树共有
________
个指针域，其中有
________
个指针域是存放了地
址，有
________________
个指针是空指针。
6.
对于一个具有
n
个 顶点和
e
条边的有向图和无向图，在其对应的
邻接表中，
所含边结点分别有
_______
个和
________
个。
7.
AOV
网是一种
___________________
的图。
8.
在一个具有
n
个顶 点的无向完全图中，包含有
________
条边，在
一
个具有
n
个顶点的有向完全图中，包含有
________
条边。
9.
假定一个线性表 为
(12,23,74,55,63,40)
，若按
Key
%
4
条件进行划
分，使得同一余数的元
素成为一个子表，则得到的四个子表分别
为
_____________ _______________
、
___________________< /p>
、
_______________________
和< /p>
__________________________
。
10.
向一棵
B_
树插 入元素的过程中，若最终引起树根结点的分裂，则
新树比原树的高度
__ _________
。
11.
在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为
_______
_
，整个堆排序过程的时间复杂度为
________
。
12.
在快速排序、堆排序、归并排序中，< /p>
_________
排序是稳定的。
三、计算题（每题
6
分，共
24
分）
1.
在如下数组
A
中链 接存储了一个线性表，表头指针为
A [0].next
，
试写出该线性表。
A 0 1 2
3 4 5 6
7
dat
60
50
78
90
34
40
2
a
nex
t
2.
请画出下图的邻接矩阵和邻接
表。
3.
已知一个图的顶点集< /p>
V
和边集
E
分别为：
V={ 1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,
(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,
7)25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小 生成树中依次
得到的各条边。
4.
画出向小根堆中加入数据
4, 2, 5, 8, 3
时，每加入一个数据后堆的
变化。
四、阅读算法（每题
7
分，共
14
分）
1.
LinkList mynote(LinkList L)
{//L
是不带头结点的单链表的头指针
if(L&&L->next){
q=L
；
L=L
－
>next
；
p=L
；
S1
：
while(p
－
>next) p=p
－
>next
；
S2
：
p
－
>next=q
；
q
－
>next=N ULL
；
}
return
L
；
}
请回答下列问题：
（
1
）说明语句
S1
< p>的功能；
（
2
）说明语句组
S2
的功能；
（
3
）设链表表示的线性表为 （
a
1
,a
2
,
…
,a
n
）
,
写出算法执行后
的返回值所表示的线性表。
3
3
5
7
2
0
4
1
2.
void ABC(BTNode * BT)
{
if
BT {
ABC (BT->left);
ABC (BT->right);
cout<
}
}
该算法的功能是：
五、算法填空（共
8
分）
二叉搜索树的查找
——
递归算法
:
bool Find(BTreeNode* BST,ElemType&
item)
4
{
if (BST==NULL)
return
false; //
查找失败
else {
if (item==BST->data){
item=BST->data;//
查找成功
return ___________;}
else
if(item
return Find(______________,item);
else return Find(_______________,item);
}//if
}
六、编写算法（共
8
分）
统计出单链表
HL
中结点的值等于给定值
X
< p>的结点数。
int CountX(LNode*
HL,ElemType x)
数据结构试卷（二）
一、选择题
(24
分
)
1
．下面关于线性表的叙述错误的是（
）
。
(A)
线性表采用顺序存储必须占用一片连续的存储空间
(B)
线性表采用链式存储不必占用一片连续的存储空间
(C)
线性表采用链式存储便于插入和删除操作的实现
(D)
线性表采用顺序存储便于插入和删除操作的实现
2
．设哈夫曼树中的叶子结点总数为
m
， 若用二叉链表作为存储结构，
则该哈夫曼树中总共有（
）个空指针域。
(A) 2m-1
(B) 2m
(C) 2m+1
(D) 4m
5
3
．设顺序循环 队列
Q[0
：
M-1]
的头指针和尾指针分别为< /p>
F
和
R
，头指
针
总是指向队头元素的前一位置，尾指针
R
总是指向队尾元素
的当前位置，则该循环队列中的元素个数为（
）
。
(A) R-F
(B) F-R
(C) (R-F+M)
％
M (D) (F-R+M)
％
M
4
．
设某棵二叉树的中序遍历序列为
ABCD
，
前序遍历序 列为
CABD
，
则后序遍历该二叉树得到序列为（
）
。
(A) BADC
(B) BCDA
(C) CDAB
(D) CBDA
5
．设某完全无向图中有
n
个顶点，则该完全无向图中有（
）条边。
(A) n(n-1)/2
(B) n(n-1)
(C) n
2
(D) n
2
-1
6
．设某棵 二叉树中有
2000
个结点，则该二叉树的最小高度为（
）
。
(A) 9
(B) 10
(C) 11
(D) 12
< br>7
．设某有向图中有
n
个顶点，则该有向图对应的邻接表中 有（
）
个表头结点。
(A) n-1
(B) n
(C) n+1
(D) 2n-1
8
．设一组初始记录关键字 序列
(5
，
2
，
6
，
3
，
8)
，以第一个记录关键
< br>字
5
为基准进行一趟快速排序的结果为（
）
。
(A) 2
，
3
，
5
，
8
，
6
(C) 3
，
< p>2，
5
，
6
，
8
二、填空题
(24
分
)
1.
为了能有效地应用
HASH
查找技术，必须解决的两个问题是
____________________
和
__________________________
。< /p>
(B) 3
，
2
，
5
，
8
< p>，6
(D) 2
，
3
，
6
，
5
，
8
6
2.
下面程序段的功能实现数据
x
进栈，要求在下划线处填上正确的
< p>语句。
typedef struct {int
s[100]; int top;} sqstack;
void
push(sqstack &stack,int x)
{
if (==m-
1) printf(“overflow”);
else
{____________________;_________________;}
}
3.
中序遍历二叉排序树 所得到的序列是
___________
序列
（填有序或
无序）
。
4.
快速排序的最坏时间复杂度为
___________
，平均时间复杂度 为
__________
。
5.
设某棵二叉树中度数为
0
的结点数为
N
0
，
度数为
1
的结点数为
N
1
，
则该二叉树中度数为
2
的结点数为
_ ________
；
若采用二叉链表作
为该二叉树的存储
结构，则该二叉树中共有
_______
个空指针域。
6.
设某无向图中顶点数和边数分别为
n
和
e
，所有顶点的度数之和
为
d
，则
e=_______
。
7.
设一组初始记录关键字序列为
(5 5
，
63
，
44
，
38
，
75
，
80
，
31
，
56)
，
则利用筛选法建立的初
始堆为
___________________________
。
< p>
8
．
已知一有向图的邻接表存储 结构如下：
从顶点
1
出发，
DFS
遍历
的输出序列是
，
BFS
遍历的输出序列是
7
三、应用题
(36
分
)
1
．
设一组初始记录关键字序列为
(45
，
80
，
48
，
40
，
22
，
78)
，则
分别给出第
4
趟简单选择排序和第
4
趟直接插入排序后的结果。
2
．
设指针变量
p
指向双向链表中结点
A
，指针变量
q
指 向被插入
结点
B
，
要求给出在结点
A
的后面插入结点
B
的操作序列
（设双向
链表中结点的两个指针域分别为
llink
和
< p>rlink）
。
3
．
设一组有序的记录关键字序列为< /p>
(13
，
18
，
24
，
35
，
47
，
50
，
62
，
83
，
90)
，查找方法用二分查找，要求计算出查找关键字
62
时的
比较次数并计算出查找成功时的平均查找长度。
4
．
设一棵树
T
中边的集合为
{(A
，
B)
，
< p>(A，
C)
，
(A
，
D)
，
(B
，
E)
，
(C
，
F)
，
(C
，
G)}
，要求用孩子兄弟表示法（二叉链表）表示出该
树的存储结构并将该树转化成对应的二叉树。
5
．
设有无向图
G
，要求给出用普里姆算法构造最小生成树所走过
的边的集合。
8
9
6
．
设有一组初始记录关键字为
(45
，
80
，
48
，< /p>
40
，
22
，
78)
，要求
构造一棵二叉排序树并给出构造过程。
四、算法设计题
(16
分
)
1
．
设有一组初始记录关键字序列（< /p>
K
1
，
K
2
，…，
K
n
）
，要求设计一
个算法能够在
O(n)
的时间复杂 度内将线性表划分成两部分，其中
左半部分的每个关键字均小于
K
i
，右半部分的每个关键字均大于
等于
K
i
。
2
．
设有两个集合
A< /p>
和集合
B
，要求设计生成集合
C=A
∩
B
的算法，
其中集合
A
、
B
和
C
用链式存储结构表示。
数据结构试卷（三）
一、选择题
(
每题
< p>1分，共
20
分
)
1
．设某数据结构的二元组形式表示为
A=(D
，
R)
，
D={01
，
02
，
03
，
04
，
05
，
06
，
07
，
08
< p>，09}
，
R={r}
，
r= {<01
，
02>
，
<01
，
03>
，
<01
，
04>
，
<02
，
05>
，
< 02
，
06>
，
<03
，
07>
，
<03
，
08>
，
<03
，
09>}
，则数据结构
A
是（
）
。
(A)
线性结构
(B)
树型结构
图型结构
2
．下面程序的时间复杂为（
）
(C)
物理结构
(D)
10
fo
r
（
i=1
，
s=0
；
< p>i<=n
；
i++
）
{t=1
；
< p>for(j=1；
j<=i
；
j++) t=t*j
；
s=s+t
；
}
(A) O(
n
)
(B) O(n
2
)
(C) O(n
3
)
(D) O(n
4
)
3
．设指 针变量
p
指向单链表中结点
A
，若删除单链表中结 点
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->ne xt
；
free(q)
；
(C) q=p->next
；
p-> next=q->next
；
free(q)
；
(D) q=p->next
；
p-> data=q->data
；
free(q)
；
4
．设有
n
个待排序的记录关键字，则在 堆排序中需要（
）个辅助
记录单元。
(A) 1
(B) n
(C) nlog
2
n
(D) n
2
5
．设一组初始 关键字记录关键字为
(20
，
15
，
14
，
18
，
21
，
< p>36，
40
，
10)
，则以
20
为基准记录的一趟快速排序结束后的结果为
( )
。
(A) 10
，
1 5
，
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
< p>6
．设二叉排序树中有
n
个结点，则在二叉排序树的 平均平均查找长
度为（
）
。
(A) O(1)
(B) O(log
2
n)
(C)
(D) O(n
2
)
7
．设无向图
G
中有
n< /p>
个顶点
e
条边，则其对应的邻接表中的表头结
点和表结点的个数分别为（
）
。
11
(A)
n
，
e
(B) e
，
n
(C) 2n
，
e
(D) n
，
2e
8.
设某强连通图中有
n
个顶点，则该强连通图中至少有（
）条边。
(A) n(n-1)
(B) n+1
(C) n
(D) n(n+1)
9
．
设有
5000
个待排序的记录 关键字，
如果需要用最快的方法选出其
中最小的
10
个记录关键字，
则用下列
（
）
方法可以达到此目的。
(A)
快速排序
(B)
堆排序
(C)
归并排序
(D)
插入排序
10.
下列四种排序中（
）的空间复杂度最大。
(A)
插入排序
(B)
冒泡排序
排序
二、填空殖<
/p>
(
每空
1
分
共
20
分
)
1.
数据的物理结构主要包括
____ _________
和
______________
两种
情况。
2.
设一棵 完全二叉树中有
500
个结点，则该二叉树
的深度为
__________
；若用二叉链表作为该完全二叉树的存储结构，则共
< p>有
___________
个空指针域。
3.
设输入序列为
1
、
2
、
3
，则经过栈的作用后可以得到
___________
种不同的输出序列。
4.
设有向图
G
用邻接 矩阵
A[n][n]
作为存储结构，则该邻接矩阵中
第<
/p>
i
行上所有元素之和等于顶点
i
的
_ _______
，第
i
列上所有元
素之和
等于顶点
i
的
________
。
(C)
堆排序
(D)
归并
12
5.
设哈夫曼树中共有
n
个结点，则该哈夫曼树中有
________
个度数
为
1
的结点。
6.
设有向图
G
中有
n
个顶点
e
条有向边，所有的顶点入度数之和为
d
，则
e
和
d
的关系为
_________
。
7.
_________ _
遍历二叉排序树中的结点可以得到一个递增的关键字
序列（填先序、中
序或后序）
。
8.
设 查找表中有
100
个元素，如果用二分法查找方法查找数据元素
< br>X
，
则最多需要比较
________
次就 可以断定数据元素
X
是否在查找
表中。
9.
不论是顺序存储结构的栈还是链式存储结构的栈， 其入栈和出栈
操作的时间复杂度均为
____________
。
10.
设有
n
个结点的完全二叉树，如果按照从自上到下、从左到右从
1
开始顺序编号 ，则第
i
个结点的双亲结点编号为
____________
，
右孩子结点的编号为
___________
。
11.
设一组初始记录关键字为
(72
，
73
，
71
，
23
，
94
，
16
< p>，5)
，则以记
录
关
键
字
72
为
基
准
的
一
趟
快
速
排
序
结
果
为
_________________
__________
。
12.
设有向 图
G
中有向边的集合
E
={<1
，
2>
，
<2
，
3>
，
<1
，
4>
，
<4
，
2>
，
<4
，
3>}
，则该图的一种拓扑序列为
____________________
。
13.
下列算法实现在顺序散列表中查找值为
x
的关键字，请在下划线
处填上正确的语句。
struct record{int key; int others;};
13
int
hashsqsearch(struct record hashtable[ ],int k)
{
int i,j;
j=i=k % p;
while (hashtable[j].k
ey!=k&&hashtable[j].flag!=0){j=(____) %m;
if (i==j) return(-1);}
if (_______________________ ) return(j); else return(-1);
}
14.
下列算法实现在二叉排序树上查找关键值
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_____________;
}
三、计算题
(
每题
< p>10分，共
30
分
)
1.
已知二叉树的前序遍历序列是
AEFBGCDHIKJ
，中 序遍历序列是
EFAGBCHKIJD
，画出此二叉树，并画出它的后序 线索二叉树。
14
2
．已知待散列的线性表为（
36
，
15
，
40
，
63
，
22
）
，散列用的一维地
址空间为
[0
< p>..6]
，
假定选用的散列函数是
H
（
K
）
= K mod 7
，若发生冲
突采用线性探查法处理，试：
< p>
（
1
）计算出每一个元素的散列地址并在下图中填写出散列表：
`
0
1
2
3
4
5
6
（
2
）求出在查找每 一个元素概率相等情况下的平均查找长度。
3
．已知序 列（
10
，
18
，
4
，
3
，
6
，
12
，
1
，
9
，
18
，
8
）请用快速排序
写出每一趟排序的结果。
四、算法设计题
(
每题
15
分，共
30
分
)
1
．
2
．
设计在单链表中删除值相同的多余结点的算法。
设计一个求结点
x
在二叉树中的双亲结点算法。
数据结构试卷（四）
一、选择题
(
每题
< p>1分共
20
分
)
1
．设一维数组中有
n
个数组元素，则读取第
i< /p>
个数组元素的平均时
间复杂度为（
）
。
(A) O(n)
(B) O(nlog
2
n)
(C) O(1) (D) O(n
2
)
2
．设一棵二叉树的深度为
k
，则该二叉树中 最多有（
）个结点。
(A) 2k-1
(B) 2
k
(C) 2
k-1
(D) 2
k
-1
15
3
．设某无向图中有
n
个顶点
e
条边，则该无向图中所有顶点的入度
之
和为（
）
。
(A) n
(B) e
(C) 2n
(D) 2e
4
．在二叉排序树中插入一个结点的时间复杂度为（
）
。
(A) O(1)
(B) O(n)
(C) O(log
2
n)
(D) O(n
2
)
5
．设某 有向图的邻接表中有
n
个表头结点和
m
个表结点， 则该图中
有（
）条有向边。
(A) n
(B) n-1
(C) m
(D) m-1
6
．设一组初始记录关键字序列为
(345
，
253
，
674
，
924
，
627)
，则用
基数排序需要进行（
）趟的分配和回收才能使得初始关键字序
列变成有序序列。
(A) 3
(B) 4
(C) 5
(D) 8
7
．设用链表作为栈的存储结构则退栈操作（
）
。
(A)
必须判别栈是否为满
(B)
必须判别栈是否为空
(C)
判别栈元素的类型
(D)
对栈不作任何判别
8
．下列四种排序中（
）的空间复杂度最大。
(A)
快速排序
(B)
冒泡排序
堆
9
．设某二叉树中度数为< /p>
0
的结点数为
N
0
，度数为
1
的结点数为
N
l
，
度数为
2
的结点数为
N
2
，则下列等式成立的是（
）
。
(A) N
0
=N
1
+1
(B) N
0
=N
l<
/p>
+N
2
(C) N
0
=N
2
+1
(D) N
0
=2N
1
+l
(C)
希尔排序
(D)
16
10
.
设有序顺序表中有
n
个数据元素，则利用二分查找法查找数据元
素
X
的最多比较次数不超过（
）
。
(A) log
2
n+1
(B) log
2
n-1
(C) log
2
n
二、填空题
(
每空
1
分共
20
分
)
1
．设有
n< /p>
个无序的记录关键字，则直接插入排序的时间复杂度为
________<
/p>
，快速排序的平均时间复杂度为
_________
。
2
．设指针变量
p
指向双向循环链表 中的结点
X
，则删除结点
X
需要
< br>执
行
的
语
句
序
列
为
(D)
log
2
(n+1)
_______
_________________________________________________<
/p>
_
（设结点中的两个指针域分别为
llink
和
rlink
）
。
3
．根据初始关键字序列
(19
，
22
，
01
，
38
，
10)
建立的二叉排序树的
高度为
____________
< p>。
4
．深度为
k
的 完全二叉树中最少有
____________
个结点。
5
．设初始记录关键字序列为
(K
1<
/p>
，
K
2
，…，
n
)
，则用筛选法思想建堆
必须从第
______
个元素开始进行筛选。
6
．设哈夫曼树中共有
99
个结点，
< p>则该树中有_________
个叶子结点；
若采用
二叉链表作为存储结构，则该树中有
_____
个空指针域。
< /p>
7
．设有一个顺序循环队列中有
M
个存储单 元，则该循环队列中最多
能够存储
________
个队 列元素；当前实际存储
________________
个队列元素（
设头指针
F
指向当前队头元素的前一个位置，尾指
针指向
当前队尾元素的位置）
。
17
8
．设顺序线性表中有
n
个数据元素，则第
i
个位置上插入一个数据
元
素需要移动表中
_______
个数据元素；
删除第
i
个位置上的数据
元素需要移动表中
_______< /p>
个元素。
9
．设一组初始记录关键字序列 为
(20
，
18
，
22
< p>，16
，
30
，
19)
，则以
20
为
中
轴
的
一
趟
快
速
排
序
结
果
为
_______________
_______________
。
10
．
设一组初始记录关键字序列为< /p>
(20
，
18
，
22
，
16
，
30
，
19)
< p>，则
根
据
这
些
初
始
关
键
字
序
列
建
成
的
初
始
堆
为
________________________
。
< p>
11
．
设某无向图
G
中有
n
个顶点，用邻接矩阵
A
作为该图的存储
结
构
，
则
顶
点
i
和
顶
点
j< /p>
互
为
邻
接
点
的
条
件
是
__________________
____
。
12
．
< /p>
设无向图对应的邻接矩阵为
A
，
则
A
中第
i
上非
0
元素的个数
_________
第
i
列上非
0
元素的个数（填等于，大于或小于）
。
13
．
设前序遍历某二叉树的序列为< /p>
ABCD
，
中序遍历该二叉树的序
列为
BADC
，则后序遍历该二叉树的序列为
_____________
。
14
．
设散列函数
H(k)=k mod p
，
解决冲突 的方法为链地址法。
要求
在下列算法划线处填上正确的语句完成在散列表
hashtalbe
中查找
关键字值等于
k
的结点，成功时返回指向关键字的指针，不成功
时返回标志
。
typedef struct node
{int key; struct node *next;} lklist;
void createlkhash(lklist *hashtable[ ])
18
{
int i,k;
lklist *s;
( 每题 10 分，共 30<
/p> 分 )
、画出广义表 LS=(( ) , (e) , (a
, (b , c , d
))) 的头尾链表
、下图所示的森林：
求树（ a ）的先根序列和后根序列；
求森林先序序列和中序序列；
3 ）将此森林转换为相应的二叉树；
、设散列表的地址范围是 [
0..9 ] ，散列函数为 H （ key = （ key ） MOD 9, 并采
用链表处理冲突，请画出元素 7 、 4 、
for(i=0;i
for(i=0;i
{
s=(lklist *)malloc(sizeof(lklist));
s->key=a[i];
k=a[i] % p;
s->next=hashtable[k];_______________________;
}
}
三
、计算题
1
存储结构。
2
(1)
(2)
（
19
A
B
D
(a)
C
E
F
I
G
H
J
(b)
K
3
2
+2
、
3
、
6
、
2
、
8
、
9
依次插入散列 表的存储结构。
四、算法设计题
每题
10
分，共
30
分
)
1
．
设单链表中有仅三 类字符的数据元素
(
大写字母、数字和其它字
符
)
，
要求利用原单链表中结点空间设计出三个单链表的算法，
使
每个单链表只包含同类字符。
2.
设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
3.
在链式存储结构上建立一棵二叉排序树。
数据结构试卷（五）
一、选择题
(20
分
)
1
．数据的最小单位是（
）
。
(A)
数据项
(B)
数据类型
数据变量
(C)
数据元素
(D)
20
2
．
设一组初始记录关键字序 列为
(50
，
40
，
95
，
20
，
15
，
70
，
60
，
45)
，
则以增量
d=4
的一趟希尔排序结束后前
4
条记 录关键字为
（
）
。
(A) 40
，
50
，
20
，
95
(C) 15
，
20
，
40
，
45
(B) 15
，
40
，
60
，
20
(D) 45
，
40
，
15
，
20
< br>3
．设一组初始记录关键字序列为
(25
，
50
，
15
，
35
，
80
，
85
，
20
，
< p>40，
36
，
70)
，其中含有
5
个长度为
2
的有序子表，则用归并排 序的方
法对该记录关键字序列进行一趟归并后的结果为（
）
。
(A) 15
，
25
，
3 5
，
50
，
20
，
40
，
80
，
85
，
36
，
70
(B) 15
，
25
，
35
，
50
，
80
，
20
，
85
，
40
，
70
，
36
(C) 15
，
25
，
3 5
，
50
，
80
，
85
，
20
，
36
，
40
，
70
(D) 15
，
25
，
35
，
50
，
80
，
20
，
36
，
40
，
70
，
85
< br>4
．函数
substr(
“
DATASTR UCTURE
”，
5
，
9)
的返回 值为（
）
。
(A)
“
STRUCTURE
”
(C)
“
ASTRUCTUR
”
(B)
“
DATA
”
(D)
“
DATASTRUCTURE
”
5
．设一个有序的单链表中有
n
个结点，现要求插入一 个新结点后使
得单链表仍然保持有序，则该操作的时间复杂度为（
）
。
(A) O(log
2
n)
(B) O(1)
(C) O(n
2
)
(D) O(n)
6
．设一棵
m
叉树中度数为< /p>
0
的结点数为
N
0
，度数为
1
的结点数为
N
l
，……，度数为
m
的结点数为
Nm
< p>，则N
0
=
（
）
。
(A) N
l
+N
2
+
……
+Nm
+(m-1)Nm
(B)
l+N
2
+2N
3
+3N
4
+
…
…
21
(C) N
2
+2N
3
+3N
4
+
……
+(m-1)Nm
+(m+1)Nm
(D)
2N
l
+3N
2
+
…
…
7
．
设有序表中有
1000
个元素，
< p>则用二分查找查找元素X
最多需要比
较（
）次。
(A) 25
(B) 10
(C) 7
(D) 1
8
．设连通图
G
中的边集
E= {(a
，
b)
，
(a
，
< p>e)，
(a
，
c)
，
(b
，
e)
，
(e
，
d)
，
(d
，
f)
，
(f
，
c)}
，则从顶点
a< /p>
出发可以得到一种深度优先遍历的顶
点序列为（
）
。
(A) abedfc
(B) acfebd
(C) aebdfc
(D) aedfcb
9
．设输入序列是
1
、
2
、
3
、……、
< p>n，经过栈的作用后输出序列的第
一个元素是
n
，则输出序列中第
i
个输出元素是（
）
。
(A) n-i
(B) n-1-i
(C) n+1-i
(D)
不能确定
10
设一组初始记录关键字序列为
(45
，
80
，< /p>
55
，
40
，
42
，
85)
，则以
第一个记录关键字
45
为基准而得到一趟快速排序的结果是
（
）
。
(A) 40< /p>
，
42
，
45
，
55
，
80
，
83
85
，
88
(C) 42
，
40
，
45
，
55
，
80
，
85
55
，
80
二、填空题
(
共
20
分
)
(D) 42
，
40
，
4 5
，
85
，
(B) 42
，
40
，
45
，
80
，
22
1.
< /p>
设有一个顺序共享栈
S[0
：
n-1]
，其中第一个栈项指针
top1
的初
值为
-1
，第二个栈顶指针
top2
的初值为
n
，则判断共享栈满的条
件是
_______________ _____
。
2.
在
图
的
邻
接
表
中
用
顺
序
存
储
结
构
存
储
表
头
结
点
的
优
点
是
_____
_______________
。
3.
设有一个
n
阶的下 三角矩阵
A
，如果按照行的顺序将下三角矩阵
中的元素（
包括对角线上元素）存放在
n(n+1)
个连续的存储单元
中，则
A[i][j]
与
A[0][0]
之间有
_______
个数据元素。
4.
栈的插入和删除只能在栈的栈顶进行，
< p>后进栈的元素必定先出栈，
所以又把栈称为
__________< /p>
表；队列的插入和删除运算分别在队
列的两端进行，先进队列的元素必定先
出队列，所以又把队列称
为
_________
表。
5.
设一棵完全二叉树的顺序存储结构中 存储数据元素为
ABCDEF
，则
该
二< /p>
叉
树
的
前
序
遍
历
序
列
为
___________
，
中
序
遍
历
序
< p>列为
___________
，后序遍历序列为
___________
。
6.
设一棵完全二叉树有
128
个结点，则该完全二叉树的深度为
________
，有
__________
个叶子结点。
7.
设有向图
G
的存储 结构用邻接矩阵
A
来表示，则
A
中第
i
行中所
有非零元素个数之和等于顶点
i
的
________
，第
i
列中所有非零
元素个数之和等于顶点
i
的
_________ _
。
8.
设一组初始 记录关键字序列
(k
1
，
k
2
，
……，
k
n
)
是堆，
则对
i=1
，
2
，
…，
n/2
而言满 足的条件为
_______________________________
。
23
9.
下面程序段的功能是实现冒泡排序算法，请在下划 线处填上正确
的语句。
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.
下
面程序段的功能是实现二分查找算法，请在下划线处填上正确
的语句。<
/p>
struct record{int key; int
others;};
int bisearch(struct record r[
], int k)
{
int low=0,mid,high=n-1;
while(low<=high)
24
{
________________________________;
if(r[mid].key==k)
return(mid+1);
else
if(____________)
high=mid-1;else low=mid+1;
}
return(0);
}
三、应用题
(32
分
)
1.
设某棵二叉树的中序遍历序列为
D BEAC
，前序遍
历序列为
ABDEC
， 要求给出该二叉树的的后序遍
历序列。
2.
设无向图
G
（如右 图所示）
，给出该图的最小生成树上边的集合并
计算最小生成树各边上的
权值之和。
3.
设一组初始记录关键 字序列为
(15
，
17
，
18
，
22
，
35
，
51< /p>
，
60)
，
要求计算出成功查找时的平均查
找长度。
4.
设散列表的长度为
8
，散列函数
H(k)=k mod 7
，初始记录关键字
序列为
(25
，
31
，
8
，
27
，
13
，
68)
，要求分别计算出用线性探测法
和链地址法作为解决冲突方法的平均查找长度。
四、算法设计题
(28
分
)
1
．
2
．
设计判断两个二叉树是否相同的算法。
设计两个有序单链表的合并排序算法。
25
数据结构试卷（六）
一、选择题
(30
分
)
1
．
设一组权值集合
W ={2
，
3
，
4
，
5
，
6}
，则由该权值集合构造的哈
夫曼
树中带权路径长度之和为（
）
。
(A) 20
(B) 30
(C) 40
(D) 45
2
．执行一趟快速排序能够得到的序列是（
）
。
(A) [41
，
12
，
34
，
4 5
，
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]
< br>3
．设一条单链表的头指针变量为
head
且该链表没有头 结点，则其判
空条件是（
）
。
(A) head==0
(B) head->next==0
(D)
head!=0
(C) head->next==head
4
．时间复杂度不受数据初始状态影响而恒为
O(nlog
2
n)
的是（
）
。
(A)
堆排序
(B)
冒泡排序
快速排序
(C)
希尔排序
(D)
26