复习题一及答案.doc

复习题一 1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( A )。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2. 在有向图中每个顶点的度等于该顶点的( C )。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 3. 下列排序算法中( C )是不稳定的排序算法。 A. 冒泡排序 B. 合并排序 C. 快速排序 . D. 插入排序 4. 在单链表中，q指向待删除结点的前驱，p指向待删除的结点，则删除节点的操作是( B )。 A. p=q-next；q-next=p-next; free (p); B. q-next=p; q-next=p-next; free (p);. C. p=q-next; free (p); q-next=p-next; D. p=q-next; p=p-next; free (p); 5. 栈操作的基本原则( B ). A. 先进先出 B. 先进后出 C. 只能进行插入 D. 只能进行删除 设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次入栈，若有6个元素出栈的顺序是S2，S3，S4，S6，S5，S1。则该栈的容量至少应该是（ B ）。 A．2 B．3 C．4 D．5 9. 具有50个结点的完全二叉树，编号为19的结点的左孩子编号为( C ) A. 46 B. 39 C. 38 D. 不存在 10. 若一棵二叉树具有10个度为2的节点，5个度为1的节点，则度为零的节点个数是( B ). A. 9 B. 11 C. 15 D. 不确定 11. 有n个顶点的无向图最多有( B )条边。 A. n-1 B. n*(n-1)/2 C. n*(n+1)/2 D. n*n 12. 对下图G，若从顶点a出发，按深度有哪些信誉好的足球投注网站法，进行遍历，则可能得到的一种顶点序列为( D )，按广度有哪些信誉好的足球投注网站法进行遍历，则可能得到的一种顶点序列为( B )。 A. a b e c f d B. a b c e f d C. a e b c f d D. a e d f c b 13. 在一个无向图中，所有顶点度数之和等于所有边数( B )倍，在一个有向图中，所有顶点入度数之和等于所有顶点出度之和的( C )倍。 A. 1/2 B. 2 C. 1 D. 4 二、填空题：（每空1分，共10分） 选择合适的存储结构，通常考虑的指标是空间复杂度和_时间复杂度__。 2. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度__O（n）_为，在表尾插入元素的时间复杂度为____O(1)___。 3. 在一棵二叉树中，第5层上的结点数最多为___16_。 4. 设有一空栈S及等待进栈的数据元素序列数据：2，3，4，5，6，7，8，9。依次进行push, push, pop, push, pop, push, push, pop, push, push, pop 操作，完成此操作后，栈S的栈顶元素为____7____，栈底元素为____2___。 5. 在一棵树中，__叶子__结点没有后继结点，__根__节点没有前驱节点。 6. 假定一棵二叉树的结点个数为10，则它的高度至多为___10___，它的高度至少为____4____。 三、判断题：（每小题1分，共10分） 1. (X )线性表的特点是每个元素都有一个前驱和一个后继。 2. (V )直接选择排序是一种不稳定的排序方法 。 3. (X )二分查找只适用于有序表，包括有序的顺序表和有序的链表。 4. (X )链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 5. (X )通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 6. (X )对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。 7. (X )二叉树的度数为2。 8. (X )在n个顶点的无向图中，若边数大于n-1，则该图必是连通图。 9. (X )有e条