一、单项选择题1．连续存储设计时，存储单元的地址（）。 A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续2．以下属于逻辑结构的是（）。 A．顺序表B.哈希表C.有序表D.单链表3.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。 A.BA+B.BA+C.BA+D.BA+．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。 A．O（i）B．O（1）C．O（n）D．O（i-1）7．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。 A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL8.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是()。A.iB.n-iC.n-i+1D.不确定9.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）。 A.B.C.D..散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。 A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理 二、填空题1．数据的物理结构包括的表示和的表示。2．数据结构中评价算法的两个重要指标是。3．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。4．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。5．在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动________个元素。6．链接存储的特点是利用________来表示数据元素之间的逻辑关系。7.一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。8．区分循环队列的满与空，只有两种方法，它们是______和______。三、判断题1．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()2.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。()3.稀疏矩阵压缩存储后，必会失去随机存取功能。（）4.数组是同类型值的集合。（）5.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（）6.稀疏矩阵压缩存储后，必会失去随机存取功能。（）7.二维以上的数组其实是一种特殊的广义表。（）8.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。（）三、解答题1.数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3.有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？四、程序阅读题1.请阅读以下程序，写出此程序所要完成的功能，及时间复杂度。int while(jA.lengthjB.length) if(A.elem[j]B.elem[j])return(-1); elseif(A.elem[j]B.elem[j])return(1); elsej++; if(A.length==B.length)return(0); elseif(A.lengthB.length)return(-1); elsereturn(1); }2.将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;if(bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q);q=(1)_;p-rchild=(2)___;(3)___=q; if(p-lchild)(4)___;if(p-rchild)(5)___; } } }五、算法设计题1．写出广度优先搜索遍历的遍历算法。
数据结构模拟试题1参考答案一、选择题（20分）1-5ABCAC6-10DDCBB二、填空题（20分）l．(n-2)(n+3)/22．n0=n2+13．．n1-1n2+n35．．直接插入排序和冒泡排序三、判断题（10分） 1．×2．× 3．√4．√5．× 6．√7．√8．×9．×10．√四、应用题（20分） 1．参考答案如下： 2．参考答案如下： 3．参考答案如下： 4．参考答案如下： 1） 2）带权路径长度 5．参考答案如下： 1）ABCDEG 2）ABCEDG 6．参考答案如下： 五、算法设计题（30分） 1．算法源代码如下：intflag=1;intmax;voidsortbitree(bitreeT){if(T){sortbitree(T-lchild);k++;if(k==1)max=T-data;else{if(T-datamax)max=T-data;elseflag=0;}sortbitree(T-rchild);}} 2．算法源代码如下：intpathed[MAX_VERTEX_NUM];inttop=0;intpath[MAX_VERTEX_NUM];intispath(algraphgraph,intvi,intvj){arcptrp;intj;pathed[vi]=1;path[++top]=vi;/*将顶点vi加入当前路径path*/if(path[top]==vj)/*存在顶点vi到顶点vj的路径*/return1;else/*将顶点vi的邻接点加入当前路径*/for(p=graph.vertices[vi].firstarc;p;p=p-nextarc)if(!pathed[p-adjvex])returnispath(graph,p-adjvex,vj);pathed[vi]=0;top--;/*将顶点vi从当前路径path中删除*/if(top==0)return0;/*不存在vi到vj的简单路径*/} 3．算法源代码如下：bithrtreeinsucc(bithrtreep)/*找p结点的后继*/{if(p-rtag==1)/*后继线索*/returnp-rchild;else/*右子树的最左下结点*/{p=p-rchild;while(p-ltag==0)p=p-lchild;returnp;}}
白殿疯图片青少年白癜风