《数据结构》模拟卷(C卷).doc

《数据结构》模拟卷 一、单项选择题 1．数据结构是（　D　）。 A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是（　B　）。 A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（　D　）。 A．插入 B．删除 C．排序 D．定位 4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　B　）。 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)的值为（　C　）。 A．15 B．16 C．17 D．18 6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（　A　）。 A．1207 B．1209 C．1211 D．1213 7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（　A　）。 A．队列 B．栈 C．线性表 D．有序表 8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（　B　）。 A．不一定相同 B．都相同 C．都不相同 D．互为逆序 9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（　C　）。 A．层次遍历算法 B．前序遍历算法 C．中序遍历算法 D．后序遍历算法 10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（　A　）。 A．图中每个顶点的入度 B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 11．图的邻接矩阵表示法适用于表示（　B　）。 A．无向图 B．有向图 C．稠密图 D．稀疏图 12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（　D　）。 A．i B．i+1 C．n-i D．n-i+1 二、填空题 1．栈是_操作受限__的线性表，其运算遵循__后进先出__的原则。 2．__队列___是限定仅在表尾进行插入或删除操作的线性表。 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是__3，1，2__。 4．二叉树由_根节点__，__左子树_，_右子树__三个基本单元组成。 5．在二叉树中，指针p所指结点为叶子结点的条件是_ p-left==NULLp-right==NULL __。 6．具有256个结点的完全二叉树的深度为__9__。 7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有__12__个叶子结点。 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的右子树的（中序序列）第一个结点（同时要修改 相应的线索关系）。 BiThrNode insert( BiThrTree Thrt, BiThrNode *s) { p=Thrt; While(p-lchild) p=p-lchild; p-lchild=s;p-Ltag=0; s-Lchild=p-lchild; s-Ltag=1; s-rchild=p; s-Rtag=1; } 2．写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。 BiThrNode