华东交大数据结构自测卷及答案.doc

《华东交大数据结构自测卷及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论一、填空题1.算法的计算量的大小称为计算的（B）。A．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（C）A．问题的规模B.待处理数据的初态C.A和B3.计算机算法指的是（C），它必须具备（B）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4．从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构5

2、．以下与数据的存储结构无关的术语是（D）。A．循环队列B.链表C.哈希表D.栈6．以下数据结构中，哪一个不是线性结构（B）？A．广义表B.二叉树C.稀疏矩阵D.串7．以下那一个术语与数据的存储结构无关？（A）A．栈B.哈希表C.线索树D.双向链表8．在下面的程序段中，对x的赋值语句的频度为（C）FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)9．程序段FORi:=n-1DOWNTO1DOFORj:=1TOiDOIFA[j]>A[j+1]THENA[j]与A[j+1]对换

3、；其中n为正整数，则最后一行的语句频度在最坏情况下是（D）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)10．以下哪个数据结构不是多型数据类型（D）A．栈B．广义表C．有向图D．字符串11．以下数据结构中，（A）是非线性数据结构A．树B．字符串C．队D．栈12.下列数据中，（C）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆13．连续存储设计时，存储单元的地址（A）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续14．以下属于逻辑结构的是（C）。A．顺序表B.哈希表C.有序表D.单链表二、判断题1.数据元

4、素是数据的最小单位。(F)2.记录是数据处理的最小单位。(T)283.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(F)4．算法的优劣与算法描述语言无关，但与所用计算机有关。(F)5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(T)6．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(T)7．程序一定是算法。(T)8．数据的物理结构是指数据在计算机内的实际存储形式。(T)9.数据结构的抽象操作的定义与具体实现有关。(F)10.在顺序存储结构中，有时也存储数据结构中元素之间的关系。

5、(F)11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(F)12.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(T)13.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(F)三、填空1．数据的物理结构包括数据元素的表示和数据关系的表示。2.对于给定的n个元素,可以构造出的逻辑结构有集合，线性，树，__图（网）_四种。3．数据的逻辑结构是指数据元素之间的逻辑关系。4．一个数据结构在计算机中表示称为存储结构。5．抽象数据类型的定义仅取决于它的一组__逻辑特性_，而与_其在计算机内部如

6、何表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。6．数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度7.数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作_，设计出相应的算法_。8．一个算法具有5个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出。9．已知如下程序段for(i=n;i>=1;i--){语句1}{x=x+1；{语句2}for(j=n;j>i;j--){语句3}y=y+1;{语句4}}；语句1执行的频度为n+1；

7、语句2执行的频度为n；语句3执行的频度为n（n+1）/2；语句4执行的频度为(n-1)n/2。10．在下面的程序段中，对ｘ的赋值语句的频度为(n3+3n2+2n)/6_____（表示为n的函数）for(i=1;i<=n;i++)　　for(j=1;j<=i;j++)　for(k=1;k<=j;k++)ｘ：＝ｘ＋delta；11.下面程序段中带下划线的语句的执行次数的数量级是：log2ni=1;while(i

8、=n;j++)x=x+1;i=i*2}2813.下面程序段中带有下划线的语句的执行次数的数量级是(log2n)i=n*nwhile(i!=1)i=i/2;14.计算