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

《数据结构联考试卷2及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、试卷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,被称为同义词的关键字是（

2、）。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个表结点，则该图

3、中有（）条有向边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的结点。第一页共六页试卷2A.9B.10C.11D.1212．在二叉树的先序遍历序列、中序遍历序列和后序遍历序列中，所有叶子结点的先后顺序（）。A．都不相同B．先序和中序相同，但与后序不同C．完全相同D．后序和中序相同，但与先序不同13．下面说法不正确的是（）。A.图的遍历有两种基

4、本算法：深度优先搜索遍历和广度优先搜索遍历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，aedfc

5、b，aefdbc，aefdcb，acfdebA．2个B．3个C．4个D．5个二、填空题(每小题2分，共20分)1.数据的逻辑结构是指。2.当线性表的元素个数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。3.带头结点的双向循环链表L为空的条件是：。第二页共六页试卷24.假设为循环队列分配的向量空间为Q[30]，若队列的长度和队首指针分别为15和19，则当前队尾指针的值为（备注：队首指针指向队首元素所在的位置，队尾指针指向队尾元素的下一个位置

6、）。5.表达式求解是应用的一个典型例子。6.已知一棵完全二叉树共有865个结点，则该二叉树中有个叶子结点。7.含n个顶点的无向连通图中至少含有______条边。8.如果待排序列已基本有序，那么在堆排序和快速排序中选择对待排序列进行排序较为合适。9.对表长为6000的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在等概率的假设下，其查找成功的平均查找长度为。10.已知有待排序{54，23，88，45，60，53，24，92，32}，请写出第一趟快速排序的结果

7、。三、应用题（共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