2013 年 12 月份考试数据结构第三次作业一、填空题 （共15题、总分30分）1.由3个结点所构成的二叉树有 （5 ）种形态。
（本 题分数 2 分。
）2.对不同的关键字可能得到同一哈希地址，即 key1key2 ，而 f（key1）f（key2），这种现象称 为 碰撞 。具有相同函数值的关键字对该哈希函数来说称作 __同义词 。（本题分数 2 分。
）3.在AOE网中，路径长度最长的路径叫做 关键路径 。（本题分数2分。）4.在一个循环队列中，队尾指针指向队尾元素的 尾 位置。
（本题分数 2 分。
）5.构造最小生成树的方法主要有克鲁斯卡尔 和 普里姆斯。（本题分数 2分。
）6.带表头结点的空循环双向链表的长度等于 0。（本题分数 2 分。
）7.为了实现逐层访问，算法中使用了一个 临时变量 ，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。（本题分数 2 分。
）8.顺序表中逻辑上相邻的元素的物理位置 也是 相邻。
单链表中逻辑上相邻的元素的物 理位置 不 相邻。（本题分数 2 分。
）9.二叉树的基本组成部分是根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种前序法（即按 N L R 次序），后序法（即按1 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是 BEFCGDH中序序列是FEBGCH D则它的后序序列必是FEGHDCB 。（本题分数 2 分。
）10.基数排序法、堆排序法与归并排序法中，堆排序 排序方法需要的辅助存储单元最少。（本题分数 2 分。
）12.邻接多重表是 无向图 的另一种链式存储结构。13.快速排序算法在最坏情况下的时间复杂度为O（n2）（本题分数 2 分。
）（本题分数 2 分。
）14.线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L23,17,47,05,31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示05U17X23V31Y47Z其中指针 X,Y,Z 的值 X 1Y 2Z 该线性表的首结点起始地址为多少末15.AOV 网络用 顶点表示活动,用弧 表示活动间的优先关系。（本题分数结点的起始地址为 首址3 末址4（本题分数 2 分。）2 分。
）二、程序阅读题 共 2 题、总分 10 分1.指出下述程序段的功能是什么 void Demo1SeqStack *Sint i; arr64 ; n0 ;while StackEmptyS arrnPopS;for i0,i n; iPushS,arri; //Demo1 本题分数 5 分。
把栈进行逆向2.指出下述程序段的功能是什么 CirQueue Q1,Q2; //设 DataType 为 int 型int x,i ,n 0;...//设Q1已有内容，Q2已初始化过while QueueEmpty EnQueue n;for i0; i n; i xDeQueueEnQueue EnQueue 本题分数 5 分。
三、简答题 （共 10题、总分 50分）1.多重链表存储结构的特点。
（ 本题分数 5 分。
）多重链表存是无向图的另一种存储结构,在邻接表中一条边用两个节点表 示,而多重链表只有一个节点。2.利用 Dijkstra 算法求下图中从顶点 a 到其他各顶点间的最短路径A,C D,F GD CF FD BE（本题分数3.简述KRUSKA算法的思想。（本题分数5分。）把n个顶点看成看成n棵分离的树（每棵树只有一个顶点），每次选取可连 接两个分离树中权值最小的边把两个分离的树合成一个新的树取代原来的两个 分离树，如果重复n-1步后便得到最小生成树。4.给定二叉树的两种遍历序列，分别是前序遍历序列D,A，C,E，B,H,F，G I ；中序遍历序列D,C,B，E，H,A，G,I，F,试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树 B的思想方 法。（本题分数5分。）二叉树B的后序遍历为DHECIGFAD5.二叉排序树的删除可能会有哪三种情况。（本题分数5分。）1.删除的节点为叶子节点2.删除的节点没有左子树3.删除的节点没有右子树6.列出（至少三种）构造散列函数的方法（本题分数5分。）开放定址法连地址法再哈希法7.何时选用顺序表、何时选用链表作为线性表的存储结构为宜 （本题分数 5分。）顺序表用于随机访问、有序的时候可用二分法查找方便，不宜用于删除与插 入比较频繁的操作。链表主要用于删除与增加方面的操作不需要移动大量元素给出下图的广度优先搜索序列8.（本题分数5分。）VI，V2,V5,V3,V4,V69.在顺序表中插入和删除一个结点需平均移动多少个结点具体的移动次数取决于哪两个因素（本题分数5分。）插入需要移动n/2删除需要移动（n -1）/2移动次数取决于插入或删除元素的位置10.空串和空格串有无区别（本题分数5分。）零个字符的串称为空串。由一个或多个空格字符组成的串称为空格串。四、程序设计题（共2题、总分10分）1.设以带头结点的双向循环链表表示的线性表L（a1，a2，...，an），试写一时间复杂度为0（n）的算法，将L改造为L（a1，a3,...，an...，a4,a2）（本题分数5分。）2.以二叉链表为存储结构，分别写出在二叉树中查找值为x的结点及求x所在 结点在树中层数的算法。本题分数5分。typedef struct no dei nt key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearchbitree *t,intkey,i nt in dex;ift_keykeyflag1;return t;elselfflagindex,flag;index,flag;bstsearcht-lchild,key,Ifflag bstsearcht-rchild,key,