一、单项选择题.docVIP

数据结构复习题 2004年6月 一、单项选择题 1．链栈和顺序栈相比，有一个较明显的优点是( )。 A.通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C.插入操作更加方便 C.删除操作更加方便 2．若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ） 方法比较次数最少。 A．直接插入排序 B．分划交换排序 C．归并排序 D．直接选择排序 3．深度为n的二叉树中所含叶子结点的个数最多为（ ）个。 A.2n B.n C.2n-1 D.2n-1 4．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。 A.1/2 B. 1 C.2 D.4 5．按照二叉树的定义,具有3个结点的二叉树有( )种。 A. 3 B. 4 C. 5 D. 6 6．栈和队列都是（ ）。 A.顺序存储的线性表 B.链式存储的线性表 C.限制存取点的线性结构 D.限制存取点的非线性结构 7．串是（ ）。 A.一些符号构成的序列 B.一些字母构成的序列 C.一个以上字符构成的序列 D.任意有限个字符构成的序列 8．在一个具有n个顶点的无向图中,要连通全部顶点至少需要( )条边。 A.n B.n+1 C.n-1 D.n/2 9．对有n个记录的有序表采用二分查找，其平均查找长度的量级为（ ）。 A. O(log2n) B. O(nlog2n) C. O(n) D.O(n2) 10．在一个单链表中，若删除(*p)结点的后继结点，则执行( )。 A．p-next=p-next-next ; B．p=p-next; p-next=p-next-next ; C．p-next=p-next ; D．p =p-next-next ; 11．邻接表的存储结构下图的深度优先遍历类似于二叉树的( )。 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 12．某二叉树的前序和后序序列正好相反，则该二叉树一定是( )二叉树。 A．空或只有一个结点 B．高度等于其结点数 C．任意结点无左孩子 D．任意结点无右孩子 13．设输入序列为1,2,3,4,5，借助一个栈可以得到的输出序列是( )。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 14．稀疏矩阵一般采用( )方法压缩存储。A.三维数组 B.单链表 C.三元组表 D.散列表15．二维数组A[5][6]的每个元素占5个单元，将其按行优先顺序存储在起始 地址为1000的连续的内存单元中，则元素A[4][5]的存储地址为（ ）。 A．1140 B．1145 C．1120 D．1125 16.具有n个顶点的有向图最多可包含( )条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1) 17.用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执 行的时间杂度为( )。 A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2) 18.下面4个序列中，只有（ ）满足堆的定义。 A. 13,27,49,76,76,38,85,97 B. 76,38,27,49,76,85,13,97 C. 13,76,49,76,27,38,85,97 D. 13,27,38,76,49,85,76,97 19.对稀疏矩阵进行压缩存储是为了（ ）。 A. 便于进行矩阵运算 B. 便于输入和输出 C. 节省存储空间 D. 降低运算的时间复杂度 20.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单 从运行时间来看，通常递归过程比非递归过程（ ）。 A．较快 B．较慢 C．相同 D．不确定 二、填空题 1．在双链表中每个结点有两个指针域，一个指向________，另一个指向__________。 2．对于顺序存储的栈