数据结构期末试题参考

1、文档供参考，可复制、编制，期待您的好评与关注！ 专业 年级 学号_ 姓 名 _密封线期末考试考试试卷（6）（ 至 学年第 学期） 课程名称： 数据结构 题目一二三四五六七八总分得分一、判断选择填空 (10分)1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。.( )2、用树的前序遍历和中序遍历可以导出树的后序遍历；.( ) 3、单链表从任何一个结点出发，都能访问到所有结点。.( )4、外部排序是在排序过程中，只使用外存储器的排序。.( )5、设串S的长度为n,则S的子串个数为n(n+1)/2。.( )6、若二叉树中的一个叶子结点是某子树中序序列的最后一个结点

2、，则它必是该子树的先序序列的最后一个结点。. ( ) 7、设h是一散列函数，key1和key2为关键码值，且 key1<>key2，但h（key1）=h（key2），这种现象称为（ ）。8、若入栈序列的元素顺序是A、B、C、D、E，判断下列哪一个出栈序列是不可能的（ ） . A、B、C、D、E . B、C、D、E、A .E、A、B、C、D.D、C、B、A、E9、设i为n个结点的完全二叉树结点编，i=1，2，3.n；若i（n-1）/2时，结点i的右孩子为（ ） . 2i . 2i+1 . 2i-1 . i+110、若S1=China'，S2='$Beijing'

3、;,则S1/S2=( )。二、（5分）简述顺序存储结构和链式存储结构的优缺点。三、（5分）简述使用顺序存储表示循环队列时，判定队列“空”和“满”的方法。四、（5分）编写子串位置定位函数Index(S,T,pos)；五、（5分）假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，画出相应的Huffman树，并写出a,b,c,d,e,f的Huffman编码。六、（5分）假设一棵二叉树的后序序列为GDBEHFCA和中序序列为DGBAECHF，请画出该二叉树，并写出先序遍历序列。七、（5分）将六题中的二叉树转换为森林。八、（5分）画出图1所示图的深

4、度优先生成树和广度优先生成树。九、（5分）对于图2，写出它的四个不同的拓朴有序序列。 图1 图2 十、（5分）求图3所示图的关键路径。 专业 年级 学号_ 姓 名 _密封线图3十一、（5分）设一个哈希表为下表，请简述查找84和38的过程。0123456789101112140168275519208479231110十二、（5分）已知含有12个关键字的有序表及其相应权值为： 关键字 A B C D E F G H I J K L 权值 8 2 3 4 9 3 2 8 7 1 1 4试构造次优二叉查找树。十三、（5分）写出用堆排序(heap sort)算法对序列F=(12，3，15，30，9，28)进行排序时,初始堆及以后每挑好一个元素重新调整后堆的状态。以下四题任选三题。十四、（10分）编写算法删除线性表中所有值相同的多余元素。（使用顺序存储结构或单链表存储结构均可）十五、（10分）编写中序遍历二