数据结构概论1-3在线作业.docx

《数据结构概论1-3在线作业.docx》由会员分享，可在线阅读，更多相关《数据结构概论1-3在线作业.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、单选数据结构通常是研究数据的 及它们之间的相互关系存储和逻辑结构存储和抽象理想与抽象理想与逻辑数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的称为存储结构逻辑结构顺序存储结构数式存储结构理线性结构是数据元素之间是存在的一种存对多关系多对多关系多对一关系一对一关系多线性结构中每个结点无直接前趋只有一个直接前驱和后继只有一个直接前驱和个数不受限制的直接后继有个数不受限制的直接前驱和后继除了考虑存储数据结构本身所占用的空间外实现算法所用辅助空间的多少 称为算法的时间效率空间效率硬件效率软件效率二、填空、数据结构包括数据的逻辑结构 数据的存储结构 数据的 运算 这三 个方面的内容、数据

2、结构按逻辑结构可分为两大类分别是线性结构和非线性结构、数据的存储结构可用四种基本的存储方法表示分别是 顺序、链式、索引、 散列 、线性结构反映结点间的逻辑关系是一对一关系非线性结构反映结点间的逻 辑关系是多对多关系、一个算法的效率可分为时间效率和空间效率 三、简答：分别写出下列两个算法的时间复杂度答：答：欧一、填空1在栈中存取数据的原则是：先进后出 2、在栈中，出栈操作的时间复杂度为：_ 0(1)3栈与一般线性表的区别主要在于栈只允许在表尾进行插入和删除操作 4、顺序栈是空栈的条件是：_ s.top=0_5插入和删除只能在一端进行的线性表，称为：受限线性表6设循环向量有 个元素，循环向量中有一

3、个循环队列，在循环队列中设队头 指针指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。在循环队列中，队空标志为队满标志为当时，队列长度为；当时，队列长度是。、在队列中存取数据应遵从的原则是：先进后出、在队列结构中，允许插入的一端称为队尾，允许删除的一端称为：队头，则在中的位置是不含任何字符的串称为空串，仅含空格字符的串称为空白串。二、简答: 、设长度为的链队列用单循环链表表示，若只设头指针，则入队，出队操作 的时间是什么？如果只设尾指针呢？答r若只曲央窟匕则出队时间物L氏队时同而要n.园为每志AJ尽均头桁m开始杳It找到最届 个元素时方可箱行入队操作,若M世尼撕什，则出凡M同均为K困为

4、隹博环镒枝潮什所指的下- 个元素糖豪头麻什柚的无素，所喙出此时中需耍恿川惑个阪刘-2、设当用模式串P匹配目标串T时，请给出所有的有效位移。朴素匹配返回的位移是哪一个？备 弓if:的有效您甚i的值为:昂乳 标眨鼻的卷回值是箱 忡嘲 区此是l问，当匹配不成功的时问，当匹配成功的时候，3、如果目标串一共有10个字符，模式串共有2个字符， 候，最多比较了多少个字符？举例说明。；.-； I ； ：- Ei.;：.1. !.： Hlu I-.；,! 口 T ? fi i Jr/ r-T i inQU c i m 4、如果目标串一共有10个字符，模式串共有2个字符， 最多比较了多少个字符？举例说明。答：，m

5、机a以坏Jl I .，.仪，湿: 4 n-m*1 j e n 4 I 上也，m 为 j事任叩 HI-24-1 作业标题练习二严晓明一、选择、用单链表方式存储的线性表存储每个结点需要两个域一个是数据 域另一个是当前结点所在地址域指针域空指针域空闲域、在具有 个结点的单链表中实现 的操作其算法的时间复杂度是遍历链表和求链表的第个结点在地址为的结点之后插入一个结点删除开始结点删除地址为的结点的后继结点、单链表的存储密度在于 等于 小于 不确定、已知一个顺序存储的线性表设每个结点需占 个存储单元若第一个结点的地址为则第个结点的地址为、在 个结点的顺序表中算法的时间复杂度是的操作是访问第 个结点和求第

6、个结点的直接前趋在第个结点后插入一个新的结点删除第个结点将个结点从小到大排序二、填空：、按顺序存储方法存储的线性表称为顺序表 按链式存储方法存储的 线性表称为链表、线性表中结点的结点是有限的 结点间的关系是1对1的、顺序表相对于链表的优点有以进行随机存取 和 节省存储、链表相对于顺序表的优点有 不需要预分配存储空间和插入、删 除 操作方便、在 个结点的顺序表中删除一个结点需平均移动（一） 个结点具体的移动次数取决于 表长 和删除位置、在 个结点的顺序表中插入一个结点需平均移动个结点具体的移动次数取决于表长和插入位置、在顺序表中访问任意一个结点的时间复杂度均为因此顺序表也称为随机存取的数据结构、

7、在 个结点的单链表中要删除已知结点 需找到 前驱结点的地址 其时间复杂度为、在双链中要删除已知结点其时间复杂度为、在单链表中要在已知结点 之前插入一个新结点仍需找到节点 的前一个节点 其时间复杂度为而在此链表中完成同样的操作其时间复杂度为、在循环链表中可根据在一结点的地址遍历整个链表 而单链表中需 要知道头指针才能遍历整个链表三、简答题：四个数字按顺序进栈问退栈的顺序有几种答即全部进栈，然后顺序出栈！，艮P 1 2先进栈，然后 出栈，然后、按顺序出栈,即，先进栈，然后 出栈，然后 出栈，然后 进栈， 最后，按顺序出栈依次类推，有的次方 种一、填空：、设二维数组按行优先顺序存储在内存中，每个元素

8、占个字节，则的地址为,已知二维数组中，每个元素占两个字节，元素的地址为，则元素 的地址为、若数组定义为，则元素的地址为：、对于任何一棵二叉树，如果其终端结点数为，度为 的结点数为，则 有什么样的关系式。、设是一棵树，是对应于的二叉树，则的先根遍历和的先序遍历相同。、深度为的二叉树至多有个结点。、对于二叉树来说，第层上至多有个结点。、某二叉树的前序遍历序列为 列为：中序遍历序列为则后序遍历序、将一棵有个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为，则编号为的结点的孩子编号为：、某二叉树的前序和后序正好相反，则该二叉树一定是高度等于苴结占数 二叉树。、设高度为 的二叉树上只

9、有度为 和度为 的结点，则此二叉树中所包含的 结点数至少为：、设森林 中有 棵树，第一，二，三，四棵树的结点个数分别是，那么当把森林 转换成一棵二叉树后，其根结点的右子树上有个结点。、树中结点的最大层次称为树的深度或高度、由一棵二叉树的前序序列和 中序遍历、由中序和后序遍历序列，能唯一确定这棵二叉树。、高度为的完全二叉树至少有个结点。、将一棵树转换成一棵二叉树后，二叉树根结点没有左子树。、森林的后根遍历序列正是相应二叉树的,历序列。森林的先根遍历正是相应二叉树的,历序列。、哈夫曼树是带权路径长度最小的二叉树。、具有个叶结点的哈夫曼树共有结点，、前序为且后序为的二叉树共,。,已知二叉树有 个叶子

10、结点，且仅有一个孩子的结点数为、则总结点数 为 ,二、简答：,在具有 个结点的（ 叉树的 叉链表表示中，有多少个空指针。个结点的叉树共有 个指针域，已使用的指针域为所以空指针的个数为：给出、已知一棵二叉树的前序序列和中序序列分别为 这棵二叉树的后序遍历序列。一、选择、在一个图中，所有顶点的度数之和等于图的边数的倍、在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的倍、有个结点的无向图最多有条边、有个结点的无向连通图最少有条边、有个结点的有向完全图有条边、用邻接表表示图进行广度优先遍历时通常采用来实现算法栈队列树图、用邻接表表示图进行深度优先遍历时通常采用来实现算法栈队列树图、深度优先遍历

11、类似于二叉树的先序遍历中序遍历后序遍历层次遍历、广度优先遍历类似于二叉树的先序遍历中序遍历后序遍历层次遍历、任何一个无向连通图的最小生成树只有一棵一棵或多棵条定有多棵可能不存在二、简答无向图G有6个结点和9条边,并依次输入这9条边为(0,1),(0,2),(0,4),(0,5),(1,2),(2,3),(2,4),(3,4),(4,5),试从顶点 0 出发,分别写出按深 度优先搜索法和广度优先搜索法进行遍历的结点序列.深度优先搜索法:0-2-3-4-5-1广度优先搜索法:0-1-2-4-5-3一、填空、下列关键字序列中是堆、堆是一种排序插入 选择 交换 归并、堆的形状是一棵二叉排序树满二叉树完全二叉树 平衡二叉树、若一组记录的排序码为则利用堆的方法建立的初始堆为、若一组记录的关键码为则利用快速排序的方法以第一个记录为基准得到的一次划分结果为、设有 个元素用折半查找法进行查找的时候最大比较的次数是、对线性表进行二分查找的时候要求线性表必须以顺序方式以链接方式存储以顺序方式存储且结点按斗争字有序排列以链接方式存储且结点按关键字有序排列 、稠密索引是指索引密度大的文件索引量大的文件为每个主记录建立一个索引项的文件 为每个页块建立一个索引项的文件、稀疏索引是指为引密度小的文件为引量小的文件为每个主记录建立一个索引项的文件为每个页块建立一个索引项的文件