下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数据结构模拟试卷DS3

数据结构模拟试卷DS3.doc

数据结构模拟试卷DS3

Cejilo
2012-10-26 0人阅读 举报 0 0 暂无简介

简介:本文档为《数据结构模拟试卷DS3doc》,可适用于高等教育领域

模拟试卷三一、选择题(每小题分共分)  在下列备选答案中选出一个正确的将其号码填在“”上。  .一个栈的输入序列为则下列序列中不可能是栈的输出序列的是。(1)(2)(3)(4).设循环队列中数组的下标范围是∽n其头尾指针分别为f和r则其元素个数为。(1)rf(2)rf(3)(rf)modn(4)(rfn)modn.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点则采用存储方式最节省时间。(1)单链表  (2)双链表  (3)带头结点的双循环链表(4)单循环链表.一棵非空的二叉树的先序序列正好相反则该二叉树一定满足。(1)其中任意一结点均无左孩子(2)其中任意一结点均无右孩子(3)其中只有一个叶子结点   (4)是任意一棵二叉树.一棵左右子树均一空的二叉树在先序线索化后其空指针域数为。(1)(2)(3)(4)不确定.数组A....的每个元素占个单元将其按行优先次序存储在起始地址为的连续的内存单元中则元素A的地址为。(1) (2) (3) (4).求最短路径的DIJKSTRA算法的时间复杂度为。(1)O(n)(2)O(ne)(3)O(n)(4)O(n×e).对有个元素的有序表作二分查找则查找A的比较序列的下标依次为。(1),,(2),,,(3),,(4),,,.快速排序算法在最好情况下的时间复杂度为。(1)O(n)(2)O(nlogn)()O(n)()O(logn).下列排序算法中某一趟结束后末必能选出一个元素放在其最终位置上的是。(1)堆排序(2)冒泡排序(3)快速排序(4)直接插入排序二、判断题(每小题分共分)  判断下列各题是否正确若正确在()内打“(”否则打“(”。  1.(  )线性表的长度是线性表所占用的存储空间的大小。  2.(  )双循环链表中任意一结点的后继指针均指向其逻辑继。  3.( )在对链队列做出队操作时不会改变front指针的值。  4.(  )如果两个串含有相同的字符则说它们相等。  5.(  )如果二叉树中某结点的度为则说该结点只有一棵子树。  6.(  )已知一棵树的先序序列和后序序列一定能构造出该树。  7.(  )图G的一棵最小代价生成树的代价未必小于G其他任何一棵生成树的代价。  8.(  )图G的拓扑序列唯一则其弧数必为n(其中n为G顶点数)9.()对一个堆按层次遍历不一定能得到一个有序序列。10.()直接选择排序算法满足:其时间复杂度不受数据的初始特性影响为O(N)。三、填空(每小题分共分).在双循环链L中指针P所指结点为尾结点的条件是 。.在单链表中删除指针P指结点的后继结占的语句是 。.队列的特性是 。.若某串的长度小于一个常数则采用存储方式最节省空间。.在有n个叶子结点的哈夫曼树中总结点数是。.一棵树T采用二叉链表BT存储如果T中某结点为叶子结点则在二叉链表BT中所对应的结点一定满足。.高度为K的树的结点至少是 。.在有n个结点的无向图中其边数最多为。.取出广义表A=(x,(a,b,c,d))中原子b的函数是      。.对矩阵采用压缩存储是为了。四、解答下列各题(分)1.分别画出满足下列条件的所有二叉树。(分)(1)先序序列和中序序列均为ABCDE。(2)先序序列为ABCDE并且与其相对应的树的高度为。2.对下面阶B树依次执行下列操作画出每步的操作结果。(分)(1)插入                                                                                                                                                                                                                                                                                                                                                                                                       (2)插入(3)插入(4)删除3.对下列数据表写出采用SHELL排序算法排序的每一趟的结果。(分)()4.求出下面AOE网中的关键路径(要求标明每个顶点的最早和最迟发生时间并画出关键路径)。(分)                                                                                                                                                                                                                                                                 ②          ⑦                                                                         ⑤                                                                       ①    ③     ⑧     ⑩                                                                  ⑥                                                                     ④          ⑨                                                                                                    五、算法设计(共分).设计算法求中序线索二叉树中指针P所指结点的后继结点的指针。(分).设计算法以判断二叉树T是否为二叉排序树(设T中任意两个结点的值均不相等)。(分).设计算法将一个带有头结点的单循环链表A分解为两个具有相同结构的链表BC其中B表中结点为A表中值为奇数的结点而C表中结点为A表中值为偶数的结点(要求利用原表结点)。(分).设计算法以判断无向图G是否是连通的若连通则返回true否则返回false。(注:可以使用以下几个函数调用:firstadj(G,v)返回图G中顶点v的第一个邻接点若不存在则返回nextadj(G,v,w)返回图G中顶点v的邻接点中处于w之后的邻接点若不存在则返回nodes(G)返回G中的顶点数)(分)

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/3

数据结构模拟试卷DS3

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利