北大数据结构与算法期末考试模拟试卷
2014年春季北大《数据结构与算法B》期末考试模拟试卷（本试卷只是给同学们看看考题形式和范围，难度与真实考卷稍有差别）
学号______________ 姓名______________ 教师/教室______________
（注：如未标明，本试卷题中的下标、位置都从0开始计数）
一、填空题（共32分）
1.设有字符串变量String A = “This”, B=“is”, C=“just”, D=“a?test”，请计算下列表达式：
（1）A+B+D=_“Thisisa?test”_；
（2）D.IndexOf(“t”) = __2___；（求字符在字符串中的第一个位置）
（3）B.Strlength() = ___2___
（4）D.SubStr(1,2) = _“?t”__（注：1为起始下标，2为子串长度）【4分】
2.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为___n___次；若
查找失败，则比较关键字的次数最多为___n___，最少为____n___次。【3分】
3.在散列函数H（key）=key%p中，p值最好取___质数（或素数）___。【1分】
4.对于下图邻接表所对应的有向图，试写出：【2分】
(1) 从顶点①出发进行深度优先遍历结果__1, 2, 3, 4, 5__；
(2) 从顶点①出发进行广度优先遍历结果__1, 2, 3, 4, 5 _；
5.当图中各条边上的权值__都相等__ 时，宽度优先搜索算法可用来解决单源最短路径问
题？【2分】
6.一棵有n个结点的满二叉树有_0_个度为1的结点、有_(n-1)/2个分支（非终端）结点；
该满二叉树的深度最大为___(n-1)/2__, 最小为int(log2n)或?log2n?。（独根树深度为0）【4分】
7.对于给定的n个元素,可以构造出的逻辑结构有线性结构，树形结构，图形
结构，_集合__四种。【2分】
8.下面程序段的时间复杂度为__O(n)_。(n>1) [大O表示法] 【2分】
sum=1；
for (i=0;sum 9. 对于最大堆65 43 59 24 37 48 57 12 23 28 5 3，删除掉最大元素后，堆中元素为 59,43,57,24,37,48,3,12,23,28,5【2分】 10.从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键 码{ 18,73,10,5,68,99,27,41,51,32,25 } 构造出一棵二叉搜索树，该二叉树转换为森林，则该森林的层次遍历序列为_18 73 99 10 68 5 27 41 51 25 32__【4分】 对于的二叉树为 11.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为12345，为了得到13542出 栈顺序，相应的S和X的操作串为_SXSSXSSXXX__。【2分】 二、单选题（18分，每题2分，最后两题每题4分） 1. 对初始状态为递增的表按递增顺序排序，最省时间的是（C ）算法。 A. 基数排序 B. 桶排 C. 直接插入排序 D. 归并排序 2. 一个n个顶点的连通无向图，其边的个数至少为（A）。 A．n-1B．n C．n+1 D．nlogn； 3．线性表（a1,a2,…,a n）以链接方式存储时，访问第i位置元素的时间复杂度为（C）A．O（i）B．O（1）C．O（n）D．O（i-1） 4. 使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号，下面正确的答案是（B）。 A. (0, 2) (3, 5) (1, 4) (2, 5) (1, 2) B. (0, 2) (2, 5) (3, 5) (1, 2) (1, 4) C. (0, 2) (3, 5) (1, 4) (1, 2) (2, 5) B. (0, 2) (1, 2) (1, 4) (2, 5) (3, 5) 5．一个有n个结点的图，最多有（D）个连通分量。 A．0 B．1 C．n-1 D．n 6. 用二分（对半）查找法检索元素速度比用顺序法( D) 。【2分】 A．必然快 B. 必然慢 C. 相等 D. 不能确定 7. 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为 ( D)。【4分】 A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 8．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟处理（对应于排序算法中一层循环或一层递归算法）后，数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（C）排序。【4分】 A. 选择 B. 快速 C. 希尔（Shell） D. 冒泡 三、简答题（30分，每题10分） 1.试问由二叉树的中序序列和后序序列是否能唯一的建立二叉树，请说明理由；若能，对 中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。 答：（1）给定二叉树结点的后序序列和对称序（中序）序列，可以唯一确定该二叉树。 因为后序序列的最后一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设有l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设有r个元素）是右子树，若为空，则右子树为空。根据后序遍历中“左子树—右子树—根”的顺序，则后序序列中由从第1元素开始的l个结点序列和中序序列根左边的l个结点序列构造 左子树；由后序序列l个元素后面r个元素序列与中序序列根右边的r个元素序列构造右子树。 （2）中序序列DBEAFGC和后序序列DEBGFCA构造的二叉树如下图 2．设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的散列函数是H(key)=key % 13，冲突用链地址法解决，设散列表的大小为13(下标为0~12)，试画出插入上述数据后的散列表。答： 3. 设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若T中有6个叶结点，试问： （1）T树的最大深度Kmax=?最小可能深度Kmin=?（假定独根二叉树深度为0） （2）T树中共有多少非叶结点？ （3）若叶结点的权值分别为1,2,3,4,5,6。请画出一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 答：1）T树的最大深度Kmax=5（除根外，每层均是两个结点） T树的最小深度Kmin=3（具有6个叶子的完全二叉树是其中的一种形态）（2）非叶子结点数是5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度wpl=51 四、算法填空题（20分，第一题10分，第2题10分） 1. 下面是求二叉树高度（独根树高度是1）的递归算法，试补充完整 二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。 int height(BinTree *p) { int hi, lh, rh; if (___p ____) // p!=NULL 也对 { if (p->lchild==null) lh=___0____; else lh=___height(p->lchild)____; if (p->rchild==null) rh=__0_____; else rh=__ height(p->rchild) _; if (lh>rh) hi=__lh+1___； else hi=___rh+1___; } else hi=___0____; return hi; } // 题目中结构已经给定，就应该按照题目要求来 // 如果根据给定的题目结构填入其他内容也正确的话，那么就是正确的。) 2．对单链表（带头结点）中元素按插入方法实现非递增序列的排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 typedef struct node { int data; struct node *next; } linknode,*link; void Insertsort(link L) { link p,q,r,u; p=L->next; __L->next = NULL____; // L->next = NULL这一句是需要的，因为p指向待插入结点，L后来一直指向排好序的链表。// 第二层while循环实际上是在L所指向的有序表中查找p应该插入的位置。 while(__p != NULL __) { r=L; q=L->next; while(q != NULL && q->data <= p->data) { r=q; q=q->next; } u=p->next; ___p->next=r->next(或p->next = q)___; ___r->next = p___; p=u; } } 【注：后面两空也可以是r->next = p; p->next = q;此时一定不能写成p->next = r->next】 2004-2005学年第二学期期末考试 C 2002级计算机科学与技术专业《数据库原理与应用》课程试题 ：1分）一、选择题（15分，每空1．在数据库中，产生数据不一致的根本原因是____。 A．数据存储量太大 B．没有严格保护数据 C．未对数据进行完整性控制 D．数据冗余 2．相对于其他数据管理技术，数据库系统有①、减少数据冗余、保持数据的一致性、②和③的特点。 ①A．数据统一 B．数据模块化 C．数据结构化 D．数据共享 ②A数据结构化 B．数据无独立性 C．数据统一管理 D．数据有独立性 ③A．使用专用文件 B．不使用专用文件 C．数据没有安全与完整性保障 D．数据有安全与完整性保障 3．关系运算中花费时间可能最长的运算是____。 A．投影 B．选择 C．笛卡尔积 D．除 4．关系数据库用①来表示实体之间的联系，关系的数学定义是②。 ①A．层次模型 B．网状模型 C．指针链 D．二维表格数据 ②A．若干域（domain）的集合 B．若干域的笛卡尔乘积（Cartesian product） C．若干域的笛卡尔乘积的子集 D．若干元组（tuple）的集合 5．集合R与S的连接可以用关系代数的5种基本运算表示为________。 A．R-(R-S) B．σ (R×S) F C．空 D．空 6．在关系代数中，对一个关系做投影操作后，新关系的元组个数____原来关系的元组个数。A．小于 B．小于或等于 C．等于 D．大于 7．下列SQL语句中，创建关系表的是____。 A．ALTER B．CREATE C．UPDATE D．INSERT 8．关系数据库设计中的陷阱（pitfalls）是指________。 A．信息重复和不能表示特定信息 B．不该插入的数据被插入 C．应该删除的数据未被删除 D．应该插入的数据未被插入 9．数据库的____是为了保证由授权用户对数据库所做的修改不会影响数据一致性的损失。 A．安全性 B．完整性 C．并发控制 D．恢复 ．事务是数据库进行的基本工作单位。如果一个事务执行成功，则全部更新提交；如果一个事务10． 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 北京大学生命科学学院考试专用纸姓名：学号：考试类别： 考试科目：普通生物学A 考试日期：2010－6－11阅卷教师：佟向军 以下为答题纸，共7 页 一、填空（每空0.5分，共35分） 1．我们的身体无法利用纤维素，是因为我们消化道内的________酶仅能水解________ 键，而无法水解_________键。构成淀粉和纤维素的单体都是________。 2．根据是否有细胞核膜来区分，细胞分为_______细胞和_______细胞。细胞骨架包括________、________以及________三种成分。其中：有丝分裂时，形成纺锤丝的是______，与胞质分裂相关的是________，与肌肉收缩有关的是______。 3．光合作用的光反应阶段在______进行，它又可分为光系统I和光系统II。前者的产物是______，后者的产物是________。光合作用的暗反应在___________进行，其主要作用是固定______，这一过程称为__________循环。4．细胞通讯与信号传递，对细胞的生命活动很重要。在这一过程中，能引起细胞反应的信号分子叫做________，包括______和______两大类。细胞本身与信号分子结合的蛋白质叫做________,它们在细胞中的位置各不相同，脂溶性信号分子的结合蛋白，主要位于__________，水溶性信号分子的结合蛋白，主要位于________。在细胞内，起第二信使作用的有________（举一例即可）。5．细胞周期包括_____、________、_______和______四个时期。DNA复制在____期。调节细胞周期的因子叫做____________，它由______和______两种蛋白组成。细胞周期有_____个检验点，它们分别位于____________期。 6．人的α－珠蛋白基因位于16p13.33, 其中16代表________________，p代表_________，13代表_______________。 7．DNA的复制是__________方式，即两条DNA链解开，分别以各自为____________，按照____________________原则，合成其互补链。复制所需要的酶主要是________________；复制无法从头开始，需要________________，它的成分是________________。新链的延伸方向是____________________，因此一条链连续复制，称为______________，另一条链复制不连续，称为____________，不连续的DNA片段叫做______________。 8．原核生物基因表达调控的主要方式是________________，它由____________、 数据库原理期末考试试 卷答案 山西大学 2008级数据库原理试卷答案 一、填空题（共10分，每空1分） 1、从数据库管理系统的角度划分数据库系统的体系结构，可分为（）、（）和（）3层。 答案：外模式、模式、内模式 2、RDBMS的中文意思是（）。 答案：关系数据库管理系统 3、在关系代数中，θ连接是由笛卡尔积和（）运算组合而成的。 答案：选择 4、通过模式分解把属于低级范式的关系模式转换为几个属于高级范式的关系模式的集合，这一过程称为（）。 答案：规范化 5、要使关系模式属于第三范式，既要消除（）， 也要消除（）。 答案：非主属性对码的部分依赖、非主属性对码的传递依赖 6、利用游标进行查询需要4种语句，分别是说明游标、（）、（）和关闭游标。 答案：打开游标、推进游标 二、单选题（共10分，每题1分） 1、数据库系统的基础是（）。 A. 数据结构 B. 数据库管理系统 C. 操作系统 D. 数据模型 答案：D 2、经过投影运算后，所得关系的元组数（）原关系的元组数。 A. 等于 B. 小于 C. 小于或等于 D. 大于 答案：C 3、关系R与关系S只有1个公共属性，T1是R与S作θ连接的结果，T2是R 与S作自然连接的结果，则（）。 A. T1的属性个数等于T2的属性个数 B. T1的属性个数小于T2的属性个数 C. T1的属性个数大于或等于T2的属性个数 D. T1的属性个数大于T2的属性个数 答案：D 4、在SQL中，与关系代数中的投影运算对应的子句是（） A. SELECT B. FROM C. WHERE D. ORDER BY 答案：A 5、在SQL的排序子句：ORDER BY 总分 DESC, 英语 DESC 表示（） A. 总分和英语分数都是最高的在前面 B. 总分和英语分数之和最高的在前面 C. 总分高的在前面，总分相同时英语分数高的在前面 D. 总分和英语分数之和最高的在前面，相同时英语分数高的在前面 答案：C 6、下面哪一个依赖是平凡依赖（） 作业参考答案 一、（带头结点）多项式乘法C= A×B： void PoｌyAdd ( list &C,liｓｔR) ／／R为单个结 点 { p=C; while(（!p-＞ｎeｘt) &＆(p->nexｔ-＞eｘp>Ｒ->eｘp)) p=p－>ｎｅｘt； ｉf (（p->next) ｜｜(ｐ->neｘt->ｅｘp<Ｒ-＞eｘp)) {R－＞nｅxt=ｐ->ｎeｘｔ;p->neｘｔ=Ｒ;} ｅlse { ｐ-＞nｅxt－＞inf +=R->inｆ;delｅte R; if （！p－>neｘｔ-＞iｎｆ) { R=ｐ-＞nｅxt；p－>next=R->ｎext;deleｔe R; ｝ } } ｖoｉｄPｏlｙMul （lｉst A, lｉst B，lｉst &C ） ｛ C=new sｔｒuct nｏｄe; Ｃ-＞neｘt=ＮUＬL；q=B->next; Wｈｉｌe (q ） { p＝A->neｘｔ; whiｌｅ（p ) { ｒ= new struct node；r->ｅxｐ= p->ｅxp ＋ｑ－>exp； r-＞ｉnf ＝ｐ-＞inf* q－>iｎf; PolyAｄd(C，r）； p=p-＞next; ｝ q=q－>ｎext; ｝ } 二、梵塔的移动次数: 已知移动次数迭代公式为：M ( ｎ)= 2M (n－1 ) + 1 初值为: Ｍ( 0 ) ＝0 则：M （n）＝ 2 （2M （n-2 ) + 1) + 1 =4M( n-2 )+ 3 = 8Ｍ(n－3 )+ 7 =２i M ( n-i ) + 2i– 1 若n＝ｉ，则Ｍ（n-ｎ) ＝0,故：M ( n ) =2ｎM( ｎ-n）+2n–1 =2n– 1 所以,梵塔的移动次数为2ｎ– 1次。 三、简化的背包问题： ｖoid Pacｋ( int ｍ, int i, ｉnt t ）// 初始值为:１１t ｛ for (k=i; k<＝ｎ; k＋＋) { soｌutiｏｎ[m] = ｗeighｔ[k]; if( t == weigｈｔ[k]) ｛ for ( j=1; ｊ<=m；j+＋) cout<＜ｓolutｉon［j]；coｕt< 北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业 张铭编写并发布 mzhang@https://www.docsj.com/doc/eb14937242.html, 第11次作业，12月17日（周一）课前提交，电子稿提交时间12月17日开课之前提交。 11.1 偶数阶的B 树插入上溢出时，中 位数有两个，需要注意采用统一的策略。例如，取第二个中位数， 即分裂后左(1)/2m ?????个关键码，右(1)/2m ?????； 或者取第一个中位数，分裂后左(1)/2m ????? 右(1)/2m ?????。请画出对右图的4阶B 树进行下来操作后的B 树。 (1) 分裂时采用第2个中位数为 分界码，请画出插入关键码113后的B 树；分析插入操作的访外次数。 (2) 分裂时采用第1个中位数为分界码，请画出插入关键码113后的B 树；分析插入操 作的访外次数。 (3) 在原树中删除关键码50；分析删除操作的访外次数（与1、2题无关，从根重新开 始操作）。 11.2 已知一组关键码为(20, 30, 50, 52, 60, 68, 70)，试依次插入关键码。 (1) 生成一棵3阶的B +树，画出插入所有关键码后B 树的结构。 (2) 画出删除50后的B + 状态，分析删除操作的访外次数。 11.3 假设一个数据文件每个记录对象需要占用128 字节（其中关键码占用4字节），且所 有记录均已按关键码有序地存储在主磁盘文件中。设磁盘页块大小为2048（= 2K ）字节，若主存中有12M 空间可以用来存储索引结构，索引项中每一个地址指针占8 字节。请简要回答以下问题（请写明你的计算过程）。 （1） 使用B 树索引，B 树的阶m 1最多可以为多少？4层m 1阶B 树，最多可以索引多 少字节的数据文件？ （2） 使用B +树索引，B +树的阶m 2最多可以为多少? （3） 假设B +树的叶层各结点链接成双链结构，B +树的叶结点阶m 2’可以跟内部结点不 一样，则阶m 2’为多少? （4） 在第(3)小题的基础上，计算4层B +树（内部结点为m 2阶，叶结点m 2’阶），最多 可以索引多少字节的数据文件？ （5） 假设尽量把B +树的头几层放入内存（本题规定不能超过12M ），那么给定关键码， 通过B +树查找到(4)小题中主数据文件的一个记录，最少几次访外？最多几次访 外？ 11.4 对于下面两种B +树，列表给出他们在1、2、3、4和5层（独根是一层树）的不同情 况下，能够存储的最大记录数和最小记录数。 (1) 对于教材定义那样的B +树，其内部结点阶为50，叶结点阶为50。 (2) 如讲义P89那样的混合型B +树，其内部结点阶为55，叶结点阶为25（叶结点除关 键码，还索引部分记录信息）。 4阶B 树 数据库原理-期末考试试题及答案 （本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、 多选或未选均无分。 1. 要保证数据库的数据独立性，需要修改的是（） A．三层模式之间的两种映射B．模式与内模式 C．模式与外模式D．三层模式 2. 下列四项中说法不正确的是（） A．数据库减少了数据冗余B．数据库中的数据可以共享 C．数据库避免了一切数据的重复D．数据库具有较高的数据独立性 3. 公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员， 从职员到部门的联系类型是（） A．多对多B．一对一 C．多对一D．一对多 4．将E-R模型转换成关系模型，属于数据库的（） A．需求分析B．概念设计 C．逻辑设计D．物理设计 5．五种基本关系代数运算是（） A．∪，—，×，π和σB ．∪，—，，π和σ C．∪，∩，×，π和σD ．∪，∩，，π和σ 6．下列聚合函数中不忽略空值 (NULL) 的是（）。 A．SUM (列名) B．MAX (列名) C．COUNT ( * ) D．AVG (列名) 7. SQL中，下列涉及空值的操作，不正确的是（）。 A. AGE IS NULL B. AGE IS NOT NULL C. AGE = NULL D. NOT (AGE IS NULL) 8. 已知成绩关系如表1所示。 执行SQL语句： SELECT COUNT（DISTINCT学号） FROM成绩 WHERE分数＞60 查询结果中包含的元组数目是（） 表1 成绩关系 A. 1 B. 2 C. 3 D. 4 9． 在视图上不能完成的操作是（ ） A. 更新视图 B. 查询 C. 在视图上定义新的基本表 D. 在视图上定义新视 图 10. 关系数据模型的三个组成部分中，不包括（ ） A. 完整性约束 B. 数据结构 C. 恢复 D. 数据操作 11. 假定学生关系是S （S ＃，SNAME ，SEX ，AGE ），课程关系是C （C ＃，CNAME ，TEACHER ）， 学生选课关系是SC （S ＃，C ＃，GRADE ）。 要查找选修“COMPUTER ”课程的“女”学生姓名，将涉及到关系（ ） A ．S B ．S C ，C C ．S ，SC D ．S ，SC ，C 12. 关系规范化中的删除操作异常是指（ ） A ．不该删除的数据被删除 B ．不该插入的数据被插入 C ．应该删除的数据未被删除 D ．应该插入的数据未被插入 13. 从E-R 模型关系向关系模型转换时，一个m:n 联系转换为关系模式时，该关系模式的码 是（ ） A ．M 端实体的码 B ．N 端实体的码 C ．M 端实体码与N 端实体码组合 D ．重新选取其他属性 14．已知关系R={A ，B ，C ，D ，E ，F}，F={A →C ，BC →DE ，D →E ，CF →B}。则(AB)F + 的闭包 是（ ） A ．ABCDEF B ．ABCDE C ．ABC D ．AB 15．设有关系R （A ，B ，C ）和S （C ，D ）。与SQL 语句select A,B,D from R,S where R.C=S.C 等价的关系代数表达式是（ ） A ．σR.C=S.C (πA,B,D (R×S)) B ．πA,B,D (σR,C= S.C (R×S)) C ．σR.C=S.C ((πA,B (R))×(π D (S))) D ．σR,C=S.C (πD ((πA,B (R))×S)) 二、多项选择题 （本大题共5小题，每小题2分，共10分） 在每小题列出的四个备选项中有多个是符合题目要 求的，多选、少选、错选、不选均无分。 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 操作系统原理试题 一. 名词解释题 1. 中断—— 2. 进程控制块(PCB)――它是进程实体的一部分，是操作系统最重要的记录型数据结构, 是进程存在的唯一标识 3. 虚时钟 4. 段式管理 5. 文件控制块(FCB) 6. 对换(SWAPPING) 7. 系统调用 8. 绝对路径名 9. 特别文件 10.虚设备技术 11.管道 12.中断接收 13.恢复现场 14.页式管理 15.作业步 16.字符流文件 17.通道 18.页面淘汰 19.多道程序设计 20.死锁 21.当前目录 22.快表 23.作业调度 24.原语 25.中断屏蔽 26.地址映射 27.文件目录 28.死锁避免 29.原语 31. CPU 状态 32.虚存 二 . 填空题 1. 分时系统追求的目标是 __及时响应 ___. 2. 用户进程从目态 （常态）转换为管态 （特态）的唯一途径是 ___ 中断 ________ . 3. 从静态的观点看 , 操作系统中的进程是由程序段、数据和 __ 作业控制块 PCB__ 三 部分组成 . 4. 在系统内核中必须包括的处理模块有进程调度、原语管理和 __中断处理 __. 5. 批处理操作系统中 , 作业存在的唯一标志是 _作业控制块 PCB ___. 6. 操作系统中的一种同步机制 , 由共享资源的数据及其在该数据上的一组操作组成 , 该同步机制称为 _管程 ______________ . 7. 在可变分区存储管理中 , 为实现地址映射 , 一般由硬件提供两个寄存器 , 一个是基 址寄存器 , 另一个是 _限长寄存器 ___. 8. 联想寄存器 （相联存储器 ） 的最重要、最独到的特点是 _按内容并行查找 ___. 9. 在虚拟段式存储管理中 , 若逻辑地址的段内地址大于段表中该段的段长 , 则发生 __ 地址越界 __中断 . 10. 文件系统中若文件的物理结构采用顺序结构 , 则文件控制快 FCB 中关于文件的物 理位置应包括 ___ 首块地址和文件长度 _. 11. 在操作系统设计时确定资源分配算法 , 以消除发生死锁的任何可能性 , 这种解决死 锁的方法是 __死锁预防 __. 12. 选择对资源需求不同的作业进行合理搭配 , 并投入运行是由 _作业调度算法 ___来完 成的. 13. 实时系统应具有两个基本特征 : 及时性和 ___可靠性 ___. 14. 磁带上的文件只能采用 _顺序 ______ 存取方式 . 15. 不让死锁发生的策略可以分成静态和动态的两种 , 死锁避免属于 __动态的 ___. 16. 在 UNIX 系统中 , 文件分成三类 , 即普通文件 , 目录文件和 ___特殊文件 __. 17. 在磁盘调度策略中有可能使 I/O 请求无限期等待的调度算法是 __最短寻道时间优先 18. 进程获得了除CPU 外的所有资源,一旦获得CPU 即可执行,这时进程处于—就绪 _ 状态 . 19. ______________________________________________________ 为实现CPU 与外部设备的并行工作，系统必须引入一通道 ____________________________________ 硬件基础. 20. 操作系统为保证不经文件拥有者授权 , 任何其它用户不能使用该文件所提出的解决 措施是 ___文件保密 __. 21. 两个或两个以上程序在计算机系统中同处于开始和结束之间的状态 , 这就称为 __ 并发 ___. 33. 磁盘调度 34. 缓冲技术 36. 进程调度 37. 虚设备 39. 死锁预防 40. 临界资源 — 42. 交换技术 43. 互斥区 段时间内只允许一个进程访问的资源，也称为独立资源 第一章 一、单项选择题 1、文件系统与数据库系统相比较，其缺陷主要表现在数据联系弱、数据冗余和（C ） A、数据存储量低 B、处理速度慢 C、数据不一致 D、操作繁琐 2、数据的存储结构与数据逻辑结构之间的独立性成为数据的（B） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 3、在数据库系统中，对数据操作的最小单位是（B ） A、字节 B、数据项 C、记录 D、字符 4、数据的逻辑结构与用户视图之间的独立性称为数据的（C） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 5、下述各项中，属于数据库系统的特点的是（C） A、存储量大 B、存取速度快 C、数据共享 D、操作方便 6、在数据库系统中，模式/内模式映像用于解决数据的（B） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 7、在数据库系统中，模式/外模式映像用于解决数据的（C） A、结构独立性 B、物理独立性 C、逻辑独立性 D、分布独立性 8、数据库结构的描述，称为（D ） A、数据库模式 B、数据库 C、数据库管理系统 D、数据字典 9、数据库中全体数据的整体逻辑结构描述成为（D ） A、存储模式 B、内模式 C、外模式 D、概念模式 10、保证数据库中数据及语义的正确性和有效性，是数据库的（C） A、安全性 B、准确性 C、完整性 D、共享性 11、在数据库系统中，数据独立性是指（C） A、用户与计算机系统的独立性 B、数据库与计算机的独立性 C、数据与应用程序的独立性 D、用户与数据库的独立性 12、结构数据模型的三个组成部分是数据结构、数据操作和（C） A、数据安全型控制 B、数据一致性规则 C、数据完整性约束 D、数据处理逻辑 13、数据操纵语言（DML）的基本功能中，不包括的是( B ) A、插入新数据B描述数据库结构 C、数据库中数据排序 D、删除数据库中数据 14、控制数据库整体结构、负责数据库物理结构和逻辑结构的定义与修改人员是（ D ） 北邮算法与数据结构习题参考答案 作业参考答案 一、（带头结点）多项式乘法 C = A×B： void PolyAdd ( list &C, list R) // R 为单个结点 { p=C; while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->exp 2015年秋季学期《数据结构》课程作业 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分） 1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K 是 ____C__的有限集合，R是K上的___H___的有限集合。（第一章） a 存储 b 数据操作c数据元素d操作 e逻辑结构 f 映象 g算法h关系 2.以下关于算法的说法不正确的是____B _________。（第一章） a 一个算法应包含有限个步骤 b算法越简单越好 c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之 d算法中的每个步骤都能在有限时间内完成 3．设某数据结构的二元组形式表示为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是______B________。（第一章） a 线性结构 b 树型结构 c 物理结构 d 图型结构 4.下面程序段的时间复杂度为___C___（第一章） int sum=0; for(i=0; i 第一章 绪论 一、选择题： 1、使用二维表格结构表达数据和数据间联系的数据模型是（C ） A 、层次模型 B 、网状模型 C 、关系模型 D 、实体—联系模型 2、DB 、DBS 、DBMS 间的关系是（C ） A 、D B 包括 DBMS 和 DBS B 、DBMS 包括 DB 和 DBS C 、DBS 包括 DB 和 DBMS 3、在数据库中存储的是（ C ） D 、DBS 与 DB 和 DBMS 无关 A 、数据 B 、数据模型 C 、数据及数据之间的联系 D 、信息 4、数据库系统中，用（ B ）描述全部数据的整体逻辑结构。 A 、外模式 B 、模式 C 、内模式 D 、数据模式 5、数据库中，导致数据不一致的根本原因是（C ） A 、数据量太大 C 、 数据冗余 B 、数据安全性不高 D 、数据完整性约束不强 6、划分层次型、网状型和关系型数据库的原则是（D ） A 、记录的长度 C 、联系的复杂程度 B 、文件的大小 D 、数据及联系的表示方式 7、数据库三级模式体系结构的划分，主要有利于保持数据库的（B ） A 、数据安全性 B 、数据独立性 C 、结构规范化 D 、操作可行性 8、数据库系统中，用（A ）描述用户局部数据的逻辑结构，它是用户和数据库系统间的接口。 A 、外模式 B 、模式 C 、内模式 D 、数据模式 9、数据库系统中，用（C ）描述全部数据的物理存储视图。 A 、外模式 B 、模式 C 、内模式 D 、数据模式 10、数据库系统中用于定义和描述数据库逻辑结构的语言是（B ） A 、DML B 、DDL C 、DCL D 、SQL 11、数据库系统支持的数据共享指的是（D ） A 、同一应用的多个程序共享同一数据集合 B 、多个用户、同一语言程序共享同一数据集合 C 、多个用户共享同一数据文件 D 、多种语言、多个用户、多个应用相互覆盖地使用同一数据集合 12、数据库系统中，当内模式发生变化时，采用（B ）来保证数据的物理独立性。 A 、修改模式定义 A 、修改模式\内模式映像 A 、修改应用程序 B 、修改外模式定义 二、填空题 1、指出下列缩写的含义： （1）DML :DBMS 提供了数据操纵语言 （2）DBMS ：数据库管理系统 ，为数据库的建立、使用和维护而配置的软件系统 （3）DDL ：DBMS 提供了数据定义语言 （4）DD ：数据字典，将数据库作为对象建立数据库，也称系统目录 （5）DBS ：数据库系统，是指带有数据库并利用数据库技术进行数据管理的计算机 系统。 （6）DB A ：数据库管理员 。、2、数据管理技术经历了（人工管理）（文件系统）（数据库系统）三个阶段。 3、DBS 组成部分包括（数据库）（数据库管理系统）（应用系统）（数据库管理员）（用户）五部 分。 、 、 、 4、DBMS 是位于（用户）和（操作系统）之间的一层管理软件。 5、数据库和文件系统的根本区别是（数据的整体结构化）。 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 2017—2018学年度第一学期期末考试 学术英语阅读 院/系_________________ 姓名_________________ 班级_________________ 学号_________________ Direction Read the following passage. While you’re reading, please pay special attention to the underlined or shaded words, phrases and sentences. You’ll be asked to explain them in English later after reading. The Price of Preference Shelby Steele 5 10 15 20 25 30 In a few short years, many blacks and a considerable number of whites would say that I was sanctimoniously (圣洁地) making affirmative action①into a test of character. They would say that this small preference is the meagerest recompense for centuries of unrelieved oppression. And to these arguments other very obvious facts must be added. In America, many marginally competent or flatly incompetent whites are hired every day—some because their white skin suits the conscious or unconscious racial preference of their employers. The white children of alumni are often grandfathered into elite universities in what can only be seen as a residual benefit of historic white privilege. Worse, white incompetence is always an individual matter, but for blacks it is often confirmation of ugly stereotypes. Given that unfairness cuts both ways, doesn’t it only balance the scales of history, doesn’t this repay, in a small way, the systematic denial under which my children’s grandfather lived out his days? In theory, affirmative action certainly has all the moral symmetry that fairness requires—the injustice of historical and even contemporary white advantage is offset (补偿) with black advantage; preference replaces prejudice, inclusion (1) answers exclusion. It is reformist and corrective, even repentant and redemptive (忏悔与救赎的). And I would never sneer at these good intentions. Born in the late forties in Chicago, I started my education (a charitable term in this case) in a segregated (种族隔离的) school and suffered all the indignities that come to blacks in a segregated society. My father, born in the South, made it only to the third grade before the white man’s fields took permanent priority (永久性优先) over his formal education. And though he educated himself into an advanced reader with an almost professorial authority, he could only drive a truck for a living, and never earned more than $90 a week in his entire life. So yes, it is crucial to my sense of citizenship, to my ability to identify with the spirit and the interests of America, to know that this country, however imperfectly, recognizes its past sins and wishes to correct them. Yet good intentions can blind us to the effects they generate when implemented. In our society affirmative action is, among other things, a (2) testament to white goodwill and to black power, and in the midst of these heavy investments its effects can be hard to see. But after twenty years of implementation I think that affirmative action has shown itself to be more bad than good and that blacks—whom I will focus on in this essay—now stand to lose more from it than they gain. In talking with affirmative action administrators and with blacks and whites in general, I found that supporters of affirmative action focus on its good intentions while detractors (反对者) emphasize its negative effects. Proponents talk about “diversity” and “pluralism”; opponents speak of (3) “reverse discrimination”, the unfairness of quotas (指标) and set-asides (保留名额). [1] It was virtually impossible to find people outside either camp. The closest I came was a white male manager at a large computer ①Affirmative action is the policy of favoring members of a disadvantaged group who suffer or have suffered from discrimination within a culture. 平权运动，扶持政策数据库期末考试习题及答案
数据结构期末考试试题及答案
北京大学 2010年 普通生物学期末考试题
数据库原理期末考试试卷答案
北邮算法与数据结构习题参考标准答案
数据结构与算法-北大 HW11 B_B+树
数据库原理-期末考试试题及答案
数据结构 期末考试复习题及答案
北京大学操作系统期末试题有答案
(完整版)郑州大学数据库原理_期末考试试题
北邮算法与数据结构习题参考答案
北大2015年秋季学期数据结构课程作业
数据库原理期末考试习题
《数据结构》期末考试题及答案
北京大学“学术英语阅读”2017年上学期期末考试真题
- 北京大学“学术英语阅读”2017年上学期期末考试真题
- 北京大学2016-2017学年第2学期高等数学A期末考试试卷
- 2018北京大学思修期末考试试题
- (完整版)北京大学微观经济学期末试题及答案
- 北京大学 2010年 普通生物学期末考试题
- 北京大学操作系统期末试题(有答案)
- 北京大学期末考试政治学原理试题集
- 北京大学电磁学2016期末考试题-参考答案03
- 北京大学法学院2013级本科生《刑法分论》期末考试题
- 北京大学期末考试题系列：政治学原理习题集
- 北京大学数据结构与算法北大2013数算期末考试题考试
- 北京大学期末考试政治学原理试题集
- 北京大学期末考试试卷规范及阅卷要求【模板】
- 北京大学2016-2017学年第2学期高等数学A期末考试试卷
- 2018北京大学热学期末考试
- 北京大学操作系统期末试题
- 北京大学算法设计方案与分析课期末试题
- 北京大学信息科学技术学院期末考试
- (完整word版)华中科技大学北京大学2016-2017学年第2 学期 高等数学A期末考试试卷
- 北京大学操作系统期末试题有答案