数据结构(c语言版)复习资料

大学 数据库复习(C语言)复习 资料

数据结构复习资料 由 其直接前驱结点的链域的值 指示。

19． 在n个结点的单链表中要删除已知结点*p，

需找到它的前驱结点的地址，其时间复杂度为O（n）。 1. 数据结构是一门研究非数值计算的程序设计问

20.栈只能在插入和删除元素；对于队列题中计算机的 操作对象 以及它们之间的 关

只能在 队尾 插入和 队首 删除元素。 系 和运算等的学科。

21. 栈是一种特殊的线性表，允许插入和删除运算2. 数据结构被形式地定义为（D, R），其中D是的一端称为 栈顶 。不允许插入和删除运算据元素 的有限集合，R是D上的 关系 有限

的一端称为 栈底 。 集合。

22. 是被限定为只能在表的一端进行插3. 数据结构包括数据的 逻辑结构、数据的存储

入运算，在表的另一端进行删除运算的线性表。 结构 和数据的 运算 这三个方面的内容。

4. 数据结构按逻辑结构可分为两大类，它们分别是 26． 由３个结点所构成的二叉

树有 5 种形态。 线性结构 和 非线性结构 。

27. 一棵深度为65. 线性结构中元素之间存在关系，树形结构6-1中元素之间存在一对多关系，图形结构中元素之间

1的结点，所以分支结点数存在多对多关系。

就是二度结点数。 6． 在线性结构中，第一个结点28． 一棵具有２５７个结点的完全二叉树，它的其余每个结点有且只有 1个前驱结点；最后一个结

深度为 9 。 点 没有 后续结点，其余每个结点有且只有1

（ 注：用 log2(n) +1= 8.xx +1=9 个后续结点。

29．设一棵完全二叉树有700个结点，则共有 350 7. 在树形结构中，树根结点没有个叶子结点。 余每个结点有且只有 1 个前驱结点；叶子结

答：最快方法：用叶子数＝[n/2]＝350 点没有 后续 结点，其余每个结点的后续结点

数可以任意多个 。

30． 设一棵完全二叉树具有1000个结点，则此完

8. 在图形结构中，每个结点的前驱结点数和后续结

全二叉树有 500 个叶子结点，有 499 个度为

点数可以 任意多个 。

2的结点，有有

9．数据的存储结构可用四种基本的存储方法表示，

个结点只有非空右子树。

它们分别是顺序 、 链式 、 索引 和 散列 。

答：最快方法：用叶子数＝[n/2]＝500 ，

10. 数据的运算最常用的有5种，它们分别是插入 、

n2=n0-1=499。 另外，最后一结点为2i属于左叶子，

删除、修改、 查找 、排序。

右叶子是空的，所以有1个非空左子树。完全二叉

11. 一个算法的效率可分为时间效率和空

树的特点决定不可能有左空右不空的情况，所以非

间 效率。

空右子树数＝0.

12. 在顺序表中插入或删除一个元素，需要平均移

31．在数据的存放无规律而言的线性表中进行检索

动 表中一半元素，具体移动的元素个数与 表长和

的最佳方法是 顺序查找（线性查找） 。 该元素在表中的位置 有关。

13. 线性表中结点的集合是的，结点间的32. 线性有序表（a1，a2，a3， ，a256)是从小到大关系是 一对一 的。 排列的，对一个给定的值k，用二分法检索表中与14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)k相等的元素，在查找不成功的情况下，最多需要之前插入一个元素时，需向后移动 n-i+1 个元素。 检索 8 次。设有100个结点，用二分法查找时，15. 向一个长度为n的向量中删除第i个元素(1≤i最大比较次数是 7 。 ≤n)时，需向前移动 n-i 个元素。 33. 假设在有序线性表a[20]上进行折半查找，则比16. 在顺序表中访问任意一结点的时间复杂度均为较一次查找成功的结点数为1；比较两次查找成功

，因此，顺序表也称为的结点数为 2 ；比较四次查找成功的结点数为 结构。

17. 顺序表中逻辑上相邻的元素的物理位置 必定；平均查找长度为。

5相邻。单链表中逻辑上相邻的元素的物理位置 不解：显然，平均查找长度＝O（log2n）<5次（2）。

一定 相邻。 但具体是多少次，则不应当按照公式 18．在单链表中，除了首元结点外，任一结点的存储位置

一、填空题

大学 数据库复习(C语言)复习 资料

ASL

n 1

log2(n 1)来计算（即（21×log221）/20n

m

元素。

＝4.6次并不正确！）。因为这是在假设n＝2-1的情况下推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为＝（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 比较大小。 35. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 决定数据的存储地址。

（ × ）7. 线性表在物理存储空间中也一定是连

续的。

错，线性表有两种存储方式，顺序存

储和链式存储。后者不要求连续存放。

（ × ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

（ × ）9. 顺序存储方式只能用于存储线性结构。

错误。顺序存储方式不仅能用于存储线性结构，还可

以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）

36. 散列法存储的基本思想是由 关键字的值 （ × ）10. 线性表的逻辑顺序与存储顺序总是一

致的。

错，理由同7。链式存储就无需一致。

二、判断正误（在正确的说法后面打勾，反之打叉）

（ × ）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（ × ）11. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）12. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

（ × ）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。

（ × ）3. 链表的删除算法很简单，因为当删除

链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。

（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链

表也是线性表！且即使是顺序表，也能存放记录型数据。

（ √ ）13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（ √ ）14. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻 …… 此处隐藏：9047字，全部文档内容请下载后查看。喜欢就下载吧 ……