数据结构期末试题.doc

《数据结构期末试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、个数为n(n+1)/2。.....()6、若二叉树中的一个叶子结点是某子树中序序列的最后一个结点，则它必是该子树的先序序列的最后一个结点。.....()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；若

3、i≤（n-1）/2时，结点i的右孩子为（）⑴.2i⑵.2i+1⑶.2i-1⑷.i+110、若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,

4、d,e,f的Huffman编码。六、（5分）假设一棵二叉树的后序序列为GDBEHFCA和中序序列为DGBAECHF，请画出该二叉树，并写出先序遍历序列。七、（5分）将六题中的二叉树转换为森林。八、（5分）画出图1所示图的深度优先生成树和广度优先生成树。九、（5分）对于图2，写出它的四个不同的拓朴有序序列。图1图2十、（5分）求图3所示图的关键路径。专业年级学号______________姓名________________密封线图3十一、（5分）设一个哈希表为下表，请简述查找84和38的过程。012345678

5、9101112140168275519208479231110十二、（5分）已知含有12个关键字的有序表及其相应权值为：关键字ABCDEFGHIJKL权值823493287114试构造次优二叉查找树。十三、（5分）写出用堆排序(heapsort)算法对序列F=(12，3，15，30，9，28)进行排序时,初始堆及以后每挑好一个元素重新调整后堆的状态。以下四题任选三题。十四、（10分）编写算法删除线性表中所有值相同的多余元素。（使用顺序存储结构或单链表存储结构均可）十五、（10分）编写中序遍历二叉树的非递归算法。

6、十六、（10分）按数组表示法存储图，请编写建立无向图的算法。十七、（10分）写出2－路归并排序的归并过程算法。