数据结构暨南大学期末试卷试题
- 格式:doc
- 大小:15.50 KB
- 文档页数:4
数据结构暨南大学期末试卷试题
一、判断题(共10分)
1. 当静态链表采用数组实现时,插入与删除操作仍需移动元素。
2. 栈也是一种线性表,也同样有顺序存储结构和链式存储结构。
3. 二叉树的三种遍历算法区别仅在于对树根、左右子树访问先后顺序的不同。
4. 邻接表是图的一种顺序存储结构。
5. 二叉树就是度数为2的树。
6. 在哈希表中勿需比较就可找到记录在表中的位置。
7. 线性表的链式存储结构既方便其存取操作,也方便其插入与删除操作。 8. 顺序存储结构既适合于完全二叉树,也同样适合于一般的二叉树。
9.一个算法是正确的、高效率的,还不能说它就是一个“好”的算法。
10. 快速排序与堆排序的平均时间复杂度相同。
二、概念填空(共20分,每题2分)
1.对顺序存储结构的线性表,设表长为La;在各元素插入为等概率条件下,插入一个数据元素需平均移动表中元素_______ 个;在最坏情况下需移动表中元素
_______ 个。 2.从逻辑角度看,四种基本的数据结构可分为__________、
___________、____________和____________;两种存储结构为_____________和
_________________。
3.一个深度为,的满k(k>2)叉树,其第i层(若存在)有________个结点;编号为p(p>1)的结点其父结点(父结点为非根结点)编号是___________________。
4.具有n个结点的完全二叉树的深度为____________;编号为p( 5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。 6.静态查找表的查找方法主要有:有序表查找及 ________________________;在n个记录中进行折半查找,当查找不成功时,与关键字比较次数最多为_____________________。 7.一颗9阶的,_ 树,其每个结点(除根外)的子树数目为________________,关健字数目为________________。 8.内部排序方法大致可分为__________、___________、____________、 __________和_________等五类;简单排序方法的时间复杂度为_________。 9.外部排序分为两个相对独立的阶段。首先产生有序子文件即___________;然后对它们进行__________,直至整个文件有序为止。 10.文件的组织方式有_________________等三种;顺序文件又可分为 _________________两大类。 三、算法(共70分) 要求:对1、2、3题,在它们的下划线处填空;对4、5、6、7题,从第7题以下的空白纸张处开始书写,标明题号且只写出最终结果即可。 1. 算法填空题 (12分) Int Search_Bin(SSTable ST, KeyType key) { 在有序表ST中折半查找其关键字等于key的数据元素。若找到,则函数值为该元素在表中的位置,否则为0。 Low =1; high=ST.length; While (__________________){ mid=_______________________; if EQ(key, ST.elem[mid].key) return mid; else if LT( key, ST.elem[mid].key) high=______________; else low=______________; } return 0; } 2. 算法填空题 (9分) 中序遍历二叉树T的递归算法,对数据元素操作调用函数printf()。struct TNode{ char data; struct TNode * lchild, * rchild; } InOrderTraverse(struct TNode *T){ if (T){ InOrderTraverse(______________); printf("%c",______________); InOrderTraverse(______________); } } 3. 算法填空 (9分) typedef struct{ char *base; char *top; int stacksize; }SqStack; void Pop(SqStack *S0, char *e){ //若栈不空,则删除栈顶元素,用e返回其值。 if(S0->top= =_____________) return; ______________; *e=*(________________); } 4. 给出一整数序列(4,2,5,6, 3),对其进行从小到大排序,分别选用直接插入排序、2—路归并排序及快速排序三种方法,写出这三种方法的一趟排序结果。(10分) 5. 已知一颗3阶的B-树(见下图),依次插入关键字3及90,分别写出每插入一个关键字后所生成的B-树? (10分)。 6. 已知一无向带权图(见下图),写出其最小生成树 (10分)。 7. 已知4个结点的权值为,20,30,32,40,78,,构造一颗赫夫曼树,并写出其赫夫曼编码 (10分)。