资源描述：
《杭州电子科技大学 数据结构 期末样卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、期末样卷参考答案一．是非题（每题1分共10分）1.线性表的链式存储结构优于顺序存储结构。F2.栈和队列也是线性表。如果需要，可对它们中的任一元素进行插入/删除操作。F3．栈是数据对象特定的线性表。F4．在单链表P指针所指结点之后插入S结点的操作是：P->next=S;S->next=P->next;F5．一个无向图的连通分量是其极大的连通子图。T6．邻接表可以表示有向图，也可以表示无向图。T7．假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。T8．通常，二叉树的第i层上有2i-1个结点。F9．对于一棵m阶的B-树，树中每个结点至多有m个关键
2、字。除根之外的所有非终端结点至少有ém/2ù个关键字。F10．对于任何待排序序列来说，快速排序均快于起泡排序。F二．选择题（每题2分共28分）1．在下列排序方法中，（c）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（d）方法所有情况下时间复杂度均为0(nlogn)。a.插入排序b.希尔排序c.快速排序d.堆排序2.在有n个结点的二叉树的二叉链表表示中，空指针数为（b）。a.不定b.n+1c.nd.n-13.下列二叉树中，（a）可用于实现符号不等长高效编码。a.最优二叉树b.次优查找树c.二叉平衡树d.二叉排序树4.下列查找方法中，（a）
3、适用于查找有序单链表。a.顺序查找b.二分查找c.分块查找d.哈希查找5.在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（a）方法。a.设置监视哨b.链表存贮c.二分查找d.快速查找6.在下列数据结构中，（c）具有先进先出特性，（b）具有先进后出特性。a．线性表b．栈c．队列d．广义表7．具有m个结点的二叉排序树，其最大深度为（f），最小深度为（b）。a.log2mb.└log2m┘+1c.m/2d.┌m/2┐-1e.┌m/2┐f.m8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57
4、。下列选择中（c）是快速排序一趟排序的结果。（b）是希尔排序（初始步长为4）一趟排序的结果。（e）是起泡排序一趟排序的结果。（a）是初始堆（大堆顶）。a.84，79，64，37，57，52，58，26，28，34，56。b.28，34，57，26，56，52，58，37，79，84，64。c.28，34，37，26，52，56，64，79，58，84，57。d.52，34，64，84，56，26，37，57，58，28，79。e.34，56，26，58，52，64，37，28，79，57，84。f.34，56，26，58，52，79，37，64，28，84，57。
5、三．填空题（每题2分共20分）1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。其后序遍历次序为（edcgbfa）。层次遍历次序为（afbcgde）。3．已知如下程序段for(i=n;i>0;i--){语句1}{x++;{语句2}for(j=n;j>=i;i--){语句3}y++;{语句4}};语句1执行的频度为（n+1）；语句4执行的频度为（n(n+1)/2）。4．请在下划线上填入适当的语句，完成以下法算。StatusPreordertraverse(BitreeT,
6、Status(*Visit)(Telemtypee)){//先序非递归遍历二叉树。Initstack(S);Push(S,T);While(!stackempty(S)){While(gettop(S,p)&&p){visit(p->data);push(S,p->lchild;}Pop(S,p);If(!stackempty(s)){pop(S,p);push(S,p->rchild);}}returnok;四．简答题（每题5分共25分）1．将图示森林转换为二叉树，并对该二叉树中序全序线索化。abdjcehfgmlkiabdjcehfgmlki2．已知Hash函
7、数为H（K）=Kmod13，散列地址为0--14，用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49，52，36，92，06，55）在散列表中的分布，并求在等概率情况下查找成功的平均查找长度。01234567891011121314529255563606347523241249ASL=22/12=11/63.右图为一棵3阶B树。（20，25）a.画出在该树上插入元素15后的B树。／│＼b.接着，再删除元素35，画出删除后的B树。(10,14)（21）（35）1420101521,2520142510152135a.b.4.已知某无向图
8、的邻接表存
