《数据结构》期中测试

《《数据结构》期中测试》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构2010年上学期考试时间：100分钟考试形式：闭卷（所有答案写在答题纸上，请在答题纸上注明班级、学号）一、概念题（每题2分，共24分）1、从逻辑角度看，数据可归结为四类基本结构：集合、线性结构、和O齐法效率度量分析的两个基本指标是和O前者是基于算法执行时间的度量，后者是基于算法所需存储空间的度量。3、线性表顺序存储的特点是：表中相邻的元素a：和如所对应的存储地址L0C（弘）和LOC（a1+I）也是的。设线性表a的起始地址为L0C（a.）,每个数组元素所占用的存储单元数为b,则表中第i（lWiWn）个元素&的存储起始地址L0CQ）可用如下公式得到o4、在线性表

2、的存储结构屮，顺序表是一个可存取的存储结构，单链表则是一个存取的存储结构。5、设单链表的结点数据类型定义和指针变量说明如下ftdefineDATATYPE2chartypedefstructnode{DATATYPE2data;structnode*next;}LINKLIST;LINKLIST*p,*q,*s;在一个单链表屮，已知q所指向结点是p所指向结点的直接前趋结点。若欲在q结点和P结点之间插入一个s所指向的结点，则可写6、关于选用顺序表结构或链表结构，在考虑线性表的操作的时间性能时，若线性表上的操作主要是查找、读取而很少做插入和删除操作时，以采用表结构为宜。

3、但是，若线性表需频繁地进行插入和删除操作时，则采用表结构为宜。7、如果在待排序的序列中，存在有多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是的；反之，若具有相同关键字的记录Z间的相对次序发生变化，则称这种排序方法是的。二、选择题（每题2分，共21分）1.若有说明；int*p,iii=5,n;以下正确的程序段的是・a）p二&n;b）p二&n;scanf（"%d〃，&p）;scanf（"%d〃，*p）;c）scanf（"%d〃，&n）;d）p二&n;*p=n;*p二m;2.若有说明语句chara[]=，zItismi

4、ne";char*p=〃Itismine";则以下不正确的叙述是•小屮1表示的是字符t的地址b)p指向另外的字符串时，字符串的长度不受限制c)p变量屮存放的地址值可以改变d)a中只能存放10个字符1.若有以下定义，则对a数组元素的正确引用是・inta[5],*p二a;a)*&a[5]b)a+2c)*(p+5)d)*(a+2)2.设有如下定义:structsk{intn;floatx;}data,*p;若要使P指向data中的n域，正确的赋值语句是・a)p二&chta.n;b)*p=data.n;c)p=(struetsk*)&data.n;d)p=(structsk

5、*)data,n;3.下面对typedef的叙述中不正确的是.a)用typedef可以定义各种类型名，但不能用来定义变量b)用typedef可以增加新类型c)用typedef只是将已存在的类型用一个新的标识符来代表d)使用typedef有利于程序的通用和移植4.C语言结构体类型变量在程序执行期间・a)所有成员一直驻留在内存中b)只有一个成员驻留在内存中c)部分成员驻留在内存中d)没有成员驻留在内存屮5.下而程序段的运行结果是.char*s=〃abcdc〃；s+二2;printf(〃％d〃，s);a)cdeb)字符'c，c)字符'c，的地址d)无确定的输出结果三、简答

6、题(25分)1、下面程序的运行结果是・(4分)main(){structcmplx{intx;inty;}cnum[2]={l,3,2,7};printf(〃%d〃,cnum[0].y/cnum[0].x*cnum[l].x);2、时间复杂度的分析(12分)1)for(i二0;i〈n;i++)2)i二s二0;for(j=0;j

7、出一组关键字(19,01,26,92,87,11,43,87,21)进行冒泡排序，试列岀每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。(9分)四、算法设计题(每题10分，共20分)1、编写函数定义，实现：从键盘上输入一个字符序列(以字符^作为输入结束标志)，按尾插入法建立带头结点的循环单链表head。单链表的结点数据类型参见概念题第6题。LINKLIST*create_lklist(){DATATYPE2x;LINKLIST*head,*last,*t;t=(LINKLIST*)malloc(sizeof(LINKLIST));head二t