二、填空题(每空1分,共26分)
1. 通常从四个方面评价算法的质量:_________、_________、_________和_________。 2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为________。 3. 假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中所含的结点数为
__________个,树的深度为___________,树的度为_________。
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条件进行划分,使得同一余数的元
素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 10. 向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度
___________。
11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序
过程的时间复杂度为________。
12. 在快速排序、堆排序、归并排序中,_________排序是稳定的。 三、计算题(每题 6 分,共24分)
1. 在如下数组A中链接存储了一个线性表,表头指针为A [0].next,试写出该线性表。 A 0 1 2 3 4 5 6 7
data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2. 请画出下图的邻接矩阵和邻接表。
3. 已知一个图的顶点集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)
{ey!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1);
}
1. 下列算法实现在二叉排序树上查找关键值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_____________; }
三、计算题(每题10分,共30分)
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHKIJD,画出此二叉树,并画出它的后序线索二叉树。
2.已知待散列的线性表为(36,15,40,63,22),散列用的一维地址空间为[0..6],假定选用的散列函数是H(K)= K mod 7,若发生冲突采用线性探查法处理,试: (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在二叉树中的双亲结点算法。
数据结构试卷(四)
二、填空题(每空1分共 20分) 1. 设有n个无序的记录关键字,则直接插入排序的时间复杂度为________,快速排序的平
均时间复杂度为_________。
2. 设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为
_________________________________________________________(设结点中的两个指针域分别为llink和rlink)。
3. 根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为____________。 4. 深度为k的完全二叉树中最少有____________个结点。
5. 设初始记录关键字序列为(K1,K2,…,Kn),则用筛选法思想建堆必须从第______个元
素开始进行筛选。
6. 设哈夫曼树中共有99个结点,则该树中有_________个叶子结点;若采用二叉链表作为
存储结构,则该树中有_____个空指针域。
7. 设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储________个
队列元素;当前实际存储________________个队列元素(设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。
8. 设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中
_______个数据元素;删除第i个位置上的数据元素需要移动表中_______个元素。 9. 设一组初始记录关键字序列为(20,18,22,16,30,19),则以20为中轴的一趟快速
排序结果为______________________________。 10. 设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字
序列建成的初始堆为________________________。 11. 设某无向图G中有n个顶点,用邻接矩阵A作为该图的存储结构,则顶点i和顶点
j互为邻接点的条件是______________________。 12. 设无向图对应的邻接矩阵为A,则A中第i上非0元素的个数_________第i列上非
0元素的个数(填等于,大于或小于)。 13. 设前序遍历某二叉树的序列为ABCD,中序遍历该二叉树的序列为BADC,则后序遍
历该二叉树的序列为_____________。 14. 设散列函数H(k)=k mod p,解决冲突的方法为链地址法。要求在下列算法划线处填
上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点,成功时返回指向关键字的指针,不成功时返回标志0。
typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]) {
int i,k; lklist *s;
for(i=0;i s=(lklist *)malloc(sizeof(lklist)); s->key=a[i]; k=a[i] % p; s->next=hashtable[k];_______________________; } }