《数据结构》期中测试答案

char *p=\"It is mine\";

数据结构2010年下学期 则以下不正确的叙述是________.d

a)a+1表示的是字符t的地址 考试时间：100分钟 考试形式：闭卷

（所有答案写在答题纸上，请在答题纸上注明班级、学号） b)p指向另外的字符串时，字符串的长度不受限制

一、概念题（每题 2 分，共 24分） c)p变量中存放的地址值可以改变

1、从逻辑角度看，数据可归结为四类基本结构：集合、线性结构、 树状结构 d)a中只能存放10个字符 和 图状结构 。 2、算法效率度量分析的两个基本指标是 时间复杂度 和 空间复杂度 。前者是基于算法执行时间的度量，后者是基于算法所需存储空间的度量。 3、线性表顺序存储的特点是：表中相邻的元素ai和ai+1所对应的存储地址 LOC（ai）和LOC(ai+1)也是____相邻_____的。设线性表a的起始地址为LOC(a1)，每个数组元素所占用的存储单元数为b，则表中第i(1≤i≤n)个元素ai的存储起始地址LOC(ai)可用如下公式得到__ LOC(ai)_ = LOC(a1)+(i-1)*b ______。 4、在线性表的存储结构中，顺序表是一个可 随机存取 存取的存储结构，单链表则是一个 顺序存取 存取的存储结构。 5、设单链表的结点数据类型定义和指针变量说明如下 #define DATATYPE2 char typedef struct node { DATATYPE2 data; struct node *next; } LINKLIST; LINKLIST *p,*q,*s; 在一个单链表中，已知q所指向结点是p所指向结点的直接前趋结点。若欲在q结点和p结点之间插入一个s所指向的结点，则可写 q->next=s;s->next=p 6、关于选用顺序表结构或链表结构，在考虑线性表的操作的时间性能时，若线性表上的操作主要是查找、读取而很少做插入和删除操作时，以采用 顺序 表结构为宜。但是，若线性表需频繁地进行插入和删除操作时，则采用 链表 表结构为宜。 7、如果在待排序的序列中，存在有多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是 稳定 的；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是 不稳定 的。 二、选择题（每题3分，共21分） 1．若有说明;int *p,m=5,n;以下正确的程序段的是________.d a)p=&n; b)p=&n; scanf(\"%d\ c)scanf(\"%d\ *p=n; *p=m; 2．若有说明语句 char a[]=\"It is mine\"; 3．若有以下定义，则对a数组元素的正确引用是_________.d int a[5],*p=a; a)*&a[5] b)a+2 c)*(p+5) d)*(a+2)

4．设有如下定义： struct sk {int n; float x;

}data ; int *p;

若要使p指向data中的n域，正确的赋值语句是_______.c a)p=&data.n; b)*p=data.n; c)p=(struct sk *)&data.n;

d)p=(struct sk *)data.n; 5．下面对typedef的叙述中不正确的是______.b a)用typedef可以定义各种类型名，但不能用来定义变量 b)用typedef可以增加新类型 c)用typedef只是将已存在的类型用一个新的标识符来代表

d)使用typedef有利于程序的通用和移植 typedef可以定义各种类型名，但是不能用来定义变量； typedef只是对已经存在的类型增加一个类型名，没有创造新的类型； typedef和#define虽然能起到类似的作用，但是两者不同，

＃define属于预编译处理，typedef采用定义变量的方法定义一个类型； 当不同的源文件中使用同一类型数据时，常常吧它们单独存放在一个文件中，然后在需要用到它们的时候，在文件中用＃include命令包含进来； 使用typedef有益于程序的通用性和移植。

6．C语言结构体类型变量在程序执行期间_________.a a)所有成员一直驻留在内存中 b)只有一个成员驻留在内存中 c)部分成员驻留在内存中 d)没有成员驻留在内存中 7．下面程序段的运行结果是________.d 输出的是一个地址 char *s=\"abcde\";

s+=2;printf(\"%d\

a)cde b)字符'c' c)字符'c'的地址 d)无确定的输出结果

情况1：char *s=\"abcde\";

s+=2; printf(\"%c\运行结果是：c

原因：指针本来是指向字符串的首地址a的，+2后指向c，故输出:c 情况2：

char *s=\"abcde\"; s+=2;

printf(\"%d\输出结果：99

原因：指向c,但是要输出整形，故读取c所占字节内容，c的ascII码为99，故即输出：99

（由于前面定义的指针s为字符型的，故即便是整形输出，也只读一个字节的内存）

三、简答题（25分）

1、下面程序的运行结果是_____6______.（4分） main() {

struct cmplx{int x; int y;

}cnum[2]={1,3,2,7};

printf(\"%d\\n\}

2、 时间复杂度的分析 （12分）

1）for (i=0;ifor (j=0;js+=i; }

3）s=0; 4）i=1;

for (i=0;i（1）答案：1、答案：O（M*N）

(2)答案：O(1n2)

(3)o(n2

) (4)O(log3n)

3、给出一组关键字（19，01，26，92，87，11，43，87，21）进行冒泡排序，试列出每一趟排序后关键字的排列次序，并比较每遍排序所进行的关键字比较次数。（9分）

答案：

01,19,26,87,11,43,87,21,92 01,19,26,11,43,87,21,87,92 01,19,11,26,43,21,87,87,92 01,11,19,26,21,43,87,87,92 01,11,19,21,26,43,87,87,92

四、算法设计题（每题10分，共20分）

1、编写函数定义，实现：从键盘上输入一个字符序列（以字符’$’作为输入结 束标志），按尾插入法建立带头结点的循环单链表head。单链表的结点数据类型参见概念题第6题。

LINKLIST *create_lklist() { DATATYPE2 x;

LINKLIST *head,*last,*t;

t=(LINKLIST *)malloc(sizeof(LINKLIST)); head=t;last=t;t->next=t;

printf(”Enter a string, ’$’ to stop:”); while (( （1）x=getchar() )!= ’$’); { t=(LINKLIST *)malloc(sizeof(LINKLIST));

t->data= （2）x ;

last->next= （3）t ;last=t; }

last->next=head;

return ( （4）head ); }

在main主函数体中，设说明 LINKLIST *head;

为使head指向所建立循环单链表的头结点，应写如下赋制值语句 （5）head=create_lklist()

2、设待排序记录的数据类型描述如下 #define MAXSIZE 100

#define KEYTYPE int typedef struct

{

KEYTYPE key;

/* otherdata……; */

} RECNODE;

下述函数定义实现：n个记录的简单选择排序。设待排序前的诸记录存放在r[0]到r[n-1]中。按记录键值递升（或不降）顺序进行排序。

void selectsort(RECNODE *r,int n) { int i,j,k; RECNODE temp;

for (i=0;i< （1） n ;i++) {

k=i;

for (j= （2）K+1 ;jif (r[j].key （3） < r[k].key) k=j;

if ( （4） r[i].key==r[k].key ) {

temp=r[i];

（5） r[i]=r[k] ; r[k]=temp; } } }

五、程序设计题（13分）

1、试用C语言编写一个高效算法，将一单链表就地逆置（只写核心语句即可）。（5分）操作前：（a1, a2, …, ai-1,ai, ai+1,…,an） 操作后：（an, …, ai+1,ai, ai-1,…, a2, a1） Void reverse(LinkList L) {

LNode *p,*q; P=L->next; L->next=NULL; While(p) {

q=p;p=p->next; q->next=L->next; L->next=q;

}

}

2、已知L是无表头结点的单链表，且*p节点既不是首结点，也不是尾结点，试完成以下操作：（写关键语句）（8分） （1）在*p结点后插入*s结点 （2）在*p结点前插入*s结点 （3）在表头插入*s结点 （4）在表尾插入*s结点

见书后第三章链表课后习题p40第五小题