《数据结构》( c 卷).doc

《数据结构》模拟卷 一、单项选择题 1．数据结构是（　　）。 A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是（　　）。 A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（　　）。 A．插入 B．删除 C．排序 D．定位 4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　　）。 A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 5．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（　　）。 A．15 B．16 C．17 D．18 6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（　　）。 A．1207 B．1209 C．1211 D．1213 7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（　　）。 A．队列 B．栈 C．线性表 D．有序表 8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（　　）。 A．不一定相同 B．都相同 C．都不相同 D．互为逆序 9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（　　）。 A．层次遍历算法 B．前序遍历算法 C．中序遍历算法 D．后序遍历算法 10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（　　）。 A．图中每个顶点的入度 B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 11．图的邻接矩阵表示法适用于表示（　　）。 A．无向图 B．有向图 C．稠密图 D．稀疏图 12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（　　）。 A．i B．i+1 C．n-i D．n-i+1 二、填空题 1．栈是_______的线性表，其运算遵循_______的原则。 2．_______是限定仅在表尾进行插入或删除操作的线性表。 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。 4．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 5．在二叉树中，指针p所指结点为叶子结点的条件是______。 6．具有256个结点的完全二叉树的深度为______。 7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。 8．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。 9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。 10．不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。 三、解答题 1．某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。 2．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。 （1）画出该二叉树； （2）画出与（1）求得的二叉树对应的森林。 3．已知带权图的邻接表如下所示，其中边表结点的结构为： 依此邻接表从顶点C出发进行深度优先遍历。 （1）画出由此得到的深度优先生成树； （2）写出遍历过程中得到的从顶点C到其它各顶点的带权路径及其长度。 四、算法设计题 1．已知中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的 一个叶子结点插入进去，并使之成为TT的右子树的（中序序列）第一个结点（同时要修改 相应的线索关系）。 2．写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。