下载文档原格式
2020-2021学年《数据结构》期末考试复习试题一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。
(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。
for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。
（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。
一、判断题：（共10分，每题1分）1. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。
（）2. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
（）3. 只有用面向对象的计算机语言才能描述数据结构算法。
（）4. 在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。
（）5. 递归的算法简单、易懂、容易编写，而且执行效率也高。
（）6. 在AOE网络中一定只有一条关键路径。
（）7. 二叉树是一棵无序树。
（）8. 在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。
（）9. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。
（）10. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
（）二、填空题（20分，每题2分）1.假定一棵二叉树的结点个数为32，则它的最小深度为______。
2.在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有______个。
3.一棵深度为5的满二叉树的结点总数为______个。
4.假定一棵树的广义表表示为A(B(C, D(E, F,G), H(I, J)))，则结点H的双亲结点为______。
5.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为______。
6.若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用____________遍历法。
7.元素关键字转换为该元素存储位置的函数f称为____________。
8.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做____________排序。
9.假定一组数据的关键字为{46,79,56,38,40,84}，则利用堆排序方法建立的初始大顶堆为__________________。
数据结构与算法模考试题（含参考答案）一、单选题（共100题，每题1分，共100分）1、某公司秘书小莉经常需要用Word编辑中文公文，她希望所录入的正文都能够段首空两个字符，最简捷的操作方法是：A、在每次编辑公文前，先将“正文”样式修改为“首行缩进 2 字符”。
B、每次编辑公文时，先输入内容然后选中所有正文文本将其设为“首行缩进 2 字符”。
C、在一个空白文档中将“正文”样式修改为“首行缩进 2 字符”，然后将当前样式集设为默认值。
D、将一个“正文”样式为“首行缩进 2 字符”正确答案：C2、现代微型计算机中所采用的电子元器件是：A、大规模和超大规模集成电路B、电子管C、晶体管D、小规模集成电路正确答案：A3、图书馆管理系统中实体图书和实体借阅人之间的联系是A、1：1B、1：NC、M：ND、N：1正确答案：C4、计算机网络最突出的优点是：A、资源共享和快速传输信息B、高精度计算和收发邮件C、运算速度快和快速传输信息D、存储容量大和高精度正确答案：A5、在 Excel 工作表单元格中输入公式时，F$2 的单元格引用方式称为：A、绝对地址引用B、交叉地址引用C、混合地址引用D、相对地址引用正确答案：C6、域名代码 MIL 表示：A、政府机关B、国际组织C、商业组织D、军事部门正确答案：D7、以下对 Excel 高级筛选功能，说法正确的是：A、高级筛选之前必须对数据进行排序B、利用“数据”选项卡中的“排序和筛选”组内的“筛选”命令可进行高级筛选C、高级筛选通常需要在工作表中设置条件区域D、高级筛选就是自定义筛选第 6 组正确答案：C8、软件工程的三要素是A、方法、工具和过程B、方法、工具和文档第 47 组C、方法、工具和环境D、方法、平台和管理正确答案：A9、字长是计算机的一个重要指标，在工作频率不变和 CPU 体系结构相似的前提下，字长与计算机性能的关系是：A、字长越长，计算机的数据处理速度越快B、字长越短，计算机的数据处理速度越快C、字长表示计算机的存储容量大小，字长越长计算机的读取速度越快D、字长越短，表示计算机的并行能力越强正确答案：A10、下面描述错误的是A、类中包含数据（属性）和方法（或操作）B、类中包含对数据的操作（方法）C、类是对象的实例D、类具有抽象性第 49 组正确答案：C11、在数据库的三级模式中,可以有任意多个A、模式B、内模式（物理模式）C、外模式（用户模式）正确答案：C12、以下关于计算机病毒的说法，不正确的是：A、计算机病毒一般会寄生在其他程序中B、计算机病毒一般会传染其他文件C、计算机病毒一般会具有自愈性D、计算机病毒一般会具有潜伏性正确答案：C13、CPU 的参数如 2800MHz，指的是：A、CPU 的速度B、CPU 的大小C、CPU 的时钟主频D、CPU 的字长正确答案：C14、设栈与队列初始状态为空。
北理工《数据结构与算法》在线作业一、单选题（共40 道试题，共100 分。
）1. 下列说法正确的是()A. 堆栈是在两端操作、先进后出的线性表B. 堆栈是在一端操作、先进后出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、后进先出的线性表正确答案：2. 判定一个队列Q(最多元素为m0)为满队列的条件是()A. rear-front= = m0B. rear-front-1= =m0C. front= =rearD. front= =rear+1正确答案：3. 评价排序算法好坏的标准主要是()。
A. 执行时间B. 辅助空间C. 算法本身的复杂度D. 执行时间和所需的辅助空间正确答案：4. 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为()。
A. 3700B. 4376C. 3900D. 4620正确答案：5. 根据二叉树的定义可知二叉树共有()种不同的形态。
A. 4B. 5C. 6D. 7正确答案：6. 以下排序方法中，稳定的排序方法是()。
A. 直接插入排序和希尔排序B. 直接插入排序和冒泡排序C. 希尔排序和快速排序D. 冒泡排序和快速排序正确答案：7. 下述几种排序方法中，平均查找长度最小的是()。
A. 插入排序B. 选择排序C. 快速排序D. 归并排序正确答案：8. 在数据结构中，与所使用的计算机无关的是数据的()结构A. 逻辑B. 存储C. 逻辑和存储D. 物理正确答案：9. 二分查找（又称折半查找）要求查找表中的记录按关键字()。
A. 有序B. 无序C. 既可有序也可无序正确答案：10. 以二叉链表作为二叉树的存贮结构时，在具有n个结点的二叉链表中(n>0)，空指针域的个数为()。
A. 2n-1B. n+1C. n-1D. 2n+1正确答案：11. 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为()A. 3B. 4C. 5D. 1正确答案：12. 长度为256的表,采用分块查找,每块最佳长度为()。
第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
3．简述逻辑结构的四种基本关系并画出它们的关系图。
4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。
A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。
（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
北京大学信息科学技术学院考试试卷 考试科目：数据结构与算法A 姓名： 学号： 考试时间：2017年 11月 15日 任课教师: 以下以下为答题纸，共 页注意事项：1． 全部题目都在空白答题纸上解答。
2． 试卷对算法设计都有质量要求，请尽量按照试题中的要求来写算法。
否则将酌情扣分。
3． 请申明所写算法的基本思想，并在算法段加以恰当的注释。
以下为试题和答题纸，共5页，请把答案写在答题纸。
题号 一 二 三 四 五 总分 分数 阅卷人 北京大学考场纪律 1、考生进入考场后，按照监考老师安排隔位就座，将学生证放在桌面上。
无学生证者不能参加考试；迟到超过15分钟不得入场。
在考试开始30分钟后方可交卷出场。
2、除必要的文具和主考教师允许的工具书、参考书、计算器以外，其它所有物品（包括空白纸张、手机等）不得带入座位，已经带入考场的必须放在监考人员指定的位置，并关闭手机等一切电子设备。
3、考试使用的试题、答卷、草稿纸由监考人员统一发放，考试结束时收回，一律不准带出考场。
若有试题印制问题请向监考教师提出，不得向其他考生询问。
提前答完试卷，应举手示意请监考人员收卷后方可离开；交卷后不得在考场内逗留或在附近高声交谈。
未交卷擅自离开考场，不得重新进入考场答卷。
考试结束监考人员宣布收卷时，考生立即停止答卷，在座位上等待监考人员收卷清点后，方可离场。
4、考生要严格遵守考场规则，在规定时间内独立完成答卷。
不准旁窥、交头接耳、打暗号，不准携带与考试内容相关的材料参加考试，不准抄袭或者有意让他人抄袭答题内容，不准接传答案或者试卷等。
凡有严重违纪或作弊者，一经发现，当场取消其考试资格，并根据《北京大学本科考试工作与学习纪律管理规定》及其他相关规定严肃处理。
5、考生须确认自己填写的个人信息真实、准确，并承担信息填写错误带来的一切责任与后果。
学校倡议所有考生以北京大学学生的荣誉与诚信答卷，共同维护北京大学的学术声誉。
装订线内不要答题一、选择与填空（每空2分，共24分）得分1.下面函数的时间复杂度是（）void recursive(int n, int m, int k){if (n <= 0)printf("%d, %d\n", m, k);else {recursive(n-1, m+1, k);recursive(n-1, m, k+1);}}A.O(n*m*k)B. O(n^2*m^2)B.O(2^n) D. O(n!)2.完成在双循环链表结点p之后插入s的操作为( ):A. p->next->prev=s; s->prev=p; s->next=p->next; p->next=s;B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;C. s->next=p->next; s->prev=p; p->next->prev=s; p->next=s;D. s->prev=p; s->next=p->next; s->prev->next=s; s->next->prev=s;3.设栈S和队列Q初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少是( )A.2;B.3;C.4;D.64.设循环队列的容量为40 （序号从0到39），现经过一系列的入队和出队运算后：1）front=12，rear=19；2）front=19，rear=12；在这两种情况下，循环队列中的元素个数分别为和。
1. 已知一个6⨯5稀疏矩阵如下所示，试：（1） （1） 写出它的三元组线性表；（2） （2） 给出三元组线性表的顺序存储表示。
1. 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
2. 3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；3. 4. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
一、 四、 阅读算法（每题7分，共14分） 1.1. int Prime(int n) { int i=1;int x=(int) sqrt(n);while (++i<=x)⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡--00700000520000000100000010000图6if (n%i==0) break;if (i>x) return 1;else return 0;}(1)(1)指出该算法的功能；(2)(2)该算法的时间复杂度是多少？2. 2.写出下述算法的功能：void AJ(adjlist GL, int i, int n){Queue Q;InitQueue(Q);cout<<i<<' ';visited[i]=true;QInsert(Q,i);while(!QueueEmpty(Q)) {int k=QDelete(Q);edgenode* p=GL[k];while(p!=NULL){int j=p->adjvex;if(!visited[j]){cout<<j<<' ';visited[j]=true;QInsert(Q,j);}p=p->next;}}}二、五、算法填空（共8分）如下为二分查找的非递归算法，试将其填写完整。
北京大学信息科学技术学院考试试卷考试科目：数据结构与算法A 姓名：学号：考试时间： 2016 年 1 月 6 日任课教师:以下为试题和答题纸(答案写在答题纸上)，包括本页共 6 页。
第一题填空题（每空1分，共8分）1.设无向图G = (V,E)中V={1, 2, 3, 4, 5, 6, 7}，E={(1,2), (1,3), (2,3), (4,5), (3,6),(4,7), (5,7)}。
则图G包含的不同生成森林的个数为_____9____。
注释：其中若两个生成森林的边集不同，则认为它们是不同的生成森林。
2.若对下面的无向图以1为起点运行单源最短路径的Dijkstra算法，则在Dijkstra算法的过程中，每一步依次被选出的顶点依次是_1,2,4,3,7,5,6,8,9,10___。
若忽略边权，以6为起点进行一次广度优先周游，将得到一棵广度优先搜索的生成树。
设仅包含一个结点的树高度为1，则该生成树的高度为_3_，树的最深层结点集合为_1,5,7,10__。
第一空回答2,4,3,7,5,6,8,9,10也算对3.用某种排序方法对序列（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序时，若序列的变化情况如下，则所采用的排序方法为__快速排序__。
25, 84, 21, 47, 15, 27, 68, 35, 2020, 15, 21, 25, 47, 27, 68, 35, 8415, 20, 21, 25, 35, 27, 47, 68, 8415, 20, 21, 25, 27, 35, 47, 68, 844.假设Shell排序的增量序列是(2k, 2k-1, … , 2, 1)，其中k=[log2 n]。
若待排序序列是正序的（已经排好）或逆序的，则Shell排序的时间复杂度分别是__O(nlogn)_、O(nlogn)_。
各0.5分5.设输入的关键码满足k1>k2>…>k n，缓冲区大小为m。
《数据结构与算法》试卷A适用专业： 考试日期： 闭卷 所需时间：120分钟 总分：100分一、 选择题(每题1分, 共20题，总共20分)。
1.算法分析的目的是（ ） A ．辨别数据结构的合理性 B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性2.在一个单链表HL 中，若要在当前由指针p 指向的结点后面插入一个由q 指向的结点，则执行如下( )语句序列。
A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（ ）A. 在队列第i 个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。
A ． 11 B.35 C. 19 D. 535.如下图所示的4棵二叉树中，（ ）不是完全二叉树。
6．下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。
B ．线性表采用顺序存储，便于进行插入和删除操作。
C ．线性表采用链接存储，不必占用一片连续的存储单元。
D ．线性表采用链接存储，便于插入和删除操作。
7．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A ．单链表B ．仅有头指针的单循环链表C ．双链表D ．仅有尾指针的单循环链表8. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A. O(0)B. O(1)C. O(n)D. O(n 2)9. 若已知一个栈的入栈序列是1,2,3,…,n ，其输出序列为p 1,p 2,p 3，…，p N ,若p N 是n ，则p i 是( )。
完美 WORD 格式数据结构习题集含答案目录目录1选择题2第一章绪论 .2第二章线性表.4第三章栈和队列.6第四章串.7第五章数组和广义表8第六章树和二叉树8第七章图.11第八章查找.13第九章排序.14简答题19第一章绪论 .19第二章线性表.24第三章栈和队列.26第四章串.28第五章数组和广义表29第六章树和二叉树31第七章图.36第八章查找.38第九章排序.39编程题41第一章绪论 .41第二章线性表.41第三章栈和队列.52第四章串.52第五章数组和广义表52第六章树和二叉树52第七章图.52第八章查找.52第九章排序.57选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得X三同学的各科成绩记录，其中数据结构考了 90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.* 数据结构是指（ A ）。
A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。
A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（ A ）。
北京大学信息科学技术学院考试试卷 考试科目：数据结构与算法A 姓名： 学号： 考试时间： 2008年 1 月 9 日 教师: 张铭、赵海燕、王腾蛟、宋国杰以下为试题和答题纸，共 4 页。
题号 一 二 三 四 五六 七 八 总分 分数 阅卷人第 1 页一、（共30分，每空3分）填空1. 1．无向图G=(V , E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c,f), (f, d), (e, d)}，对该图进行深度优先遍历，得到的顶点序列正确的是____。
A ．a,b,e,c,d,fB ．a,c,f,e,b,dC ．a,e,b,c,f,dD ．a,e,d,f,c,b2. 下图中的强连通分量的个数为________个。
3. 设有向图G 如下:写出所有拓扑序列:___________________________________________添加一条弧________________________之后, 则仅有唯一的拓扑序列. 4. 请问下面哪些操作在已排序数据上实施比在无序的数据上快 ？A ．找最小值 B. 计算算术平均值 C. 找中位数 D. 找出现次数最多的值5. 序列{15，142，51，68，121，46，57，575，60，89，185 }按最低位优先法进行基数排序，进行一次分配和收集后得到的序列 。
6. 设输入的关键码满足k 1>k 2>…>k n ，缓冲区大小为m ，用最小值堆进行置换-选择排序方法可产生____个初始归并段。
7. 在包含n 个关键码的线性表中进行顺序检索，若检索第i 个关键码的概率为p i , 且分布如下：n n n n p p p p 21,21,....,41,211121====−−成功检索的平均检索长度是_______________。
8. 假设计算机系统有2048个字节的磁盘块，要存储的每一条记录中4个字节是关键码，磁盘指针4个字节，64个字节是数据字段。
2022年北京建筑大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入B.选择C.希尔D.二路归并3、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341566、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
8、有关二叉树下列说法正确的是（）。
A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。
A.直接插入排序B.起泡排序C.简单选择排序D.快速排序二、填空题11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表示方式的数目。
例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。
2017《数据结构》期末考试一试题及答案《数据结构》期末考试一试题及答案1..................................... .. (2)试题1答案............................................. ............................................... (7)《数据结构》期末考试一试题及答案2..................................... .. (9)试题2答案............................................. ............................................... (14)《数据结构》期末考试一试题及答案3..................................... (16)试题3答案............................................. ............................................... (21)第1页共23页《数据结构》期末考试一试题及答案 1一、单项选择题（每题2分，共20分）1. 栈和行列的共同特色是( )。
A.只同意在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点用链接方式储存的行列，在进行插入运算时().A.仅改正头指针B.头、尾指针都要改正C.仅改正尾指针D.头、尾指针可能都要改正以下数据结构中哪一个是非线性结构？()A.行列B.栈C.线性表D.二叉树4.设有一个二维数组A[m][n]，假定A[0][0]寄存地点在644(10)，A[2][2]寄存地点在676(10)，每个元素占一个空间，问A[3][3](10)寄存在什么地点？脚注(10)表示用10进制表示。
北京大学信息科学技术学院考试试卷考试科目：数据结构与算法A 姓名：学号：考试时间： 2016 年 1 月 6 日任课教师:以下为试题和答题纸(答案写在答题纸上)，包括本页共 6 页。
第一题填空题（每空1分，共8分）1.设无向图G = (V,E)中V={1, 2, 3, 4, 5, 6, 7}，E={(1,2), (1,3), (2,3), (4,5), (3,6),(4,7), (5,7)}。
则图G包含的不同生成森林的个数为_________。
注释：其中若两个生成森林的边集不同，则认为它们是不同的生成森林。
2.若对下面的无向图以1为起点运行单源最短路径的Dijkstra算法，则在Dijkstra算法的过程中，每一步依次被选出的顶点依次是____。
若忽略边权，以6为起点进行一次广度优先周游，将得到一棵广度优先搜索的生成树。
设仅包含一个结点的树高度为1，则该生成树的高度为__，树的最深层结点集合为___。
3.用某种排序方法对序列（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序时，若序列的变化情况如下，则所采用的排序方法为____。
25, 84, 21, 47, 15, 27, 68, 35, 2020, 15, 21, 25, 47, 27, 68, 35, 8415, 20, 21, 25, 35, 27, 47, 68, 8415, 20, 21, 25, 27, 35, 47, 68, 844.假设Shell排序的增量序列是(2k, 2k-1, … , 2, 1)，其中k=[log2 n]。
若待排序序列是正序的（已经排好）或逆序的，则Shell排序的时间复杂度分别是__、_。
5.设输入的关键码满足k1>k2>…>k n，缓冲区大小为m。
在n=150, m=25的情况下，用最小值堆进行置换-选择排序方法可产生初始归并段的个数为_______。
6.假定有一棵B+树，它的内部结点可以存储多达20个子结点，叶结点可以存储多达15条记录（本题中的B+树把所有记录存放在叶结点上）。
2022年北京大学数据科学与大数据技术专业《计算机系统结构》科目期末试卷B(有答案）一、选择题1、下列关于标量流水机的说法不正确的是（）A.可对标量数据进行流水处理B.没有向量数据表示C.不能对向量数据进行运算D.可以对向量、数组进行运算2、在系统结构设计中，提高软件功能实现的比例会( )。
A.提高解题速度B.减少需要的存贮容量C.提高系统的灵活性D.提高系统的性能价格比3、利用时间重叠概念实现并行处理的是( )。
A.流水处理机B.多处理机C.并行（阵列）处理机D.相联处理机4、对系统程序员不透明的应当是( )。
A.Cache存贮器XB.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存贮器5、不同系列的机器之间，实现软件移植的途径不包括( )A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真6、在尾数下溢处理方法中，平均误差最大的是（）A.截断法B.舍入法C.恒置"1"法D.ROM查表法7、计算机系统结构不包括( )。
A.主存速度B.机器工作状态C.信息保护D.数据8、以下说法不正确的是( )A.线性流水线是单功能流水线B.动态流水线是多功能流水线C.静态流水线是多功能流水线D.动态流水线只能是单功能流水线9、费林按指令流和数据流的多倍性把计算机系统分类，这里的多倍性指（）。
A.系统瓶颈部件上处于同一执行阶段的指令流是数据流的多少倍。
B.系统瓶颈部件上处于同一执行阶段的数据流是指令流的多少倍。
C.系统瓶颈部件上处于同一执行阶段的指令或数据的最大可能个数。
D.A和B10、块冲突概率最高的Cache地址映象方式是( )A.段相联B.组相联C.直接D.全相联二、填空题11、页面替换是发生于页面失效，同时又发生________的时候。
12、根据多台外围设备共享通道的不同情况，可将通道分为三种类型：________和________13、软件和硬件成本由________和________组成。
