《数据结构》期末复习题2011

《《数据结构》期末复习题2011》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》期末复习题一、单选题1．某程序的时间复杂度为（3n+nlog2n+n2+8）,其数量级表示为（C）。A．O（n）B．O（nlog2n）C．O（n2）D．O（log2n）2．队列的插入操作是在（B）进行。A．队首B．队尾C．队前D．对后3．二叉树上叶结点数等于（C）。A．分支结点数加1B．单分支结点数加1C．双分支结点数加1D．双分支结点数减14．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（A）排序A．插入B．交换C．选择D．归并5．在一个图中，所有顶点的度数之和等于所有边数的（A）倍。A．2B．1C．3D．46．

2、队列的删除操作是在（A）进行。A．队首B．队尾C．队前D．对后7．当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则退栈时，用（A）语句修改top指针。A．top++;B．top=0;C．top--;D．top=N;8．由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（A）。A．51B．23C．53D．749．在一棵二叉树中，第4层上的结点数最多为（B）。A．31B．8C．15D．1610．向堆中插入一个元素的时间复杂度为（A）。A．O(log2n)B．O(n)C．O(1)D．16O(nlog2n)11．在一个

3、长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（B）个元素。A．n-iB．n-i+1C．n-i-1D．i12．在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（A）。A．n/mB．m/nC．n/(n+m)D．m/(n+m)13．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（）。A．原树高度加1B．原树高度减1C．原树高度D．不确定14．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（B）。A．行号B．列号C．元

4、素值D．地址15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（C）条边。A．nB．2nC．n-1D．n+116．某程序的时间复杂度为（10n+nlog2n+n2）,其数量级表示为（C）。A．O（n）B．O（nlog2n）C．O（n2）D．O（log2n）17．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（）个元素。A．n-iB．n-i+1C．n-i-1D．i18．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定（A）该结点的值。A．小于B．大于C．不小于D．大于等于19．

5、对于一棵具有n个结点的树，该树中所有结点的度数之和为（A）。A．n-1B．nC．n+1D．2n20．某程序的时间复杂度为（3n+100×log2n+nlog2n）,其数量级表示为（）。A．O（n）B．O（nlog2n）C．O（100）D．O（log2n）21.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，822．根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（D）。A．O(n)B．O(log2n)C．O(n

6、2)D．O(nlog2n)23.按照数据逻辑结构的不同，可以将数据结构分成C。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构24.下列关于数据结构的叙述中正确的是A。A.数组是同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为复杂C.树是一种线性的数据结构D.用一维数组存储二叉树，总是以先序顺序遍历各结点25.在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为BA.逻辑结构B.顺序存储结构C.链式存储结构D.以上都不对26.以下关于算法特性的描述中，B是正确的。（1）算法至少有一个输

7、入和一个输出（2）算法至少有一个输出但是可以没有输入（3）算法可以永远运行下去A.（1）B.（2）C.（3）D.（2）和（3）27.对顺序存储的线性表（a1,a2,…,an）进行插入操作的时间复杂度是C。A.O(n)B.O(n-i)C.(n/2)D.O(n-1)28.链表不具有的特点是A。A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度成正比29.线性链表中各链结点之间的地址C。A.必须连续B.部分地址必须连续C.不一定连续D.连续与否无关30.以下关于链式存储结构的叙述中，C是不正确的。A.结点除自身

8、信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结