南昌大学～学年第二学期数据结构期末考试标准答案C.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

南昌大学 ～ 第二学期期末考试试卷
试卷编号:
(C)卷
课程编号:
课程名称: 数据结构考试形式: 闭卷
适用班级: 计算机系 07级 姓名:
学院: 信息工程学院 专业: 计算机科学与技术 考试日期:
学号:
班级:
题号
题分
得分
一
二
三
四
五
六
七
八
九
十
总分 累分人
签名
30
20
20
30
100
考生注意事项: 1、 本试卷共 7 页, 请查看试卷中是否有缺页或破损。如有立即举手报告以便更
换。
2、 考试结束后, 考生不得将试卷、 答题纸和草稿纸带出考场。
一、 填空题(每空 2分, 共 30分)
得分 评阅人
1. 若要在一个单链表的*p结点之前插入一个*s结点, 可执行以下操作:
s->next= p->next
;s->data= t
2. 在计算机软件系统中, 有两种处理字符长度的方法, 一种是
, 第二种是 长度指针
; p->next=s; t=p->date;p->data=
s->data
。
固定长
度
。
3. 假定对线性表R[059]进行分块检索, 共分10块, 每块长度等于6。若假定检索索引
和 块 均 用 顺 序 检 索 的 方 法 , 则 检 索 每 个 元 素 的 平 均 检 索 时 间 为
9 。
4. 一组记录( 50,40,95,20,15,70,60,45,80) 进行冒泡排序时, 第一趟需进行相邻记
录的交换次数为
成。
5. 在堆排序、 快速排序和归并排序中, 若从节省存储空间角度考虑, 应首先选取
6
, 在整个排序过程中共需进行
7
趟才可完
堆排序
方法, 其次选
快速排序
方法, 最后选择
归并排序方法; 若从排序结构的稳定性角度考虑, 应选取 归并排序
若从平均情况下排序的速度来考虑, 则选择 快速排序
方法;
方法; 若从最坏情
方法。
况下排序最快而且要节省内存角度考虑, 则应该取
堆排序
6、 一个算法, 如果不论问题规模大小, 运行所需时间都是一样, 则该算法的时间复杂
度是 O(1) 。
第 1 页 共 6页

二、 判断题( 每题1分, 共20分, 正确打√, 错的打×)
得分 评阅人
1. 具有线性关系集合中, 若 a,b 是集合中的任意两个元素, 则必定有 a<b 的关系。
( × )
2. 二叉搜索树的左、 右子树都是二叉搜索树。( √ )
3. 在堆中执行 INSERT和 DELETEMIN运算都只需 O(log2n)时间。( √ )
4. 一棵满二叉树同时又是一棵平衡树。( × )
5. 即使某排序算法是不稳定的, 但该方法仍可能有实际应用价值。( √ )
6. 连通分量是无向图中的极小连通子图。( × )
7. 先序遍历一棵二叉搜索树所的结点访问序列不可能是键值递增序列。( × )
8. 不论 adt 栈是用数组实现, 还是用指针实现, Pop(s)与 Push(x,s)的耗时均为 O(n)。
( × )
9. 表中的每一个元素都有一个前驱元素和一个后继元素。( × )
10. 作为解决一类特定问题的算法, 不能没有输入运算项。( × )
11. 数据元素是数据的最小单元。( × )
12. 在单链表中任何两个元素的存储位置之间都有固定的联系, 因此能够从头结点进
行查找任何一个元素。( × )
13. 设有两个串 p 和 q, 其中 q 是 p 的子串, 把 q 在 p 中首次出现的位置作为 q 在 p
中的位置的算法称为匹配。( √ )
14. 若有一个叶子结点是某子树的中序遍历的最后一个结点, 则它必是该子树的先序
遍历的最后一个结点。( × )
15. 对于 n 个记录的集合进行冒泡排序, 在最坏的情况下的时间复杂度是 O(n2)。
( √ )
16. 用相邻矩阵法存储一个图时, 在不考虑压缩存储的情况下, 所占用的存储空间大
小与图中结点的个数有关, 而与图的边数无关。( √ )
17. 哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。
( × )
18. 因为算法和程序没有区别, 因此在数据结构中二者是通用的。( × )
19. 按中序遍历一棵二叉排序树所得的中序遍历序列是一个递增序列。( √ )
20. 进栈操作 push(x,s)作用于链接栈时, 无须判满。( × )
第 2 页 共 6页

三、 解答题( 共20分)
得分 评阅人
1、 已知一棵二叉树的中序遍历结果为 DBHEAFICG, 后序遍历结果为 DHEBIFGCA,
画出该二叉树。( 10分)
解答:
2．设哈希表的地址空间为0..16, 开始时哈希表为空, 用线性探测再散列法处理冲突,
对于数据元素Jan, Feb, Mar,Jun, Aug, Sep, Oct, Nev, Dev, 试构造其对应的散列
表, H(key)=i/2,其中i为关键字第一个字母在字母表中的序号。( 10分)
解答:
依题意 m=17, 线性探测开放地址法下一地址计算公式为:
d1=H(key)
dj+1=(dj+1)%m; j=1,2,…..
其计算函数如下:
H(Jan) = 10/2 = 5;
H(Feb) = 6/2 = 3
H(Mar) = 13/2 = 6
H(Jun) = 10/2 = 5 冲突
H(Jun)= (5+1)%17 = 6 仍冲突
H(Jun)= (6+1)%17 = 7
H(Aug) = 1/2 = 0
H(Sep)= 19/2 = 9
H(Oct)=15/2 = 7冲突
H(Oct)=(7+1)%17 = 8
H(Nev) = 14/2 = 7 冲突
H(Nev)=(7+1)%17 = 8仍冲突
H(Nev)=(8+1)%17= 9仍冲突
H(Nev)=(9+1)%17 =10
H(Dec)= 4/2 = 2; 冲突
H(Dec)=(2+1)%17 = 3仍冲突
H(Dec)=(3+1)%17 = 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Au
g
Fe De Ja Ma Ju Oc Se Ne
b c n r n t p v
第 3 页 共 6页

四、 编程题( 共30分)
得分 评阅人
1. 编一个程序, 输出二叉搜索树 BT中的最小键值( 15分)
解答
void min(bitree *BT)
{
bitree *p;
p = BT;
while(p->lchild != NULL)
{
p = p->lchild;
}
printf("%d\n", p->key);
}
第 4 页 共 6页

2. 编写算法, 在一棵二叉树中查找值为x的叶子结点, 找到返回该结点的指针, 找
不到返回空指针。( 15分)
已知二叉树结点数据结构如下:
Typedef struct linkNode
{
int data;
struct linkNode *lchild,*rchild;
} Node;
解: Node *searchnode(int x,Node *r)
{
Node *p;
if(r == NULL)
{
p = NULL;
}
else
{
if(x == r->data)
{
p = r;
}
else if(x != r->lchild->data)
{
p = searchnode(x, r->lchild);
}
else if(x != r->rchile->data)
{
p = searchnode(x, r->rchild);
}
}
return p;
}
第 5 页 共 6页

第 6 页 共 6页