北大2015年秋季学期数据结构课程作业
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 for(j=i;j s++; a. O(m+n) b. O(n*n) c. O(m*n) d. O(m*logn) 5. 下列有关线性表的叙述中，正确的是____A____。（第二章） a 一个线性表是 n 个数据元素的有限序列 b 线性表中任何一个元素有且仅有一个直接前驱 c 线性表中任何一个元素有且仅有一个直接后继 d 以上说法都不正确 6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的 平均次数为___B___（第二章） a．n b．n/2 c．(n+1)/2 d．(n-1)/2 7.链表不具备的特点是______D___。（第二章） a不必事先估计存储空间 b 插入删除不需要移动元素 c 可顺序访问任一结点 d 所需空间与其长度无关 8.带附加头结点的双循环链表L为空表的条件是_______C_____。（第二章） a L==NULL b L->next==NULL c L->prior==L d L->prior==NULL 9.设广义表L=（（a,b,c））,则L的长度与深度分别为___D_________。（第三章） a 1和1 b 1和3 c 2和3 d 1和2 10. 若栈采用链式存储结构,则下面的说法中正确的是____A____（第四章） a.不需要判断栈满但需要判断栈是否为空 b.需要判断栈是否栈空与栈满 c.需要判断栈满但不需要判断栈空 d.栈满栈空都不需要判断 11. 在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为_____B_______。（第四章） a t->next=r;t=r; b r->next=s;s=r; c s->next=r;s=r; d r->next=t; 12.一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列___B___（第四章） 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 13. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_____A_______。（第四章） a (rear-front+m)%m b rear-front+1 c rear-front-1 d rear-front 14.栈和队列的共同特点是______A____。（第四章） a.只允许在端点处插入和删除元素 b.都是先进后出 c.都是先进先出 d.没有共同点 15.中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是__D____（第四章） a．AB+D*E/FA+*DC+ b．ABD*+EFAD*+/C+ c．ABDEFADC+*+/+*+ d．AB+D*EFAD*+/+C+ 16.如下图所示的4棵二叉树，____C_____不是完全二叉树。（第五章） 17. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为_____C_______。（第五章） a 9 b 10 c 11 d 12 18. 深度为6(根的层次为1)的二叉树至多有____B___结点（第五章） a.64 b.63 c.31 d.32 19.二叉树的第k层的结点数最多为________D____。（第五章） a. 2k-1 b. 2K+1 c. 2K-1 d. 2k-1 20.如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是____B___。（第五章） a 空或只有一个结点 b 高度等于其结点数 c 任一结点无右孩子 d 任一结点无左孩子 21. 树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论_______A__是正确的。（第五章） a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 b.树的后根遍历序列与其对应的二叉树的先序遍历序列相同 c.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 d.以上都不对 22.根据使用频率为5个字符设计的哈夫曼编码不可能是______B______。（第六章） a 111，110，10，01，00 b 000，001，010，011，01 c 001，000，01，11，10 d 100，111，110，101，0 23. 下列数据结构中,不属于二叉树的是______D______（第六章） a. 堆 b. 哈夫曼树 c. 线索二叉树 d. B树 24.采用邻接表存储的图的广度优先遍历算法类似于二叉树的_____D_____。（第七章） a 先序遍历 b 中序遍历 c 后序遍历 d 层次遍历 25.对用邻接表表示的图进行深度优先遍历时，通常是借助___A______来实现算法。 （第七章） a 栈 b 队列 c 树 d 图 26. 在一个图中，所有顶点的度数之和等于图的边数的____C_____倍。（第七章） a. 1/2 b. 1 c. 2 d. 4 27.对线性表进行二分查找，要求线性表必须_______B_____。（第九章） a 以顺序方式存储 b 以顺序方式存储，且结点按关键字有序排序 c 以链接方式存储 d 结点按关键字有序排序，存储方式无所谓 28.排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为 空）的末尾，该排序方法称为_______C_____。（第十章） a 希尔排序 b 冒泡排序 c选择排序 d 插入排序 29.下列四种排序中，_______C_____的空间复杂度最大。（第十章） a. 插入排序 b. 冒泡排序 c. 归并排序 d. 快速排序 二. 填空题，请将正确答案填在____上。（每空1分，共30分） 1.数据结构分为____逻辑结构____和物理结构两种结构。（第一章） 2.线性结构中元素之间存在一对一关系，而树形结构中元素之间存在__一对多___关系， 图形结构中元素之间存在多对多关系。（第一章） n+4n-7)/(5n),则该算法的时间复 3.一个算法的最基本的原操作执行次数为(3n2+2nlog 2 杂度为____ O(n)_____。（第一章） 4.链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑 关系通过___指针_______间接地反映。（第二章） 5.向一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移 动_____N-i+1_______个元素。（第二章） 6.当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时， 应采用_____链式_____存储结构。（第二章） 7.在单链表中，要删除某一指定的结点，必须找到该结点的______前驱______结点。 （第二章） 8.删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行q=____P->next __,p->next=__ q->next ____和___ delete q____的操作。（第二章） 9.设广义表L=（（a，（b,c,d）））,则L的长度为_____1___，深度为_____3____。（第 三章） 10.队列的特点是先进先出，与之对应，栈的特点是___后进先出_________。（第四章） 11.在栈顶进行插入删除一个元素的时间复杂度是___ O(1)_____。（第四章） 12.后缀算式9 2 3 +- 10 2 / -的值为__-1____。（第四章） 13.一个环形队列中共有MaxSize个单元，那么队满时共有__ MaxSize – 1 ____个元素。（第四章） 14.设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S， 一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是______5______。（第四章） 15.一棵高度为6的完全二叉树至少有____32____个结点，最多有___63___个结点。 （第五章） 16.如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为__2n或 2n-1___。（第五章） 17.设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列 为______CABD____。（第五章） 18.已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是__求矩形第i行非零元素之和__。（第七章） 1、19.一个图的三种存储方法中，__________邻接矩阵，邻接表和边集数组____________ 表示法是不唯一的。（第七章） 2、20.一个有n个顶点的无向连通图最少有__n-1_条边，最多___ n(n-1)/2___条边。（第 七章） 21.设一个连通图G中有n个顶点e条边，则其最小生成树上有_____n-1___条边。（第 八章） 22.外排序是指在排序前后，数据在___外存____上，排序时数据调入内存进行的排序 方法。（第十章） 23.在选择排序、冒泡排序、归并排序中，_____选择____排序是不稳定的。（第十章） 三. 简答题。（每小题4分，共40分） 1.简述顺序表和链表存储方式的特点。（第二章） 顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不 移动结点）。其缺点是不能进行随机访问，只能顺序访问；另外，每个结点上增加指针域，造成额外存储空间增大。 2.在一个单链表HL中删除指针p所指结点，应执行如下关键操作：（第二章） if(________) HL = HL->next; else { q = HL; while(________) q = q->next; _____________; } delete p; 答案： 1、p == HL 2、q->next != p 3、q->next = p->next; 或 q->next = q->next->next; 以下2个问题基于下面的环形队列： 设环形队列Q[7]的当前状态如下， 3.写出队列Q的队空、队满定条件及进队、出队操作的的描述语句；（第四章） 空：rear == front 满：(rear+1)%MaxSize == front 进队操作：rear = (rear+1)%MaxSize; Q(rear)=x 出队操作：front = (front+1)%MaxSize; X=Q(front) 4.画出元素a0,a1,a2出队，元素a4,a5,a6,a7进队后队列Q的状态。（第四章） 5.写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序列。（第五章） 前序遍历：ABDFCEGH 中序遍历：BFDACGEH 后序遍历：FDBGHECA 层次遍历：ABCDEFGH 6.已知一组元素为(30,46,62,27,32,50,13,45)，画出按元素排列顺序输入生成的一棵二叉搜索树，并写出在这棵二叉搜索树中查找元素50所需的元素比较次数。（第六章） 二叉搜索树如下图，查找50所需比较次数为4. 7. 给定权值{6,7,12,10,30,25}，构造相应的哈夫曼树，要求写出构造步骤，并计算该树的带权路径长度。（第六章） 构造的哈夫曼树为： 带权路径长度为：(30+25)*2 + (6+7+10+12)*3 = 215 8. 已知一个无向图的邻接表表示为： 画出该图的图形表示，并写出在该邻接表存储结构下，以顶点v4为出发点进行深度优先遍历的遍历序列。（第七章） 图形如下：以v4为出发点的遍历序列为：v4,v3,v5,v2,v1 9.对如下的图，用Prim算法从顶点5开始求最小生成树，写出按次序产生的边。采用 Kruscal算法产生的边次序是哪些？画出最小生成树。（第八章） Prim(5,6)(4,6)(1,4)(3,4)(1,2) Kruscal(1,4)(5,6)(3,4)(4,6)(1,2) 10.已知序列（49，38，65，97，76，13，27，49）请用插入排序写出每一趟排序的结果。（第十章） 第一趟：38，49，65，97，76，13，27，49 第一趟：38，49，65，97，76，13，27，49 第一趟：38，49，65，97，76，13，27，49 第一趟：38，49，65，76，97，13，27，49 第一趟：13，38，49，65, 76，97，27，49 第一趟：13，27，38，49，65, 76，97，49 第一趟：13，27，38，49，49，65, 76，97 数据结构大作业 作业题目：职工信息管理系统 姓名： 学号： 班级: 指导教师: 日期： 一、主要功能： 这个职工信息管理系统是由C语言编写的程序，它用起来很方便又很灵活。它由输入职工信息，输出职工信息，按职工号，部门号，工资排序，按职工号，部门号，工资来输出职工的所有信息。删除有关职工的所有信息，保存职工的所有信息并退出等11个模块儿组成。 二、实验环境：C语言、C++、C# 等等。 三、功能说明： 下面按步骤来介绍一下，职工信息管理系统的基本操作。 这是运行程序以后出现的主界面。如图（1）所示： 图（1）主界面 1.输入职工的信息 该模块儿的功能是分别输入职工的姓名，职工号，部门号，工资等信息。每次输入职工的所有信息以后，界面上会显示出《输入完成！》的命令。如图（2）所示： 图（2）输入职工信息 2.输出所有的职工信息 该模块儿的功能是显示出有关职工的所有信息。操作如图（3）所示： 图（3）输出所有的职工信息 3.按职工号排序 该模块儿的功能是按职工号排序所有的职工。我们按3的时候，界面上会显示出《排序完成！》的命令。如图（4）所示： 图（4）按职工号排序 4.输出所有的职工号码 该模块儿的功能是显示出已排序好的所有职工的号码。操作如图（5）所示： 图（5）输出所有的职工号 5.按部门号排序 该模块儿的功能是按部门号排序所有职工的部门号。我们按5的时候，界面上会显示出《排序完成！》的命令。如图（6）所示： 图（6）按部门号排序 6.输出所有的部门号 该模块儿的功能是显示出已排序好的所有部门号。操作如图（7）所示： 图（7）输出所有的部门号 7.按职工的工资排序 该模块儿的功能是按工资排序所有职工的工资。我们按7的时候，界面上会显示出《排序完成！》的命令。如图（8）所示： 题目： 学院： 专业班级： 学生姓名： 指导教师： 2016 年06 月2 9日 目录 一、课程设计目的 (3) 二、课程设计步骤 (3) 三、课程设计内容 (4) 四、课程设计报告 (6) 五、提交材料 (6) 六、考核方式与评分标准 (7) 七、参考文献 (8) 附录1 齐齐哈尔大学软件工程系课程设计说明书（报告）撰写规范 (9) 一、课程设计目的及要求 《数据结构与算法分析》课程设计培养计算机专业的学生的算法程序设计能力。通过上机实验，可以培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对数据结构课程和算法的理解。使学生更好地掌握数据结构的基本概念、基本原理、及基本算法,具有分析算法、设计算法、构造和开发较复杂算法的基本能力。 要求学生能综合运用《数据结构与算法分析》的相关知识，培养学生上机解决一些与实际应用结合紧密的、规模较大的问题的能力，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析实际问题的能力并提高C语言编程技巧，培养良好的编程风格。 课程设计要求独立完成，题目自选（参考题目见三，也可自拟）,但需要老师确认(6月16日前定题)，一人一题，要求程序有能采用交互式工作方式的界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。要求在教学周的第18周前完成。 二、课程设计步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的课程设计的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，完成课程设计的应有如下的5个步骤： 1.问题分析和任务定义 通常，课程设计题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2.数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个 数据结构大作业报告 数据结构大作业实验报告课程名称:数据结构设计题目:客户去银行储蓄模拟程序一( 实验题目 (1)内容描述:编写一个程序反映客户到银行储蓄的过程。 (2)基本要求:要实现以下功能:1:排队 2:储蓄 3:查看排队4.:删除自己所排的队 5.不再排队,剩下的客户依次储蓄 6:下班 二( 实验的工程组成图和程序结构图 main bank 本工程的组成结构如左图所示,程序结构图如右图所示。三( 工程所包含的函数的功能描述 Bank():模拟客户到银行去储蓄的过程。客户排队储蓄，所以要用到一个队列， 这里设计了一个不带头结点的单链表作为队列。 四( 实验工程的算法描述及流程图 //客户排队去银行储蓄,用到了队列的知识,这里设计了一个不带头结点的单链表作为队列来完成排队储蓄过程 #include #include 北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业 张铭编写并发布 mzhang@https://www.wendangku.net/doc/1f8959585.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 树 操作系统原理试题 一. 名词解释题 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. 互斥区 段时间内只允许一个进程访问的资源，也称为独立资源 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 数据结构实验讲义 一实验步骤 随之计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10，000行的程序的难度绝不仅仅是一个5，000行的程序两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如(从实际问题中提出来的)一个“真正的，，软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的五个步骤：’ (一)问题分析和任务定义 通常，实习题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。注意：本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。 (二)数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的规格说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类c语言写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 (三)编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过60个字符。每个函数体，即不计首部和规格说明部分，一般不要超过40行，最长不得超过60行，否则应该分割成较小的函数。要控制if语句连续嵌套的深度。其他要求参见第一篇的 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（选择最准确的一项，共15小题，每小题2分，共计30分） 1. 数据结构是指。 A. 一种数据类型 B. 数据的存储结构 C. 一组性质相同的数据元素的集合 D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为。 void fun(int n) { int i=1,s=0; while (i<=n) { s+=i+100; i++; } } A. O(n) B. O(n) C. O(nlog2n) D. O(log2n) 3. 在一个长度为n的有序顺序表中删除其中第一个元素值为x的元素时，在查找元素x时采用二分查找方法，此时删除算法的时间复杂度为。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n) 4. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是。 A.top++;s[top]=x; B.s[top]=x;top++; C.top--;s[top]=x; B.s[top]=x;top--; 5. 设环形队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。 A. rear-front B. rear-front-1 C. (rear-front)％N+1 D. (rear-front+N)％N 6. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的 数据结构课程设计 一、引言 (1) 二、原始数据和系统功能 (2) （一）原始数据 (2) （二）系统功能 (2) 三、程序总体设计 (2) （一）数据结构 (2) （二）模块划分和层次结构 (4) （三）函数原型清单 (5) （四）程序总体框架 (6) （五）程序组织 (10) 四、功能模块函数设计和调试 (11) （一） (11) （二） (13) 五、课程设计总结 (13) 六、程序清单 (14) （一）主控源程序文件main.cpp (14) （二）航空订票a.cpp (15) 一、引言 数据结构这门课程能够让我们更加深入的去理解c语言的结构和算法，增加我们对算法的理解程度。而数据结构试验更是在理论的基础上让我们更深层次的进行实践，加强我们的逻辑思维处理错误的能力，同时对我们各个方面都有着重要的影响，所以学好数据结构是非常有必要的 二、原始数据和系统功能 （一）原始数据 hainan 1 B60 SAT 121 180 fujian 2 C61 MON 10 100 lkongyan 3 S62 THU 10 50 guangxi 4 M63 WED 30 30 hefei 5 H64 THU 30 10 （二）系统功能 * 1.查看航线信息: * * 2.查看已订票客户信息: * * 3.查询航线: * * 4.添加航线: * * 5.办理订票业务: * * 6.办理退票业务* * 7.退出系统: * 三、程序总体设计 （一）数据结构 （二）模块划分和层次结构 依据程序的数据结构和功能，遵照“自顶向下”原则，采用基于函数的逐步求精法，描述该程序的层次结构。图1显示出该程序的层次结构，共三层。 数据结构课程设计课题名称 专业名称 学生姓名 学号+电话 指导教师 评分细则 目录 评分细则----------------------------------------------------------------------------------------------------------------- 2 一、课题描述 ---------------------------------------------------------------------------------------------------------- 4 二、需求分析 ---------------------------------------------------------------------------------------------------------- 4 2.1 ------------------------------------------------------------------------------------------------------------------ 4 2.2- ------------------------------------------------------------------------------------------------------------------4 2.3--------------------------------------------------------------------------------------------------------------------4 三、概要设计 ---------------------------------------------------------------------------------------------------------- 4 3.1 结构分析 ----------------------------------------------------------------------------------------------------------- 4 3.2函数------------------------------------------------------------------------------------------------------------ 4 3.2.1 malloc() --------------------------------------------------------------------------------------------- 4 3.2.2getchar() ----------------------------------------------------------------------------------------------------- 5 3.2.3 list_create() ------------------------------------------------------------------------------------------------ 5 3.2.4 list_disp() --------------------------------------------------------------------------------------------------- 5 3.2.5 list_sort() --------------------------------------------------------------------------------------------------- 5 四、详细设计 ---------------------------------------------------------------------------------------------------------- 5 4.1课题分析 ----------------------------------------------------------------------------------------------------- 5 4.1.1选择 ------------------------------------------------------------------------------------------------- 5 4.1.2冒泡 --------------------------------------------------------------------------------------------------------- 5 4.1.3 堆------------------------------------------------------------------------------------------------------------ 6 4.1.4 快速--------------------------------------------------------------------------------------------------------- 6 4.1.5 基数--------------------------------------------------------------------------------------------------6 4.1.6 希尔--------------------------------------------------------------------------------------------------------- 6 4.1.7 归并--------------------------------------------------------------------------------------------------6 4.2课题实现 ----------------------------------------------------------------------------------------------------- 7 五、测试数据及结果------------------------------------------------------------------------------------------------- 9 六、调试分析及总结----------------------------------------------------------------------------------------------- 10 北京大学1997硕士入学数据结构试题 1 （16分） 填空 ① 设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数 为，最小结点数为。 ② 某二叉树结点的对称序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列为，该二叉树对应的树林包括棵树。 ③ 求具有最小带权外部路径长度的扩充二叉树的算法称为算法，对于给出的一组权W={10，12，16，21，30}，通过该算法求出的扩充二叉树的带权外部路径长度为。 ④ 设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是。 2 （10分） 请简要回答下列问题 ① 什么是抽象数据类型？试举一例说明之。 ② 什么是广义表？请简述广义表与线性表的主要区别。 3 （6分） 给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用散列法进行存储，规定负载因子a=0.6。 ① 请给出除余法的散列函数。 ② 用开地址线性探查法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。 4 （6分） 本题要求在检索各结点的概率不相等的条件下构造最佳二叉排序树。给出关键码集合 { B, E, H} key1 key2 key3 以及权的序列 ( 9 4 5 8 6 1 3) p1 p2 p3 q0 q1 q2 q3 请构造最佳二叉排序树。 5 （12分） ① 请画出往图1的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码150后得到的B-树。 ② 包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程） 图1 题5图 6 （10分） 如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去了平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。 ①请画出调整后的AVL树。 ②假设AVL树用llink-rlink法存储，T是指向根结点的指针、请用PASCAL（或C）语句表示出这个高速的过程。 （说明：不必写出完整的程序，只需用几个语句表示出在本题所给的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用）。 课程设计报告排序二叉树 完成日期：2015/01/03 目录 一、需求分析 1.运行环境； 2.程序所实现的功能； 3.程序的输入： 4.程序的输出： 5.测试数据， 6.合作人及其分工 二、设计说明 1.算法设计的思想； 2.主要的数据结构设计说明； 3.程序的主要流程图； 4.程序的主要模块，； 5.程序的主要函数及其伪代码说明. 6.合作人设计分工。 三、上机结果及体会 1.合作人编码分工； 2.实际完成的情况说明； 3.程序的性能分析； 4.打印程序运行时的初值和运行结果，画出相应的图示； 5.上机过程中出现的问题及其解决方案； 6.程序中可以改进的地方说明； 7.收获及体会； 8.源程序清单并附上注释。 四、参考文献 一、需求分析 1.运行环境 a软件环境 操作系统：windows 7 编译器 microsoft visual studio 2010 b硬件环境 联想 n480 2.程序所实现的功能 1.创建二叉树： （1）按提示信息输入一组关键字值，并建立相应的二叉排序树。 （2）按照先序遍历方式显示建立的二叉排序树。 （3）按照中序遍历方式显示建立的二叉排序树。 （4）按照后序遍历方式显示建立的二叉排序树。 2.显示二叉排序树： （1）按照先序遍历方式显示二叉排序树。 （2）按照中序遍历方式显示二叉排序树。 （3）按照后序遍历方式显示二叉排序树。 （4）按照层次遍历方式显示二叉排序树。 3.删除一个结点： 要求可以实现删除根结点、叶子结点以及其它任意结点的功能。 （1）按照先序、中序、后序方式显示删除前的二叉排序树。 （2）按提示信息输入被删除结点的值，并在二叉排序树进行删除。 （3）显示删除是否成功的结果。 （4）若删除成功，则按照先序、中序、后序方式显示删除后的二叉排序树。 4.插入一个结点： （1）按照先序、中序、后序方式显示插入前的二叉排序树。 （2）按提示信息输入要插入结点的值，并在二叉排序树进行插入。 （3）显示插入是否成功的结果。 （4）若插入成功，则按照先序、中序、后序方式显示插入后的二叉排序树。 5.查找给定值的结点： （1）按照先序、中序、后序方式显示二叉排序树。 （2）按提示信息输入待查找的值，并在二叉排序树进行查找。 （3）显示查找是否成功的结果。 6.交换二叉排序树： （1）按照先序、中序、后序方式显示初始的二叉排序树。 （2）按照先序、中序、后序方式显示交换左右子树后的二叉排序树。 7.退出：退出整个算法演示程序。 3.程序的输入： “数据结构”课程设计题目 1、城市链表 [问题描述] 将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 [基本要求] （1）给定一个城市名，返回其位置坐标； （2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。 [测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 2、约瑟夫生死者游戏 [问题描述] 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 [测试数据] m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 [实现提示] 程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 3、括号匹配的检验 [问题描述] 假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）[ ]）或[（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： 数据结构课程设计大作业 题目纸牌游戏 专业计算机科学与技术 学生姓名 __________________ 学号 _____________________ 指导教师 __________________ 完成日期 __________________ 信息与工程学院 目录 一、实验内容概述（设计任务与技术要求） (1) 二、实验目的概述（总体设计方案） (1) 三、解题思路的描述（数据结构和算法的设计）： (1) 四、源程序清单（源程序中应该附有必要的注释） (2) 五、程序调试及测试结果 (4) 六、结论 (4) 七、参考文献 (5) 【内容摘要】 编号为1~52的牌，正面向上，从第二张开始，以2为基数，是2的倍数的牌翻一次，直到最 后一张牌；然后，从第三张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从 第四张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；依次类推，知道所有以52 为基数的牌翻过一次。输出：这时正面向上的牌有哪些？ 【关键字】 52张纸牌，倍数，基数，数组 【Abstract 】 Numbered 1 to 52 cards, face up, starting from the second to 2 as the base, is a multiple of 2 cards turning on ce, un til the last card; and the n, begi nning from the third to 3 as the base,is a multiple of 3 cards turning once, un til the last card; and the n start from the fourth to 4 as the base, is a multiple of 4 cards turning once, un til the last card; and so on, that was all of 52base of the card turned over on ce.Output: At this time what the cards face up? 【Key words 】 52 cards, multiple, base, array 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 题目：数据结构上机报告学院：电子工程学院 专业：信息对抗技术 学生姓名：甘佳霖 学号：14020310092 西安电子科技大学 数据结构课程实验报告实验名称线性表 电子工程学院 1402031 班Array姓名甘佳霖学号 14020310092 同作者 实验日期 2017 年 3 月 18 日 实验一线性表 一、实验目的 1．熟悉线性表的顺序和链式存储结构 2．掌握线性表的基本运算 3．能够利用线性表的基本运算完成线性表应用的运算 二、实验要求 1.设有一个线性表E={e1, e2, … , e n-1, e n}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ e n, e n-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。 2.已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。 三、设计思路 1.顺序表做逆置操作时将对应的首尾元素位置交换，单链表的指针end指向链表的末尾，指针start指向链表头结点，指针s用来找到指向end节点的节点，将指向链表末尾和头结点的存储内容交换，然后头结点指针指向下一节点，s指针从start节点开始遍历寻找指向end 指针的节点，并将end指针赋值为s指针，就完成了单链表的逆置，可以看出单链表和顺序表都可以完成线性表的逆置。 2.分解单链表的实现思路是首先新建3个循环链表，然后顺序遍历单链表，ASCII码判断链表中的元素属于哪一类元素，然后将这个元素添加到对应的循环链表中，从而实现分解单链表的功能。 四、运行结果 1.单链表逆置： 第七章树 PROBLEM 2 (1/1 分) 一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.) k^(h-1) k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确 (k^h-1)/(k-1) Explanation 层数---节点数 number of levels---number of nodes 0---1 1---k 2---k^2 3---k^3 .... h---k^h 所以答案是： so, the answer is： 1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1) PROBLEM 3 (1/1 分) 2-3树是一种特殊的树，它满足两个条件： （1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同； 如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。(多项) 2-3 tree is a special kind of tree, it satisfy: （1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node. If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers） 4, 7, - 正确 4 5 6 7 Explanation 倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。 倒数第二层若是4个结点，深度为3，倒数第三层（第二层）有2个结点，一共4+2+1=7个非叶子结点。 If the second level from the bottom has 3 nodes, the depth of tree will be 2, and the tree will has 4 non-leaf nodes, including the root node. If the second level from the bottom has 4 nodes, the depth of tree will be 3, the third level from the bottom will has 2 nodes, and the tree will has 4+2+1=7 non-leaf nodes数据结构大作业含源代码
数据结构课程设计
数据结构大作业报告
数据结构与算法-北大 HW11 B_B+树
北京大学操作系统期末试题有答案
数据结构课程作业
数据结构大作业要求
数据结构考试题8
数据结构课设汇总
大数据结构大作业报告材料
北京大学1997硕士入学数据结构试题
数据结构课设
数据结构课程设计题
数据结构大作业-纸牌游戏
北大2015年秋季学期数据结构课程作业
西电数据结构大作业
北大PKU 慕课 EDX 数据结构与算法 第七章图 quiz答案与解析
- 北京大学各院系课程设置一览
- 北大2015年秋季学期数据结构课程作业
- 北京大学2016年秋季学期《数据结构》课程作业【答案】
- 北京大学操作系统期末试题有答案
- 北京大学数据结构与算法信科数算2007秋期末考试题
- 北京大学1997硕士入学数据结构试题
- 北京大学网络教育数据结构作业
- 北京大学数据结构1997年考研真题硕士研究生入学考试试题
- 北京大学数据结构与算法北大2013数算期末考试题考试
- 北京大学数据结构与算法2017-2018数算期中考试题考试试题(Final)
- 北大数据结构课件,内部资料,精品
- 北大数据结构讲义数据结构及算法的复习
- 北京大学数据结构与算法B 王洪庆 16期末考试题
- 北京大学各院系课程设置一览
- 北京大学数据结构与算法2015-16DS期末考试题考试
- 算法与数据结构(北京大学信息学院)课件1
- 北大数据结构与算法期末考试模拟试卷
- 北京大学1997硕士入学数据结构试题
- 北大考题(数据结构与算法)
- 北京大学数据结构与算法2016-2017数据结构与算法final-ans