数据结构期末试题6.docVIP

期末考试考试试卷（6） （ 至 学年第 学期） 课程名称： 数据结构 题目 一 二 三 四 五 六 七 八 总分 得分 一、判断选择填空 (10分) 1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。....( ) 2、用树的前序遍历和中序遍历可以导出树的后序遍历；......( ) 3、单链表从任何一个结点出发，都能访问到所有结点。.....( ) 4、外部排序是在排序过程中，只使用外存储器的排序。.....( ) 5、设串S的长度为n,则S的子串个数为n(n+1)/2。.....( ) 6、若二叉树中的一个叶子结点是某子树中序序列的最后一个结点，则它必是该子树的先序序列的最后一个结点。..... ( ) 7、设h是一散列函数，key1和key2为关键码值，且 key1key2，但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、E 9、设i为n个结点的完全二叉树结点编，i=1，2，3...n；若i≤（n-1）/2时，结点i的右孩子为（ ） ⑴. 2i ⑵. 2i+1 ⑶. 2i-1 ⑷. i+1 10、若S1=‘China，S2=$Beijing,则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分）将六题中的二叉树转换为森林。 八、（5分）画出图1所示图的深度优先生成树和广度优先生成树。 九、（5分）对于图，写出它的四个不同的拓朴有序序列。 图1 图 十、（5分）求图3所示图的关键路径。 图3 十二、（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分）编写中序遍历二叉树的非递归算法。 十六、（10分）按数组表示法存储图，请编写建立无向图的算法。 十七、（10分）写出2－路归并排序的归并过程算法。 数据结构考试题第2页（共2页） 专业 年级 学号______________ 姓 名 ________________ 密 封 线 专业 年级 学号______________ 姓 名 ________________ 密 封 线