浙江工商大学《数据结构》xxxx年考试样卷(A卷)

浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第1页共15页浙江工商大学xxxx/xxxy学年第一学期考试试卷课程名称：《数据结构》考试方式：闭卷完成时限：120分钟班级名称：学号：姓名：题号一二三四五六总分分值101010142036100得分阅卷人一.判断题（每题1分，共10分）1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。................................()2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构相关，是依赖于计算机的。................................()3、线性表中的每个结点最多只有一个直接前驱和一个直接后继。..................................................()4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。........................................()5、二维数组是其数组元素为线性表的线性表。................()6、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。..................................()7、由一棵二叉树的前序序列和后序序列可以唯一确定它。......()8、在数据的存放无规律而言的线性表中进行查找的最佳方法是顺序查找（线性查找）。......................................()9、多重表文件和倒排文件都归属于多关键字文件。............()浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第2页共15页10、不定长文件是指文件的长度不固定。.....................()二.填空题（每题1分，共10分）1、若将数据结构形式定义为二元组(D，R)，其中D是数据元素的有限集合，则R是D上。2、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为。3、若不带头结点的单链表的头指针为head，则该链表为空的判定条件是。4、对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。5、树的存储结构常见的有，，。6、深度为k的完全二叉树至少有个结点，至多有个结点。7、一棵有n个结点的满二叉树有个度为1的结点、有个分支（非终端）结点和个叶子，该满二叉树的深度为。8、大多数排序算法都有两个基本的操作和。9、线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法查找表中与k相等的元素，在查找不成功的情况下，最多需要查找次。设有100个结点，用二分法查找时，最大比较次数是。10、设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键字按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；快速排序一趟扫描的结果是。浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第3页共15页三.选择题（每题1分，共10分）1、算法指的是()A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2、线性表采用链式存储时，结点的存储地址()A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()A．O(1)B．O(n)C．O(m)D．O(m+n)4、已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行操作()A.s-link=p；p-link=s；B.s-link=p-link；p-link=s；C.s-link=p-link；p=s；D.p-link=s；s-link=p；5、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是()A.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，46、判断线索二叉树中p节点有右孩子的条件是()A．p!=NULLB.p-rchild!=NULLC.p-rtag==0D.p-rtag==17、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是()浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第4页共15页A．9B．11C．15D．不确定8、在表长为ｎ的链表中进行线性查找，它的平均查找长度为()A.ASL=nB.ASL=(n+1)/2C.ASL=＋1D.ASL=log2(n+1)-19、对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。A．3B．4C．5D．610、在二叉排序树中，每个结点的关键字A，B一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是C。供选择的答案:A：①比左子树所有结点的关键字大，比右子树所有结点的关键字小②比左子树所有结点的关键字小，比右子树所有结点的关键字大③比左右子树的所有结点的关键字都大④与左子树和右子树各自所有结点的关键字无必然关系B：①前序遍历②中序(对称)遍历③后序遍历④层次遍历C：①除最下二层可以不满外，其余都是充满的②除最下一层可以不满外，其余都是充满的③每个结点的左右子树的高度之差的绝对值不大于1④最下层的叶子必须在最左边答案：A＝B＝C＝四.简答题（每题7分，共14分）1、假设以数组seqn［m］存放循环队列的元素，设变量rear和quelenn浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第5页共15页分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式；(3)设m=40,rear=13,quelen=19,求队头元素的位置；(4)写出一般情况下队头元素位置的表达式。2、什么叫线索，线索二叉树，线索化？五.算法题（每题10分，共20分）1、阅读下面的算法：LinkListmynote(LinkList*L){//L是不带头结点的单链表的头指针if(L&&L-next)浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第6页共15页{q=L；L=L－next；p=L；S1：while(p－next)p=p－next；S2：p－next=q；q－next=NULL；}returnL；}请回答下列问题：(1)说明语句S1的功能；(2)说明语句组S2的功能；(3)设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。2、利用两个栈sl,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第7页共15页六.应用题（每题6分，共36分）1、分析下面程序段的时间复杂性：y=0;while(n=(y+1)*(y+1)){y++;}。2、已知二叉树如下图所示：haceibdfgj浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第8页共15页(1)写出上图二叉树的中序遍历和后序遍历的结果；(2)画出此二叉树还原成森林的图。3、试画出对下图执行深度优先遍历产生的生成树（从1开始），并写出遍历序列。4、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：12345678浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第9页共15页(1)画出描述折半查找过程的判定树；(2)若查找元素54，需依次与哪些元素比较？(3)若查找元素90，需依次与哪些元素比较？(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。5、设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起，逐个输入各个数据而生成的二叉排序树。浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第10页共15页6、设待排序的排序码序列为{12,2,16,30,28,10,16*,20,6,18},试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。(1)直接插入排序(2)希尔排序(增量为5,2,1)(3)冒泡排序(4)快速排序浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第11页共15页参考答案及评分标准一.判断题（每题1分，共10分）1、√；2、×；3、√；4、×；5、√；6、√；7、×；8、√；9、√；10、×；二.填空题（每题1分，共10分）1、关系的有限集合；2、head=p－next－next；3、head==NULL；4、进栈、出栈；5、双亲表示法，孩子链表表示法，孩子-兄弟表示法；6、2k-1、2k-1；7、0、(n-1)/2、(n+1)/2、log2n+1；8、比较、移动；9、8、7；10、HCQPAMSRDFXY、PACSQHFXRDMY、FHCDPAMQRSYX；三.选择题（每题1分，共10分）1、D；2、B；3、C；4、B；5、D；6、C；7、B；8、B；9、C；10、①、②、②；四.简答题（每题7分，共14分）1、（1）quelen==m；（2）quelen==0；（3）34（4）(rear-quelen+m)%m；2、将二叉树各节点中的空的左孩子指针域改为指向其前驱，空的右孩子指针浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第12页共15页域改为指向其后继，称这种新的指针为线索，所得到的二叉树称为线索二叉，将二叉树转变成线索二叉树的过程称为线索化。五.算法题（每题10分，共20分）1、（1）找到next域为NULL的节点，即链表的尾节点；（2）令尾节点的next域指向原表头，即链表中的第一个节点；再令第一个节点的next域为NULL；从而将原来链表中的第一个节点变为尾节点。（3）算法执行后的线性表为（a2,…,an，a1）。2、（1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出队列元素），则不能入队。（2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空，队列空，不能出队。（3）判队空若栈s1为空并且s2也为空，才是队列空。六.应用题（每题6分，共36分）1、该程序段中主要计算量在于循环过程。当y的平方小于等于n时，y在每次循环过程中加1，直到y的平方大于n为止。所以该循环总共执行y次，且在循环退出时有y*y=n成立，注意到y是从0开始自加的，因此总的执行次数为y=sqrt(n)，从而复杂度为O(sqrt(n))。2、（1）中序：bjfdgachei(1分，次序错一处都不得分)浙江工商大学《数据结构》课程考试试卷，适用专业：电子、通信、测仪第13页共15页后序：jfgdbhieca(1分，次序错一处都不得分)（2）评分标准：每画对一个树，得1分。3、1－2－4－5－3－6－7－84、（1）先画出判定树如下（注：mid=(1+12)/2=6）：（2）查找元素54，需依次与30,63,42,54等元素比较；（3）查找元素90，需依次与30,63,87,95,72等元素比较；（4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×