文档介绍：可以失败,不可以失志。可以失望,不可以绝望。只要眷恋奇迹,才会得到奇迹的眷恋。
数据结构复****资料
一、填空题
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科
2. 数据结构被形式地定义为(D
R)
其中D是数据元素的有限集合
R是D上的关系有限集合
3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容
4. 数据结构按逻辑结构可分为两大类
它们分别是线性结构和非线性结构
5. 线性结构中元素之间存在一对一关系
树形结构中元素之间存在一对多关系
图形结构中元素之间存在多对多关系
6. 在线性结构中
第一个结点没有前驱结点
其余每个结点有且只有 1个前驱结点;最后一个结点没有后续结点
其余每个结点有且只有1个后续结点
7. 在树形结构中
树根结点没有前驱结点
其余每个结点有且只有 1 个前驱结点;叶子结点没有后续结点
其余每个结点的后续结点数可以任意多个
8. 在图形结构中
每个结点的前驱结点数和后续结点数可以任意多个
它们分别是顺序、链式、索引和散列
10. 数据的运算最常用的有5种
它们分别是插入、删除、修改、查找、排序
11. 一个算法的效率可分为时间效率和空间效率
12. 在顺序表中插入或删除一个元素
需要平均移动表中一半元素
具体移动的元素个数与表长和该元素在表中的位置有关
13. 线性表中结点的集合是有限的
结点间的关系是一对一的
14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时
需向后移动 n-i+1 个元素
15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时
需向前移动 n-i 个元素
16. 在顺序表中访问任意一结点的时间复杂度均为 O(1)
因此
顺序表也称为随机存取的数据结构
17. 顺序表中逻辑上相邻的元素的物理位置必定相邻
单链表中逻辑上相邻的元素的物理位置不一定相邻
除了首元结点外
任一结点的存储位置由其直接前驱结点的链域的值指示
19. 在n个结点的单链表中要删除已知结点*p
需找到它的前驱结点的地址
其时间复杂度为O(n)
20. 向量、栈和队列都是线性结构
可以在向量的任何位置插入和删除元素;对于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入和队首删除元素
21. 栈是一种特殊的线性表
允许插入和删除运算的一端称为栈顶
不允许插入和删除运算的一端称为栈底
22. 队列是被限定为只能在表的一端进行插入运算
在表的另一端进行删除运算的线性表
23. 不包含任何字符(长度为0)的串称为空串; 由一个或多个空格(仅由空格符)组成的串称为空白串
24. 子串的定位运算称为串的模式匹配; 被匹配的主串称为目标串
子串称为模式
25. 假设有二维数组A6×8
每个元素用相邻的6个字节存储
存储器按字节编址
已知A的起始存储位置(基地址)为1000
则数组A的体积(存储量)为 288 B ;末尾元素A57的第一个字节地址为 1282 ;若按行存储时
元素A14的第一个字节地址为(8+4)×6+1000=1072 ;若按列存储时
元素A47的第一个字节地址为(6×7+4)×6+1000)=1276
26. 由3个结点所构成的二叉树有 5 种形态
27. 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子
注:满二叉树没有度为1的结点
所以分支结点数就是二度结点数
28. 一棵具有257个结点的完全二叉树
它的深度为 9
( 注:用? log2(n) ?+1= ? ?+1=9
则共有 350 个叶子结点
答:最快方法:用叶子数=[n/2]=350
30. 设一棵完全二叉树具有1000个结点
则此完全二叉树有 500 个叶子结点
有 499 个度为2的结点
有 1 个结点只有非空左子树
有 0 个结点只有非空右子树
答:最快方法:用叶子数=[n/2]=500
n2=n0-1=499
另外
最后一结点为2i属于左叶子
右叶子是空的
所以有1个非空左子树
完全二叉树的特点决定不可能有左空右不空的情况
所以非空右子树数=0.
(线性查找)
32. 线性有序表(a1
a2
a3
...
a256)是从小到大排列的
对一个给定的值k
用二分法检索表中与k相等的元素
在