— :号—位—座— — — — — — :名—姓—— — —题 — — — —答 — :号— 学— —要 — — — —不 — :别— 班— —内 — — — —线 — :— 业— 专—封 — — — —密 —:级—年— — — — — — :)—院—(系—— ∞考 试 时 间 玉林师范学院期中课程考试试卷
年 月 日 下午 （2010——2011学年度第一学期）
命题教师：刘恒 命题教师所在系：数计系 课程名称：数据结构与算法 考试专业：信计 考试年级：09级 线 题 号 一 二 三 四 五 总 分 应得分 30 10 10 40 10 满分：100 实得分 评分： 评卷人 签 名 一、单项选择题（每题2分，共30分，把正确答案填入表格中） 1 2 3 4 5 6 7 8 ∞C B C C D A C A 订9 10 11 12 13 14 15 C D B B B A D 1、在数据结构中，从逻辑上可以把数据结构分成( C)。
A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、逻辑结构和存储结构 2、结构中的数据元素之间存在一个对多个的关系，称为(B )结构。 A、线性 B、树形 C、图状 D、网状 装3、以下关于线性表的说法不正确的是(C )。
A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。
C、线性表中的每个结点都有且只有一个直接前驱和直接后继。 D、存在这样的线性表：表中各结点都没有直接前驱和直接后继。 4、关于单链表的说法，请选出不正确的一项( C)。
∞ A、逻辑相邻、物理不一定相邻 B、不能随机存取
C、插入与删除需移动大量元素 D、表容量易于扩充 5、关于顺序表的说法，请选出不正确的一项(D )。 A、逻辑相邻、物理相邻 B、可实现随机存取 C、存储空间使用紧凑 D、表容量易于扩充
6、设N为正整数，试确定下列程序段中前置以记号@语句的频度为(A )。 x=91;y=100;
while(y>0){
@if(x>100){x-=10;y--;} else x++; } A、1100 B、 9100 C、110 D、 910
7、在顺序表中删除一个元素，平均需要移动( C)元素，设表长为n。
A、n/2-1 B、n/2+1
C、n/2 D、(n+1)/2
8、对单链表执行下列程序段，请选出正确的一项( A)。
H 2 5 7 3 8 ┅ 4 ^ P Q S R T=P;
While(T->next!=NULL){T—>data=T—>data*2;T=T—>next;} A、R->data=4 B、R->data=8
C、H->data=4 D、Q->data=7
9、若一个栈的输入序列是1，2，3，┅，n，输出序列的第一个元素是n,则第k个输出元素是( C)。
A、k B、n-k-1 C n-k+1 D、不确定
10、判断一个顺序栈S(最多有n个元素 )为满的条件是( )D。 A、s.top!=0 B、s.top= =0 C、s.top!=n D、s.top= =n 11、一个队列的出队序列是1 2 3 4，则队列的入队序列是(B )。 A、4 3 2 1 B、1 2 3 4
C、1 4 3 2 D、3 2 4 1 12、选出合适的答案，“队列”结构实现的是( B)。 (1) 先进/后出 (2) 后进/先出 (3) 先来/先服务 (4) 先进/先出 (5) 后进/后出
A、(1)、(2) B、(3)、(4)、(5) C、(1)、(4)、(5) D、(1) 13、串是一种特殊的线性表，其特殊性体现在( B)。 A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符
14、设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的字串，len(s)返回串s的长度，则：
con(subs(s1,3,len(s2)),subs(s1,len(s2),3))的结果串是( A)。 A、CDEFGEFG B、CDEFEFG C、BCDEFEFG D、CDEFGEF 15、下列说法哪个是不正确的：( D)。
A、空格串≠空串 B、数据元素是由若干数据项组成 C、串也称字符串 D、栈的表头端称为栈顶
二、填空题（每题1分，共10分）
1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 2、一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))。
3、线性表中每个结点包含两个指针域，称此线性表为双向链表。 4、 一个顺序表的开始地址是1000，每个元素的长度是8，则第7个元素的存储地址是1048。
5、 执行p=(JD*)malloc(sizeof(JD))的作用是生成一个JD型结点，并用指针变量p指向（答出前半句即得分）。 6、所谓顺序表(Sqlist)是线性表的顺序存储表示。 7、栈是限定仅在表尾进行插入或则删除操作的线性表。
8、人们日常计算用到的表达式，都被称为中缀表达式，这是由于这种算术
表达式的运算符被置于两个操作数中间。 9、队列的插入操作是在队尾进行。
10、设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占4个字节。
三、名词解释（每题2分，共10分） 1、抽象数据类型
抽象数据类型－简称ADT，是指一个数学模型以及定义在该模型上的一组操作。可用三元组表示（D,S,P），其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。（1分）如：ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义>
}ADT 抽象数据类型名 （1分）
2、物理结构
数据结构在计算机中的表示（又称映像或存储结构）。（1分）数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。（1分）
3、语句的频度
该语句重复执行的次数。（2分）
4、循环链表
是线性表的一种链式存储结构。（1分）其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。（1分）
5、算法的可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（2分）
注：可视答案的合理程度酌情给分。
四、解答题（每题5分，共40分）
1、分别写出循环队列中判断队空和队满的条件（设循环队列的最大存储空间是M）。
队空：front= =rear （2.5分） 队满：(rear+1)%M= =front （2.5分）
2、已知L是带表头结点的非空单链表，且P结点既不是第一个元素结点，也不是最后一个元素结点，请写出删除P结点的直接后继结点的语句序列：
L a1 ┅ ai ┅ an ^ P Q=P->next; （2分） P->next=p->next->next; （2分） free(Q); （1分）
3、简述以下算法的功能：
Status algo(Stack s,int e){ Stack T; int d; InitStack(T);
while(!StackEmpty(S)){ Pop(S,d)
if(d!=e) push(T,d);} while(!StackEmpty(T)){ Pop(T,d); Push(S,d);} }
借助栈T把栈s中与e相等的元素删掉（5分）p22 3.4(2)
4、写出下列程序段的输出结果（队列中的元素类型QElemType为char）。 void main()
{ Queue Q; Init Queue (Q); Char x=’e’,y=’c’ ;
EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’);
While(!QueueEmpty(Q)){ DeQueue(Q,y);printf(y);} printf(x); }
char （5分） p23 3.12
5、已知下列字符串:
a=’THIS’,f=’A SAMPLE’,C=’GOOD’,D=’NE’,b=’ ’, s=Concat(a, Concat(SubString(f,2,7), Concat(b, SubString(a,3,2)))), t=Replace(f, SubString(f,3,6),c), A GOOD u= Concat(SubString(c,3,1),D) ONE,g=’IS’,
v= Concat(s, Concat(b, Concat(t, Concat(b,u)))), THIS SAMPLE IS A GOOD ONE
试问：s,v,StrLength(s),Index(v,g),Index(u,g)各是什么？ s: THIS SAMPLE IS （1分） v: THIS SAMPLE IS A GOOD ONE （1分） StrLength(s)=14 （1分） Index(v,g)=3 （1分） Index(u,g)=0 （1分）
6、下面算法实现串的基本操作StrInsert(&S,pos,T)(S、T用定长顺序存储表示)，请填空完成。
Status StrInsert(SString &S, int pos, SString T)
{ if(pos<1||pos>S[0]+1||S[0]+T[0]>maxstrlen) return ERROR; S[pos+T[0]…S[0]+T[0]]=S[pos…S[0]];
S[pos…pos+T[0]-1]= T[1…T[0]];（2.5分） S[0]= S[0]+T[0];（2.5分） Return OK; }
7、设有3个元素A，B，C依次进栈，给出它们所有可能的出栈次序。 A B C A C B C B A B C A B A C
8、下列算法的功能是: 已知线性表La和Lb中的元素按值非递减排列。归并La和Lb得到新的线性表 Lc，Lc的元素也按值非递减排列。填空完成该算法。
void MergeList(List La, List Lb, List &Lc) { InitList(Lc);
i = j = 1; k = 0;
La_len = ListLength(La); Lb_len = ListLength(Lb);
while ( (i<=La.len)&&(j<=Lb.len) ) { (2.5分)
GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) {
ListInsert(Lc, ++k, ai); ++i; }
else { ListInsert(Lc, ++k, bj); ++j; } }
while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); }
while (j <= Lb_len) { GetElem(Lb, j++, bj); ListInsert(Lc,++k,bj); }
课本P21 算法2.2
五、算法设计题：编一段算法实现单链表的逆向生成（10分） Linklist CreaaList_L(Linklist L, int n) {
int i;
Linklist p;
L=(linklist)malloc(sizeof(LNode)); L->next=NULL; for(i=n;i>0;i--)
{ p=(linklist)malloc(sizeof(LNode)); p-data=x;
p-next=L->next; L->next=p; }
return L; }
大队长、中队长、小队长、少先队员，为了健全完善我校少先队组织，特制定以下方案： 一、成员的确定 1、大队长由纪律部门、卫生部门、升旗手、鼓号队四个组织各推荐一名优秀学生担任（共四名），该部门就主要由大队长负责部门内的纪律。 2、中、小队长由各班中队公开、公平选举产生，中队长各班一名（共11名），一般由班长担任，也可以根据本班的实际情况另行选举。小队长各班各小组先选举出一名（共8个小组，就8名小队长）然后各班可以根据需要添加小队长几名。 3、在进行班级选举中、小队长时应注意，必须把卫生、纪律部门的检查学生先选举在中、小队长之内，剩余的中、小队长名额由班级其他优秀学生担任。 4、在班级公开、公平选举出中、小队长之后，由班主任老师授予中、小队长标志，大队长由少先队大队部授予大队长标志。 二、成员的职责及任免 1、大、中、小队长属于学校少先队组织，各队长不管是遇见该班的、外班的，不管是否在值勤，只要发现任何人在学校内出现说脏话、乱扔果皮纸屑、追逐打闹、攀爬栏杆、乱写乱画等等一些违纪现象，都可以站出来制止或者报告老师。 2、班主任在各中队要对中、小队长提出具体的责任，如设置管卫生的小队长，管纪律的小队长，管文明礼貌的、管服装整洁的等等，根据你班的需要自行定出若干相应职责，让各位队长清楚自己的职权，有具体可操作的事情去管理，让各位队长成为班主任真正的助手，让学生管理学生。各中队长可以负责全班的任何违纪现象，并负责每天早上检查红领巾与校牌及各小队长标志的佩戴情况。 3、大、中、小队长标志要求各队长必须每天佩戴，以身作则，不得违纪，如有违纪现象，班主任可根据中、小队长的表现撤消该同学中、小队长的职务，另行选举，大队长由纪律、卫生部门及少先队大队部撤消，另行选举。 4、各班中、小队长在管理班级的过程中负责，表现优秀，期末评为少先队部门优秀干部。 小学少先队组织机构 少先队组织由少先队大队部及各中队组成，其成员包括少先队辅导员、
相关推荐：
loading