《数据结构》模拟试卷三.doc

模拟试卷三 一、选择题（每小题2分，共20分） 1．一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是 。 a． 2 3 4 1 5 b． 5 4 1 3 2 c． 2 3 1 4 5 d． 1 5 4 3 2 2． 设循环队列中数组的下标范围是l～n，其头尾指针分别为f和r，则其元素个 数为 。 a． r－f b. r－f＋1 c．（r－f）mod n＋1 d.（r－f＋n）mod n 3．若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结 点，则采用 存储方式最节省时间。 单链表 b. 双链表 c. 带头结点的双循环链表 d．单循环链表 4．一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足 。 a．其中任意一结点均无左孩子 b．其中任意一结点均无右孩子 C．其中只有一个叶子结点 d．是任意一棵二叉树 5．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为 。 a．0 b. l c．2 d．不确定 6．数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址 为1000的连续的内存单元中，则元素A［5，5］的地址为 。 a．1140 b．1145 c．1120 d. 1125 7．求最短路径的DIJKSTRA算法的时间复杂度为 。 a．O（n） b．O（n＋e） c. O（n2） d．O（n×e） 8. 对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为 。 a. l，2，3 b. 9，5，2，3 c. 9，5，3 d．9，4，2，3 9．快速排序算法在最好情况下的时间复杂度为 。 a．O（n） b．O（nlog2n） c．O（n2） d．O（log2n） 10．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是 。 a．堆排序 b．冒泡排序 c. 快速排序 d．直接插入排序 二、判断题（每小杨1分，共10分） 1．（ ）线性表的长度是线性表所占用的存储空间的大小。 2.（ ）双循环链表中，任意一结点的后继指针均指向其逻辑后继。 3．（ ）在对链队列做出队操作时，不会改变front指针的值。 4．（ ）如果两个串含有相同的字符，则说它们相等。 5.（ ）如果二叉树中某结点的度为1，则说该结点只有一棵子树。 6.（ ）已知一棵树的先序序列和后序序列，一定能构造出该树。 7．（ ）图G的一棵最小代价生成树的代价未必小于G的其他任何一棵生成树的 代价。 8．（ ）图G的拓扑序列唯一，则其弧数必为n－1（其中n为G的顶点数）。 9．（ ）对一个堆技层次遍历，不一定能得到一个有序序列。 1O．（ ）直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为 O（n2）。 三、境空（每小题2分，共20分） 1．在双循环链表L中，指针P所指结点为尾结点的条件是 。 2．在单链表中，删除指针P所指给点的后继