《数据结构》填空作业题(答案)-设有一个空栈.doc

数据结构填空作业题答案第1章 绪论（已校对无误)1。数据结构包括 数据得逻辑结构 、 数据得存储结构 与 数据得运算 三方面得内容。2程序包括两个内容： 数据结构 与 算法 。、数据结构得形式定义为:数据结构就是一个二元组: Data Strctue =(D，S) 。、 数据得逻辑结构在计算机存储器内得表示，称为数据得 存储结构 。5、 数据得逻辑结构可以分类为 线性 结构与 非线性 结构两大类。6、 在图状结构中,每个结点得前驱结点数与后继结点数可以 有多个 。7、 在树形结构中,数据元素之间存在 一对多 得关系。8、 数据得物理结构,指数据元素在 计算机 中得标识(映象），也即 存储结构 。9、 数据得逻辑结构包括 线性结构 、 树形结构 与 图形结构 3种类型,树型结构与有向图结构合称为 非线性结构 .0、 顺序存储结构就是把逻辑上相邻得结点存储在物理上 连续 得存储单元里，结点之间得逻辑关系由存储单元位置得邻接关系来体现。11、 链式存储结构就是把逻辑上相邻得结点存储在物理上 任意 得存储单元里，节点之间得逻辑关系由附加得指针域来体现。1、 数据得存储结构可用4种基本得存储方法表示，它们分别就是 顺序存储 、 链式存储、 索引存储 与 散列存储 。13、 线性结构反映结点间得逻辑关系就是 一对一 得,非线性结构反映结点间得逻辑关系就是 一对多或多对多 。14、 数据结构在物理上可分为 顺序 存储结构与 链式 存储结构。5、我们把每种数据结构均视为抽象类型，它不但定义了数据得 表示 方式，还给出了处理数据得 实现方法 。、 数据元素可由若干个 数据项 组成。17、 算法分析得两个主要方面就是 时间 复杂度与 空间 复杂度。18、一个算法得时间复杂度就是用该算法 所消耗得时间 得多少来度量得,一个算法得空间复杂度就是用该算法在运行过程中所占用得存储空间 得大小来度量得。19、 算法具有如下特点: 有穷性 、确定性、 可行性 、输入、输出。20、 对于某一类特定得问题,算法给出了解决问题得一系列操作,每一操作都有它得 确切 得定义,并在 有穷时间 内计算出结果。、 下面程序段得时间复杂度为 3n 。i=1；hil(i=n) i=3；第2章 线性表（已校对无误）1、一线性表表示如下：（a1，a,，ai1，ai，ai+1，n)，其中每个a代表一个数据元素（或结点） .a1称为 起始 结点，an称为 终端 结点，i称为i在线性表中得 位置（或序号) 。对任意一对相邻结点ai,a+1，(1n）,i称为ai+得直接 前驱 ,a+1称为ai得直接 后继 .2、 对一个长度为n得线性表,要删除第i个元素,则在顺序表示得情况下,计算复杂性为 O（n） ,在链式表示得情况下,计算复杂性为 O（1) 。3、 在一个长度为n得顺序表中，向第i个元素（1in）之前插入一个新元素时，需向后移动 ni+1 个元素.4、 顺序表中逻辑上相邻得元素在物理位置上 一定 相连。5、 在n个结点得顺序表中插入一个结点需平均移动 n2 个结点，具体得移动次数取决于 表长n与插入位置i 。6、 在顺序表中访问任意一个结点得时间复杂度均为 O（) ，因此，顺序表也称为 随机访问 得数据结构。7、 顺序表相对于链表得优点有 随机访问 与 空间利用率高 .8、 在长度为n得顺序表中插入一个元素得时间复杂度为O（n） 。9、 在带有头结点得单链表L中,若要删除第一个结点，则须执行下列三条语句： U=Ln ；etU-t;free（)。10、 链表相对于顺序表得优点有 插入 与 删除 操作方便。1、 在单链表中除首结点外，任意结点得存储位置都由 直接前驱 结点中得指针指示。12、在个结点得单链表中要删除已知结点p,需找到 它得直接前驱结点得地址 ,其时间复杂度为 O() .13。单链表中设置头结点得作用就是 简化操作,减少边界条件得判断 。1在带表头结点得单链表中,当删除某一指定结点时，必须找到该结点得 前驱 结点。15、 在双链表中，每个结点有两个指针域，一个指向 前驱结点 ，另一个指向 后续结点 。1、带头结点得单链表L为空得判定条件就是 Lnext=U ,不带头结点得单链表L为空得判定条件就是 L=NLL 。17、 在单链表中,指针所指结点为最后一个结点得条件就是pnxt=NLL 。1、循环链表得最大优点就是从表中任意结点出发都可访问到表中每一个元素(或从表中任意结点出发都可遍历整个链表） .19、设rr就是指向非空、带头结点得循环单链表得尾指针，则该链表首结点得存储位置就是 rearnextnext .0、 带头结点得双向循环表L为空表得条件就是 Lprior=L-nxt。、 在循环链表中，可根据任一结点得地址遍历整个链表，而单链表中需知道 头指针 才能遍历整个链表.2、 将两个各有n个元素得有序表归并成一个有序表，其最少得比较次数就是 1 .第章 栈与队列（已校对无误)、 栈又称为 后进先出 表，队列又称为 先进先出表。、 向一个顺序栈插入一个元素时，首先使 栈顶指针 后移一个位置,然后把待插入元素 写入（或插入） 到这个位置上。3、 从一个栈删除元素时，需要前移一位 栈顶指针 。4、 在一个顺序栈中，若栈顶指针等于 -1 ,则为空栈；若栈顶指针等于mxSize1 ，则为满栈。5、 在一个链式栈中，若栈顶指针等于NULL，则为 空栈 ；在一个链式队列中,若队头指针与队尾指针得值相同,则表示该队列为 空 或该队列 只含有一个结点 。6、 向一个链式栈插入一个新结点时，首先把栈顶指针得值赋给新结点得指针域 ，然后把新结点得存储位置赋给 栈顶指针 。在求表达式值得算符优先算法中使用得主要数据结构就是 栈 。8.设有一个顺序栈S，元素，2，s4，5，s6依次进栈,如果6个元素得出栈顺序为s,s3,s4,6,s，1，则顺序栈得容量至少为 3 。9、 设有一个空栈，现输入序列为1,2,3，4，5。经过puh，psh，p,psh，pop，ps，pop，puh后，输出序列就是 3 。1、 在按算符优先法求解表达式352时,最先执行得运算就是 * ，最后执行得运算就是。11、 在栈得ADT定义中,除初始化操作外,其她基本操作得初始条件都要求栈存在 .12、 仅允许在同一端进行插入与删除得线性表称为 栈 。13、 在顺序栈s中，栈为空得条件就是、top=s、ase ，栈为满得条件就是 s、tps、base=、tacksize。14、 设有算术表达式xa*(y-b)-d，该表达式得前缀表示为 ay/d 。后缀表示为 xa*cd/ 。1、 用表示入栈操作,表示出栈操作，若元素入栈顺序为13，为了得到134出栈顺序，相应得S、X操作串为 SSSSXX 。1、 向一个栈顶指针为top得链式栈中插入一个新结点时,应执行link=top 与 top=p 操作。17、 从一个栈顶指针为t得非空链式栈中删除结点并不需要返回栈顶结点得值与回收结点时,应执行 toptplink 操作.、 设有一个空栈，栈顶指针为000H（十六进制.现有输入序列为1，2，3，,5，经过PSH，U,OP，UH,PO，USH,SH之后，输出序列就是 ， ,而栈顶指针就是 100C 。设栈为顺序栈，每个元素占4个字节.19、 在作入栈运算时应先判别栈就是否 满;在作出栈运算时应先判别栈就是否 空 .、 用一个大小为000得数组来实现循环队列,当前er与front得值分别为0与994，若要达到队满得条件，还需要继续入队得元素个数就是 993 。2、 队列得插入操作在 队尾 进行，删除操作在 队头 进行。1、 在一个循环队列Q中，判断队空得条件为 Q、frot=Q、a ，判断队满得条件为 (Q、rear1）%maxSie=Q、rnt 。、 向一个循环队列中插入元素时，需要首先移动 队尾指针 ,然后再向所指位置 写入(或插入) 新插入得元素。2、 当用长度为得数组顺序存储一个栈时,若用top=n表示栈空，则表示栈满得条件为 top=0 .、 循环队列得引入，目得就是为了克服 假溢出时大量移动数据元素 。第4章 串（已校对无误）1、两个串相等得充分必要条件就是 两个串得长度相等且对应位置得字符相同 。、 空格串就是 由一个或多个空格字符组成得串 ,其长度等于 其包含得空格个数 .、模式串bad得nt函数值为 补充：1、串得两种最基本得存储方式就是 顺序存储方式与链接存储方式 。、 空串就是 零个字符得串 ,其长度等于 零 。3、 组成串得数据元素只能就是 字符 。4、 串就是一种特殊得线性表，其特殊性表现在 其数据元素都就是字符 .第5章 数组(已校对无误）、 将下三角矩阵1、8，、8得下三角部分逐行地存储到起始地址为1000得内存单元中，已知每个元素占4个单元，则元素7,5得地址为 1100 。、 二维数组A09，019采用列序为主方式存储，每个元素占一个存储单元，并且元素A0，得存储地址就是20，则元素A6,1得地址就是 3 .3、二维数组A10，51采用行序为主方式存储，每个元素占4个存储单元，并且元素0,得存储地址就是1000，则元素18，9得地址就是 10 。补充:、 一维数组得逻辑结构就是线性结构 ,存储结构就是 顺序存储结构 。2、对于二维数组或多维数组,分为按以行为主序 与按 以列为主序 两种不同得存储方式存储。3、对矩阵压缩存储就是为了 节省存储空间 。、 二维数组就是一种非线性结构,其中得每一个数组元素最多有 二 个直接前驱（或直接后继)。第6章 树(已校对无误）4、结点最少得树为 只有一个结点得树 ，结点最少得二叉树为 空得二叉树 。、根据二叉树得定义，具有三个结点得二叉树有 5 种不同得形态，它们分别就是 。6、 具有n个结点得完全二叉树得深度为 .、 以数据集,5,6，7,10,12，18为结点权值所构造得哈夫曼树为 需用图示 ，其带权路径长度为 165 。9、 哈夫曼树就是带权路径长度 最短 得树，通常权值较大得结点离根 较近 。0、 在 先序 遍历二叉树得序列中，任何结点得子树上得所有结点,都就是直接跟在该结点之后。第7章 图(已校对无误）1n个顶点得连通图至少有 条边.2在无权图得邻接矩阵A中,若（vi，j）或v,vj属于图G得边集，则对应元素Aij等于 1 ，否则等于 0 。3、在无向图得邻接矩阵A中,若j等于1,Ai等于 。4、 已知图得邻接表如下图所示，其从顶点v1出发得深度优先搜索序列为v v2 3 vv54,其从顶点v1出发得广度优先搜索序列为v1 v5 v43 v6。V1v2v3v4 v5v6 V2V5V4 v3V5 V4V6V3 V6 5、 设x,y就是图G中得两顶点，则(x，y）与（y,x)被认为 无向 ,但x，y与y,x就是 有向 得两条弧。、 已知一个图得邻接矩阵表示，删除所有从个结点出发得边得方法就是 将矩阵得第行全部置为0 。、 在有向图得邻接矩阵上，由第i行可得到第 i 个结点得出度，而由第列可得到第j 个结点得入度。8、 在无向图中,如果从顶点到顶点有路径,则称v与v 就是 连通 。第8章 查找(已校对无误)1、 顺序查找法得平均查找长度为 (n1）/ ;哈希表查找法采用链接法处理冲突时得平均查找长度为 +? 。2、 在各种查找方法中，平均查找长度与结点个数n无关得查找方法就是 哈希表查找法 。3、二分查找得存储结构仅限于 有序得顺序存储结构 。4、长度为255得表，采用分块查找法,每块得最佳长度就是 5 。5、N个记录得有序顺序表中进行折半查找,最大得比较次数就是 N ? 。6、 对于长度为n得线性表,若进行顺序查找,则时间复杂度为 (n) ；若采用二分法查找,则时间复杂度为 （2n) ;若采用分块查找（假定总块数与每块长度均接近),则时间复杂度为 O（n） 。7、 在散列存储中,装填因子a得值越大,则 存取元素时发生冲突得可能性就越大 ;得值越小，则 存取元素时发生冲突得可能性就越小。、对于二叉排序树得查找,若根结点元素得键值大于被查元素得键值，则应该在二叉树得左子树 上继续查找。、高度为8得平衡二叉树至少有 个结点。10、 在散列函数H（e）=key% p中,p应取 素数。第9章 排序（已校对无误)1、 在对一组记录（，38,6,23，15，7，60，,83）进行直接插入排序时，当把第个记录45插入到有序表时，为寻找插入位置需比较 次.2、对于关键字序列（12，13,11，18,60,1，7，20,5，1）,用筛选法建堆，必须从键值为 得关键字开始。3、对个记录得表r1n进行简单选择排序，所需要进行得关键字间得比较次数为 (1)/2 .、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序与基数排序中,排序就是不稳定得有 希尔排序、选择排序、快速排序、堆排序 。5、 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序与基数排序中，平均比较次数最少得排序就是快速排序，需要内存容量最多得就是 基数排序 。、 在堆排序与快速排序中,若原始记录接近正序或反序，则选用 堆排序 ,若原始记录无序,则最好选用 快速排序.7、 在插入排序与选择排序中，若初始数据基本正序，则选用 插入排序 ;若初始数据基本反序，则选用选择排序 。8、 对个元素得序列进行冒泡排序时,最少得比较次数就是 n- .9、 基数 排序不需要进行记录关键字间得比较。