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