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

模拟试卷九一、单项选择题（每小杨2分，共20分） 1某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元 素，则采用 存储方式最节省运算时间。 （l）单链表 （2）仅有头指针的单循环链表 （3）双链表 （4）仅有尾指针的单循环链表 2. 串的长度是 。 （1）串中不同字母的个数 （2）串中不同字符的个数 （3）串中所含字符的个数，且大于0 （4）串中所含字符的个数 3若用数组Sl.n作为两个栈S1和S2的共用存储结构，对任何一个钱，只有当 sl.n全满时才木能作入栈操作。为这两个栈分配空间的最佳方案是 。 （1）S1的栈底位置为0， S2的栈底位置为n1 （2）S1的栈底位置为0， S2的栈底位置为n2 （3）S1的栈底位置为l， S2的栈底位置为n （4）S1的栈底位置为1， S2的残底位置为n2 4. 队列操作的原则是 。 （1）先进先出 （2）后进先出 （3）只能进行插入 （4）只能进行删除 5有 64个结点的完全二叉树的深度为 （根的层次为 1）。 （1）8 （2）7 （3）6 （4）5 6. 在有n个结点的二叉链表中，值为非空的链域的个数为 。 （1）n-l （2）2n-l （3）nl （4）2n1 7带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中 。 （1）第i行非的元素之和 （2）第i列非的元素之和 （3）第i行非且非0的元素个数 （4）第i列非且非O的元素个数 8. 在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数 的数量级为 。 （1） O（n） （2） O（log2n） （3） O（nlog2n） （4） O（n2） 9若表R在排序前已按键值递增顺序排列，则 算法的比较次数最少。 （1）直接插入排序 （2）快速排序 （3）归并排序 （4）选择排序10下列排序算法中， 排序在某趟结束后不一定能选出一个元素放到其最 终的位置上。 （l）选择 （2）冒泡 （3）归并 （4）堆二、判断题（每小题1分，共10分） 1（ ）在带头结点的单循环链表中，任一结点的后继指针均不空。2（ ）线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间 复杂度都是O（n），因而两种存储方式的插入、删除运算所花费的时 间相同。 3（ ）在栈为空的情况下，不能作出栈操作，否则产生下溢出。 4.（ ）对矩阵压缩存储的方法是用三元组表存储矩阵元素。5（ ）在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则 该顶点的度一定为o。6.（ ）如果有向图G =（V，E）的拓扑序列唯一，则图中必定仅有一个顶点 的人度为O，一个顶点的出度为0。7（ ）向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序 树的高度。8（ ）在索引顺序表的查找中，对索引表既可采用顺序查找方法，也可采用 二分查找方法。9.（ ）在快速排序算法中，以待排序的n个记录中的第一个记录的键值为基 准，将所有记录分为两组，该记录就在这两组的中间，这也是该记录 的最终位置。 10（ ）在一个大根堆中，最小元素不一定在最后。三、填空题（每小题2分，共24分） 1在单链表中，若要在指针P所指结点之后插入由指针S所指的结点，则需执行下 列语句：S.next := P.next； 。 2. 在带有头结点的双链表L中，指针P所指结点是第一个元素结点的条件是 。3设sq1.maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置。能作 入栈操作的条件是 。如要把栈顶元素弹出并送到X中，则需执行下列 语句 。 43个结点可构成 棵不同形态的树。5树t的存储结构为二叉链表bt，树t中的一个非叶子结点在bt中满足条件 。6设有向图G的邻接矩阵为A，如果图中不存在孤，则Ai，j的值为 。 7如果含n个顶点的图是一个环，则它有 棵生成树。 8. 对有17个元素的有序表A1.17作二分查找，在查找值等于A8的元素时， 被比较的元素的下标依次为 。 9二叉排序树的结点及指针类型如下： type bitre = bnode； bnode = record data：datatype； Lchild，Rchild：bitre end； 请在下面算法划线处填上适当内容，以完成在二叉排序树t中查找键值为K的结点。 function search（t：bitre； K：datatype）：bitre； 在t中查找键值为K的结点，成功时返回该结点的指针，否则退回 nil begin if t = nil then return（t） else case t.data = K ： return（t）； t.data K ： ； t.data K ： ； end end； 1O利用直接选择排序算法对n个记录进行排序，最坏情况下，记录的交换次数为 。四、解答下列各题（共22分）1 对下边的树，分别画出其孩子链表和孩子兄弟链表存储结构。（4分） A B C D E F G H2已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造 出该二叉树。（5分） 3一项工程P由P1，P2，P3，P4，P5，P6六个子工程组成，这些工程之间有下列 关系：P1P2，P1P3，P1P4，P2P3，P2P5，P3P6，P4P6，P5P6。 其中符号子“”表示先于关系，例如 P1P3表示只有在 P1完成之后才能进 行 P3的工作。请给出工程P的四种可能的施工顺序。（4分）4. 设散列表的长度为9，散列函数为H（X）= i div 3，其中i为键值X中第一个 字母在字母表中的序号，若键值的输入序列为Jan，Feb，Mar，Apr，May，Jun， Jul，Aug，Sep，Oct，Nov， Dec，用拉链法处理冲突，要求：（ 5分） （1）构造散列表。 （2）求出在等概率情况下，查找成功时的平均查找长度。5采用直接插入排序算法，对关键字序列（46，32，55，81，65，11，25，43）按 从小到大的次序进行排序，写出每趟排序的结果。（4分）五、算法设计（井24分） 1两个链表L1和L2分别表示两个集合，其中每个结点有两个字段，分别为data 和next，请画出这种链表的结构，并编写算法以判断集合L1是否是集合L2的子 集，即判断L1中的元素是否都是1上中的元素，若成立，返回true，否则返回 false。（8分）2设一棵二叉树以二又链表作为存储结构，其中每个结点有三个字段，分别是 Lchild，data和rchild，其中data字段的类型为char。设计算法以求出该H叉 树中data域的值为大写字母的结点个数。（6分） 3有n个顶点的有向图的邻接表定义如下： type vertex = 1 n； eptr = enode； enode = record 边或弧结点 num： vertex； 邻接点） next： eptr end； vnode record Vinfo：datatype； 顶点信息