《数据结构》模拟试卷七.docVIP

模拟试卷七 一、选择题（每小题2分，共10分） 1．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除 运算，则采用 存储方式最节省时间。 a．顺序表 b．双链表 c．带头结点的双循环链表 d．单循环链表 2．在用邻接表表示图时，求最短路径的Dijkstra算法的时间复杂度为 。 a．O（n） b．O（n＋e） c．O（n2） d．O（u3） 3．依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的算法是 。 a．快速排序 b．插入排序 b. 冒泡排序 d. 堆排序 4. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已 知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 型调整 以使其平衡。 a． LL b． LR c． RL d． RR 5. 已知数据表A中每个元素距其最终位置不远，则采用 排序算法最节省时间。 a．堆排序 b. 插入排序 c．快速排序 d．直接选择排序 二、判断题（每小题1分，共10分） 1．（ ）线性表就是顺序表。 2．（ ）链表只能借助于指针和动态变量来实现。 3．（ ）线性表的长度是指其中元素所占用的存储空间的字节数。 4．（ ）对广义表A =（a，（b，c），d）的运算head（tail（A））的结果不是b。 5.（ ）若一棵树中某结点的度为1，则该结点仅有一棵子树。 6.（ ）所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。 7．（ ）AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的 长度。 8．（ ）若从某顶点开始对有向图G进行深度遍历，所得的遍历序列唯一，则 可断定其弧数为n－1。 9．（ ）理想情况下，在散列表中查找一个元素的时间复杂度为O（l）。 10.（ ）快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。 三、填空题（每空2分，共20分） 1．在带头结点的双循环链表L中，最后一个结点的指针是 。 2．在仅有尾指针R指示的单循环链表R中，在表尾插入一个结点S^ 的语句序列是 。 3．已知栈的输入序列为1，2，3，…，n，输出序列为a1，a2，…，an，a2=n的输出 序列共有 种输出序列。 4．已知循环队列用数组data［1..n］存储元素值，用 f，r分别作为头尾指针，则 当前元素个数为 。 5．在左右子树均不空的先序线索二叉树中，空链域的数目是 。 6. 在二叉链表中，判断某指针P所指结点为叶子结点的条件是 。 7．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点 数是 。 8．在有n个顶点的连通图中，其边数至少为 。 9．已知数组A[1..10，1..10]为对称矩阵，其中每个元素占5个单元。现将其下三 角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,6] 对应的地址为 。 10. 直接选择排序算法在最好情况下所作的交换元素的次数为 。 四、解答下列各题（每小题5分，共20分） 1．已知一树的双亲表示如下，其中各兄弟结点是依次出现的，画出该树及对应的二 叉树。 2．一棵二叉排序树结构如下，各结点的值从小到大依次为l～8，请标出各结点的值。 3．对下面数据表，写出采用冒泡排序算法排序的每一