《2018年四川轻化工大学数据结构与算法考研真题》由会员分享，可在线阅读，更多相关《2018年四川轻化工大学数据结构与算法考研真题（9页珍藏版）》请在装配图网上搜索。
1、2018年四川轻化工大学数据结构与算法考研真题一、选择题（每题2分，共40分)。1.顺序表是线性表的（）。A链式存储结构；B.顺序存储结构；C.索引存储结构；D.散列存储结构。2.对于顺序表，以下说法错误的是（）。A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址；B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列；C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻；D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中。3.单链表的一个存储结点包含（）。A.数据域或指针域；B.指针域或链域；C.指针域和链域；D.数据域和链域。4.设指
2、针P指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画。A.p-prior-next-=p-next-next；B.p-prior-prior-=p-next-prior；C.p-prior-next-=p-next-prior；D.p-next-next=p-prior-prior。5.在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（）。A.real和rear-next-next；B.rear-next和rear；C.rear-next-next和rear；D.rear和rear-next。6.顺序查找法适合于（）存储结构的查找表。A.压缩；B.散
3、列；C.索引；D.顺序或链式。7.堆是一个键值序列k1,k2,kn,对i=1,2,|_n/2_|,满足()。A.kik2ik2i+1；B.kik2i+1data=x；_；p-next=s；2.以下是图的深度优先算法。请分析算法，并在_处填上适当的语句。voidLDFS(LGraph*lg,inti)/邻接表表示的图的递归深度优先遍历ArcNode*p；printf(%3d,i)；visitedi=1；p=lg-verticesi.firstarc；while(p)if(Visitedp-adjvex=0)LDFS(lg,p-adjvex)；3.以下为先序遍历二叉树非递归算法。请分析算法，并在_
4、处填上适当的语句。voidst_PreOrder(BiTNode*tree)LinkStacktop；top=NULL；while(tree!=NULL)printf(%c,tree-data)；if(tree-rchild!=NULL)Push(top,tree-rchild)；if(tree-lchild!=NULL)；Pop(top,tree)；4.以下是直接选择排序的算法。请分析算法，并在_处填上适当的语句。voidselect(listr,intn)for(i=1；i=n-1；i+)/*每次循环，选择出一个最小键值*/k=i；for(j=i+1；jnext；j+；if(i=j)ret
5、urn(p)；elsereturn(NULL)；四、综合题（每题10分，共50分）。1.见下图所示的森林：(1)求各树的前序序列和后序序列；（3分）(2)求森林的前序序列和后序序列；（3分）(3)将此森林转换为相应的二叉树。（4分）2.设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是22，15，2，5，17，11，9，19，试为这8个字母设计相应的哈夫曼编码。（要求写出过程）3.已知如下所示长度为12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度ASL。（5分）(2)若对表中元素先进行排序构成有序表,求其在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。(5分)4.对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。5.请用C语言编写表尾插入法建立带头结点的单链表的算法。StatusCreatLinkL(LinkList&L,intn,ElemType*E)/用表尾插入法建立带头结点的单链表
2018年四川轻化工大学数据结构与算法考研真题
