数据结构06-08真题及答案.doc

山东省2008年普通高等教育专升本统一考试 数据结构（50分） 一、单项选择题（10分，每题1分） 1. 【答案】D 【解析】栈的基本性质是后进先出，本题中，在输出序列第一个元素是i时，只能确定1-i-1这些元素的输出的先后次序，但是不能确定出第i个元素具体输出哪个元素。 2. 【答案】D 【解析】在循环队列中，rear指针指示队尾，本题中存储数组实质上为A[m+1]。所以，入队列的操作应该是修改rear=(rear+1)%(m+1),答案Ｃ是错误的。 3. 【答案】B 【解析】本题中二维数组属于9行10列。所以，首先确定以行序为主序的存储中，A[8][5]在所有元素排列中的位置为第85位，同样的确定以列序为主序的第85个存储元素的元素应该为A[3][10]。 4. 【答案】A 【解析】构成广义表的数据元素可以是单个元素，也可以是广义表。广义表的表头就是广义表中的第一个元素，可以是单个元素，也可以是子表。选项B、C、D都是正确的。 5. 【答案】D 【解析】在算数表达式的前缀表达式实质上就是运算符写在两个运算数的前面，当然在实现转换时，要考虑运算数的相对位置不变，而且考虑运算的优先级问题。当然，也可以采用二叉树表示出算数表达式，这样，前序遍历顺序即为前缀表达式（波兰式），后序遍历即位后缀表达式（逆波兰式），本题答案选D。 6. 【答案】D 【解析】哈夫曼树的特点是没有度为1的结点，根据二叉树的性质3，n0=n2+1，所以，具有n个叶子结点的二叉树具有n-1个度为２的结点，因此，答案选Ｄ。 7. 【答案】C 【解析】因为在中序线索二叉树中，结点X有左子树，所以，该结点前驱在左子树中，左子树中最右的结点是子树中最后一个遍历的结点，该结点可能为叶子结点，也可能是度为1的结点（即有左孩子）。 8. 【答案】A 【解析】根据本题无向图的定义，可以图G如右图所示： 根据广度优先遍历的算法思想，可以确定A是正确的，选项B、C、D都是错误的。 9. 【答案】D 【解析】采取线性探测法存储这k个同义词，则第一个关键字可以直接存储，其余的k-1个元素中，理想的情况下，第１个元素探测１次可以存储，第２个元素探测２次才能存储，以此类推，因此，至少需要探测的次数为k(k+1)/2。 10. 【答案】B 【解析】直接插入排序的算法思想是从第2到最后一个元素，依次插入到前面的有序序列中，因此，每趟执行结束，不能确定出一个元素最终的位置；快速排序的每趟可以确定出枢轴元素的最终位置，而且，当元素基本有序时，其排序性能会降低，所以选B。选项C、D能符合第一条要求，但是其时间性能跟待排元素的序列无关。 二、填空题（本大题共10小题，每小题1分，共10分） 1. 【答案】6、9、11、12 【解析】根据有序表的折半查找的mid的取值为(low+high)/2，可以确定判定树的形态如下， 查找下标为12的元素时，先后要与下标为：6、9、11、12四个元素进行比较。 2．【答案】克鲁斯卡尔（Kruskal） 【解析】求解最小生成树的算法主要有两种，普里姆算法（Prim）时间复杂度为O（n2）,与网中的边数无关，因此适合于求边稠密的网的最小生成树；而克鲁斯卡尔（Kruskal）算法时间复杂度为O（eloge），因此，适合于求边稀疏的网的最小生成树。 3. 【答案】2 【解析】左子树为空，则根结点没有前驱，左孩子指针域为空，另外，根结点右子树中最后一个结点没有后继，右孩子指针域也为空，所以，该二叉树中空链域的个数为2。 4. 【答案】p-next!=NULL（或文字说明“指针P所指结点的指针域不等于NULL”） 【解析】在单链表L中，指针p所指结点有后继，前提是指针P所指结点的指针域不等于NULL，如果指针域默认为next，则可以表示为“p-next!=NULL” 。（注：NULL一定是大写） ５．【答案】 【解析】深度为K的结点已经构成完全二叉树，所以前i个结点也为完全二叉树，所以根据性质4可以确定第i个结点的深度为 。 三、判断题（5分，每题1分） 1．【答案】√ 【解析】链式存储结构的线性表的优点就在于实现插入和删除操作时，不需要大量元素的移动，因此，比顺序存储结构中实现插入删除操作效率高。 2．【答案】× 【解析】实现二叉树的按层遍历时，应借助于一个队列作为辅助结构。 3．【答案】√ 【解析】树转换为二叉树是依据的孩子兄弟表示法这种存储结构，树根没有兄弟，所以，一棵树转换成二叉树，对应二叉树根结点没有左子树。 4．【答案】× 【解析】有向图的邻接表中结点的个数与逆邻接表中结点的个数是相等的，都等于图中所有顶点的入度和（或出度和）的值。 5．【答案】× 【解析】就平均时间而言，快速排序目前被认为是最好的一种内部排序方法，但是，当待排序列基本有序时，快速排序将蜕