搜索
浙江大学远程教育学院试题卷B卷课程名称数据结构与算法教学站年级专业(层次)学号姓名注意：所有试题答案均按题目编号写在答题卷上。一.单项选择题（每项选择1.5分，共60分）1、数据结构形式地定义为（D，S），其中D是①的有限集合，S是D上的②的有限集合。①A.算法B.数据元素C.逻辑结构D.数据操作②A.结构B.操作C.存储D.关系2、计算机算法是指①，它必须具备输入、输出和②等五个特性。①A.计算方法B.排序方法C.调度方法D.解决问题的有限运算序列②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、稳定性和有穷性D.易读性、稳定性和安全性3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。①A.必须是连续的B.部分地址必须是连续的C.连续或者不连续都可以D.一定是不连续的4、线性表的逻辑顺序和存储顺序总是一致的，这种说法①。①A.不正确B.正确5、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的出栈序列是①。①A.edcbaB.decbaC.dceabD.abcde6、判断一个循环队列Q(最多元素为MAXQSIZE)为空队列的条件是①，为满队列的条件是②。A.Q.front==Q.rearB.Q.front!=Q.rearC.Q.front==(Q.rear+1)%MAXQSIZED.Q.rear==(Q.front+1)%MAXQSIZE7、一个一维数组第一个存储单元的地址是100，每个元素的长度是4，则它的第5个元素的地址是①。①A.120B.116C.110D.1048、某语言采用低下标优先方式存放数组元素，数组下标从1开始。设维数为（5,6,7）的数组A5x6x7的起始存储地址为Loc[1][1][1]=1000，每个数组元素占用4个字节。则元素A[3][4][5]所在的地址Loc[3][4][5]=①。①A.1692B.1636C.1436D.1173E.1159F.11099、设有三对角矩阵（aij）nxn（1=i,j=n），将其三条对角线上的元素存于数组B[3][n]中，使得：B[u][v]=aij（0=u=2,0=v=n-1）。并且已知B[0][1]至B[0][n-1]依次存放上对角线元素，B[1][0]至B[1][n-1]依次存放主对角线元素，B[2][0]至B[2][n-2]依次存放下对角线元素。请问：B[1][4]所对应的元素aij的下标是①，a67所对应的B中的下标是②。①A.i=1,j=4B.i=4,j=1C.i=4,j=4D.i=5,j=5②A.u=0,v=6B.u=0,v=7C.u=6,v=7D.u=1,v=710、不带头结点的单链表L为空表的判定条件是①。①A.L==NULLB.L-next==NULLC.L!=NULLD.L-next==L11、在一个单链表L中，已知q所指结点是p所指结点的前驱结点，若要在q和p结点之间插入s结点，则执行①。①A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;12、假设双向链表结点的类型如下：typedefstructDlinkNode{intdata;/*数据域*/structDlinkNode*prior;/*指向前驱结点的指针域*/structDlinkNode*next;/*指向后继结点的指针域*/}bnode;在一个双向循环链表的p所指结点后插入s结点，则执行①。①A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;13、设有两个串p和q，求q在p中首次出现的位置的运算称为①。①A.连接B.模式匹配C.求子串D.求串长14、设串s1=“ABCDEFG”,s2=”PQRST”，函数Concat(x,y)返回x和y的连接串，Subs(s,i,j)返回串s的从序号i的字母开始的j个字符组成的子串，Length(s)返回串s的长度，则下面函数Concat(Subs(s1,2,Length(s2)),Subs(s2,Length(s2),2))的结果串是①。①A.BCDEFB.BCDEFTD.BCPQRSTD.BCDEFEF15、设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为①。①A.2h-1B.2hD.2h+1D.h16、如果某二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历序列是①。①A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca17、树最适合用来表示①。①A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据18、具有五层结点的平衡二叉树至少有①个结点。①A.10B.12C.15D.1719、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中，①是正确的。①A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对20、线索二叉树是一种①结构。①A.逻辑B.逻辑和存储C.线性D.物理21、下图所示的二叉树中，①不是完全二叉树。22、常对数组元素进行的两种基本操作是①。①A.建立与删除B.索引与修改C.查找与删除D.查找与修改23、在一个无向图中，所有顶点的度数之和等于所有边数的①倍。①A.1/2B.1C.2D.424、具有4个顶点的无向完全图有①条边。①A.6B.12C.16D.2025、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为①；邻接表中所有结点总数是②。①A.nB.n+1C.n-1D.n+e②A.e/2B.2eC.eD.n+e26、关于有向图的邻接表和逆邻接表表示法，下列结论①比较正确。①A.用邻接表表示法计算入度比较方便B.用邻接表表示法计算入度和出度都方便C.用逆邻接表表示法计算入度和出度都不方便D.用逆邻接表表示法计算入度比计算出度方便27、已知一个图如下图所示，从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为①；按广度优先搜索法进行遍历，则可能得到的一种顶点序列为②。①A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,b28、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为①。①A.nB.(n+1)/2C.n/2D.(n-1)/229、在待排序的元素序列基本有序的前提下，效率最高的排序方法是①。①A.插入排序B.快速排序C.归并排序D.选择排序30、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为①。①A.希尔排序B.归并排序C.插入排序D.选择排序31、一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为①。①A.38，40，46，56，79，84B.38，46，56，79，40，84C.38，40，56，79，46，84D.46，38，56，79，40，8432、快速排序方法在①情况下最不利于发挥其长处。①A.要排序的数据量太大B.要排序的数据在含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数33、堆栈和队列的共同点是①。①A.只允许在端点处插入和删除B.都是先进先出C.都是先进后出D.没有共同点34、一棵二叉树是下列四种树之一，且只有度为0和度为2的结点，那么它是①。①A.完全二叉树B.二叉排序树C.堆D.最优树二.填空题（将正确的答案填在相应的空位中,每空1-2分，共20分）1、设m和n为正整数，下面程序段中前置以记号@的语句的频度是①。for(i=0;in;i++){for(j=i;jm;j++)@a[i][j]=0;}2、向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动①个元素。3、把递归算法改为非递归算法，通常需要增加使用一个①的存储结构。4、两个串相等的充分必要条件是①。5、对一个下三角矩阵A，采用压缩存储方式存储在一维数组S[1..n*(n+1)/2]中（以行序为主序，且A[0][0]=S[1]）,则A[i][j]对应S中的位置是①。6、已知一棵树边的集合是{f,g,a,d,c,f,c,e,a,b,f,h,d,i,a,c}。那么根结点是①，结点g的双亲是②，结点c的子孙有③，树的深度是④，树的度是⑤，结点h的层次是⑥。7、n个顶点的连通图至少有①条边。8、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，不稳定的排序有①等几种。三.分析计算题（每题5分，共20分）1、简述以下关于二叉树某操作的算法的功能和主要思想。typedefstructBiTNode{chardata;//结点信息是字符structBiTNode*lchild,*rchild;//左右孩子指针}*BiTree;Statusxxxx(BiTreeT,Status(*Visit)(chare)){TStackS;BiTreep;InitStack(S);if(T)Push(S,T);while(!StackEmpty(S)){Pop(S,p);Visit(p-data);if(p-lchild)Push(S,p-lchild);if(p-rchild)Push(S,p-rchild);}returnOK;}2、令有串u=”baabaca”和v=”abcaabbaabcabaabc”，分别求出u,v作为模式串时在KMP算法中各自的next[j]值（如下面表1和表2所示）。j1234567u[j]baabacanext[j]表1j1234567891011121314151617v[j]abcaabbaabcabaabcnext[j]表23、设无向网络图G的邻接矩阵的上三角部分如下表，请回答：（1）画出该网络图；（2）求该网络图的最小生成树(只要给出生成树即可)；（3）给出从顶点V5出发深度优先搜索遍历该图的顶点序列（顶点标号小者优先）。V1V2V3V4V5V6V7V1∞18∞∞2346V2∞5812∞∞V3∞10∞∞∞G:V4∞1520∞V5∞25∞V6∞7V7∞4、已知序列{503，61，512，87，908，170，897，275}，请给出采用快速排序法对该序列作升序排列时每一趟的结果。