文档介绍：第 1页,共 5页一、填空题 1. 栈和队列的共同特点是( 只允许在端点处插入和删除元素)。 2. 在深度为 5 的满二叉树中,叶子结点的个数为( 31) 3. 算法分析的目的是( 分析算法的效率以求改进)。 4. 由两个栈共享一个存储空间的好处是( 节省存储空间,降低上溢发生的机率)。 5. 串的长度是( 串中所含字符的个数)。 6. 设有两个串 p和q ,求 q在p 中首次出现位置的运算称做( 模式匹配) 个顶点的连通图中边的条数至少为( N-1 )。 8 .N 个顶点的强连通图的边数至少有( N)。 9. 对长度为 n 的线性表进行顺序查找, 在最坏情况下所需要的比较次数为(N)。 P259 10. 假设线性表的长度为 n ,则在最坏情况下,冒泡排序需要的比较次数为( n(n-1)/2 )。 P292 个结点的单链表中要删除已知结点*p ,需找到它的前驱结点的地址, 其时间复杂度为 O(n)。 12. 在具有 n 个单元的循环队列中,队满时共有 n-1 个元素。 13. 有向图 G 用邻接表矩阵存储, 其第 i 行的所有元素之和等于顶点 i的出度。 14. 用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。第 2页,共 5页 15. 在图形结构中, 每个结点的前驱结点数和后续结点数可以任意多个。 16 .在一个循环队列中,队首指针指向队首元素的前一个位置。 17. 在顺序表中插入或删除一个元素, 需要平均移动表中一半元素, 具体移动的元素个数与表长和该元素在表中的位置有关。 18. 线性表中结点的集合是有限的,结点间的关系是一对一的。 19. 数据结构被形式地定义为( D,R) ,其中 D是数据元素的有限集合, R是D 上的关系有限集合。 20. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。 21. 一个算法的效率可分为时间效率和空间效率。 22. 在顺序表中访问任意一结点的时间复杂度均为 O(1) , 因此, 顺序表也称为随机存取的数据结构。 23. 在n 个结点的单链表中要删除已知结点*p ,需找到它的前驱结点的地址, 其时间复杂度为 O(n)。 24. 在具有 n 个单元的循环队列中,队满时共有 n-1 个元素。 25. 对于栈只能在栈顶插入和删除元素; 对于队列只能在队尾插入和队首删除元素。 26. 一棵深度为 6 的满二叉树有 n 1 +n 2 =0+ n 2=n 0 -1=31 个分支结点和 2 6-1 =32 个叶子。 27. 有向图 G 用邻接表矩阵存储, 其第 i 行的所有元素之和等于顶点 i的出第 3页,共 5页度。 27. 用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。 29. n 个顶点 e 条边的图, 若采用邻接矩阵存储, 则空间复杂度为 O(n 2)。二、单项选择题 1. 线性表 L =( a1,a2,a3, …… ai, …… an) ,下列说法正确的是() A. 每个元素都有一个直接前件和直接后件 B. 线性表中至少要有一个元素 C. 表中诸元素的排列顺序必须是由小到大或由大到小 D. 除第一个和最后一个元素外,其余每个元素都有一个且只有一个直接前趋和直接后继(A) 2. 算法分析的两个主要方面是: A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性(A)3. 判定一个队列 QU (最多元素为 m0 )为满队列的条件是 A. QU->front == (QU->rear+1)% m0 B. QU->rear - QU->front -1== m0 C. QU->front == QU->rear D. QU->front == QU->rear+1 (B)4. 线性表L在情况下适用于使用链式结构实现。 A. 需经常修改L中的结点值 B. 需不断对L进行删除插入第 4页,共 5页 C. L中含有大量的结点 D. L中结点结构复杂 5. 从供选择的答案中, 选出应填入下面叙述? 内的最确切的解答, 把相应编号写在答卷的对应栏内。设有 4 个数据元素 a1、 a2、 a3和 a4 ,对他们分别进行栈操作或队操作。在进栈或进队操作时,按 a1、 a2、 a3、 a4 次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次,出栈一次,再进栈两次,出栈一次;这时,第一次出栈得到的元素是 A ,第二次出栈得到的元素是 B是;类似地,考虑对这四个数据元素进行的队操作是进队两次,出队一次,再进队两次, 出队一次; 这时, 第一次出队得到的元素是 C, 第二