搜索
第1页共6页三峡大学2017年研究生入学考试试题(A卷)科目代码：836科目名称：数据结构考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、填空题（每空2分，共20分）1）__________是组成数据的基本单位，是数据集合的个体。2）数据结构的存储结构分为顺序存储结构和__________两种。3）如下程序段:for(i=1;i=9;i++)for(j=i+1;j=10;j++)x++;其中语句x++执行的次数为__________。4)在带头结点循环单链表L（L同时表示头指针，结点指针域用next表示）中，判断指针p所指结点是否为表尾结点的条件是__________。5）当两个对顶栈共享一个存储区时，可利用一维数组stack[M]实现（下标从0到M-1），两个栈的栈顶指针分别为top[1]和top[2]，则栈满的条件是__________。6）若用一个大小为6的数组来实现循环队列，且当前的rear和front的值分别为0和3，当从队列中删除2个元素后，再加入3个元素后，rear的值为______。7）设一个哈希表表长M为200，用除留余数法构造哈希函数，及H（K）=K%P，为使函数具有较好性能，P应选_________。8）在树结构中，一个结点的子树个数称为此结点的_________。9）图遍历中的两种主要遍历方法分别是_________和广度优先搜索。10）为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的_________。第2页二、单项选择题（每小题3分，共30分）1）有一个带头结点的单链表L，则判断其是否为空链表的条件是（）A.L==NULLB.L-next==NULLC.L-next==LD.L!=NULL2）若线性表最常用的操作是存取第i个元素及其前驱的值，可采用（）存储方式最节省时间。A.单向链表B.双向链表C.单向循环链表D.顺序表3）某个栈的入栈的序列为A,B,C,D,E,F,G，则可能的出栈序列为（）A.ABCDEFGB.GABCDEFC.DCBAGEFD.BAFDCEG4）评价一个算法性能好坏的重要标准是（）A.算法易于调试B.算法易于理解C.算法的正确性D.算法的时间复杂度5）已知哈希表的长度m=20，哈希函数H(key)=key%19，关键字为k的记录在定位时产生了冲突，若采用开放定址解决冲突，则新地址的计算公式为（）A.(H(k)+di)%20B.(H(k)+di)%19C.(H(k)+di)/19D.(H(k)+di)/206）栈和队列的共同特点是（）A.只允许在端点处插入和删除元素B.都是先进后出C.都是后进先出D.没有共同点7）以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树8）链表不具备的特点是（）A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比9）与单链表相比，双链表的优点之一是（）A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活10）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）A.O(0)B.O(1)C.O(n)D.O(n2)第3页三、简答题（每小题10分，共50分）1、给出四种基本数据结构名称及其关系图示。2、数据结构研究内容主要包括数据的逻辑结构和数据的物理结构。请分别简述逻辑结构和物理结构的含义，并简要指出线性表的两种常见物理结构。3、已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。中序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA4、给定表（19，14，22，15，20，21，56，10）1）按元素在表中的次序，建立一棵二叉排序树；2）对1）中所建立的二叉排序树进行中序遍历，写出遍历序列；5、已知一维数组中的数据为（18，12，25，53，18），1）试写出插入排序（升序）过程，2）并指出具有n个元素的插入排序的时间复杂度是多少？四、构造题（共30分）1、对以下关键字序列建立一个长度为20的哈希表（ZuoPing,ZuoWencheng,LiuJinqiao,LiMengting,LiWeiwen,ZhuZequn,WanQiubo），哈希函数为H(K)=(K中第一个字母在字母表中的序号)%19，用线性探测法解决冲突。要求给出如下结果：1）计算出每个关键字对应的哈希地址，如果有冲突，需要给出线性探测法解决冲突后的哈希地址。需要给出每个哈希地址的计算过程，并绘制构造好的哈希表。2）计算在等概率情况下查找成功时的平均查找长度。五、编程完善程序（共20分）下列c语言编写的程序，主要完成如下功能：1）初始化三个带头结点的单链表La，Lb，Lc；2）连续读入一组整数（比如123-1-2-34-4-550），并将非零整数第4页依次存储在单链表La中（注意：碰到第一个0结束输入）；3）将La分解成两个带头结点的单链表Lb和Lc，其中Lb中存放负整数，Lc中存放正整数。要求Lb和Lc利用La中的结点空间。4）在分解后，能显示Lb中所有的负整数，Lc中所有的正整数。请根据上述已知条件，并结合下面的代码，完成下面三个问题：1）在voidDisplayList(LinkListL)函数体中，写出代码，使之能显示单链表L中的数据元素；2）voidDivideList(LinkListLa,LinkListLb,LinkListLc)函数体中，写出代码，使之能将La分解成满足上述要求的Lb和Lc。3）假定在主函数中调用CreateFromTail(La)时，输入的整数系列是：123-1-2-34-4-550，请给出主函数调用DivideList(La,Lb,Lc);后，调用DisplayList(Lb);和DisplayList(Lc);后的屏幕输出结果。//----------------------------------------------代码-------------------------------------------------#includestdio.h#includestdlib.h#defineElemTypeintstructtag_node/*结点类型定义*/{ElemTypedata;structtag_node*next;};typedefstructtag_nodeNode;typedefstructtag_node*LinkList;voidInitList(LinkList*L);voidCreateFromTail(LinkListL);voidDisplayList(LinkListL);voidDivideList(LinkListLa,LinkListLb,LinkListLc);第5页main(){LinkListLa,Lb,Lc;InitList(&La);//初始化单链表LaInitList(&Lb);//初始化单链表LbInitList(&Lc);//初始化单链表Lcprintf(构造链表La:请输入一系列整数，并以输入整数0结束输入\n);CreateFromTail(La);//输入数据，构造单链表LaDivideList(La,Lb,Lc);//将La分解成Lb和Lcprintf(\nAfterdividing:);DisplayList(Lb);//显示LbDisplayList(Lc);//显示Lc}voidInitList(LinkList*L){*L=(LinkList)malloc(sizeof(Node));(*L)-next=NULL;}voidCreateFromTail(LinkListL){Node*r,*s;intc;intflag=1;r=L;while(flag)/*flag初值为1，当输入0时，置flag为0，建表结束*/{scanf(%d,&c);if(c!=0){s=(Node*)malloc(sizeof(Node));/*建立新结点s*/s-data=c;r-next=s;第6页r=s;}else{flag=0;s-next=NULL;}}}voidDisplayList(LinkListL){//请写出代码，实现显示单链表L中所有数据元素的功能//注意，答案写在答题纸上}voidDivideList(LinkListLa,LinkListLb,LinkListLc){//请写出代码，实现将La分解成两个带头结点的单链表Lb和Lc的功能//注意，答案写在答题纸上}//第3问的答案也写在答题纸上