《[2017年整理]数据结构复习(1)》由会员分享，可在线阅读，更多相关《[2017年整理]数据结构复习(1)（4页珍藏版）》请在金锄头文库上搜索。
1、1. （6 分）将关键字序列（7,8,30,11,18,9,14）散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一维数组。散列函数是： H(key)=(key*3) MOD 7，处理冲突采用线性探测再散列法，要求装填因子为 0.7。要求：（1）画出所构造的散列表；（ 2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。（1）因为装填系数是 0.7，所以表长=7/0.7=10，数组下标为 09. -（1 分）H(key)=(key*3) MOD 7： (7*3) MOD 7=0，(8*3) MOD 7=3，(30*3) MOD 7=6，(11*3) MOD 7=5，(18*
2、3) MOD 7=5（冲突） ，(5+1) MOD 10=6（冲突） ，(5+2) MOD 10=7，(9*3) MOD 7=6（冲突） ，(6+1) MOD 10=7（冲突） ，(6+2) MOD 10=8，(14*3) MOD 7=0（冲突） ，(0+1) MOD 10=1 散列表如下图（3 分，若错误看过程酌情给分）0 1 2 3 4 5 6 7 8 97 14 8 11 30 18 9（2）等概率情况下查找成功的 ASL=12/7=1.71（1 分）等概率情况下查找成功的 ASL=（3+2+1+2+1+5+4）=18/7=2.57（1 分）2. （6 分）写出邻接表存储的图的存储结构定
3、义，并使用克鲁斯卡尔算法求其最小生成树（要求给出每个步骤） 。（1）邻接表的类型定义：const MAX_VERTEX_NUM=20;typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针InfoType weight; /指向该弧相关的权值ArcNode; typedef struct VNodeVertexType data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧VNode, AdjListMAX_VERTEX_NUM; const MAX_VE
4、RTEX_NUM=20;typedef structAdjList vertices;int vexnum, arcnum; /图的当前顶点数和弧数int kind; /图的种类标志ALGraph; （2）生成树（每条边 0.5 分）0 1 （ 1） 4 2 3 4 6 7 5 1 4 2 3 4 5 6 （ 3） 6 7 5 1 4 2 3 4 5 6 （ 4） 6 8 7 5 1 4 2 3 12 4 5 6 （ 5） 6 8 7 5 1 4 2 3 12 4 5 6 18 （ 6） 6 8 7 5 4 2 3 4 6 7 5 5 1 （ 2） 20 1 4 25 2 3 12 4 10
5、5 6 18 7 6 23 15 8 7 5 3.（6 分）已知有 6 个顶点（顶点编号为 05）单位有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行主序（行优先）保存在如下的一维数组中。4 6 5 4 3 3 3要求：（1）写出 G 的邻接矩阵 A；（2）画出图 G；（3）写出从顶点 0 出发进行深度优先搜索和广度优先搜索的遍历顺序。（1）G 的邻接矩阵 A （2 分）（2）图 G（2 分）003450641302 545634 33（3）从顶点 0 出发的深度优先搜索的遍历：012453 （1 分）从顶点 0 出发的广度优先搜索的遍历：012345 （1 分）4.（6 分） 根据给定的关
6、键字序列（5，18，26，88，45，78，81）构造一棵平衡二叉树，要求给出插入每个关键字的步骤。5. （6 分）求下图的关键路径及非关键活动的松弛时间。acbdegkfha9=6a1=6a2=4a3=5a4=1a5=5a6=6a11=4a10=4a8=7a7=85(5)185(18)26(26)51826(88)51888(45)518882645(78)18457888265(81)2452813713 78 88上表各 2 分。活动 a2,a3,a5,a6,a7,a9,a10,a11 为关键活动。 （1 分）a1 的松弛时间为 2，a 4 的松弛时间为 2，a 8 的松弛时间为 1。
7、（1 分）1. 已知一个带有表头结点的单链表，假设该链表只给出了头指针 L。要求：（1）写出单链表 LinkList 的定义；（2）在不改变单链表的前提下，设计一个尽可能高效的算法，查找链表中的倒数第 k 个位置上的结点（k 为正整数） 。若查找成功，算法输出该结点的域的值，并返回 True；否则，只返回 False。算法的函数头为：bool InverseSearchList(LinkList L,int k,ElemType &e)。自己想2.请写出树按层次遍历的算法，树采用孩子-兄弟表示法存储。要求先写出树的存储结构，再写层次遍历函数。typedef struct CSNode Elem
8、 data; struct CSNode *firstchild,*nextSibling;CSNode,*CSTree; void BFSTraverse(CSTree T) SqQueue Q; CSNode *p=T; InitQueue_Sq(Q); if(T)EnQueue_Sq(Q,T); while(!QueueEmpty_Sq(Q) DeQueue_Sq(Q,p); coutdata firstchild) EnQueue_Sq(Q,p- firstchild ); p=p- firstchild; while(p- nextSibling) EnQueue_Sq(Q,p- nextSibling); p=p- nextSibling /while/if/BFSTraverse212117171717111199554486000171701717011111109099055044286000000220abcdefghka1a2a3a4a5a6a7a8a9a10a11
