2018年秋江南大学现代远程教育第一阶段练习题
考试科目:《数据结构》第一章至第四章(总分100分)
一、选择题(每题3分,共30分)
1、()是数据的不可分割的最小单位。
A、数据元素B、数据对象C、数据项D、数据结构
2、若采用顺序映象,则数据元素在内存中占用的存储空间()。
A、一定连续B、一定不连续C、可连续可不连续
3、下列说法中错误的是()。
A、栈是一种非线性结构
B、一个数据元素由一或多个数据项构成
C、在顺序存储结构中,结点间的逻辑关系由存储单元的邻接关系来体现
D、语句的频度就是语句的执行次数
4、以下属单链表优点的是()。
A、顺序存取B、插入操作能在O(1)的时间复杂度上完成
C、插入时不需移动数据元素D、节省存储空间
5、顺序表中数据元素的存取方式为()。
A、随机存取B、顺序存取C、索引存取D、连续存取
6、设输入序列为ABC,输出序列为CBA,则经过的栈操作为()。
A、push,pop,push,pop,push,pop B、push,push,push,pop,pop,pop
C、push,push,pop,pop,push,pop D、push,pop,push,push,pop,pop
7、若用一个大小为6的数组来实现循环队列,且当前队尾指针rear和队头指针front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为()。
A、1和5 B、2和4C、4和2 D、5和1
8、串是一种特殊的线性表,其特殊性体现在()。
A、可以顺序存储B、数据元素是一个字符
C、可以链接存储D、数据元素可以是多个字符
9、设串s='abcdefgh',则其子串数为()。
A、8 B、37C、36 D、9
10、设串s1='abcdefg',s2='ab',则Concat(s1,s2)的返回值()。
A、ab B、cdefg C、abcdefg D、abcdefgab
二、(10分)设n为正整数,则在下面的程序段中,语句“a+=2;”的频度为多少?
for(x=0;x<n;++x)
for(y=0;y<n;++y)
a+=2;
答:n2 ( n的平方)
三、(15分)设单链表L带头结点且非空,指针变量p指向L中的一个结点,且该结点既不是L中的第一个结点,也不是L中的最后一个结点,指针变量s指向一个待插入L的新结点。
试写出能完成下列操作的语句序列。
⑴在p所指结点之前插入s所指结点;
⑵在L中最后一个结点之后插入s所指结点;
⑶删除p所指结点的直接后继;
⑷删除L中第一个结点。
⑴在p 所指结点之前插入s 所指结点;q = L; while(q->next !=p) q=q->next; //q 指向p 的直接前驱s->next = p; q->next = s; ⑵在L 中最后一个结点之后插入s 所指结点;q = L; while(q->next != null ) q=q->next; s->next =NULL; q->next =s; ⑶删除p 所指结点的直接后继;q = p->next; .//q 指向待删结点p->next = q->next; free(q);
⑷删除L 中第一个结点。
q = L->next; L->next = q->next; free(q);
四、(10分)有5个元素,其入栈次序为:A,B,C,D,E,在各种可能的出栈次序中,以元素C,D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?
答:CDEBA CDBEA CDBAE
五、(15分)设a='colomn',b='How are you!',c='please',试求:
⑴ StrLength(b)的返回值;
⑵ Index(a,'o',5)的返回值;
⑶执行StrInsert(a,3,c)后串a的值;
⑷执行Replace(c,'e','x')后串c的值;
⑸执行SubString(s,b,5,3)后串s的值。
试求:⑴ StrLength(b)的返回值;答:12 ⑵ Index(a,'o',5)的返回值;答:0 ⑶ 执行StrInsert(a,3,c)后串a 的值;答:‘copleaselomn’ ⑷ 执行Replace(c,'e','x')后串c 的
值;2
答:’plxasx’⑸执行SubString(s,b,5,3)后串s 的值。
答:’are’
六、(20分)假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数,试写出其入队和出队算法(在出队算法中要返回队头元素)。
答:定义该循环队列的存储结构:
#define datatype char
#define MAXSIZE 100 /*队列的最大容量*/
typedef struct
{datatype data[MAXSIZE]; /*队列的存储空间*/
int rear,length;
}SEQQUEUE;
SEQQUEUE*q;
循环队列的队空条件是:q->length==0
循环队列的队满条件是:q->length==MAXSIZE
(1)入队
void Add_Queue(SEQQUEUE*q,datatype x)
{ if(q->length==MAXSIZE)/*队列满*/
printf("Queue full\n");
else
{ q->rear=(q->rear+1)%MAXSIZE;
q->data[q->rear]=x;
q->length++;
}
}
(2)出队
dat atype Del_Queue(SEQQUEUE*q)
{datatype x;
int front;
if(q->length==0) /*队列为空*/
{printf("Queue empty\n");
x=NULL;)
else
{ front=(MAXSIZE+q->rear-q->length+1)%MAXSIZE;/*计算头指针位置*/ x=q->data[front];
q->length--;)
return x;
}。