数据结构试题及答案6要点.doc

《数据结构》自考复习思考试题 一、填空题（每小题2分） 1、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（） A 存储结构 B 逻辑结构 C 算法 D 操作 2、链式栈与顺序栈相比，一个比较明显的优点是（） A 插入操作更加方便 B 通常不会出现栈满的情况 C 不会出现栈空的情况 D 删除操作更加方便 3、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（） A 直接选择排序 B 直接插入排序 C 快速排序 D 起泡排序 4、若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（） A 上三角矩阵 B 稀疏矩阵 C 对角矩阵 D 对称矩阵 5、在一个顺序存储的循环队列中，队头指针指向队头元素的（） A 前一个位置 B 后一个位置 C 队头元素位置 D 队尾元素的前一位置 6、用链表表示线性表的优点是（） A 便于随机存取 B 花费的存储空间比顺序表少 C 便于插入与删除 D 数据元素的物理顺序与逻辑顺序相同 7、对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。 A 8 B 10 C 15 D 25 8、下列存储形式中，（）不是树的存储形式 A 双亲表示法 B 左子女右兄弟表示法 C 广义表表示法 D 顺序表示法 9、在一棵具有5层的满二叉树中结点数为（） A 31 B 32 C 33 D 16 10、设有100个数据元素，采用折半有哪些信誉好的足球投注网站时，最大比较次数为（） A 6 B 7 C 8 D 10 二、判断题（每小题1分） （）1、算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。 （）2、二维数组是数组元素为一维数组的线性表，因此它是线性结构。 （）3、顺序表用一维数组作为存储结构，因此顺序表是一维数组。 （）4、通常使用两个类来协同表示单链表，即链表的结点类和链表类。 （）5、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。 （）6、在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。 （）7、具有n个结点的完全二叉树的高度为┖log2n┘+1。 （）8、为度量一个有哪些信誉好的足球投注网站算法的性能，需要在时间和空间方面进行权衡。 （）9、闭散列法通常比开散列法时间效率更高。 （）10、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。 三、阅读理解题（10分） void unknown(BinTreeNode *T,int a[],int i){ if(T!=NULL){ a[i]=T-data; unknown(T-leftChild,a,2*I+1); unknown(T-rightChild,a,2*I+2); } } 主程序调用方式unknown(BT.root,a,0); // 将完全二叉树所有结点从要开始，自顶向下，同一层自左向右连续编号， //根结点的编号为0。 四、简答题（共35分） 1、对下面的带权无向图采用prim算法从顶点①开始构造最小生成树。（写出加入生成树顶点集合S和选择Edge的顺序）（10分） ① 9 10 ② 7 ③ 5 6 7 ④ ⑤ ⑥ 11 8 S： 顶点号 Edge： （顶点，顶点，权值） ① （ ， ， ） ① （ ， ， ） ① （ ， ， ） ① （ ， ， ） ① （ ， ， ） ① 2、某二叉树的结点数据采用顺序存储表示如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B （1）试画出此二叉树的图形表示。（3分） （2）写出结点D的双亲结点及左、右子女。（3分） （3）将此二叉树看作森林的二叉树表示，试将它还原为森林。（3分） 3、设待排序序列