《数据结构联考试卷2及答案资料》由会员分享，可在线阅读，更多相关《数据结构联考试卷2及答案资料（6页珍藏版）》请在金锄头文库上搜索。
1、试卷试卷 2 第 一 页 共 六 页 一、一、单项选择题( (每小题每小题 2 2 分，共分，共 3030 分分) ) 1. 在数据结构中，数据的逻辑结构可以分成（）。 A. 动态结构和静态结构B. 内部结构和外部结构 C. 线性结构和非线性结构D. 紧凑结构和非紧揍结构 2以下与数据的存储结构无关的术语是（）。 A哈希表B栈C循环队列D链表 3设某棵二叉树的中序遍历序列为 ABCDE，先序遍历序列为 CABED，则后序 遍历该二叉树得到序列为（）。 A. BAEDCB. CAEDBC. BADCED. BADEC 4队和栈的主要区别是（）。 A. 逻辑结构不同B. 所包含的运算个数不同 C.
2、 限定插入和删除的位置不同D. 存储结构不同 5对于哈希函数 H(key) = key % 17,被称为同义词的关键字是（）。 A. 38 和 41B. 19 和 44C. 27 和 39D. 33 和 50 6若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出 现的出栈序列是（）。 A. 2，3，5，1，6，4B. 2，4，3，1，5，6 C. 3，2，4，1，6，5D. 4，3，2，1，5，6 7二维数组 A1218采用以列为主优先存储方法，若每个元素各占 3 个存储 单元，且第 1 个元素的地址为 150，则元素 A108的地址为（）。 A.609B.612C.4
3、65D.468 8. 设某棵二叉树中有 2200 个结点，则该二叉树的最小高度为（）。 A.9B. 10C. 11D. 12 9设某有向图的邻接表中有 n 个表头结点和 m 个表结点，则该图中有（） 条有向边 A. mB. m 1 C. nD. n - 1 10从广义表 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. 9
4、B. 10C. 11D.12 12在二叉树的先序遍历序列、中序遍历序列和后序遍历序列中，所有叶子结点 的先后顺序（）。 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，1
5、9，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 个序列中，合法的深度优先搜索遍历序列有 （）。 a e b d f c，a e d f c b，a e f d b c，a e f d c b，a c f d e b A2 个B3 个C4 个D5 个 二、填空题( (每小题每小题 2 2 分，共分，共 2 20 0 分分) ) 1. 数据的逻辑结构是指。 2. 当线性表的元素个数基本稳定，且很少进行插入和删除操作，但要求以最快
6、的速度存取线性表中的元素时，应采用存储结构。 3. 带头结点的双向循环链表 L 为空的条件是：。 试卷试卷 2 第 三 页 共 六 页 4. 假设为循环队列分配的向量空间为 Q30，若队列的长度和队首指针分别为 15 和 19，则当前队尾指针的值为（备注：队首指针指向队首元素所在的 位置，队尾指针指向队尾元素的下一个位置）。 5. 表达式求解是应用的一个典型例子。 6. 已知一棵完全二叉树共有 865 个结点，则该二叉树中有个叶子结点。 7. 含 n 个顶点的无向连通图中至少含有_条边。 8. 如果待排序列已基本有序， 那么在堆排序和快速排序中选择对待排序 列进行排序较为合适。 9. 对表长为
7、 6000 的索引顺序表进行分块查找，假设每一块的长度均为 15，且 以顺序查找确定块，则在等概率的假设下，其查找成功的平均查找长度为 。 10. 已知有待排序54，23，88，45，60，53，24，92，32，请写出第一趟快速 排序的结果。 三、应用题（共（共 3 34 4 分）分） 1. 假设通信电文使用的字符集为a, b, c, d, e, f, g，字符的哈夫曼编码依次为： 0110，10，110，111，00，0111 和 010。要求：（1）请根据哈夫曼编码画出此 哈夫曼树，并在叶子结点中标注相应字符；（7 分分）（2）若这些字符在电文中出 现的频度分别为：3，35，13，15，
8、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 如下所示，要求：根
9、据 Prim 算法求 G 的最小生成树（请给出生成 过程，出发顶点为 v0）。（7 分）分） 试卷试卷 2 第 四 页 共 六 页 四、设计题（每小题（每小题 8 8 分，共分，共 1616 分）分） 1在带头结点的循环链表 L 中， 结点的数据元素为整型， 且按值递增有序存放。 给定两个整数 a 和 b，且 a next = L p = L; while(p-next != L if(p-next != L) q = p-next; while(q != L p-next = q; free(s);s = NULL; /while /if 2int JudgeBTree ( BTree bt1, BTree bt2 ) if (bt1=NULL else if (bt1=NULL | bt2=NULL | bt1-data!=bt2-data) return(0); elsereturn(JudgeBTree(bt1-lchild,bt2-lchild)*JudgeBTree (bt1-rchild,bt2-rchild);
