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

一、 单选数据结构通常是研究数据的及它们之间的相互关系存储和逻辑结构存储和抽象理想与抽象理想与逻辑数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的称为存储结构逻辑结构顺序存储结构数式存储结构理线性结构是数据元素之间是存在的一种存对多关系多对多关系多对一关系一对一关系多线性结构中每个结点无直接前趋只有一个直接前驱和后继只有一个直接前驱和个数不受限制的直接后继有个数不受限制的直接前驱和后继除了考虑存储数据结构本身所占用的空间外实现算法所用辅助空间的多少称为算法的时间效率空间效率硬件效率软件效率二、 填空、数据结构包括数据的逻辑结构数据的存储结构数据的运算这三个方面的内容、数据结构按逻辑结构可分为两大类分别是线性结构和非线性结构、数据的存储结构可用四种基本的存储方法表示分别是顺序、链式、索引、散列、线性结构反映结点间的逻辑关系是一对一关系非线性结构反映结点间的逻辑关系是多对多关系、一个算法的效率可分为时间效率和空间效率三、简答：分别写出下列两个算法的时间复杂度答：答： 欧一、填空1在栈中存取数据的原则是：先进后出2、在栈中，出栈操作的时间复杂度为：_0(1)3栈与一般线性表的区别主要在于栈只允许在表尾进行插入和删除操作4、顺序栈是空栈的条件是：_s.top=0_5插入和删除只能在一端进行的线性表，称为：受限线性表6设循环向量有个元素，循环向量中有一个循环队列，在循环队列中设队头指针 指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。在循环队列中，队空标志为 队满标志为当 时，队列长度为 ；当 时，队列长度是。、在队列中存取数据应遵从的原则是：先进后出、在队列结构中，允许插入的一端称为 队尾，允许删除的一端称为：队头

，则在中的位置是

不含任何字符的串称为空串，仅含空格字符的串称为空白串。二、简答:、设长度为的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？答r若只曲央窟匕则出队时间物L氏队时同而要n.园为每志AJ尽均头桁m■开始杳It找到最届个元素时方可箱行入队操作,若M世尼撕什，则出凡M同均为K困为隹博环镒枝潮什所指的下-个元素糖豪头麻什柚的无素，所喙出此时中需耍恿川惑个阪刘-2、设 当用模式串P匹配目标串T时，请给出所有的有效位移。朴素匹配返回的位移是哪一个？备弓if:•的有效您甚i的值为:"昂乳标眨鼻的卷回值是箱忡嘲⑧区此是l问，当匹配不成功的时问，当匹配成功的时候，3、如果目标串一共有10个字符，模式串共有2个字符，候，最多比较了多少个字符？举例说明。问，当匹配不成功的时问，当匹配成功的时候，；'.-•；I；'：-Ei.;：.1.!.：HluI-.；,,!口T?■fiiJr/'■r-T■iinQUcim4、如果目标串一共有10个字符，模式串共有2个字符，最多比较了多少个字符？举例说明。答：，m机「a以坏"JlI.，. 仪，湿'•:4■n-m*1jen4I上也，m为j'事任叩HI-24-1•作业标题练习二严晓明一、选择、用单链表方式存储的线性表存储每个结点需要两个域一个是数据域另一个是当前结点所在地址域指针域空指针域空闲域、在具有个结点的单链表中实现的操作其算法的时间复杂度是遍历链表和求链表的第个结点在地址为的结点之后插入一个结点删除开始结点删除地址为的结点的后继结点、单链表的存储密度在于等于小于不确定、已知一个顺序存储的线性表设每个结点需占个存储单元若第一个结点的地址为 则第个结点的地址为、在个结点的顺序表中算法的时间复杂度是 的操作是访问第个结点 和求第个结点的直接前趋在第个结点后插入一个新的结点删除第个结点将个结点从小到大排序二、填空：、按顺序存储方法存储的线性表称为顺序表按链式存储方法存储的线性表称为链表、线性表中结点的结点是有限的结点间的关系是1对1的—、顺序表相对于链表的优点有以进行随机存取和节省存储、链表相对于顺序表的优点有不需要预分配存储空间—和—插入、删除操作方便、在个结点的顺序表中删除一个结点需平均移动（一）个结点具体的移动次数取决于表长和删除位置、在个结点的顺序表中插入一个结点需平均移动 个结点具体的移动次数取决于表长和插入位置、在顺序表中访问任意一个结点的时间复杂度均为 因此顺序表也称为随机存取 的数据结构、在个结点的单链表中要删除已知结点需找到前驱结点的地址其时间复杂度为、在双链中要删除已知结点其时间复杂度为、在单链表中要在已知结点之前插入一个新结点仍需找到节点的前一个节点其时间复杂度为 而在此链表中完成同样的操作其时间复杂度为、在循环链表中可根据在一结点的地址遍历整个链表而单链表中需要知道头指针 才能遍历整个链表三、简答题：四个数字按顺序进栈问退栈的顺序有几种答 即全部进栈，然后顺序出栈！，，，艮P12先进栈，然后出栈，然后、按顺序出栈,,,即，，先进栈，然后出栈，然后出栈，然后进栈，最后，按顺序出栈依次类推，有的次方种一、填空：、设二维数组 按行优先顺序存储在内存中，每个元素占个字节，则 的地址为,已知二维数组 中，每个元素占两个字节，元素 的地址为 ，则元素的地址为、若数组定义为 ，则元素 的地址为：、对于任何一棵二叉树，如果其终端结点数为，度为的结点数为，则有什么样的关系式。、设是一棵树， 是对应于的二叉树，则的先根遍历和的先序 遍历相同。、深度为的二叉树至多有 个结点。、对于二叉树来说，第层上至多有 个结点。

、某二叉树的前序遍历序列为列为：中序遍历序列为则后序遍历序、某二叉树的前序遍历序列为列为：中序遍历序列为则后序遍历序、将一棵有 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为，则编号为的结点的孩子编号为：、某二叉树的前序和后序正好相反，则该二叉树一定是高度等于苴结占数二叉树。、设高度为的二叉树上只有度为和度为的结点，则此二叉树中所包含的结点数至少为：、设森林中有棵树，第一，二，三，四棵树的结点个数分别是 ，那么当把森林转换成一棵二叉树后，其根结点的右子树上有个结点。、树中结点的最大层次称为树的深度或高度、由一棵二叉树的前序序列和中序遍历、由中序和后序遍历序列 ，能唯一确定这棵二叉树。、高度为的完全二叉树至少有 个结点。、将一棵树转换成一棵二叉树后，二叉树根结点没有左子树。、森林的后根遍历序列正是相应二叉树 的,历序列。森林的先根遍历正是相应二叉树的 ,历序列。、哈夫曼树是带权路径长度 最小的二叉树。、具有个叶结点的哈夫曼树共有 结点，、前序为 且后序为 的二叉树共 ,。,已知二叉树有个叶子结点，且仅有一个孩子的结点数为、则总结点数为,二、简答：,在具有个结点的（叉树的叉链表表示中，有多少个空指针。个结点的叉树共有个指针域，已使用的指针域为 所以空指针的个数为：给出、已知一棵二叉树的前序序列和中序序列分别为这棵二叉树的后序遍历序列。给出一、选择、在一个图中，所有顶点的度数之和等于图的边数的 倍、在一个有向图中所有顶点的入度之和等于所有顶点的出度之和的 倍、有个结点的无向图最多有 条边、有个结点的无向连通图最少有条边、有个结点的有向完全图有 条边、用邻接表表示图进行广度优先遍历时通常采用 来实现算法栈 队列 树 图、用邻接表表示图进行深度优先遍历时通常采用 来实现算法栈 队列 树 图、深度优先遍历类似于二叉树的先序遍历 中序遍历 后序遍历 层次遍历、广度优先遍历类似于二叉树的先序遍历 中序遍历 后序遍历 层次遍历、任何一个无向连通图的最小生成树只有一棵 一棵或多棵 条定有多棵 可能不存在二、简答无向图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一、填空、下列关键字序列中 是堆、堆是一种 排序插入选择交换归并、堆的形状是一棵二叉排序树 满二叉树 完全二叉树平衡二叉树、若一组记录的排序码为 则利用堆的方法建立的初始堆为、若一组记录的关键码为 则利用快速排序的方法以第一个记录为基准得到的一次划分结果为、设有个元素用折半查找法进行查找的