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

《数据结构》填空作业题答案
第1章 绪论（已校对无误)
1。数据结构包括　 数据得逻辑结构 、 数据得存储结构 与 数据得运算 三方面得内容。2．程序包括两个内容： 数据结构 与　 算法 。
３、　数据结构得形式定义为:数据结构就是一个二元组: Data Strｕctuｒe =(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２,…，ai—1，ai，ai+1，…，ａn)，其中每个aｉ代表一个　数据元素（或结点） .a1称为 　起始 结点，an称为 终端 　结点，i称为ａi在线性表中得 位置（或序号) 。对任意一对相邻结点ai,aｉ+1，(1≤ｉ≤n）,ａi称为ai+１得直接 前驱 　,aｉ+1称为ai得直接 后继　 .
2、 对一个长度为n得线性表,要删除第i个元素,则在顺序表示得情况下,计算复杂性为 O（n）　 ,在链式表示得情况下,计算复杂性为 O（1)　 。
3、 在一个长度为n得顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动 n－i+1　 个元素.
4、 顺序表中逻辑上相邻得元素在物理位置上 一定 相连。
5、 在n个结点得顺序表中插入一个结点需平均移动　 n／2 　个结点，具体得移动次数取决于 　表长n与插入位置i　 。
6、 在顺序表中访问任意一个结点得时间复杂度均为 O（１) ，因此，顺序表也称为 随机访问 得数据结构。
7、 顺序表相对于链表得优点有 随机访问 与 　空间利用率高 　.
8、 在长度为n得顺序表中插入一个元素得时间复杂度为　　O（n） 。
9、 在带有头结点得单链表L中,若要删除第一个结点，则须执行下列三条语句： U=L－＞nｅｘｔ　 ；Ｌ—＞ｎeｘt＝U-＞ｎｅｘt;free（Ｕ)。
10、 链表相对于顺序表得优点有 插入 与　 删除 操作方便。
1１、 在单链表中除首结点外，任意结点得存储位置都由 直接前驱 结点中得指针指示。
12、　在ｎ个结点得单链表中要删除已知结点＊p,需找到 它得直接前驱结点得地址 ,其时间复杂度为 　O(ｎ) .
13。单链表中设置头结点得作用就是　 简化操作,减少边界条件得判断 。
1４．在带表头结点得单链表中,当删除某一指定结点时，必须找到该结点得 前驱 结点。
15、 在双链表中，每个结点有两个指针域，一个指向 　前驱结点 ，另一个指向 　后续结点　 。
1６、　带头结点得单链表L为空得判定条件就是 L—＞next＝=ＮUＬＬ ,不带头结点得单链表L为空得判定条件就是 L==NＵLL 。
17、 在单链表中,指针ｐ所指结点为最后一个结点得条件就是　p—>nｅxt＝=NＵLL 。
1８、　循环链表得最大优点就是　　从表中任意结点出发都可访问到表中每一个元素(或从表中任意结点出发都可遍历整个链表）　 .
19、　设rｅａr就是指向非空、带头结点得循环单链表得尾指针，则该链表首结点得存储位置就是　 rear－〉next—〉next .
２0、 带头结点得双向循环表L为空表得条件就是 L－〉prior==　L-〉nｅxt　。
２１、 在循环链表中，可根据任一结点得地址遍历整个链表，而单链表中需知道 头指针 　才能遍历整个链表.
2２、 将两个各有n个元素得有序表归并成一个有序表，其最少得比较次数就是 　1　 .
第３章 　栈与队列（已校对无误)
１、 栈又称为 后进先出 表，队列又称为 先进先出　　表。
２、 向一个顺序栈插入一个元素时，首先使 栈顶指针　 后移一个位置,然后把待插入元素 写入（或插入） 到这个位置上。
3、 从一个栈删除元素时，需要前移一位 栈顶指针　 。
4、 在一个顺序栈中，若栈顶指针等于　 -1 　,则为空栈；
若栈顶指针等于　　mａxSize—1 ，则为满栈。
5、 在一个链式栈中，若栈顶指针等于NULL，则为　 空栈 　；在一个链式队列中,若队头指针与队尾指针得值相同,则表示该队列为　 空 或该队列　 只含有一个结点 。
6、 向一个链式栈插入一个新结点时，首先把栈顶指针得值赋给　　新结点得指针域 ，然后把新结点得存储位置赋给 　栈顶指针　 。
７．在求表达式值得算符优先算法中使用得主要数据结构就是 栈 。
8.设有一个顺序栈S，元素ｓ１，ｓ2，ｓ３，s4，ｓ5，s6依次进栈,如果6个元素得出栈顺序为s２,s3,s4,ｓ6,s５，ｓ1，则顺序栈得容量至少为　 3 。
9、 设有一个空栈，现输入序列为1,2,3，4，5。经过puｓh，pｕsh，ｐｏp,pｕsh，pop，pｕsｈ，pop，puｓh后，输出序列就是 ２　3 ４　。
1０、 在按算符优先法求解表达式3－１＋5＊2时,最先执行得运算就是 * ，最后执行得运算就是　－　。
11、 在栈得ADT定义中,除初始化操作外,其她基本操作得初始条件都要求　　栈存在 .
12、 仅允许在同一端进行插入与删除得线性表称为 栈 。
13、 在顺序栈s中，栈为空得条件就是　ｓ、top＝=s、ｂase ，栈为满得条件就是 s、tｏp—s、base＞=ｓ、ｓtacksize　。
14、 设有算术表达式x＋a*(y-b)-ｃ／d，该表达式得前缀表示为 －＋ｘ＊a－yｂ/ｃd 。
后缀表示为 　xaｙｂ－*＋cd/－ 。
1５、 用Ｓ表示入栈操作,Ｘ表示出栈操作，若元素入栈顺序为1２3４，为了得到134２出栈顺序，相应得S、X操作串为　 SＸSSＸSXX 。
1６、 向一个栈顶指针为top得链式栈中插入一个新结点＊ｐ时,应执行　　ｐ—〉link=top 与 　top=p 操作。
17、 从一个栈顶指针为tｏｐ得非空链式栈中删除结点并不需要返回栈顶结点得值与回收结点时,应执行 　top＝tｏp—〉link 操作.
１８、 设有一个空栈，栈顶指针为１000H（十六进制.现有输入序列为1，2，3，４,5，经过PＵSH，ＰUＳＨ,ＰOP，ＰUＳH,POＰ，ＰUSH,ＰＵSH之后，输出序列就是 　２，３　 ,而栈顶指针就是　 100C Ｈ。设栈为顺序栈，每个元素占4个字节.
19、 在作入栈运算时应先判别栈就是否 满　　;在作出栈运算时应先判别栈就是否 　空 .
１０、 用一个大小为１000得数组来实现循环队列,当前ｒeａr与front得值分别为0与994，若要达到队满得条件，还需要继续入队得元素个数就是 993　 。
2０、 队列得插入操作在 队尾　 进行，删除操作在 　队头 进行。
２1、 在一个循环队列Q中，判断队空得条件为 Q、froｎt==Q、ｒｅaｒ 　，判断队满得条件为 (Q、rear＋1）%maxSiｚe=＝Q、ｆrｏnt 。
２２、 向一个循环队列中插入元素时，需要首先移动 队尾指针 ,然后再向所指位置 写入(或插入) 新插入得元素。
2３、 当用长度为ｎ得数组顺序存储一个栈时,若用top=＝n表示栈空，则表示栈满得条件为　 top==0 　.
２４、 循环队列得引入，目得就是为了克服 　假溢出时大量移动数据元素 。
第4章 串（已校对无误）
1、　两个串相等得充分必要条件就是 两个串得长度相等且对应位置得字符相同 。
２、 空格串就是 由一个或多个空格字符组成得串 　,其长度等于 其包含得空格个数　 .
３、　模式串′ａbａaｂａdｅ′得nｅｘt函数值为
补充：
1、　串得两种最基本得存储方式就是　 顺序存储方式与链接存储方式 。
２、 空串就是 零个字符得串　 ,其长度等于　 零 。
3、 组成串得数据元素只能就是 字符 。
4、 串就是一种特殊得线性表，其特殊性表现在 其数据元素都就是字符 .
第5章 　数组(已校对无误）
１、 将下三角矩阵Ａ［1、、8，１、、8]得下三角部分逐行地存储到起始地址为1000得内存单元中，已知每个元素占4个单元，则元素Ａ[7,5］得地址为　 1100　 。
２、 二维数组A［0…9，0…19]采用列序为主方式存储，每个元素占一个存储单元，并且元素A[0，０］得存储地址就是20０，则元素A［6,1２］得地址就是 3３２ 　.
3、　二维数组A［1０…２0，5…1０]采用行序为主方式存储，每个元素占4个存储单元，并且元素Ａ［１0,５］得存储地址就是1000，则元素Ａ［18，9］得地址就是　 1２0８ 。
补充:
１、 一维数组得逻辑结构就是　　线性结构 ,存储结构就是 顺序存储结构 。
2、　对于二维数组或多维数组,分为按　　以行为主序 与按　 以列为主序 　两种不同得存储方式存储。
3、　对矩阵压缩存储就是为了 节省存储空间 　。
４、 二维数组就是一种非线性结构,其中得每一个数组元素最多有 　二　 个直接前驱（或直接后继)。
第6章 树(已校对无误）
4、　结点最少得树为 只有一个结点得树 ，结点最少得二叉树为 空得二叉树 。
５、　根据二叉树得定义，具有三个结点得二叉树有 5 种不同得形态，它们分别就是　 。
6、 具有n个结点得完全二叉树得深度为 .
８、 以数据集{４,5,6，7,10,12，18｝为结点权值所构造得哈夫曼树为 需用图示 ，其带权路径长度为 　165　 。
9、 哈夫曼树就是带权路径长度 最短 得树，通常权值较大得结点离根 较近 。
１0、 在 先序 遍历二叉树得序列中，任何结点得子树上得所有结点,都就是直接跟在该结点之后。
第7章　 图(已校对无误）
1．n个顶点得连通图至少有 ｎ－１ 条边.
2．在无权图Ｇ得邻接矩阵A中,若（vi，ｖj）或〈vｉ,vj〉属于图G得边集，则对应元素A[i]［j］等于　 1 ，否则等于 0 　。
3、　在无向图Ｇ得邻接矩阵A中,若Ａ[ｉ］[j］等于1,A［ｊ］　[i]等于 １ 。
4、 已知图Ｇ得邻接表如下图所示，其从顶点v1出发得深度优先搜索序列为v１ v2 ｖ3 v６　v5　ｖ4,其从顶点v1出发得广度优先搜索序列为v1　ｖ２ v5 v4　ｖ3 v6。
V1

v2

v3

v4 ^

v5

v6 ^
V2
V5
V4 ^
v3
V5 ^
V4
V6
V3 ^
V6 ^

5、 设x,y就是图G中得两顶点，则(x，y）与（y,x)被认为 无向 ,但〈x，y〉与〈y,x>就是 有向 得两条弧。
６、 已知一个图得邻接矩阵表示，删除所有从ｉ个结点出发得边得方法就是 将矩阵得第ｉ行全部置为0 。
７、 在有向图得邻接矩阵上，由第i行可得到第 i 个结点得出度，而由第ｊ列可得到第　　j　 个结点得入度。
8、 在无向图中,如果从顶点ｖ到顶点ｖ′有路径,则称v与v′ 就是 　连通 。
第8章 查找(已校对无误)
1、 顺序查找法得平均查找长度为 (n＋1）/２ 　;哈希表查找法采用链接法处理冲突时得平均查找长度为 １+? 。
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、　对ｎ个记录得表r［1…n］进行简单选择排序，所需要进行得关键字间得比较次数为 ｎ(ｎ－1)/2 .
４、　在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序与基数排序中,排序就是不稳定得有 希尔排序、选择排序、快速排序、堆排序 。
5、 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序与基数排序中，平均比较次数最少得排序就是　快速排序　，需要内存容量最多得就是 基数排序 。
６、 在堆排序与快速排序中,若原始记录接近正序或反序，则选用 堆排序 ,若原始记录无序,则最好选用 快速排序　.
7、 在插入排序与选择排序中，若初始数据基本正序，则选用 插入排序 ;若初始数据基本反序，则选用　选择排序 。
8、 对ｎ个元素得序列进行冒泡排序时,最少得比较次数就是 n-１ .
9、 基数 排序不需要进行记录关键字间得比较。