研究生入学考试《数据结构》候选题集(判断选择填空)参考答案.doc

《数据结构》候选题集及参考答案 一、判断题 线性表的逻辑顺序与物理顺序总是一致的。线性表的顺序存储表示优于链式存储表示。线性表的链式存储表示优于顺序存储表示。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。栈是一种线性结构。（ ）是一种线性结构。（ ）即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同（101，88，46，70，34，39，45，58，66，10）是堆将一棵树转换成二叉树后，根结点没有左子树将一棵树转换成二叉树后，根结点没有子树用树的前序遍历和中序遍历可以导出树的后序遍历用树的前序遍历和中序遍历可以导出树的后序遍历哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离较近。夫曼树一定是满二叉树。（ ）AVL树的任何子树都是AVL树。用邻矩阵图所用的存储空间大小与图的边数成正比。（ ）用邻矩阵图所用的存储空间大小与图的数成正比。（ ）用邻矩阵存储图时所需存储空间大小与图的结点数有关，而与边数无关算法的时间复杂度取决于??????.问题的规模.待处理数据的初态. Both A and B D. 没有确定的因素 若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用??_________?? 存储方式最节省运算时间。 （ D ） A. 单链表??? B. 双链表??? C. 单循环链表??? D. 顺序表 用单循环链表表示队列，正确的说法是???????A.可设一个头指针使入队、出队都方便可设一个尾指针使入队、出队都方便必须设头尾指针才能使入队、出队都方便无论如何只可能使入队方便?? ???。 （ B ） A. 不必事先估计存储空间????? B. 可随机访问任一元素 C. 插入删除不需要移动元素??? D. 所需空间与线性表长度成正比 设输入序列为1、2、3、4，则借助栈所得到的输出序列不可能是????。 （ D ） A. 1、2、3、4??????????????? B. 4、3、2、1 C. 1、3、4、2??????????????? D. 4、1、2、3 队列的操作原则是??????。 （ B ） A. 先进后出??? B. 先进先出??? C. 只能进行插入?? D. 只能进行删除 ?广义表A=（a,b,(c,d),(e,(f,g))）,则Head(Tail(Head(Tail(Tail(A)))))的值为??? 。 （ D ） ??? A．（g）??? B.(d)??? C.c??? D.d n 个结点的二叉链表中，非空的链域个数为??______???。 （ A ） A. n-1?? B. n??? C. n+1??? D. 不确定 若一棵二叉树具有10个度为2的结点，则该二叉树度为0的结点个数是???????A. 9 B. 11 C. 12 D. 不确定一个二叉树的前序序列为ABCDEFG，它的序序列可能是??。 （ B ）A. CABDEFG B. ABCDEFG C. DACEFBG D. EABCDFG ????? 的遍历仍需要栈的支持。前序线索树 .中序线索树 .后序线索树 下面关于图的存储的叙述中，正确的???? ???。 （ C ） A.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关用邻矩阵法存储图占用的存储空间数只与图中结点个数有关,而与边数无关 用邻矩阵法存储图占用的存储空间数只与图中边数有关,而与结点个数无关对无向图而言，同一条边在邻接表中用两个结点表示，而在邻接多重表中只用一个结点表示，故此邻接多重表所需存储量比邻接表???????A.少一半 多，但差异不大 少，但差异不大???? ??。 （ B ） A. O(n)??? B. O(n+e) ???C.? O(n*n)? ??D. O(n*e) 若一个有向图的邻接矩阵中主对角线以下的元素均为零则该图的拓扑有序序列???????A.存在.不存在平衡二叉树中，若某个结点在左、右子结点的平衡因子为零，则该的平衡因子是A. 0 B. 1 C. -1 D . A、B和C都有可能 折半查找法要求查找表中各元素的关键字必须是??????。