数据结构复习新讲述.doc

数据结构复习 一、选择题。 1、以下数据结构中，是非线性数据结构的是( )。 A、树 B、字符串 C、数组 D、栈 2、下列时间复杂度中最的是 ( ) 。A、O(1) B、O(n) C、O(log2n) D、O(n2) 3、线性表中有一个直接前驱一个直接后继 ( )。A、中间元素 B、尾元素C、首元素D、所有的元素 ） A、线性表采用顺序存储必须占用一片连续的存储空间。 B、线性表采用链式存储不必占用一片连续的存储空间。 C、线性表采用链式存储便于插入和删除操作的实现。 D、线性表采用顺序存储便于插入和删除操作的实现。 5、以下关于链式存储结构的叙述中，( )是不正确的。 A、结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B、逻辑上相邻的结点物理上不必邻接 C、可以通过计算直接确定第i个结点的存储地址 D、插入、删除操作方便，不必移动结点 6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定 7、栈是限定在进行插入或删除操作的线性表A、端点 B、栈顶 C、栈底 D、中间 8、某堆栈为,2,3,4，不可能是它的序列（　 ）。A、1,3,2,4 B、?2,3,4,1 C、3,4,2,1 D、4,3,1,2 9、串的长度是（ ）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数且大于0 D、串中所含字符的个数 9、具有10个叶结点的二叉树中有（ ）个度为2的结点。 A．8 B．9 C．10 D．ll 11、串是一种特殊的线性表，其特殊性体现在（ ） A、可以顺序存储 B、数据元素是一个字符 C、可以链式存储 D、数据元素可以是多个字符 12、设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。 A、99 B、100 C、101 D、102 13、 有关二叉树下列说法正确的是（ ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 14、栈的插入和删除操作在（ ）进行。 A、端点 B、栈顶 C、栈底 D、栈中 15、将含有21个结点的完全二叉树从根结点开始编号,根为1号,后面按上到下，从左到右的顺序对结点的编号,那么编号为11的双亲结点编号为( )。 A、5 B、6 C、7 D、8 16、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 17、树的表示法很多，下面哪一个不是树的表示法的是（ ） A、广义表 B、文氏图 C、集合 D、凹入法 18、设完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、(n-1)/2 19、若二叉树上只有度为和的结点且度为的结点数为h,则该二叉树的结点数为A、2h-1 B、h C、2h D、h+1 20、深度为的二叉树至多有个结点A、31 B、32 C、63 D、64 21、下面几个符号串编码集合中，不是前缀编码的是（ ）。 A．{0,10,110,1