还剩3页未读,继续阅读
文本内容:
试卷编号拟题教研室(或老师)签名东屹波教研室主任签名长沙理工高校考试试卷(A卷)课程名称(含档次)数据结构A课程代号0812023615课程编号002131专业计算机相关专业层次(本、专)本科考试方式(开、闭卷)闭卷
一、应用题(2小题,共8分)设有一个栈,元素进栈的次序为ABCDE用I表示进栈操作,表示出栈操作,写出下列出栈的操作序列CBADE
(2)ACBED
二、推断正误(5小题,共10分).依次表结构相宜于进行依次存取,而链表相宜于进行随机存取().一个栈的输入序列为ABCD可以得到输出序列CABD().子串“ABC”在主串“AABCABCD”中的位置为2().设一棵树T可以转化成二叉树BT则二叉树BT中肯定没有右子树().调用一次深度优先遍历可以访问到图中的全部顶点()
三、单项选择题(H小题,共22分).两个指针P和Q分别指向单链表的两个元素,P所指元素是Q所指元素前驱的条件是()oA.P-next==Q-nextB.P-next==QC.Q-next==PD.P==Q.从一个具有n个结点的单链表中查找其值等于x结点时,在查找胜利的状况下,需平均比较()个结点A.nBn/2C.(n-l)/2D.(n+l)/
2.假如以链表作为栈的存储结构,则出栈操作时()A.必需判别栈是否满B.必需判别栈是否空C.必需判别栈元素类型D.对栈可不做任何判别.设输入序列是
1、
2、
3、……、n经过栈的作用后输出序列的第一个元素是n则输出序列中第i个输出元素是()oAn-iBn-l-iCn+1-iD不能确定.下列说法不正确的是()A.串中元素只能是字符B.串中元素只能是字母C.串是一种特别的线性表D.串中可以含有空白字符.线索二叉树中某结点R没有左孩子的充要条件是()0A.R.lchild=NULL.BR.ltag=OC.R.ltag=lD.R.rchild=NULL.树最适合用来表示()oA.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据.设有向无环图G中的有向边集合E={vl2233414}则下列属于该有向图G的一种拓扑排序序列的是()oA.1234B2341C.1423D.
1243.设数据结构A=(DR)其中D={1234}R={r}r={l2233441}则数据结构A是()oA线性结构B树型结构C图型结构D集合.每个结点只含有一个数据元素,全部存储结点相继存放在一个连续的存储区里,这种存储结构称为()结构A.依次存储B.链式存储C.索引存储D.散列存储.下列叙述中,错误的是OA.数据的存储结构与数据处理的效率亲密相关B.数据的存储结构与数据处理的效率无关C.数据的存储结构在计算机中所占的空间不肯定是连续的D.一种数据的逻辑结构可以有多种存储结构
四、算法设计题(3小题,共32分).已知一个单链表,编写一个函数从单链表中删除自第i个结点起的k个结点(11分).设计一个在链式存储结构上统计二叉树中结点个数的算法(11分).先阅读下列函数arrange再做下面
(1)和
(2)两小题intarrange(inta[]intlinthintx){//l和h分别为数据区的下界和上界inti=l;j=h;while(ij){while(ija[j]=x)j—;while(ija[i]=x)i++;if(ij){t=a[j];a[j]=a[i];a[i]=t;})if(a[i]x)returni;elsereturni_1;
(1)写出该函数的功能;(5分)
(2)写一个调用上述函数实现下列功能的算法对一整型数组b[n]中的元素进行重新排列,将全部负数均调整到数组的低下标端,将全部正数均调整到数组的高下标端,若有零值,则置于两者之间,并返回数组中零元素的个数(5分)
五、填空题(5小题,共10分).由两个栈共享一个存储空间的好处是().设长度为n的链队列用单循环链表表示,若只设尾指针,则出队操作的时间困难度为()o.设无向图G中顶点数为n则图G至少有()条边,至多有()条边.在无向图的邻接矩阵中,第i行(列)中“1”的个数是第i个顶点的,矩阵中“1”的个数的一半是图中的O.依次存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的
六、简答题Q小题,共10分).请说明依次表和单链表各有何优缺点.设指针变量p指向双向链表中结点A指针变量q指向被插入结点B要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)o
七、名词说明(2小题,共8分).什么是AOE网?.简述下列概念线性结构、非线性结构长沙理工高校计算机与通信工程学院2023-2024学年一学期数据结构A期末考试试卷A卷答案部分
一、应用题1小题,共8分
1.解1IIIOOOIOIO2IOIIOOIIOO
二、推断正误5小题,共10分
1.X
2.X
3.V
4.V
5.X
三、单项选择题H小题,共22分B
2.D
3.B
4.C
5.B
四、算法设计题3小题,共32分.解:voidDelListNode*headintiintknodeintj;ifi==lForj=l;j=k;j++//删除前k个元素p=head;〃p指向要删除的结点head=head-next;Freep;elsep=head;forj=l;j=i-2;j++p=p-next;//p指向要删除的结点的前一个结点forj=l;j=k;j++q=p-next;//q指向要删除的结点p-next=q-next;freeq;.解voidcountnodcbitrcc*btintcount{ifbt!=O{count++;countnodebt-lchildcount;countnodebt-rchildcount;}.解答
(1)该函数的功能是调整整数数组a口中的元素并返回分界值i使全部Vx的元素均落在a[l..i]±使全部2x的元素均落在a[i+l..h]±o
五、填空题(5小题,共10分)节约存储空间,降低上溢发生的机率0
(1)0n(n-l)/2度边数存储位置指针
六、简答题(2小题,共10分)•答
(1)依次表的优点
①无需为表示表中元素之间的逻辑关系而增加额外的存储空间;
②可以快速地存取表中任一位置的元素(即随机存取)依次表的缺点
①插入和删除操作需移动大量元素;
②表的容量难以确定;
③造成存储空间的“碎片工
(2)单链表的优点
①不必事先知道线性表的长度;
②插入和删除元素时只需修改指针,不用移动元素单链表的缺点
①指针的结构性开销;
②存取表中随意元素不便利,只能进行依次存取.答:q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;
七、名词说明(2小题,共8分).答若在带权有向图G中以项点表示事务,以有向边表示活动,边上的权值表示该活动持续的时间,则此带权有向图称为用边表示活动的网(ActivityOnEdgenetwork)简称AOE网.答线性结构数据逻辑结构中的一类,它的特征是若结构为非空集,则该结构有且只有一个起先结点和一个终端结点,并且全部结点都最多只有一个干脆前趋和一个干脆后继线性表就是一个典型的线性结构非线性结构数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个干脆前趋和干脆后继。