数据结构期末复习题答案数据结构期末复习题答案.doc

《数据结构》复习题 （含部分参考答案版） 单项选择题 1. 按照数据逻辑结构的不同，可以将数据结构分成 C 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 2. 下列关于数据结构的叙述中正确的是 A 。 A. 数组是同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为复杂 C. 树是一种线性的数据结构 D. 用一维数组存储二叉树，总是以先序顺序遍历各结点 3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为 B A.逻辑结构 B.顺序存储结构 C.链式存储结构 D.以上都不对 4. 以下关于算法特性的描述中， B 是正确的。 （1）算法至少有一个输入和一个输出 （2）算法至少有一个输出但是可以没有输入 （3）算法可以永远运行下去 A. （1） B. （2） C. （3） D. （2）和（3） 5. 对顺序存储的线性表（a1,a2,…,an）进行插入操作的时间复杂度是 C 。 A.O(n) B. O(n-i) C. (n/2) D. O(n-1) 6. 链表不具有的特点是 A 。 A.可随机访问任一元素 B.插入和删除时不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性表的长度成正比 7.线性链表中各链结点之间的地址 C 。 A.必须连续 B.部分地址必须连续 C.不一定连续 D.连续与否无关 8. 以下关于链式存储结构的叙述中， C 是不正确的。 A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B.逻辑上相邻的结点物理上不必邻接 C.可以通过计算直接确定第i个结点的存储地址 D.插入、删除操作方便，不必移动结点 9. 设依次进入一个栈的元素序列为d, a, c, b,得不到出栈的元素序列为 D 。 A. dcba B. acdb C. abcd D. cbda 10. 将新元素插入到链式队列中时，新元素只能插入到 B 。 A. 链头 B. 链尾 C. 链中 D. 第i个位置，i大于等于1，大于等于表长加1 11. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、和e1，则栈S容量至少应该是 C 。 A. 6 B. 4 C. 3 D. 2 12.下面 D 是‘abcd321ABCD’的子串。 A. abcd B. 321ab C. ‘abc ABC’ D. ‘21AB’ 13.假设8行10列的二维数组A[1…8，1…10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3，5]的地址与以列序为主序时 C 元素相同。 A. a[7，3] B. a[8，3] C. a[1，4] D. ABC都不对 14. 数组A[0…5，0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址为 A 。 A. 1175 B. 1180 C. 1205 D.1210 15.下列广义表中，长度为3的广义表为 B 。 A.（a,b,c,( )） B. ((g),(a,b,c,d,f),( )) C. (a,(b,(d))) D. ((( ))) 16. 以下关于广义表的叙述中，正确的是 A 。 A. 广义表是0个或多个单元素或子表组成的有限序列 B. 广义表至少有一个元素是子表 C. 广义表不可以是自身的子表 D. 广义表不能为空表