数据结构期末考试

数据结构期末考试Tag内容描述：<p>1、四川大学期末考试题解答 (2003-2004 学年第二学期 ) 课程名: 数据结构(B) 计算机科学与技术专业适用 人数: 学院: 专业: 教师姓名: 姓名: 学号: 成绩: 一、 设 n 个人围坐在一个圆桌周围，现在从第 s 个人开始报数，数到第 m 个人，让他出 局；然后从出局的下一个人重新开始报数，数到第 m 个人，再让他出局，如此反复 直到所有的人全部出局为止。下面要解决的 Josephus 问题是：对于任意给定的 n, s 和 m， 求出这 n 个人的出局序列。请以 n = 9, s = 1, m = 5 为例，人工模拟 Josephus 的求解过程以 求得问题的解。 （9 分） 【解答】 出。</p><p>2、第1章 绪论1. 填空（1）（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 （2）（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。 （3）从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。【解答】集合，线性结构，树结构，图结构 （4）数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。【解答】顺序存储结构，链接存储结构。</p><p>3、数据结构数据结构 应用题应用题 天涯古巷天涯古巷 出品出品 第三章第三章 题型一：表达式求值题型一：表达式求值 按照四则运算加按照四则运算加（+ +） 、减、减（- -） 、乘、乘（* *） 、除、除（/ /）和幂运算和幂运算( ( ) )优先关系的惯例优先关系的惯例，画出对下列算术，画出对下列算术 表达式求值时操作数栈和运算符栈的变化过程：表达式求值时操作数栈和运算符栈的变化过程：A A- -B BC/D+C/D+EEF F 解：解：BC=G G/D=H ABC=G G/D=H A- -H=I EF=J I+J=KH=I EF=J I+J=K 步骤步骤 OPTROPTR 栈栈 OPNDOPND 栈栈 输入字符输入字符 主。</p><p>4、第1章 绪论1.数据(Data) ：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。2.数据元素(Data Element) ：表示一个事物的一组数据称为一个数据元素（结点顶点、记录）；数据元素是数据的基本单位。3.数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。4.数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C =A,B,C, 。</p><p>5、试题一一、单项选择题（每小题 2 分，共20分）（1）以下数据结构中哪一个是线性结构？（）A）有向图 B）队列 C）线索二叉树 D）B树（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）字符A。</p><p>6、2013春季算法与数据结构期末考试复习注：以下复习资料样式和类型与期末考试一样但绝不是考试原题，请大家不要误会。包括平时的三次作业特别是本次复习题要认真做。只有类似的题会做，考试才能作答。一、（10%）现开列数据结构是：单链表、双向链表、栈、队列、树、二叉树、森林、有向图（网）和无向图（网）。参考上述开列，将下列五个小题中属于何种数据结构写在括号中的横线上1. 答：（________________）ACBD2. 答：（________________）ACBD3. 答：（________________）ACBCD4. 答：（________________）A4CB5CD6 8 29。</p><p>7、1. 、选择题1) （无序或有序）顺序表中插入元素的时间复杂度：__O(n)__。2) 带头结点的链表，如何判断其是否为空链表：__head-data=0___。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针.3) 数组形式存放的队列，其大小为n，最多可存放多少个元素（即在具有n个单元的循环队列中，队满时共有多少个元素 ）：_n-1_。常用空闲单元法（人为浪费一个单元，则队满特征可改为front=(rear+1)%N）：即front和rear之一指向实元素，。</p><p>8、数据结构课后练习题一、填空题（第二章）1、顺序表中逻辑上相邻元素的物理位置相邻，单链表中逻辑上相邻的元素物理位置可以相邻，也可以不相邻。2、在一个长度为n的顺序表中删除第i个元素，平均要移动n-i个元素，如果在第i个元素之前插入一个元素，平均要移动n-i+1个元素。3、在一个单链表中，若p所指的结点不是最后结点，在p之后插入s结点，则执行s-next=p-next;p-next=s。4、在一个长度为n的顺序表的表尾插入一个新元素的时间负责度为O。5、非空的单循环链表head的尾结点（由指针P所指）满足p-next=head。（第三章）1.栈和队列都是线性。</p><p>9、院（系） 班级 姓名 学号 装订线专业数据结构（C语言描述）期末试卷（ 学年 第 学期）题号总分得分一、填空题（每空 1 分，共 15 分） 1、 实现数据结构的基本存储方法有： ， 。 顺序存储结构； 链接存储结构2、 若算法中的语句执行次数之和为 T ( n )=3525 n +4 n log n ，则算法的时间复杂度是 。 O （ n log n ）3、 假设以 S 和 X 分别表示进栈和出栈操作，则对输入序列 a , b , c , d , e 进行一系列操作 SSXSXSSXXX 之后，得到的输出序列为。 b , c , e d , a4、 在串。</p><p>10、四川大学期末考试题解答(2003-2004学年第二学期)课程名: 数据结构(B) 计算机科学与技术专业适用 人数:学院: 专业: 教师姓名:姓名: 学号: 成绩:一、 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。（9分）【解答】出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2。</p><p>11、华南农业大学期末考试试卷及参考答案华南农业大学期末考试试卷及参考答案 2011 学年第一学期学年第一学期 考试科目 数据结构考试科目 数据结构 考试类型 闭卷 考试时间 考试类型 闭卷 考试时间 120 分钟分钟 班级班。</p>