对外经济贸易大学数据结构期末考试试卷(B卷)

学号___________班级___________

对外经济贸大学数据结构期考试试卷（）本试卷适用于：信息管理与信息系统专业姓名___________成绩___________一、填题（每小题,共20分）1性结构中元素之间存在关系树形结构中元素之间存在关系，图形结构中元素之间存在关系。2．在线性构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3．在具有n单元的循环队列中，队满时共有个元素4．带有一头结点的单链表head为空的条件是5．在hq链队列中，判定只有一个结点的条件是6于一个具有n个结点的单链表在已知所指向结点后插入一个新结点的时间复杂度是在给定值为x的结点后插入一个新结点的时间复杂度是7.两个串相等的充分必要条件是

且8.设s='I_AM_A_TEACHER其长度是9．一棵二树的第I（）层最多有个结点；一棵有n（n>0）个结点的满二叉树共有个叶子和非终端结点10在无向图的邻接矩阵A中，若A[i][j]等于1，则A[j][i]于11．已知一个图的邻接矩阵表示，删除所有从第I个结点出发的边方法是二、选题（每小题,共40分）1．在数据构中，从逻辑上可以把数据结构分成①。A．动态构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2性表的顺序存储结构是一种①的存储结构线性表的链式存储结构是一种②的存储结构。A．随机取B．顺序存取C．索引存取D．散列存取3.设有两个串pq求q在p首次出现的位置的运算称作A．连接B模式匹配C求子串D求串长4．算法分的两个主要方面是。A．空间杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性5．每种结都具备三个基本运算：插入、删除和查找，这种说法①A．正确B．不正确6．栈的特是，队列的特点是。A．先进出．先进后出7．判定一循环队列QU（最多元素为）为满队列的条件是。

A．QU.front==（QU.rear+1）%m0B．！（）%m0C．QU.front==D．QU.front！8．不带头点的单链表head为空的判定条件是A．head=NULLB．->next=NULLC．D．9．在循环链表p所指结点之后插入s指结点的操作是A．pright=s;sleft=p;prightleft=s;sright;B．prightleft=s;sC．right=s;prightleft=s;D．right;pleft=s;p10一个具有个结点的单链表中查找其值等于x结点时在查找成功的情况下，需平均比较_结点。A．nB．n/2．(n1)/2D．11.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法A正确B错误12.设高度为的二叉树上只有度为0和度为的结点，则此类二叉树中所包含的结点数至少为A2hB2h-1C2h+1Dh+113.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是AbdgcefhaBgdbecfhaCbdgaechfDgdbehfca14.树最适合用来表示A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据15.线索二叉树是一种_结构A逻辑B逻辑和存储C物理D线性16具有6顶点的无向图至少应有条边才能确保是一个连通图A．5B．6C．7D．817采用邻接表存储的图的广度优先遍历算法类似于二叉树的：A．先序历B．中序遍历C．后序遍历D．按层遍历18判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用：A．求关路径的方法C．广度优先遍历算法三、每题5分20分1．2．3．4．四、写法（分1．删除顺表中第i个元素的算法

B．最短路径的方法D．深度优先遍历算法

&L,i,&e)2．顺序栈入栈算法Push(SqStack3．链队列出队列算法QelemType&e)4．已知两整数