发布时间 : 星期一 文章数据结构与算法复习题及更新完毕开始阅读ee8216e5580102020740be1e650e52ea5418ce59
2016《数据结构域算法》复习题
二、填空题
1．数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 2．下面程序段的时间复杂度是 O(log3n) 。
i ＝ 1；
while（i<=n） i = i * 3；
3．在顺序表中插入或删除一个元素，需要平均移动 表中一半 元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。
4．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用 顺序 存储结构。
5．在n个结点的单链表中要删除已知结点*p，需找到它的 前驱结点 的地址，其时间复杂度为O（n）。 6．已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。
删除P结点的直接后继结点的语句序列是 (11)(4)(14) 。 删
除
P
结
点
的
语
句
序
列
是
(10)(12)(7)(4)(14) 。
(1) P = P->next ; (2) P->next = P; (3) P->next = P->next->next
13
2016《数据结构域算法》复习题
(4) P->next = P->next->next; (5) while(P!=NULL) P = P->next ;
(6) while(Q->next != NULL) {P = Q; Q=Q->next;} (7) while(P->next != Q) P = P->next; (8) while(P->next->next != Q) P = P->next; (9) while(P->next->next != NULL) P = P->next; (10) Q = P; (11) Q = P->next; (12) P = L ; (13) L = L->next; (14) free(Q);
7．栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。
8．设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是 3 。
9．用S表示入栈操作，X表示出栈操作，若元素入栈的
顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为 SXSSXSXX 。
10．数据的逻辑结构可以分为 线性 和 非线性 两大类。
11．数据的运算用 算法 表示。
12．逻辑上相邻的结点在存储器中也相邻，这是 顺序 存储结构的特点。
13．在长度为n的顺序表上实现定位操作，其算法的时间
14
2016《数据结构域算法》复习题
复杂度为 O(n) 。
14．为了实现随机访问，线性结构应该采用 顺序 存储。
15．在长度为n的顺序表中插入一个元素，最多要移动 n 个元素。
16．栈的存储结构主要有 顺序 和 链式 两种。 17．在编写程序的时候，如果栈的最大长度难以预先估计，则最好使用 链式 栈。
18．在树形结构中，如果某结点 没有前驱（双亲） ，则称该结点为根结点；如果某结点 没有后继（孩子） ，则称该结点为叶子。
19．在树形结构中，每个结点最多只有一个前驱（双亲）。 20． 由3个结点所构成的二叉树有 5 种形态。 21．二叉树的前序遍历按如下三个步骤进行： ①访问根结点 ； ②前序遍历左子树 ； ③前序遍历右子树 。【注意：②③中一定要加“前序”两字！】 22．二叉树的中序遍历按如下三个步骤进行：①中序遍历左子树 ； ②访问根结点 ；③中序遍历左子树 。【注意：①③中一定要加“中序”两字！】
23．在n个顶点的无向图中，至少有 0 条边，至多有 n(n-1)/2 条边。
24．在n个顶点的有向图中，至少有 0 条边，至多有 n(n-1) 条边。
15
2016《数据结构域算法》复习题
25．如果排序不改变关键字相同的记录之间的相对次序，则称该排序方法是稳定的。
26．如果排序改变了关键字相同的记录之间的相对次序，则称该排序方法是不稳定的。
27．当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是 直接插入排序 。
28．在一个图中，所有顶点的度数之和是所有边数的 2 倍。
29．无向图中边的数目等于邻接矩阵中非零元素个数的 0.5 倍。
30．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
31．在有序表（2，4，6，8，10，12，14，16，18）上用
折半查找法查找元素9，其中第二次被比较的元素是 4 。
32．在有序表（2，4，6，8，10，12，14，16，18）上用
折半查找法查找元素9，其中第三次被比较的元素是 6 。
三、简答题
1．对链表设置头结点的作用是什么？（至少说出两条好处）
16