1、第 1 页 共 7 页四川理工学院四川理工学院 2019 年研究生入学考试业务课年研究生入学考试业务课样卷样卷（满分：（满分：150 分，所有答案一律写在答题纸上）分，所有答案一律写在答题纸上）招生专业：招生专业：0811 控制科学与工程、控制科学与工程、085210 控制工程控制工程考试科目：数据结构与算法考试科目：数据结构与算法考试时间：考试时间：3 小时小时一、一、选择题选择题（每题每题 2 2 分，共分，共 4040 分分)。1.顺序表是线性表的（）。A链式存储结构；B.顺序存储结构；C.索引存储结构；D.散列存储结构。2.对于顺序表，以下说法错误的是（）。A.顺序表是用一维数组实现的
2、线性表，数组的下标可以看成是元素的绝对地址；B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列；C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻；D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中。3.单链表的一个存储结点包含（）。A.数据域或指针域；B.指针域或链域；C.指针域和链域；D.数据域和链域。4.设指针 P 指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画。A.p-prior-next-=p-next-next；B.p-prior-prior-=p-next-prior；C.p-prior-next-=p-next-prior；
3、D.p-next-next=p-prior-prior。5.在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（）。A.real 和 rear-next-next；第 2 页 共 7 页B.rear-next 和 rear；C.rear-next-next 和 rear；D.rear 和 rear-next。6.顺序查找法适合于（）存储结构的查找表。A.压缩；B.散列；C.索引；D.顺序或链式。7.堆是一个键值序列k1,k2,kn,对 i=1,2,|_n/2_|,满足()。A.kik2ik2i+1；B.kik2i+1data=x；p-next=s；第 5 页 共
4、 7 页2 2.以下是图的深度优先算法。请分析算法，并在_处填上适当的语句。void LDFS(LGraph*lg,int i)/邻接表表示的图的递归深度优先遍历ArcNode*p；printf(%3d,i)；visitedi=1；p=lg-verticesi.firstarc；while(p)if(Visited p-adjvex=0)LDFS(lg,p-adjvex)；3 3.以下为先序遍历二叉树非递归算法。请分析算法，并在_处填上适当的语句。void st_PreOrder(BiTNode*tree)LinkStack top；top=NULL；while(tree!=NULL)prin
5、tf(%c,tree-data)；if(tree-rchild!=NULL)Push(top,tree-rchild)；if(tree-lchild!=NULL)；Pop(top,tree)；4.以下是直接选择排序的算法。请分析算法，并在_处填上适当的语句。void select(list r,int n)for(i=1；i=n-1；i+)/*每次循环，选择出一个最小键值*/k=i；for(j=i+1；jnext；j+；if(i=j)return(p)；else return(NULL)；四、综合题四、综合题（每题每题 1010 分，共分，共 5050 分分）。1.见下图所示的森林：第 7 页
6、 共 7 页(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,int n,ElemType*E)/用表尾插入法建立带头结点的单链表第 7 页 共 6 页1
