数据结构期末考试试题和标准答案及评分标准

1《数据结构》试题（A卷）（考试时间：90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。A．数据B.数据元素C.数据对象D.数据结构2.算法计算量的大小称为算法的（）。A.效率B.复杂度C.数据元素之间的关系D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。A.链式存储B.索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。A.p-next=p-next-nextB.p-next=p-nextC.p=p-next;p-next=p-next-nextD.p=p-next-next6.带头结点的单链表head为空的判定条件是（）。A.head==NULLB.head-next==NULLC.head-next==headD.head!==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。A.p-head==NULLB.p==NULLC.p-next==headD.p==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链式存储，不必占用一片连续的存储单元。D.线性表采用链式存储，便于插入和删除操作。9.队列操作的原则是（）。A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。A.栈首B.栈尾C.栈顶D.栈底11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。A．（rear-front+n）%nB.rear-front+1C.(front-rear+n)%nD.(rear-front)%n12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（）。A.（rear+1）%n==frontB.rear==frontC.rear+1==frontD.(rear-1)%n==front13.将一个十进制的数转换成二进制的数，可以使用以下一种称为（）的数据结构。A.图B.树C.广义表D.栈14.把一棵树转换为二叉树后，这棵二叉树的形态是（）。A.有2种B.有3种C.有4种D.唯一的15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数是（）。2A.3B.2C.0D.不确定二、填空题（本大题共10个空，每空2分，共计20分）1．数据结构是研究程序设计中计算机操作的以及它们之间的关系和运算的一门学科。2．在一个单链表中，已知指针q所指结点是指针p所指结点的前驱结点，若在q和p之间插入结点s，则应执行两条语句：______，。3．字符串采用结点大小为2的链表作为其存储结构，是指链表的每个链结点的域中只存放了2个字符。4．广义表（a,b,c,d）的表尾是。5．一棵深度为k的二叉树，最多有个结点。6．已知有向图G=（V，E），其中:V={v1,v2,v3,v4,v5,v6,v7},E={v1,v2,v1,v3,v1,v4,v2,v5,v3,v5,v3,v6,v4,v6,v5,v7,v6,v7},则G的拓扑序列是______。7.有n个顶点的连通图至少有条边。8.图的存储常采用和两种方法。三、判断题（本大题共10小题，每题1分，共10分）（请在每小题后面的括号里写出答案，如果正确，请写“√”，如果错误，请写“×”）1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）2．线性表就是顺序存储的表。（）3.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。（）4．线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。（）5.串的长度是指串中所含不同字符的个数。（）6.对稀疏矩阵进行压缩存储的目的是节省存储空间。（）7.二叉树是非线性数据结构，所以它不能采用顺序存储结构存储。（）8.任意一棵二叉树中至少有一个结点的度为2。（）9.对线性表进行二分查找时，要求线性必须以顺序方式存储，且结点按关键字有序排序。（）10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址必须大于等于原散列地址。（）四、应用题（本小题共5小题，每小题6分，共30分）1.简述以下算法的功能（假设栈和队列的元素类型均为int）(6分)voidfun1(Queue&Q){StackS;intx;Initstack(S);While(!QueueEmpty(Q)){DeQueue(Q,x);Push(S,x);}While(!StackEmpty(S)){Pop(S,x);3EnQueue(Q,x);}}2.请将如图4.1所示的一棵树转换成一棵二叉树。（6分）3.给定叶结点(a,b,c,d,e,f,g)，权值分别为{23,12,15,7,17,2,8}，画出对应的哈夫曼树，并写出各叶结点的哈夫曼编码。（6分）4.（6分）已知图G的邻接表如图4.2所示，则：从顶点v1出发的深度优先搜索序列为_______。从顶点v1出发的广度优先搜索序列为_______。5.求构造图4.3所示无向网的最小生成树（6分）ABCDEFG图4.1一棵树图4.2图G的邻接表4五、算法设计题（本大题共1小题，每小题10分，共10分）1.已知查找表的数据元素类型如下：TypedefstructRectype{intnum;charname[8];}Rectype;假设查找表中有n个记录，并且是按num降序顺序存储TypedefRectypeSqlist[100];要求：（1）写出对给定值K进行二分查找的算法和main函数。（2）二分查找算法的函数头部为“intbinsearch(SqlistR,intn,intK)“（3）在main函数中建立该查找表、调用二分查找算法，并输出查找结果。图4.3无向网5《数据结构》试题（B卷）（考试时间：90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1．在数据结构中，数据的（）结构是独立于计算机的。A.逻辑B.存储C.散列D.索引2．下列程序段的时间复杂度为（）。for(i=0;in;i++)x=x-2;A.O（2n）B.O（n）C.O（1）D.O（n2）3.链式存储结构表示的线性表也称为（）。A.链表B.顺序表C.双链表D.物理表4.不带头结点的单链表（头指针为head）为空的判定条件是（）。A．head==NULLB．head-next==headC．head-next==NULLD．head!=NULL5．线性表若采用顺序结构时，要求内存中可用存储单元的地址（）。A．一定是不连续的B．部分地址是连续的C．一定是连续的D．连续不连续都可以6.对于单链表，在两个结点之间插入一新结点需要修改的指针共（）个。A.0B.1C.2D.47.若线性表中有n个元素，算法（）在单链表上实现要比在顺序表上实现效率更高。A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换其中某两个元素的值8.对于顺序表，访问结点和增加、删除结点的时间复杂度分别为（）。A.O(n)O(n)B.O(1)O(n)C.O(n)O(1)D.O(1)O(1)9.队列的删除操作是在（）进行。A．队首B．队尾C．队首前一单元D．队尾后一单元10.下列关于栈的叙述中，正确的是（）。A．栈底元素一定是最后入栈的元素B．栈操作遵循先进后出的原则C．栈顶元素一定是最先入栈的元素D．以上三种说法都不对11.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少是（）个。A.3B.4C.5D.612.假设为循环队列分配的向量空间为Q[20],若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。A.10B.11C.12D.1313.银行业务叫号系统采用了数据结构。A．栈B．广义表C．队列D．图14.按照二叉树的定义，具有3个结点的不同形状的二叉树有______种。A.3B.4C.5D.615.n个结点的线索二叉树上含有的线索数为______。A.0B.n-1C.n+1D.2n6二、填空题（本大题共10个空，每空2分，共20分）1．数据结构包含三个方面的内容，即数据的逻辑结构、数据的结构和对数据所施加的操作。2．已知指针q值为NULL、指针p指向单链表L中的某结点，则删除其后继结点（要求由指针q指向）的语句是，，free(q)。3．设广义表L=（a,()）,则Head(L)=。4．当且仅当两个串的相等并且各个对应位置上的字符都相等时，称这两个串相等。5.二叉树的第4层结点数最多为个。6．除了利用求关键路径的方法，还可以利用方法判断出一个有向图是否有环（回路）。7．图的遍历主要有和两种方法。8.具有4个顶点的无向完全图有条边。三、判断题（本大题共10小题，每题1分，共10分）（请在每小题后面的括号里写出答案，如果正确，请写“√”，如果错误，请写“×”）1.对于一个线性表，采用顺序存储方式进行插入和删除结点时效率太低，采用链式存储方式更好。（）2.所谓静态链表就是一直不发生变化的链表。（）3.在顺序表中，最后一个元素有一个后继。（）4.线性表就是链式存储的表。（）5.串是一种特殊的线性表，其特殊性体现在数据元素可以是多个字符。（）6.对稀疏矩阵进行压缩存储的目的是便于输入和输出。（）7.任意一棵二叉树中的度可以小于2。（）8.树形结构最适合用来表示元素之间具有分支层次关系的数据。（）9.当采用分块查找时，数据的组织方式为：数据分成若干块，每块内数据必须有序。（）10.顺序查找法适合于存储结构为顺序存储或链式存储的线性表。（）四、应用题（本小题共5小题，每小题6分，共30分）1.下面是对二叉树进行操作的算法，其功能为（6分）Voidunknown(BtreeBT){Btreep=BT,temp;If(p!=NULL){temp=p-lchild;p-lchild=p-rchild;p-rchid=temp;unknown(p-lchild);unknown(p-rchild);}2.请写出如图4.1所示二叉树的先序遍历序列、中序遍历序列和后序遍历序列。（6分）ABCDEFG73．已知如图4.2所示的有向图，请给出：（共6分）①每个顶点的入度和出度；（2分）②邻接矩阵；（4分）4.要求用普里姆算法画出如图4.3所示无向网的最小生成树，假设从a顶点出发构造最小生成树，写出各条边加入生成树的次序（用权值表示）。（6分）5.下列算法的运行结果是（栈的元素类型为char）(6分)voidmain(){stackS;charx=’a’,y=’b’;initstack(S);push(S,x);push(S,y);printf(“%c”,x);printf(“%c”,y);pop(S,x);pop(S,y);printf(“%c”,x);printf(“%c”,y);}图4.1二叉树图4.2有向图图4.3无向网8五、算法设计题（本大题共1小题，每题10分，共10分）1.已知查找表的数据元素类型如下：TypedefstructRecty