《数据结构》试卷一 一、填空题：（共２０分） 1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。 2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 。 3、在一棵二叉树中，度为０的结点个数为 n0，度为２的个数为 n2，则 n0= 。 4、二叉树的前序遍历序列等同于该二叉树所对应森林的 遍历序列 5、对一棵二叉排序树，若以 遍历该树，将得到一个以关键字递增顺序排列的有序序列。 6、三个结点 a,b,c 组成二叉树，共有 种不同的结构。 7、在 AVL 树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用 型平衡旋转。 8、图的遍历有两种,它们是 。 9、堆排序的时间复杂度为 。 10、在含有 N 个结点的二叉链表中有 空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。 二、单项选择题（共２０分） １、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（ ） （A）２，４，１，３ （B）３，１，４，２ （C）３，４，１，２ （D）１，２，３，４ ２、有一棵非空的二叉树，（第０层为根结点），其第i 层上最多有多少个结点？（ ） （A） ２ i （B）２1i （C） ２1i （D） i ３、设电 文 中出现 的字母 为 A，B，C，D，E，每 个字母 在电 文 中出现 的次 数分别 为９ ，２７ ，３，５ ，１１，按 huffman 编 码 ，则字母 A 编 码 为（ ） （A） １０ （B） １１０ （C） １１１０ （D） １１１１ ４、下 面 关于数据 结构的叙 述 中，正 确 的叙 述 是（ ） （A）顺序存储方 式的优 点是存储密 度大 ，且插、删除运 算 效 率 高 （B）链表中每 个结点都 恰 好 包 含一个指 针 （C）包 含n 个结点的二叉排序树的最大 检 索长 度为 log2 n （D）将一棵树转为二叉树后 ，根结点无 右子树 ５ 、程 序段 ：y:＝ 0 while n>=(y+1)*(y+1) do y:=y+1 enddo 的时间复杂度为（ ） （A）O(n) （B）O(n 2 ) （C）O(n2/1) （D）O(1) 6、排序方法中,关键码比较的次数与记录的初始排列无关的是( ) (A) shell 排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序 7、数组q[0..n-1]作为一个环行队列,f 为...
