宁波大学数据结构试题

宁波大学学年《数据结构与算法》上机测试题学号：______________姓名：______________课号：课名：数据结构与算法阅卷教师：__________成绩:_______________第1页共1页学号姓名注意事项：1.考试时间：3小时2.题目完成后以本人“学号”为目录名存放在本机的D盘上,例如“D:\074100101\”。3.请勿随意重启或关闭机器!4.请在以下题目中任选一题作答考题一如果将“大顶堆”的定义扩展为如下完全三叉树:(1)空树为堆;(2)根结点的值不小于所有子树根的值,且所有子树均为堆。要求用C/C++编程实现采用这种三阶堆的堆排序算法。考题二利用静态三元组表示稀疏矩阵，用C/C++编程实现两个稀疏矩阵的相加运算。输入包括两个稀疏矩阵的大小、非零元素个数、元素值，输出为两个矩阵的和。考题三假设K1，…，Kn是n个关键词，试解答：(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn时，用算法建立一棵以LLINK/RLINK链接表示的二叉查找树。(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为：该二叉查找树的嵌套括号表示结构为：B（A，D（C，E））。宁波大学学年第学期期中考试卷（1）学号：______________姓名：______________课号：课名：数据结构与算法阅卷教师：__________成绩:_______________第1页共2页学号姓名答案写在答题纸上一、单选题：（每小题2分，10小题，共20分）（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第10个元素的地址是_____________。A、100B、108C、110D、118（2）一个数组a[10],指针p,如果p指向a，那么*(p+1)+2是________A、a[3]B、a[5]C、a[2]+1D、a[1]+2（3）已知一个推入堆栈的字符序列顺序是a,b,c,d,e,下列哪个字符序列是不能得到的字符序列______。A、e,d,c,b,aB、d,e,c,b,aC、d,c,e,a,bD、a,b,c,d,e（4）如果推入一个队列的字符序列是a,b,c,d,e,那么队列的输出序列是_________。A、a,b,c,d,e;B、a,c,d,b,e;C、e,d,c,b,a;D、d,c,e,a,b;（5）下列是4个二叉树，请指出哪个是完全二叉树________。ABCD（6）下图是一个二叉树后序遍历的结果是________。A、abcdefB、cfabdeC、dbaecfD、cbfade(7)、线性表采用链式存储时，结点的存储地址________。A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续(8)、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较________个结点。A.nB.n/2C.(n–1)/2D.(n+1)/2(9)、设计一个判别表达式中左右括号是否配对的算法，采用________数据结构最佳。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈(10)、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是________。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;二、填空题（每空2分,共26分）1.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是____。{for(i=1;i=n;i++)for(j=1;j=i;j++)couti+j;}2.在双向链表中，每个结点有两个指针域，一个指向______，另一个指向_____。3.空格串是____，其长度等于____。4.稀疏矩阵的压缩存储结构，一种是表示法，而另一种是表示法。5.对于长度为n的关键字有序的线性表，若进行顺序查找，则时间复杂度为____；若采用二分法查找，则时间复杂度为____；6、链表适用于查找。7、队列的插入操作在进行，删除操作在进行。三、简答题:（39分）（1）一颗二叉树，如果前序遍历的结果是123456,中序遍历的结果是324651.请画出这颗二叉树.(7分)（2）:请用Prim算法画出下图的最小生成树的过程.(7分)宁波大学学年第学期期中考试卷（1）学号：______________姓名：______________课号：课名：数据结构与算法阅卷教师：__________成绩:_______________第2页共2页学号姓名（3）请根据序列{1002867213054180110138}画出二叉查找树.如果删除元素28，那么二叉树又是如何？(8分)（4）什么是B-树？有何特点？就下列关键字序列，建立一棵5阶B-树。(6分)（20，54，69，84，71，30，78，25，93，41，7，76）（5）下列函数是二叉排序树的什么算法？如果K值为5，针对下图所示二叉树，运行下列算法，输出是什么？比较几次得到结果？（4分）VoidBstree::Search(KeyTypeK){intflag=0;BstNode*q=root,*p=NULL;while((q!=NULL)&&(flag==0)){if(q-key==K)flag=1;elseif(Kq-key){p=q;q=q-lch;}else{p=q;q=q-rch;}}if(flag==0)cout\n查找失败，无此结点！\n;elsecout\n查找成功，找到：q-keyendl;}（6）假设用于通信的电文仅由6个字符组成，其频率分别为：11，9，13，15，29，23试为这6个字符设计哈夫曼编码，要求给出相应的哈夫曼树。（7分）四、算法设计题（15分）1.在一个带头结点的单链表中，查找值为X的结点。如果找到了，删除该结点；否则，输出“NO！”。（5分）2.写一算法，统计二叉树的结点的总个数。提示：主要算法采用递归算法（6分）；要求写出与之配套的主调函数（4分）。9Head716^59ACEBDF7852429宁波大学学年第学期期中考试卷（2）学号：______________姓名：______________课号：课名：数据结构与算法阅卷教师：__________成绩:_______________第1页共2页学号姓名答案写在答题纸上一、单选题：（每小题2分，9小题，共18分）（1）如果一个数组，首地址空间标号是20,每个元素占用4个字节,t那么第四个元素的地址空间为_______A、20B、26C、32D、38（2）一个数组a[10],指针p,如果p指向a，那么*(p+1)+2是________A、a[3]B、a[5]C、a[2]+1D、a[1]+2（3）已知插入堆栈的字符序列是a,b,c,d,e,下列________字符序列是堆栈不可能输出的。A、e,d,c,b,aB、d,e,c,b,aC、d,c,e,a,bD、a,b,c,d,e（4）下图二叉树的中序遍历结果是______。A、abcdefB、abdcefC、dbaecfD、dbefca（5）上图所示二叉树的前序遍历结果是_________。A、abcdefB、abdcefC、dbaecfD、dbefca（6）.推入一个队列的数字序列是2,1,3,4,5,那么队列的输出数字序列是_________。A、1,2,3,4,5;B、2,1,3,4,5;C、1,2,4,3,5;D、2,4,3,5,1;（7）．判定一个循环队列QU（最多元素为m0）为满队列的条件是。A．QU-front==QU-rearB．QU-front！==QU-rearC．QU-front==（QU-rear+1）％m0D．QU-front!==（QU-rear+1）％m0（8）．串是一种特殊的线性表，其特殊性体现在__________。A．可以顺序存储B.数据元素是一个字符C．可以链接存储D.数据元素可以是多个字符（9）．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足_______。A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树二、填空题（每题1分，共10分）1、在数据结构中，从逻辑上可以把数据结构分成___________和___________。2、在一个单链表中删除p所指结点时，应执行以下操作：(1)q=p-next;(2)p-data=p-next-data;(3)p-next=_________________;(4)_________________________;3、一个k层的完全二叉树最多有_______个结点，最少有_______个结点。4、对电文“dodoesdoordoors”进行哈夫曼编码，其哈夫曼树的结点个数为_______，该电文的总编码长度为_______。5、B+树有两个查找的入口指针，其中一个指向____________，另一个指向____________。三、简答题:（50分）1、已知二叉树T如右所示：（10分）（1）．画出T的先序线索二叉树；（4分）宁波大学学年第学期期中考试卷（2）学号：______________姓名：______________课号：课名：数据结构与算法阅卷教师：__________成绩:_______________第2页共2页学号姓名（2）．画出T对应的森林。（4分）2．简述以下算法的功能（5分）。StatusA(LinkedListL){//L是无表头结点的单链表if(L&&-next){Q=L;L=L-next;P=L;While(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnOK;}//A3．简述以下算法的功能（5分）。statusalgo2(StackS，inte){StackT；intd；InitStack(T)；while(!StackEmpty(S))｛Pop(S，d)；if(d!=e)Push(T，d)；}while(!StackEmpty(S))｛Pop(S，d)；Push(S，d)；}}4．设给定权集w={2，3，4，7，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。（10分）5．已知一个单链表L,函数converse倒置链表的结点.请在空白处正确填写代码。(10分)StructSLNode{DateTypedate;——————;};voidconverse(SLNode*head){SLNode*q,*p=head-next;head-next=NULL;while(______){_______;p=p-next;________;head-next=q;}}6、已知关键字值序列（53，27，58，36，22，42，80，77，72，25）。（共12分，每小题6分）（1）．关键字值序列是否为堆？若不是则将它调整为小顶堆；（2）．按上述关键字值次序构造一棵初始状态为空的二叉排序树；四、算法设计题（20分）1．请构造函数intfull(btree*bt),该函数判断一颗二叉树是否为满二叉树:（10分）Structbtree{DateTypedate;btree*left;btree*right;}2．以二叉链表作为存储结构，写出求二叉树中叶子结点数目的算法。（10分）宁波大学2008/2009学年第二学期考试卷（A）学号：______________姓名：______________课号：102J07A03课名：数据结构与算法阅卷教师：__________成绩:_______________第1页共4页学号姓名答案写在答题纸