(完好版)数据构造期末考试试题及答案.docx
(完好版)数据构造期末考试试题及答案数据构造期末考试试题及答案期末样卷参考答案一是非题每题1分共10分1.线性表的链式存储构造优于顺序存储构造。F2.栈和队列也是线性表。假如需要，可对它们中的任一元素进行操作。F3字符串是数据对象特定的线性表。T4在单链表P指针所指结点之后插入S结点的操作是：P->next=S;S->next=P->next;F5一个无向图的连通分量是其极大的连通子图。T6邻接表能够表示有向图，可以以表示无向图。T7假设B是一棵树，B是对应的二叉树。则B的后根遍历相当于B的中序遍历。T8通常，二叉树的第i层上有2i-1个结点。F9对于一棵m阶的B-树,树中每个结点至多有m个关键字。除根之外的所有非终端结点至少有é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适用于查找有序单链表。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/2f.m8已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。下列选择中c是快速排序一趟排序的结果。b是希尔排序初始步长为4一趟排序的结果。d是基数排序一趟排序的结果。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。三填空题每题2分共20分1有向图的存储构造有邻接矩阵、邻接表、十字链表等方法。2已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。其后序遍历次序为edcgbfa。层次遍历次序为afbcgde。3设有二维数组A5x7,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是144；按列存储时，元素A14的第一个字节的地址是184。4请在下划线上填入适当的语句，完成下面法算。StatusPreordertraverse(BitreeT,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将图示森林转换为二叉树，并对该二叉树中序全序线索化。2已知Hash函数为HK=Kmod13，散列地址为0-14，用二次探测再散列处理冲突，给出关键字23，34，56，24，75，12，49,52，36，92，06，55在散列地址的分布。012345678910111213143.右图为一棵3阶B树。20，25a.画出在该树上插入元素15后的B树。b.接着，再删除元素35，画出删除后的B树。(10,14)21354.已知某无向图的邻接表存储构造如下图。a.请画出该图。b.根据存储构造给出其深度优先遍历序列及广度优先遍历序列。c.画出其深度优先生成树及广度优先生成树。0a24/1b234/2c014/3d1/4e012/5.设在某通信系统中使用了八个字符，它们出现的频率分别为0.08，0.05，0.1，0.12，0.26，0.18，0.14，0.07，试构造一棵赫夫曼树，并给出赫夫曼编码。五算法设计题共17分1.单链表结点的类型定义如下：typedefstructLNodeintdata;structLNode*next;LNode,*Linklist;写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。(注:不毁坏A和B的原有构造.)Merge(LinklistA,LinklistB,Linklist&C)voidMerge(LinklistA,LinklistB,Linklist&C)C=(Linklist)malloc(sizeof(LNode);pa=A->next;pb=B->next;pc=C;while(pa&&pb)pc->next=(Linklist)malloc(sizeof(LNode);pc=pc->next;if(pa->datadata)pc->data=pa->data;pa=pa->next;elsepc->data=pb->data;pb=pb->next;if(!pa)pa=pb;while(pa)pc->next=(Linklist)malloc(sizeof(LNode);pc=pc->next;pc->data=pa->data;pa=pa->next;pc->next=NULL;2.二叉树用二叉链表存储表示。typedefstructBiTNodeTelemTypedata;StructBiTNode*lchild,*rchild;BiTNode,*BiTree;编写一个复制一棵二叉树的递归算法。BiTreeCopyTree(BiTreeT)if(!T)returnNULL;if(!(newT=(BiTNode*)malloc(sizeof(BiTNode)exit(Overflow);newT->data=T->data;newT->lchild=CopyTree(T->lchild);newT->rchild=CopyTree(T->rchild);returnnewT;
