数据结构习题与解析.pdf

第 1-3 章习题 一、选择题 1.若进栈序列为 a，b，c，d，进栈过程中可以出栈，则 不可能是一个出栈序列。 A) a,d,c,b B) b,c,d,a C) c,a,d,b D) c,d,b,a 6.设用一维数组 A[1,…,n]来存储一个栈，令 A[n]为栈底，用整型变量 T 指示当前栈顶 位置，A[T]为栈顶元素。当从栈中弹 出一个元素时，变量 T 将变化为 。 A) T=T + 1 B) T=T – 1 C) T 不变 D) T= n 7. 一个栈的入栈序列为 a，b，c，d，e,则栈不可能的出栈序列是 。 A) e d c b a B) d e c b a C) d c e a b D) a b c d e 8.若语句 S 的执行时间为 O(1),那么下列程序段的时间复杂度为 。 For(i = 0; i = n ; i++) For(j = 0; j =n ;j++) s A) O(n) B) O(n*n) C) O(n*log2n) D) O(n*i) 18.设计一个判断表达式中左右括号是否配对的算法，采用 数据结构最佳。 A) 队列 B) 堆栈 C) 二叉树 D) 链表 24.一个队列的入队序列是 1，2，3，4，则队列的输出序列是 。 A) 1，4，3，2 B) 4，3，2，1 C) 1，2，3，4 D) 3， 2，4，1 29.在一个单链表中，若要删除 P 结点的后续结点，则应执行 。 A) P-next = P-next-next B) p = P-next; P-next = P-next-next C) delete(P-next) D) p = P-next-next 30.在计算递归函数时，如不使用递归过程，则一般情况下必须借助于 数据结构。 A) 栈 B) 树 C) 双向队列 D) 广义表   1 41.下列叙述中，正确的是 。 A) 用指针的方式存储一棵有 n 个结点的二叉树最少需要 n+1 个指针 B) 不使用递归，也可以实现二叉树的前序、中序和后序遍历 C) 已知树的前序遍历并不能唯一确定一棵树，因为不知道树的根结点是哪一个 D) 任一棵树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查 找时间 50.以下有关数据结构的叙述，正确的是 。 A) 线性表的线性存储结构优于链式存储结构 B) 二叉树的第 i 层上有 2i-1 个结点，深度为 k 的二叉树上有 2k-1 个结点 C) 二维数组是其数据元素为线性表的线性表 D) 栈的操作方式是先进先 出 52.在一个单链表中，若要在指针 P 所指向的结点之后插入结点 q，应执行的操作 是 。 A)