《数据结构》试卷六
一,填空题:(共20分)
1,在计算机中可使用一批连续的存储单元来存放数组,称为数组的顺序分配, 一般有两种存储方式:分别是 为主存储,
2,两栈合用空间,判栈满的条件为 .
3,ADT称为 .
4,线性表有两种存储结构,分别为 .
5,Head(Tail(Head(((a,b),(c,d))))= .
6,队列简称 结构,循环队列判队空条件为 .
7,如图:该树度为 ,树深度为 ,树的路径长度为 .
A
/ │\
B C D
/ \
E F
\
G
8,集合结构中的数据元素之间,除了 的联系之外,没有其他关系.
9,如果对于给定的一组权值,所构造出的二叉树的带权路径长度最小,则该树称为________.
10,设F是由T1,T2和T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2和T3的结点个数分别n1,n2和n3,则二叉树B的根结点的左子树和右子树中的结点个数分别为n1—1和 .
二,单项选择题:(共20分)
1,若进栈序列为1,2,3,4,假定进栈和出栈可以穿插进行,则可能的出栈序列是-----( )
(A)2,4,1,3 (B)3,1,4,2
(C)3,4,1,2 (D)1,2,3,4
2,有一棵非空的二叉树,(第0层为根结点),其第i层上最多有多少个结点
-----------------( )
(A) 2 (B)2 (C) 2 (D) i
3,设电文中出现的字母为A,B,C,D,E,每个字母在电文中出现的次数分别为9,27,3,5,11,按huffman编码,则字母E编码为------( )
(A) 10 (B) 110 (C) 1110 (D) 1111
4,下面关于数据结构的叙述中,正确的叙述是-------( )
(A)顺序存储方式的优点是存储密度大,且插,删除运算效率高
(B)链表中每个结点都恰好包含一个指针
(C)包含n个结点的二叉排序树的最大检索长度为log-2n
(D)将一棵树转为二叉树后,根结点无右子树
5,程序段FOR I:=N-1 DOWNTO 1 DO
FOR J:=1 TO I DO
IF A[J]>A[J+1] THEN
A[J]与A[J+1] 对换;
其中n为正整数,则最后一行的语句频度在最坏情况下是( )
(A) O(n) (B) O(nlogn) (C) O(n) (D) O(n)
6,某二叉树的前序遍历结点访问顺序为A B C D E F G,中序遍历结点访问顺序为C B D A F G E,则其后序遍历结点访问顺序为----------------( )

下一页