中国的石油大学大数据的结构试的题目及问题解释

1、数据结构试题一、 单选题1、 在数据结构的讨论中把数据结构从逻辑上分为（）A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A必须是连续的B部分地址必须是连续的C一定是不连续的D可连续可不连续3、 采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。AnB n/2C （n-1）/2D （ n+1）/24、 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点 s，则执行（）。Astlink :=p link ;p link :=s;Bp link :=s;s link

2、 = q;CpTlink :=slink ;slink :=p；Dqlink :=s;s link = p;5、 如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。A起泡排序B 堆排序 C锦标赛排序D快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。A 求子串B模式匹配 C 串替换D 串连接7、在数组A中，每一个数组元素Aij 占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中 ，则存放该数组至少需要的存储字数是（）。A 80B 100C 240D 270&将一个递归算法改为对应的非递归算法时，通常需要使用（

3、）。A 栈B队列C循环队列D优先队列9、 一个队列的进队列顺序是1,2, 3, 4，则出队列顺序为（）。10、在循环队列中用数组 A0. m-1存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。A （ front - rear + 1） % mB （rear - front + 1） % mC （ front - rear + m） % mD （ rear - front + n） % m11、一个数组元素ai与（ ）的表示等价。A * （ a+i）B a+iC *a+iD &a+i12、若需要利用形参直接访问实参，则应把形参变量说明为（）参数。A指针B引

4、用C 值D变量13、下面程序段的时间复杂度为（）for (i nt i=0;im;i+)for (i nt j=0;j li nk=p;p-li nk=s;B s-li nk=p-li nk;p-li nk=s;C s-li nk=p-li nk;p=s;D p-li nk=s;s-li nk=p;19、 设单链表中结点结构为（data,link）.已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（）B q-li nk=s; s-li nk=pA s-li nk=p-li nk; p-li nk=s;C p-li nk=s-li nk;s-l

5、i nk=p; D p-li nk=s; s-li nk=q;20、设单链表中结点结构为（data,link）. 若想摘除结点*p的直接后继，则应执 行下列哪一个操作（）A p-li nk=p-li nk-li nk;B p=p-li nk; p-li nk=p-li nk-li nk;C p-li nk=p-li nk;D p=p-li nk-li nk;21、设单循环链表中结点的结构为（data,link ）,且rear是指向非空的带表头 结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪 一个操作（D ）A s=rear; rear=rear-li nk; delet

6、e s;B rear=rear-li nk; delete rear;C rear=rear-li nk-li nk; delete rear;D s=rear-link-link; rear-link-link=s-link; delete s;s 为第一个结点硫22、设单循环链表中结点的结构为（data,link ）,且first为指向链表表头的指 针，current为链表当前指针，在循环链表中 检测current是否达到链表表尾的 语句是（D ）。A curre nt-li nk =nullB first-li nk=curre ntC first=curre ntD curre nt-

7、li nk=first？ 23、一个栈的入栈序列为a，b，c，贝U出栈序列不可能的是（C ）。A c,b,a B b,a,c C c,a,b D a,c,b24、 栈的数组表示中，top为栈顶指针，栈空的条件是（A ）。A top=0 B top=maxSize Ctop=maxSize D top=-125、栈和队列的共同特点是（C ）。A都是先进后出B都是先进先出C 只允许在端点处插入和删除D没有共同点26、 假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为（D ）.A f+1= =rB叶仁=fC f= =0D f= =r27、当利用大小为n的数组顺序存储一个队

8、列时，该队列的最大长度为（A n-2B n-1C nD n+128、当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则 向这个栈插入一个元素时，首先应执行（）语句修改top指针。A top+;B top-;C top=0;D top;29、设链式栈中结点的结构为（data, link ）,且top是指向栈顶的指针。若想 摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（A ） 操作。A x=top-data; top=top-li nk;B top=top-li nk; x=top-data;C x=top; top=top-li nk;D x=top-da

9、ta;30、设循环队列的结构是：const int Maxsize=100;typedef int Data Type;typedef struct Data Type dataMaxsize;Int fron t, rear; Queue;若有一个Queue类型的队列Q,试问判断队列满的条件应是下列哪一个语句（D ）A Q.fro nt= = Q.rear;B Q.fro nt - Q.rear= = Maxsize;C Q.fro nt + Q.rear= = Maxsize;D Q.fro nt= = （Q.rea 叶1）% Maxsize;31、设有一个递归算法如下：int fact

10、(int n ) if (n =0) return 1;else return n *fact( n-1);下面正确的叙述是(B )A 计算fact(n)需要执行n次递归 B fact(7)=5040C此递归算法最多只能计算到fact(8) D以上结论都不对32、设有一个递归算法如下int x (int n) if (n=1）为（i-1）/2n ）.16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆 中，堆顶结点的值是所有结点中的（最小值）。17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为 LOC（a1）,那么，LOC（ai）=

11、 LOC（a1）+（i-1）*k。18、 在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（4）个字符编码。19、 设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为 0,若 设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1）个。20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。21、 以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序） 表。22、 已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二 叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235）23

12、、 对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理 想平衡树）。24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（5）,判定树中前5层的结点数为（3 1），最后一层的结点数为（19）。25、在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。在一个具有n个顶点的无向完全图中，包含有（n（n-1）/2）条边，在一个具有n个顶点的有向完全图中，包含有（n（n-1）条边。26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别 为（n）和（n-1 ）。27、 设线性表中元素的类型是实型，其首地址为1024,则线性表中第6个元素 的存储位置是

13、（1044）。28、 在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始 数据基本反序，则最好选择（选择排序）。29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。30、对于一个具有n个顶点肯e条边的无向图，进行拓朴排序时，总的进间为（n）31、 构造哈希函数有三种方法，分别为（平方取中）法、（除留余数）法、（折迭移 位）法。32、处理冲突的三种方法，分别为（线性探测）、（随机探测）、（链地址法）。33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成 树，其时间复杂度为（O（n2）、利用克鲁斯卡尔算法产生的最

14、小生成树， 其时间复杂度为（0（ elog 2e）34、 快速排序在平均情况下的时间复杂度为（0（ nlog2n），在最坏情况下的 时间复杂度为（0（n2）；快速排序在平均情况下的空间复杂度为 （O （log 2n）, 在最坏情况下的空间复杂度为（0（ n）。35、假定一组记录的排序码为（46,79,56,38,40,80） ，对其 进行归并排序的过程中，第二趟排序后的结果是（ 3 8 4 6 5 6 7 9 4080）36、假定一组记录的排序码为（46,79,56,38,40,80） ，对其进行快速排序的第一次划分的结果是 384 0 4 6 5 67 980）。37、 一个结点的子树的（个

15、数）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（零 ）的结点称为分支结点或非终端结点。 树中各结点度的（最大值 ）称为树的度。38、 设K=Kj（1v=i=n, 1=ji）且在排序前的序列中 R领先于R （i1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 答案：结点个数为n时，高度最小的树的高度为1,有2层；它有n-1个叶结点， 1个分支结点；高度最大的树的高度为 n-1,有n层；它有1个叶结点，n-1个分 支结点。6、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余

16、各 层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序 从1开始对全部结点进行编号，试问：(1) 各层的结点个数是多少？(2) 编号为i的结点的父结点(若存在)的编号是多少？(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少？(4) 编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？(5) 若结点个数为n,则高度h是n的什么函数关系？答案：(1) 各层的结点个数是ki (i=0,1,2,h)(2) 编号为i的结点的父结点(若存在)的编号是匚(i+k-2)/k(3) 编号为i的结点的第m个孩子结点(若存在)的编号是(i-1)*k+m+1(4) 当(i-1

17、)%k0时有右兄弟，右兄弟的编号为i+1(5) 若结点个数为n，贝U高度h和n的关系为：h=log k(n*(k-1)+1)-1 (n=0时 h=-1)9、题目：11、将下面的森林变换成二叉树(7分)。答案:答案:（7 分）（7 分）10、将算术表达式(a+b)+c*(d+e)+f)*(g+h)转化为二叉树答案：153315757712、将给定的图简化为最小的生成树，要求从顶点1出发13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05,0.29，0.07，0.08，0.14，0.23，0.03，0.11 试设计赫夫曼编码。答案：为方便起见，设各种字符的权值 w=5,29,7

18、,8,14,23,3,11。因为n=8,所以要构造的赫夫曼树共有 m=2n-1=2*8-仁15个结点。生成的赫夫曼树为下图所示：10012329011114853赫夫曼编码为：概率为0.23的字符编码为：00概率为0.11的字符编码为：010概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111概率为0.29的字符编码为：10概率为0.14的字符编码为：110概率为0.07的字符编码为：1110概率为0.08的字符编码为：111114、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIG J试画出这棵二叉树，并给出这棵二叉树的后序遍历序列

19、。所得二叉树如图:15、在结点个数为n(n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结 点？多少个分支结点?答案：结点个数为n时，高度最小的树的高度为1,有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为 n-1,有n层；它有1个叶结点，n-1个分 支结点。16、对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树,其最大高度是多少？最小高度是多少？ 答案：设高度为h(空树的高度为-1)的AVL树的最少结点为M，则M = F h+3 -1Fh是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3/2*log 2(n+1).最小咼度为log 2(n+1) n -1。17、7-7设有序顺序表中的元素依次为 017, 094, 154, 170