北大18秋08281006-数据结构发（资料）

同学情 · 发表于 2018-10-27 20:36:09

【北京大学】08281006-数据结构
试卷总分:100 得分:100
第1题,[单选题]（第一章）数据的逻辑结构被形式地定义为B=(K,R),其中K是 ______的有限集合。
A:存储
B:数据操作
C:数据元素
D:操作
E:逻辑结构
F:映象
G:算法
:关系
:
正确资料:

第2题,[单选题]（第一章）数据的逻辑结构被形式地定义为B=(K,R),其中R是K上的______的有限集合。

A:存储
B:数据操作
C:数据元素
D:操作
E:逻辑结构
F:映象
G:算法
:关系
:
正确资料:

第3题,[单选题]（第一章）以下关于算法的说法不正确的是______________。
A:一个算法应包含有限个步骤
B:算法越简单越好
C:算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之
D:算法中的每个步骤都能在有限时间内完成
E:
正确资料:

第4题,[单选题]（第一章）设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是______________。
A:线性结构
B:树型结构
C:物理结构
D:图型结构
E:
正确资料:

第5题,[单选题]
（第一章）下面程序段的时间复杂度为______


int sum=0; 
     for(i=0; i<m;i++) 
         for(j=i;j<n;j++) 
    s++;

A:O(m+n)
B:O(n*n)
C:O(m*n)
D:O(m*logn)
E:
正确资料:

第6题,[单选题]（第二章）下列有关线性表的叙述中，正确的是________。
A:一个线性表是 n 个数据元素的有限序列
B:线性表中任何一个元素有且仅有一个直接前驱
C:线性表中任何一个元素有且仅有一个直接后继
D:以上说法都不正确
E:
正确资料:

第7题,[单选题]（第二章）在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为______
A:n
B

n-1)/2
C:n/2
D

n+1)/2
E:
正确资料:

第8题,[单选题]（第四章）若栈采用链式存储结构,则下面的说法中正确的是________
A:不需要判断栈满但需要判断栈是否为空
B:需要判断栈是否栈空与栈满
C:需要判断栈满但不需要判断栈空
D:栈满栈空都不需要判断
E:
正确资料:

第9题,[单选题]（第四章）在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为____________。
A:t-next=r;t=r;
B:r-next=s;s=r;
C:s-next=r;s=r;
D:r-next=t;
E:
正确资料:

第10题,[单选题]（第二章）链表不具备的特点是____________。
A:不必事先估计存储空间
B:插入删除不需要移动元素
C:可顺序访问任一结点
D:所需空间与其长度无关
E:
正确资料:

第11题,[单选题]（第二章）带附加头结点的双循环链表L为空表的条件是____________。
A

==NULL
B

-next==NULL
C

-prior==L
D

-prior==NULL
E:
正确资料:

第12题,[单选题]（第三章）设广义表L=（a,（b,c,d））,则L的长度与深度分别为____________。
A:1和3
B:1和2
C:2和3
D:2和2
E:
正确资料:

第13题,[单选题]（第四章）一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列______
A:1, 2, 3, 4, 5, 6
B:3, 2, 6, 4, 5, 1
C:2, 4, 6, 5, 3, 1
D:6, 5, 4, 3, 2, 1
E:
正确资料:

第14题,[单选题]（第四章）循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____________。
A

rear-front+m)%m
B:rear-front+1
C:rear-front-1
D:rear-front
E:
正确资料:

第15题,[单选题]（第四章）栈和队列的共同特点是____________。
A:只允许在端点处插入和删除元素
B:都是先进后出
C:都是先进先出
D:没有共同点
E:
正确资料:

第16题,[单选题]（第四章）中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是______
A:AB+D*E/FA+*DC+
B:ABD*+EFAD*+/C+
C:ABDEFADC+*+/+*+
D:AB+D*EFAD*+/+C+
E:
正确资料:

第17题,[单选题]（第五章）如下图所示的4棵二叉树，_________不是完全二叉树。
A:img alt="" src="../fileroot/question/bfd78753-572d-4312-8c8e-1ddf47b25f18/image/20170216/20170216172821_2376.jpg" /
B:img alt="" src="../fileroot/question/bfd78753-572d-4312-8c8e-1ddf47b25f18/image/20170216/20170216172831_7292.jpg" /
C:img alt="" src="../fileroot/question/bfd78753-572d-4312-8c8e-1ddf47b25f18/image/20170216/20170216172844_4160.jpg" /
D:img alt="" src="../fileroot/question/bfd78753-572d-4312-8c8e-1ddf47b25f18/image/20170216/20170216172856_5846.jpg" /
E:
正确资料:

第18题,[单选题]（第五章）设某棵二叉树中有2000个结点，则该二叉树的最小高度为____________。
A:9
B:10
C:11
D:12
E:
正确资料:

第19题,[单选题]（第五章）深度为6(根的层次为1)的二叉树至多有__________结点
A:64
B:63
C:31
D:32
E:
正确资料:

第20题,[单选题]（第五章）二叉树的第k层的结点数最多为____________。
A:2supk/sup-1
B:2k+1
C:2k-1
D:2supk-1/sup
E:
正确资料:

第21题,[单选题]（第五章）如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是__________。
A:空或只有一个结点
B:高度等于其结点数
C:任一结点无右孩子
D:任一结点无左孩子
E:
正确资料:

第22题,[单选题]（第五章）树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论__________是正确的。
A:树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B:树的后根遍历序列与其对应的二叉树的先序遍历序列相同
C:树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D:以上都不对
E:
正确资料:

第23题,[单选题]（第六章）根据使用频率为5个字符设计的哈夫曼编码不可能是____________。
A:100，111，110，101，0
B:111，110，10，01，00
C:000，001，010，011，01
D:001，000，01，11，10
E:
正确资料:

第24题,[单选题]（第六章）下列数据结构中,不属于二叉树的是____________
A:堆
B:哈夫曼树
C:线索二叉树
D:B树
E:
正确资料:

第25题,[单选题]（第七章）采用邻接表存储的图的广度优先遍历算法类似于二叉树的__________。
A:先序遍历
B:中序遍历
C:后序遍历
D:层次遍历
E:
正确资料:

第26题,[单选题]（第七章）对用邻接表表示的图进行深度优先遍历时，通常是借助_________来实现算法。
A:队列
B:栈
C:树
D:图
E:
正确资料:

第27题,[单选题]（第七章）在一个图中，所有顶点的度数之和等于图的边数的_________倍。
A:1/2
B:1
C:2
D:4
E:
正确资料:

第28题,[单选题]（第九章）对线性表进行二分查找，要求线性表必须____________。
A:以顺序方式存储
B:以顺序方式存储，且结点按关键字有序排序
C:以链接方式存储
D:结点按关键字有序排序，存储方式无所谓
E:
正确资料:

第29题,[单选题]（第十章）排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为____________。
A:选择排序
B:冒泡排序
C:希尔排序
D:插入排序
E:
正确资料:

第30题,[单选题]（第十章）下列四种排序中，____________是空间复杂度最大的。
A:选择排序
B:冒泡排序
C:归并排序
D:快速排序
E:
正确资料:

第31题,[谋学网（www.mouxue.com）]（第一章）数据结构分为___和物理结构两种结构。
正确资料:

第32题,[谋学网（www.mouxue.com）]（第一章）线性结构中元素之间存在一对一关系，而图形结构中元素之间存在___关系。
正确资料:

第33题,[谋学网（www.mouxue.com）]（第一章）线性结构中元素之间存在一对一关系，而树形结构中元素之间存在___关系。
正确资料:

第34题,[谋学网（www.mouxue.com）]（第一章）一个算法的最基本的原操作执行次数为(3n2+2nlog2n+4n-7)/(7n),则该算法的时间复杂度为___。
正确资料:

第35题,[谋学网（www.mouxue.com）]（第二章）链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过___间接地反映。
正确资料:

第36题,[谋学网（www.mouxue.com）]（第二章）向一个长度为n的顺序表中的第i个元素(1≤i≤n)之后插入一个元素时，需向后移动___个元素。
正确资料:

第37题,[谋学网（www.mouxue.com）]（第二章）当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用___存储结构。
正确资料:

第38题,[谋学网（www.mouxue.com）]（第二章）在单链表中，要删除某一指定的结点，必须找到该结点的___结点。
正确资料:

第39题,[谋学网（www.mouxue.com）]（第二章）删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行以下操作：
第一步 q=___;
正确资料:

第40题,[谋学网（www.mouxue.com）]（第二章）第二步 p->next=___;
正确资料:

第41题,[谋学网（www.mouxue.com）]（第二章）第三步 ___;
正确资料:

第42题,[谋学网（www.mouxue.com）]（第三章）设广义表L=（（a,b,c））,则L的长度为___。
正确资料:

第43题,[谋学网（www.mouxue.com）]（第三章）设广义表L=（（a,b,c））,则L的深度为___。
正确资料:

第44题,[谋学网（www.mouxue.com）]（第四章）栈的特点是，与之对应后进先出，队列的特点是___。
正确资料:

第45题,[谋学网（www.mouxue.com）]（第四章）在栈顶进行插入删除一个元素的时间复杂度是___。
正确资料:

第46题,[谋学网（www.mouxue.com）]（第四章）后缀算式9 2 3 +- 10 2 / -的值为___。
正确资料:

第47题,[谋学网（www.mouxue.com）]（第四章）一个环形队列中共有MaxSize个单元，那么队满时共有___个元素。
正确资料:

第48题,[谋学网（www.mouxue.com）]（第四章）设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是___。
正确资料:

第49题,[谋学网（www.mouxue.com）]（第五章）一棵高度为5的完全二叉树至少有___个结点。
正确资料:

第50题,[谋学网（www.mouxue.com）]（第五章）一棵高度为5的完全二叉树最多有___个结点。
正确资料:

第51题,[谋学网（www.mouxue.com）]（第五章）如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为___或___。
正确资料:

第52题,[谋学网（www.mouxue.com）]（第五章）设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为___。
正确资料:

第53题,[谋学网（www.mouxue.com）]（第七章）已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是___。
正确资料:

第54题,[谋学网（www.mouxue.com）]（第七章）一个图的三种存储方法中，___表示法是唯一的。
正确资料:

第55题,[谋学网（www.mouxue.com）]（第七章）一个图的三种存储方法中，___和边集数组表示法是不唯一的。
正确资料:

第56题,[谋学网（www.mouxue.com）]（第七章）一个有n个顶点的无向连通图最少有___条边。
正确资料:

第57题,[谋学网（www.mouxue.com）]（第七章）一个有n个顶点的无向连通图最多___条边。
正确资料:

第58题,[谋学网（www.mouxue.com）]（第八章）设一个连通图G中有n个顶点e条边，则其最小生成树上有___条边。
正确资料:

第59题,[谋学网（www.mouxue.com）]（第十章）外排序是指在排序前后，数据在___上，排序时数据调入内存进行的排序方法。
正确资料:

第60题,[谋学网（www.mouxue.com）]（第十章）在选择排序、冒泡排序、归并排序中，___排序是空间复杂度最大的。
正确资料:

第61题,[谋学网（www.mouxue.com）]（第二章）简述顺序表和链表存储方式的特点。
正确资料:

第62题,[谋学网（www.mouxue.com）]（第二章）

在一个单链表HL中删除指针p所指结点，应执行如下关键操作：


if(________)

<blockquote>

HL = HL->next;

</blockquote>

else


{

<blockquote>

q = HL;


while(________)

<blockquote>

q = q->next;

</blockquote>

_____________;

</blockquote>

}


delete p;


 


请将代码补充完整。

正确资料:

第63题,[谋学网（www.mouxue.com）]（第四章）

以下2个问题基于下面的环形队列：


设环形队列Q[7]的当前状态如下，


<img src="../fileroot/question/bb9fd388-4113-492a-a553-413731997f5f/image/20170217/20170217150934_2371.jpg" alt="" />


写出队列Q的队空、队满定条件及进队、出队操作的的描述语句。

正确资料:

第64题,[谋学网（www.mouxue.com）]（第四章）画出元素a0,a1,a2出队，元素a4,a5,a6,a7进队后队列Q的状态。
正确资料:

第65题,[谋学网（www.mouxue.com）]（第五章）写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序列。

<img src="../fileroot/question/957f1a78-94ca-4f44-8fb4-cc8147c8c890/image/20170217/20170217150723_6207.jpg" alt="" height="189" width="156" />


 


 



 

正确资料:

第66题,[谋学网（www.mouxue.com）]（第六章）已知一组元素为(30,46,62,27,32,49,13,45)，画出按元素排列顺序输入生成的一棵二叉搜索树，并写出在这棵二叉搜索树中查找元素49所需的元素比较次数。
正确资料:

第67题,[谋学网（www.mouxue.com）]（第六章）给定权值{6,7,12,10,30,25}，构造相应的哈夫曼树，要求写出构造步骤，并计算该树的带权路径长度。
正确资料:

第68题,[谋学网（www.mouxue.com）]（第七章）

已知一个无向图的邻接表表示为：


<img src="../fileroot/question/b8d10a0f-b8a9-4974-973e-8805659fd2bd/image/20170217/20170217154010_8582.png" alt="" />


画出该图的图形表示，并写出在该邻接表存储结构下，以顶点v4为出发点进行深度优先遍历的遍历序列。

正确资料:

第69题,[谋学网（www.mouxue.com）]（第八章）
对如下的图，用Prim算法从顶点5开始求最小生成树，写出按次序产生的边。采用 Kruscal算法产生的边次序是哪些？画出最小生成树。

<img src="../fileroot/question/6d7f83bc-be41-4488-8e5d-43611865e7a2/image/20170217/20170217154525_2202.jpg" alt="" height="238" width="208" /> .

正确资料:

第70题,[谋学网（www.mouxue.com）]（第十章）已知序列（50，39，65，97，76，13，27，50）请用插入排序写出每一趟排序的结果。
正确资料:

		自动登录	找回密码
密码			会员注册

VIP会员，3年作业免费下！	奥鹏作业，奥鹏毕业论文检测	新手作业下载教程，充值问题	没有找到答案，请在此处留言！
2022年5月最新全国统考资料	投诉建议，加盟合作！		奥鹏课程积分软件(2021年最新)

[谋学网首发] 北大18秋08281006-数据结构发（资料）