数据结构联考试卷2及答案

试卷2第一页共六页一、单项选择题(每小题2分，共30分)1.在数据结构中，数据的逻辑结构可以分成（）。A.动态结构和静态结构B.内部结构和外部结构C.线性结构和非线性结构D.紧凑结构和非紧揍结构2．以下与数据的存储结构无关的术语是（）。A．哈希表B．栈C．循环队列D．链表3．设某棵二叉树的中序遍历序列为ABCDE，先序遍历序列为CABED，则后序遍历该二叉树得到序列为（）。A.BAEDCB.CAEDBC.BADCED.BADEC4．队和栈的主要区别是（）。A.逻辑结构不同B.所包含的运算个数不同C.限定插入和删除的位置不同D.存储结构不同5．对于哈希函数H(key)=key%17,被称为同义词的关键字是（）。A.38和41B.19和44C.27和39D.33和506．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）。A.2，3，5，1，6，4B.2，4，3，1，5，6C.3，2，4，1，6，5D.4，3，2，1，5，67．二维数组A[12][18]采用以列为主优先存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A[10][8]的地址为（）。A.609B.612C.465D.4688.设某棵二叉树中有2200个结点，则该二叉树的最小高度为（）。A.9B.10C.11D.129．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边A.mB.m–1C.nD.n-110．从广义表LS＝((a,b),c,d)中分解出原子b的运算是（）。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(LS)))D.tail(tail(head(LS)))11．具有12个叶子结点的二叉树中有（）个度为2的结点。试卷2第二页共六页A.9B.10C.11D.1212．在二叉树的先序遍历序列、中序遍历序列和后序遍历序列中，所有叶子结点的先后顺序（）。A．都不相同B．先序和中序相同，但与后序不同C．完全相同D．后序和中序相同，但与先序不同13．下面说法不正确的是（）。A.图的遍历有两种基本算法：深度优先搜索遍历和广度优先搜索遍历B.图的遍历是指从给定源点出发访问且只访问一次每个顶点C.图的深度优先搜索遍历算法不适用于有向图D.图的深度优先搜索遍历是一个递归的过程14．对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为（）。A.(23，56，78，66，88，92，19，34)B.(19，23，67，56，34，78，92，88)C.(19，23，34，56，67，78，88，92)D.(19，23，56，34，78，67，88，92)15．设图如下所示，在下面的5个序列中，合法的深度优先搜索遍历序列有（）。aebdfc，aedfcb，aefdbc，aefdcb，acfdebA．2个B．3个C．4个D．5个二、填空题(每小题2分，共20分)1.数据的逻辑结构是指。2.当线性表的元素个数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。3.带头结点的双向循环链表L为空的条件是：。试卷2第三页共六页4.假设为循环队列分配的向量空间为Q[30]，若队列的长度和队首指针分别为15和19，则当前队尾指针的值为（备注：队首指针指向队首元素所在的位置，队尾指针指向队尾元素的下一个位置）。5.表达式求解是应用的一个典型例子。6.已知一棵完全二叉树共有865个结点，则该二叉树中有个叶子结点。7.含n个顶点的无向连通图中至少含有______条边。8.如果待排序列已基本有序，那么在堆排序和快速排序中选择对待排序列进行排序较为合适。9.对表长为6000的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在等概率的假设下，其查找成功的平均查找长度为。10.已知有待排序{54，23，88，45，60，53，24，92，32}，请写出第一趟快速排序的结果。三、应用题（共34分）1.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。要求：（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；（7分）（2）若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。（2分）2．已知对有序序列{6，11，17，29，33，34，37，45，77，80}进行折半查找，要求：（1）请画出对应的判定树；（3分）（2）请问成功查找17和77需要分别与哪些关键字进行比较；（4分）（3）在等概率的假设下，请计算出查找成功时的平均查找长度和查找失败时的平均查找长度。（4分）3．已知一组元素为(46，25，78，62，12，37，70，29)，要求：（1）试画出按元素排列次序插入生成的一棵二叉排序树；（5分）（2）请写出它的中序遍历序列。（2分）4．已知图G如下所示，要求：根据Prim算法求G的最小生成树（请给出生成过程，出发顶点为v0）。（7分）试卷2第四页共六页四、设计题（每小题8分，共16分）1．在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且ab，编写算法删除链表L中元素值大于a且小于b的所有结点。typedefstructCNode{intdata;structBNode*next;}CNode,*CLinkList;2.设计判断两个二叉树是否相同的算法。typedefstructBNode{datatypedata;structBNode*lchild,*rchild;}BNode,*BTree;试卷2第五页共六页数据结构联考试卷（2）参考答案一、单项选择题(每小题2分，共30分)123456789101112131415CBDCDADDACCCCBA二、填空题(每小题2分，共20分)1.数据元素之间的逻辑关系2.顺序3.L-next==L&&L-prior==L4.45.栈6.4337.n-18.堆排序9.208.510.32，23，24，45，53，54，60，92，88三、应用题（共34分）1.（1）(7’)WPL=(0.03+0.05)*4+(0.13+0.15+0.09)*3+(0.35+0.2)*2=2.53(2’)2.（1）(3’)（2）成功查找17需要分别与关键字33，11，17比较(2’)；成功查找77需要分别与关键字33，45，77比较(2’)。（3）ASL成功=1/10(1*1+2*2+3*4+4*3)=2.9(2’)ASL失败=1/11(3*5+4*6)=3.55(2’)3.（1）(5’)（2）(2’)中序遍历序列为：12,25,29,37,46,62,70,784.共6页第六页共六页四、设计题（第1题14分，第2题16分，共30分）1．voidDeleteDataFromList(CLinkListL){CNode*p=NULL,*q=NULL,*s=NULL;p=L;while(p-next!=L&&p-next-data=a)p=p-next;if(p-next!=L){q=p-next;while(q!=L&&q-datab){s=q;q=q-next;p-next=q;free(s);s=NULL;}//while}//if}2．intJudgeBTree(BTreebt1,BTreebt2){if(bt1==NULL&&bt2==NULL)return(1);elseif(bt1==NULL||bt2==NULL||bt1-data!=bt2-data)return(0);elsereturn(JudgeBTree(bt1-lchild,bt2-lchild)*JudgeBTree(bt1-rchild,bt2-rchild));}