2018年四川轻化工大学数据结构与算法考研真题.doc-资料库

第1页 / 共9页

第2页 / 共9页

第3页 / 共9页

第4页 / 共9页

第5页 / 共9页

第6页 / 共9页

第7页 / 共9页

第8页 / 共9页

2018 年四川轻化工大学数据结构与算法考研真题一、选择题（每题 2 分，共 40 分)。 1.顺序表是线性表的（）。 A．链式存储结构；B.顺序存储结构； C.索引存储结构；D.散列存储结构。 2.对于顺序表，以下说法错误的是（）。 A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址； 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； 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.散列； C.索引；D.顺序或链式。 7.堆是一个键值序列{k1,k2,…,kn},对 i=1,2,…,|_n/2_|,满足()。 A.ki≤k2i≤k2i+1；B.ki

C.键值有序的顺序表；D.顺序表但键值不一定有序。 12.对于循环队列，下列说法错误的是（）。 A.可用顺序存储结构；B.会产生下溢； C.不会产生上溢；D.不会产生假溢出。 13.如果以链表作为栈的存储结构，则退栈操作时（）。 A.必须判别栈是否满；B.对栈不作任何判别； C.必须判别栈是否空；D.判别栈元素的类型。 14.二叉树第 i(i≥1)层最多有()个结点。 A．2i；B．2i； C．2i-1；D．2i-1。 15.以下不稳定的排序方法是（）。 A.直接插入排序；B.冒泡排序； C.直接选择排序；D.二路归并排序。 16.任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置()。 A.肯定发生变化；B.有时发生变化； C.肯定不发生变化；D.无法确定。 17.设二叉树有 n 个结点，则其深度为()。 A.n-1；B.n； C.5floor(log2n)；D.无法确定。 18.设深度为 k 的二叉树上只有度为 0 和度为 2 的节点，则这类二叉树上所含结点总数最少（）个。 A.k+1；B.2k； C.2k-1；D.2k+1。

19.以下时间复杂性不是 O(n2)的排序方法是（）。 A.直接插入排序；B.二路归并排序； C.冒泡排序；D.直接选择排序。 20.串的基本运算中，属于引用型运算的有（）。 A.ASSIGN(S,T)；B.INSERT(S1,i,S2)； C.DELETE(S,i,j)；D.SUBSTR(S,i,j)。二、填空题（每题 2 分，共 30 分）。 1.数据结构有线性结构、树结构、等几种逻辑结构。 2.所有结点按 1 对 1 的邻接关系构成的整体就是结构。 3.如果指针 p 指向一棵二叉树的一个结点，则判断 p 没有左孩子的逻辑表达式为。 4.循环队列的引入，目的是为了克服。 5.具有 354 个结点的完全二叉树深度为。 6.在单链表中，指针 p 所指结点为最后一个结点的条件是。 7.队列是一种的结构（要求填特性）。 8.对有向非网络图，顶点 Vi 的出度是第 i______非零的数据元素之和。 9.顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为________。 10.直接插入排序的时间复杂度是。 11.对无向图，其邻接矩阵是一个关于对称的矩阵。 12.由转换成二叉树时，其根结点的右子树总是空的。 13.已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点，则该树中有个叶子的结点。 14.树有三种常用的存储结构，即孩子链表表示法、孩子兄弟链表表示法

和。 15.一个数组的长度为 20，用于存放一个循环队列，则队列最多只能有个元素。三、算法阅读填空题（每题 5 分，共 30 分）。 1.以下为单链表的插入运算。请分析算法，并在____处填上正确的语句。 voidinsert_lklist(lklisthead,datatypex,inti) /*在表 head 的第 i 个位置上插入一个以 x 为值的新结点*/ {p=find_lklist(head,i-1)； if(p==NULL)error(“不存在第 i 个位置”)； else{s=mailloc(size)；s->data=x； ________________________； p->next=s； } } 2.以下是图的深度优先算法。请分析算法，并在____处填上适当的语句。 voidLDFS(LGraph*lg,inti) //邻接表表示的图的递归深度优先遍历 { ArcNode*p； printf("%3d",i)； visited[i]=1； p=lg->vertices[i].firstarc；

while(p){ if(Visited[p->adjvex]==0) LDFS(lg,p->adjvex)；； } 3.以下为先序遍历二叉树非递归算法。请分析算法，并在____处填上适当的语句。 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；j<=n；j++)if()k=j； if(_k!=I)swap(r[k],r[i]）；/*函数 swap(r[k],r[i]）交换 r[k]和 r[i]的位置*/ } } 5.程序段的功能是利用 tmp 栈将一个非空栈 s1 的所有元素按原样复制到一个栈 s2 当中去，请在处填上正确的语句。 SeqStackS1,S2,tmp； DataTypex； ...//假设栈 tmp 和 S2 已做过初始化 while(!StackEmpty(&S1)) { x=Pop(&S1)； } while(!StackEmpty(&tmp)) { x=Pop(&tmp)； Push(&S1,x)； Push(&S2,x)； } 6.以下为单链表按序号查找的运算。请分析算法，并在____处填上正确的语句。 pointerfind_lklist(lklisthead,inti)

{p=head；j=0； while(_______________) {p=p->next；j++；} if(i==j)return(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 分)

资料库

2018年四川轻化工大学数据结构与算法考研真题.doc

相关推荐

考研

热门标签

最新资料