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

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<k2i+1<k2i； C.ki≤k2i 且 ki≤k2i+1(2i+1≤n)；D.ki≤k2i 或 ki≤k2i+1(2i+1≤n)。 8.以下说法错误的是()。 A.一般在哈夫曼树中，权值越大的叶子结点离根结点越近； B.哈夫曼树中没有度数为 1 的分支结点； C.若初始森林中共有 n 棵二叉树，最终求得的哈夫曼树共有 2n-1 个结点； D.若初始森林中共有 n 棵二叉树，进行 2n-1 次合并后才能剩下一棵最终的哈夫曼树。 9.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是 （）。 A.acbed；B.deabc； C.decab；D.cedba。 10.设有一个无向图 G= （V，E）和G’= （V’，E’）如果G’为G 的生成树，则下面不正 确的说法是（）。 A.G’为G 的子图；B.G’为G 的连通分量； C.G’为G 的极小连通子图且V’=V；D.G’为G 的一个无环子图。 11.折半查找要求被查找的表是（）。 A.键值有序的链接表；B.链接表但键值不一定有序； 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