数据结构(李春葆)习题与解析.doc

《数据结构(李春葆)习题与解析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.数据结构（C语言篇）―习题与解析（修订版）清华大学一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题计算机的　　以及它们之间的　　和运算等的学科。　1　A.数据元素　B.计算方法　　C.逻辑存储　　D.数据映像　2　A.结构　　　B.关系　　　　C.运算　　　　D.算法2.数据结构被形式地定义为(K,R)，其中K是　　的有限集，R是K上的　　有限集。　1　A.算法　　　B.数据元素　　C.数据操作　　D.逻辑结构　2　A.操作　　　B.映像　　　　C.存储　　　　D.关系3.在数据结构中，从逻辑上可

2、以把数据结构分成　　　　。　A.动态结构和静态结构　　　　　　B.紧凑结构和非紧凑结构　　C.线性结构和非线性结构　　　　　D.部结构和外部结构4.线性结构的顺序存储结构是一种　A　的存储结构，线性表的链式存储结构是一种　B　的存储结构。　A.随机存取　　　B.顺序存取　　C.索引存取　　D.散列存取5.算法分析的目的是　C　，算法分析的两个主要方面是　AB　。　1　A.找出数据结构的合理性　　　B.研究算法中的输入和输出的关系..C.分析算法的效率以求改进　　D.分析算法的易懂性和文档性　2　A.空间复杂度和

3、时间复杂度　　B.正确性和简单性　　C.可读性和文档性　　　　　　D.数据复杂性和程序复杂性6.计算机算法指的是　C　，它必须具备输入、输出和　B　等　5个特性。　1　A.计算方法　　B.排序方法　　C.解决问题的有限运算序列　　D.调度方法　2　A.可执行性、可移植性和可扩充性　　　B.可行性、确定性和有穷性　　C.确定性、有穷性和稳定性　　　　　　D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法　　B　　。　　　A.正确　　　　　　B.不正确8线性表若采用链式存储结构时，要求存中

4、可用存储单元的地址　D　　。　　　A.必须连续的B.部分地址必须连续的　C.一定是不续的　D连续不连续都可以9.以下的叙述中，正确的是　　B　　。A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进后出D.队列的操作方式是..先进先出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法　　B　。A.正确　　　　　　B.不正确填空题1.数据逻辑结构包括三种类型线性结构　、树形结构　和　图形结构　　　　，树形结构和图形结构合称为　非线性结构　　　　。2.在线

5、性结构中，第一个结点　没有　　　前驱结点，其余每个结点有且只有　1　个前驱结点；最后一个结点　　没有　　后续结点，其余每个结点有且只有　　1　个后续结点。3.在树形结构中，树根结点没有　前驱　　　结点，其余每个结点有且只有　1　个前驱结点；叶子结点没有　　后续　结点，其余每个结点的后续可以　任意多个　　　。4.在图形结构中，每个结点的前驱结点数和后续结点数可以　任意多个　　　　。5.线性结构中元素之间存在　一对一　　　关系，树形结构中元素之间存在　一对多　　　关系，图形结构中元素之间存在　多对多　　　关系。6.

6、算法的五个重要特性是　　有穷性　　、　　确定性　　、　　可行性　　、　输入　　　、　输出　　　。7.下面程序段的时间复杂度是　O（m*n）　　　。..for(i=0;i

7、m=s;10.下面程序段的时间复杂度是　　O（log3n）　　。i=1;while(i<=n)i=i*3;二、线性表单项选择题..1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是　B　。　　A.110　　　B.108　　　C.100　　　D.1202.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是　　C　　　　　。　　A.edcba　　　B.decba　　C.dceab　　D.abcde3.若一个栈的入栈序列是1、2、3、…、n，其输出序列为p1、p2、p3、…、

8、pn，若p1=n，则pi为　　C　　　　。　A.i　　　B.n=iC.n-i+1　　　　D.不确定4.栈结构通常采用的两种存储结构是　　A　　　　。　　A.线性存储结构和链表存储结构　　　B.散列方式和索引方式　　C.链表存储结构和数组　　　　　　　D.线性存储结构和非线性存储结构5.判断一个栈ST(最多元素为m)为空的条件是　　B　　　　。　A.ST->top!=0　　B.ST->t