数据结构复习题2

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

1、一、选择题（1）数据结构通常是研究数据的（A）及它们之间的相互联系。A.存储结构和逻辑结构B.存储和抽象C.联系和抽象D.联系与逻辑（2）在逻辑上可以把数据结构分成：（C）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构（3）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结（4）算法分析的两个主要方面是（A）。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性（5）下列时间复杂度中最坏的是（D）。A.O（1）B.

2、O（n）C.O（log2n）D.O（n2）（6）等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（C）。A．nB．(n-1)/2C．n/2D．(n+1)/2（7）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为(D)A．1234B．1243C．1324D．1423（8）如果以链表作为栈的存储结构，则出栈操作时（B）A．必须判别栈是否满B．必须判别栈是否空C．必须判别栈元素类型D．队栈可不做任何判别（9）链栈与顺序栈相比，有一个比较明显的优点是（B）。A．插入操作更加方便B．通常不会出现栈满的情况。C．不会出现栈空的

3、情况D．删除操作根加方便（10）插入和删除只能在一端进行的线性表，称为(C)。A．队列B．循环队列C．栈D．循环栈（11）若进队的序列为：A，B，C，D，则出队的序列是（C）。A．B，C，D，AB．A，C，B，DC．A，B，C，DD．C，B，D，A（12）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为(B)。A．5和1B．4和2C．2和4D．1和5（13）S="morning"，执行求子串函数SubStr(S,2,2)后的结果为(B)。A．"mo"B．"or"C．"in"

4、D．"ng"（14）S1="good"，S2="morning"，执行串连接函数ConcatStr(S1,S2)后的结果为(A)。A．"goodmorning"B．"goodmorning"C．"GOODMORNING"D．"GOODMORNING"（15）S1="good"，S2="morning"，执行函数SubStr(S2,4,LenStr(S1))后的结果为(B)。A．"good"B．"ning"C．"go"D．"morn"（16）设串S1="ABCDEFG"，S2="PQRST",则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1

5、,LenStr(S2),2))的结果串为(D)。A．BCDEFB．BCDEFGC．BCPQRSTD.BCDEFEF(17)已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（B）。A．872B．860C．868D．864（18）在一棵具有五层的满二叉树中，结点的总数为（B）A．16B．31C．32D．33（19）具有64个结点的完全二叉树的深度为（C）A．5B．6C．7（20）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（D）。A．2iB．2i+1C．2i

6、-1D．不存在（若2i<=n，则答案为A）（21）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（B）。A．46B．47C．90D．91（22）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（B）。A．98B．99C．50D．100（23）用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是（B）。Ａ．32Ｂ．33Ｃ．34Ｄ．15（先构造哈夫曼树，WPL=（1+2）*3+（3+4+5）*2=33）（24）二叉树的叶结点个数比度为2

7、的结点的个数（C）。A．无关B．相等C．多一个D．少一个（25）对于一个具有n个顶点的有向图的边数最多有（B）。A．nB．n(n-1)C．n(n-1)/2D．2n（26）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。A．nB．n+1C．n-1D．n/2（27）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（C）。A．n-1B．n+1C．nD．n+e（28）在图的表示法中，表示形式唯一的是（A）。A．邻接矩阵表示法B．邻接表表示法C．逆邻接表表示法D．