（精品课件）数据结构课程试卷15卷.docVIP

苏州大学 数据结构 课程试卷15卷（共 5 页） 考试形式：闭卷 年 月 院系 ______________ 年级 ______________ 专业 ______________ 学号 ______________ 姓名 ______________ 成绩 ______________ 一、填空题（2分×15） 1、下列算法的时间复杂度是 。 x=n; y=0; while ((x=（y+1）*（y+1）)) y=y+1; 4、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用______存储结构。…kn-1}建立一个堆。首先将该序列中的关键字依次排列到一棵完全二叉树上，然后从最后一个非叶结点开始到根结点为止，依次插入结点至已经完成的部分堆中。此非叶结点的编号 个元素开始筛选。 7、假设二叉树根结点的层次为0，则二叉树的第k层上的结点总数最多为 个。 8、假设一个12阶的下三角矩阵A按行优先顺序压缩存储在一维数组B[0..MAX-1]中，则B的容量MAX至少为 。如A矩阵的第一个元素为a00,则非零元素a98在B中的存储位置k= 。 10、n个顶点的无向连通图至少含有 条边，无向非连通图的连通分量是指： 。 二、应用题 1、判别以下说法是否正确，并简单说明原因。 （1）队列是一种先进后出的数据结构。 （2）队列的顺序存储方案通常采用循环队列的方法。 （3）队列的顺序存储结构比链式存储结构更优越。 2、已知一个无向图的邻接表如下图所示，要求：（10分） 画出该无向图。 根据邻接表，分别写出DFS和BFS算法从顶点v0开始的遍历该图后所得到的遍历序列，并画出DFS生成树和BFS生成树。 0 1 2 3 4 5 6 3、设表达式a+b*(c-d)-e/f 可以表示成如下二叉树结构。 请将此二叉树的结点填写完整。 如果表达式以二叉树表示，简述对一个表达式进行求值的过程。（提示：可利用二叉树的后序遍历来进行） ? ? ? ? ? ? ? ? ? ? ? ? ? 4.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。 算法设计题 1、为简单单链表类设计拷贝构造函数。（10分） template class List_entry ListList_entry :: List(const ListList_entry copy) 2、在递增有序顺序表下，完成顺序查找的递归算法。（10分） Error_code sequential_search(const Ordered_ListRecord the_list,const Key target,int position) 3、二叉树以二叉链表作为存储结构，设计一个递归算法判断二叉树是否为二叉排序树。（10分） template class Entry int Binary_treeEntry :: recursive_is_searchtree(Binary_nodeEntry *sub_root) const 5 V0 V1 V2 V3 V4 V5 V6 2 3 6 ^ 1 3 ^ 1 ^ 6 5 3 0 4 2 ^ 0 6 1 ^ 1 2 4 ^ 0 2 5 0 ^