2022年数据结构与算法期中考试卷.docx

《2022年数据结构与算法期中考试卷.docx》由会员分享，可在线阅读，更多相关《2022年数据结构与算法期中考试卷.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - : 号 位 座题考 试 时 间玉林师范学院期中课程考试试卷学习必备欢迎下载 A 、规律相邻、物理不肯定相邻 B、不能随机存取年月日 C 、插入与删除需移动大量元素 D、表容量易于扩充下午（2022 2022 学年度第一学期）5、关于次序表的说法,请选出不正确的一项D ；: 名姓线命题老师：刘恒命题老师所在系：数计系A、规律相邻、物理相邻 B、可实现随机存取C、储备空间使用紧凑 D、表容量易于扩充课程名称：数据结构与算法考试专业：信计考试年级： 09 级6、设 N为正整数,试确定以下程序段中前置以记号语句的频度为 A ；题号一二三四五总分 x=9

2、1;y=100; 应得分30 10 10 40 10 满分： 100 whiley0 实得分评分：ifx100x-=10;y-; : 号学答订评卷人else x+; 签名 A、1100 B、 9100 一、单项挑选题（每题2 分,共 30 分,把正确答案填入表格中）要C、110 D、 910 7、在次序表中删除一个元素,平均需要移动 C 元素,设表长为 n；1 2 3 4 5 6 7 8 不A、n/2-1 B、n/2+1 : 别 班C B C C D A C A C、n/2 D、n+1/2 内9 10 11 12 13 14 15 8、对单链表执行以下程序段,请选出正确的一项 A ；C D B

3、 B B A D H 2 5 7 3 8 4 : 业专线装1、在数据结构中,从规律上可以把数据结构分成 C ；P Q S R A、动态结构和静态结构 B、紧凑结构和非紧凑结构T=P; 封C、线性结构和非线性结构 D、规律结构和储备结构While T-next.=NULL T data=Tdata*2;T=T next; 2、结构中的数据元素之间存在一个对多个的关系,称为B 结构；A、R-data=4 B、R-data=8 A、线性 B、树形密C、H-data=4 D、Q-data=7 : 级 年C、图状 D、网状9、如一个栈的输入序列是1,2,3, , n,输出序列的第一个元素是n, 就3、以

4、下关于线性表的说法不正确选项C ；第 k 个输出元素是 C ；A、线性表中的数据元素可以是数字、字符、记录等不同类型；A、k B、n-k-1 C n-k+1 D 、不确定: 院 系B、线性表中包含的数据元素个数不是任意的；10、判定一个次序栈S最多有 n 个元素 为满的条件是 D ；A、s.top.=0 B、s.top= =0 C、s.top.=n D、s.top= =nC、线性表中的每个结点 都有 且只有一个直接前驱和直接后继；11、一个队列的出队序列是1 2 3 4 ,就队列的入队序列是 B ；D、存在这样的线性表：表中各结点都没有直接前驱和直接后继；A、4 3 2 1 B、1 2 3 4

5、 4、关于单链表的说法,请选出不正确的一项 C ；名师归纳总结 - - - - - - -第 1 页,共 4 页精选学习资料 - - - - - - - - - C、1 4 3 2 D、3 2 4 1 学习必备欢迎下载表达式的运算符被置于两个操作数中间；12、选出合适的答案,“ 队列” 结构实现的是 B ；9、队列的插入操作是在 队尾 进行；4 的链串的储备密度为50%,就 1 先进/ 后出 2 后进 / 先出 3先来 / 先服务10、设每个字符占1 个字节,如结点大小为 4 先进/ 先出 5 后进 / 后出其每个指针占 4 个字节； A 、1 、2 B、3 、4 、5 C、1 、4 、5 D

6、 、1 13、串是一种特别的线性表,其特别性表达在 B ；A、可以次序储备 B、数据元素是一个字符C、可以链接储备 D、数据元素可以是多个字符14、设串 s1=ABCDEFG,s2=PQRST,函数 conx,y 返回 x 和 y 串的三、名词说明（每题 1、抽象数据类型 抽象数据类型简称2 分,共 10 分）ADT,是指一个数学模型以及定义在该模型上的一组操作；可用三元组表示（ D,S,P）,其中, D是数据对象, S是 D上的关系集, P 是对 D的基本操作集；（1 分）如： ADT 抽象数据类型名 连接串,subss,i,j返回串 s 的从序号 i 的字符开头的 j 个字符组成的数据对象

7、： 数据关系： 基本操作： 字串, lens 返回串 s 的长度,就：consubss1,3,lens2,subss1,lens2,3的结果串是 A ； ADT 抽象数据类型名（1 分）A、CDEFGEFG B、CDEFEFG C、BCDEFEFG D、CDEFGEF 2、物理结构数据结构在运算机中的表示（又称映像或储备结构）；（1 分）数据元素之间15、以下说法哪个是不正确的： D ；的关系在运算机中有两种不同的表示方法：次序映像和非次序映像, 并由此A、空格串 空串 B、数据元素是由如干数据项组成得到两种不同的储备结构：次序储备结构和链式储备结构；（1 分）C、串也称字符串 D、栈的表头端

8、称为栈顶3、语句的频度二、填空题（每题1 分,共 10 分）该语句重复执行的次数； （2 分 ）1、数据结构 是相互之间存在一种或多种特定关系的数据元素的集合；2、一般情形下,算法中基本操作重复执行的次数是问题规模 n 的某个函数fn,算法的时间量度记作 Tn=Ofn；3、线性表中每个结点包含两个指针域,称此线性表为 双向链表 ；4、 一个次序表的开头地址是 1000,每个元素的长度是 8,就第 7 个元素的储备地址是 1048；5、 执行 p=JD*mallocsizeofJD 的作用是 生成一个 JD型结点,并用指4、循环链表 是线性表的一种链式储备结构； （1 分）其特点是表中最终一个结

9、点的指针 域指向头结点,整个链表形成一个环； （1 分）5、算法的可行性一个算法是能行的, 即算法中描述的操作都是可以通过已经实现的基本运算 执行有限次来实现的； （2 分）针变量 p 指向（答出前半句即得分） ；注：可视答案的合理程度酌情给分；6、所谓次序表 Sqlist是线性表的 次序储备表示 ；7、栈是限定仅在表尾进行插入或就删除操作的线性表；四、解答题（每题 5 分,共 40 分）1、分别写出循环队列中判定队空和队满的条件（设循环队列的最大储备空名师归纳总结 8、人们日常运算用到的表达式,都被称为中缀表达式 ,这是由于这种算术间是 M）；第 2 页,共 4 页- - - - - - -

10、精选学习资料 - - - - - - - - - 队空： front= =rear （2.5 分）学习必备欢迎下载队满： rear+1%M= =front （2.5 分）5、已知以下字符串 : 2、已知 L 是带表头结点的非空单链表,且P 结点既不是第一个元素结点,a=THIS,f= A SAMPLE,C=GOOD,D=NE,b= , s=Concata, ConcatSubStringf,2,7, Concatb, SubStringa,3,2, 也不是最终一个元素结点,请写出删除P 结点的直接后继结点的语句序列：t=Replacef, SubStringf,3,6,c,A GOODL a1

11、 ai an u= ConcatSubStringc,3,1,D ONE,g= IS, v= Concats, Concatb, Concatt, Concatb,u, THIS SAMPLE IS A GOOD ONE P 试问： s,v,StrLengths,Indexv,g,Indexu,g各是什么？s: THIS SAMPLE IS （1 分）Q=P-next; （2 分）v: THIS SAMPLE IS A GOOD ONE （1 分）P-next=p-next-next; （2 分）StrLengths=14 （1 分）freeQ; （1 分）Indexv,g=3 （1 分）3、

12、简述以下算法的功能： Status algoStack s,int e Stack T; int d; InitStackT; while.StackEmptyS PopS,d ifd.=e pushT,d; while.StackEmptyT PopT,d; PushS,d; Indexu,g=0 （1 分）6、下面算法实现串的基本操作StrInsert&S,pos,TS、T 用定长次序储备表示 ,请填空完成；Status StrInsertSString &S, int pos, SString T ifposS0+1|S0+T0maxstrlen return ERROR; Spos+T

13、0 S0+T0=Spos S0; Spos pos+T0-1= T1 T0 ; （2.5 分） S0= S0+T0; （2.5 分） Return OK; 借助栈 T 把栈 s 中与 e 相等的元素删掉（ 5 分）p22 3.427、设有 3 个元素 A,B,C依次进栈,给出它们全部可能的出栈次序；4、写出以下程序段的输出结果（队列中的元素类型QElemType为 char ）； A B C A C B C B A B C A B A C 8、以下算法的功能是 : 已知线性表 La 和 Lb 中的元素按值非递减排列；归void main Queue Q; Init Queue Q; Char

14、x=e,y= c ; EnQueueQ, h; EnQueueQ, r ; EnQueueQ,y; DeQueueQ,x; EnQueueQ,x; DeQueueQ,x; EnQueueQ,a; While.QueueEmptyQ DeQueueQ,y;printfy; printfx; 并 La 和 Lb 得到新的线性表 Lc ,Lc 的元素也按值非递减排列；填空完成该 算法；名师归纳总结 （5 分） p23 3.12void MergeListList La, List Lb, List &Lc 第 3 页,共 4 页char InitListLc; - - - - - - -精选学习资料

15、 - - - - - - - - - 学习必备 欢迎下载 i = j = 1; k = 0; La_len = ListLengthLa; Lb_len = ListLengthLb; while i=La.len&j=Lb.len 2.5 分 GetElemLa, i, ai; GetElemLb, j, bj; if ai = bj ListInsertLc, +k, ai; +i; else ListInsertLc, +k, bj; +j; while i = La_len GetElemLa, i+, ai; ListInsertLc, +k, ai; while j next=NULL; fori=n;i0;i- p=linklistmallocsizeofLNode; p-data=x; p-next=L-next; L-next=p; return L; 其次章课件 P18 算法描述名师归纳总结 - - - - - - -第 4 页,共 4 页