一、填空题
4.数据结构按逻辑结构可分为两大类，它们分别是 线性结构 非线性结构
4.算法分析的两个主要方面是：
12.在顺序表中插入，需要移动元素。具体移动的元素个数与 表长和该元素在表中的位置有关。
13.线性表中结点的集合是的。
14.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。
15.向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。
16.在顺序表中访问任意一结点的时间复杂度均为因此，顺序表也称为的数据结构。
17.顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置 相邻。
18．在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值指示。
19． 在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。
20.向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
23.不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。
24.子串的定位运算称为串的模式匹配； 被匹配的主串称为目标串，子串称为模式。
25.假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276。
26． 由３个结点所构成的二叉树有种形态。 课本P127,128
27.一棵深度为6的满二叉树有 126-1个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。或总结点数可算，叶子结点数可算，两个相减
28． 一棵具有２５７个结点的完全二叉树，它的深度为（ 注：用 log2(n) +1= 8.xx +1=9
29．设一棵完全二叉树有700个结点，则共有答：最快方法：用叶子数＝[n/2]＝350
30． 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。
答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.
31．在数据的存放无规律而言的线性表中进行检索的最佳方法是。
32.线性有序表（a1，a2，a3，„，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。即树高
33.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为3.7。
解：显然，平均查找长度＝O（log2n）
不应当按照公式
ASLn1m）。因为这是在假设n＝2-1的情况下log2(n1)来计算（即（21×log221）/20＝4.6次并不正确！n5
推导出来的公式。应当用穷举法罗列：
全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7！！！
34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。
二、判断正误（在正确的说法后面打勾，反之打叉）
（ ×）1.链表的每个结点中都恰好包含一个指针。
答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（ ×）2.链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。
（ ×）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。
（ ×）5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”
（ ×）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
（ ×）7.线性表在物理存储空间中也一定是连续的。
错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。
（ ×）9.顺序存储方式只能用于存储线性结构。
错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）
（ ×）10.线性表的逻辑顺序与存储顺序总是一致的。
错，理由同7。链式存储就无需一致。
（ √）13.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √）14.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
（ ×）15.栈和链表是两种不同的数据结构。
错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。
（ √）17.栈和队列的存储方式既可是顺序方式，也可是链接方式。
（ √）18.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（ √ ）21.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （ √ ）23.二叉树中每个结点的两棵子树是有序的。
（ × ）26.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）
（ × ）27.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（ √ ）29.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
三、单项选择题
（B）1.非线性结构是数据元素之间存在一种：
A）一对多关系B）多对多关系C）多对一关系D）一对一关系
（C）2.数据结构中，与所使用的计算机无关的是数据的结构；
A) 存储B) 物理C) 逻辑D) 物理和存储
（C）3.算法分析的目的是：
A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性
（B）17.判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST->top0Ｂ．ST->top=0Ｃ．ST->topm0Ｄ．ST->top=m0
（B）22．在表长为ｎ的链表中进行线性查找，它的平均查找长度为
Ａ.ＡＳＬ＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;
Ｃ.ＡＳＬ＝n＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（C）24．对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。 公式p229A．3B．4C．5D． 6
