2023年数据结构与算法期中考试卷含超详细解析答案.pdf

《2023年数据结构与算法期中考试卷含超详细解析答案.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构与算法期中考试卷含超详细解析答案.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备 欢迎下载 玉林师范学院期中课程考试试卷（20102011 学年度第一学期）命题教师：刘恒 命题教师所在系：数计系 课程名称：数据结构与算法 考试专业：信计 考试年级：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、紧凑结构和非紧凑结

2、构 C、线性结构和非线性结构 D、逻辑结构和存储结构 2、结构中的数据元素之间存在一个对多个的关系，称为(B)结构。A、线性 B、树形 C、图状 D、网状 3、以下关于线性表的说法不正确的是(C)。A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前驱和直接后继。D、存在这样的线性表：表中各结点都没有直接前驱和直接后继。4、关于单链表的说法，请选出不正确的一项(C)。A、逻辑相邻、物理不一定相邻 B、不能随机存取 C、插入与删除需移动大量元素 D、表容量易于扩充 5、关于顺序表的说法，请选出不正确的一项(D

3、)。A、逻辑相邻、物理相邻 B、可实现随机存取 C、存储空间使用紧凑 D、表容量易于扩充 6、设 N为正整数，试确定下列程序段中前置以记号 语句的频度为(A)。x=91;y=100;while(y0)if(x100)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)。T=P;While(T-next!=NULL)T data=Tdata*2;T=T next;A、R-data=4

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 2 5 7 3 8 4 P Q R S 考 试 时 间 年 月 日 下午 系(院):年级:专业:班别:学号:姓名:座位号:

5、密 封 线 内 不 要 答 题 装 订 线 H 学习必备 欢迎下载 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

6、的从序号 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

7、(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

8、 的链串的存储密度为 50%，则其每个指针占 4 个字节。三、名词解释（每题 2 分，共 10 分）1、抽象数据类型 抽象数据类型简称 ADT，是指一个数学模型以及定义在该模型上的一组操作。可用三元组表示（D,S,P），其中，D是数据对象，S 是 D上的关系集，P是对 D的基本操作集。（1 分）如：ADT 抽象数据类型名 数据对象：数据关系：基本操作：ADT 抽象数据类型名 （1 分）2、物理结构 数据结构在计算机中的表示（又称映像或存储结构）。（1 分）数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。（1 分）

9、3、语句的频度 该语句重复执行的次数。（2 分）4、循环链表 是线性表的一种链式存储结构。（1 分）其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。（1 分）5、算法的可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（2 分）注：可视答案的合理程度酌情给分。四、解答题（每题 5 分，共 40 分）1、分别写出循环队列中判断队空和队满的条件（设循环队列的最大存储空间是 M）。年级级一二三四五总分满分评分题号应得分实得分评卷人签名一单项选和存储结构结构中的数据元素之间存在一个对多个的关系称为结构线性点都有且只有一个直接前驱和直接后继存在

10、这样的线性表表中各结点都学习必备 欢迎下载 队空：front=rear （2.5 分）队满：(rear+1)%M=front （2.5 分）2、已知 L 是带表头结点的非空单链表，且 P 结点既不是第一个元素结点，也不是最后一个元素结点，请写出删除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

11、);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);p

12、rintf(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

13、(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(posS0+1|S0+T0maxstrlen)return ERROR;Spos+T0S0+T0=SposS0;Spospos+

14、T0-1=T1T0;（2.5 分）S0=S0+T0;（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);L a1 P an ai 年级级一二三四五总分满分评分题号应得分实得分评卷人签名一单项选和存储结构结构中的数据元素之

15、间存在一个对多个的关系称为结构线性点都有且只有一个直接前驱和直接后继存在这样的线性表表中各结点都学习必备 欢迎下载 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 next=NULL;for(i=n;i0;i-)p=(linklist)malloc(sizeof(LNode);p-data=x;p-next=L-next;L-next=p;return L;第二章课件 P18 算法描述 年级级一二三四五总分满分评分题号应得分实得分评卷人签名一单项选和存储结构结构中的数据元素之间存在一个对多个的关系称为结构线性点都有且只有一个直接前驱和直接后继存在这样的线性表表中各结点都