当前位置:文档之家› 广东工业大学数据结构与C语言2011-2019年考研初试真题

广东工业大学数据结构与C语言2011-2019年考研初试真题

广东工业大学数据结构与C语言2011-2019年考研初试真题

数据结构C语言第三版习题5参考答案

习题5参考答案 5.1 选择 (1)C(2)B(3)C(4)B(5)C(6)D(7)C(8)C(9)B(10)C (11)B(12)C(13)C(14)C(15)C(16)B 5.2 填空 (1)1 (2)1036;1040 (3)2i (4) 1 ; n ; n-1 ; 2 (5)2k-1;2k-1 (6)ACDBGJKIHFE (7)p->lchild==NULLL (8)Huffman树 (9)其第一个孩子; 下一个兄弟 (10)先序遍历;中序遍历 5.3 叶子结点:C、F、G、L、I、M、K; 非终端结点:A、B、D、E、J; 各结点的度: 结点: A B C D E F G L I J K M 度: 4 3 0 1 2 0 0 0 0 1 0 0 树深:4 5.4 无序树形态如下: 二叉树形态如下:

5.5 二叉链表如下: 三叉链表如下: 5.6 先序遍历序列:ABDEHICFJG

中序遍历序列:DBHEIAFJCG 后序遍历序列:DHIEBJFGCA 5.7 (1) 先序序列和中序序列相同:空树或缺左子树的单支树; (2) 后序序列和中序序列相同:空树或缺右子树的单支树; (3) 先序序列和后序序列相同:空树或只有根结点的二叉树。 5.8 这棵二叉树为: 5.9 先根遍历序列:ABFGLCDIEJMK 后根遍历序列:FGLBCIDMJKEA 层次遍历序列:ABCDEFGLIJKM 5.10 证明:设树中结点总数为n,叶子结点数为n0,则 n=n0 + n1 + …… + n m (1) 再设树中分支数目为B,则 B=n1 + 2n2 + 3n3+ …… + m n m (2) 因为除根结点外,每个结点均对应一个进入它的分支,所以有 n= B + 1 (3) 将(1)和(2)代入(3),得 n0 + n1 + …… + n m = n1 + 2n2 + 3n3+ …… + m n m + 1 从而可得叶子结点数为: n0 = n2 + 2n3+ …… + (m-1)n m + 1 5.11 由5.10结论得,n0 = (k-1)n k + 1 又由 n=n0 + n k,得n k= n-n0,代入上式,得 n0 = (k-1)(n-n0)+ 1 叶子结点数为:n0 = n (k-1) / k

2014(1)数据结构-A-试题

南阳理工学院2013-2014学年第2学期试卷(A卷) 课程:《数据结构》课程号:1504108130 考核方式:(闭卷)课程性质:专业必修课适用对象:12级软件工程专业 题号一二三四五总分复核人 满分20 20 10 30 20 100 得分 评卷人得分 一、选择题:(每题2 分,共20 分) 1.设某数据结构的二元组形式表示为A=(D,R),D={01,02,03,04,05,06, 07,08,09},R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03, 07>,<03,08>,<03,09>},则数据结构A是()。 A.线性结构 B.树型结构 C.物理结构 D.图型结构 2.栈和队列的共同特点是()。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 3.在头指针为head的循环链表中,判断指针变量P指向尾结点的条件是()。 A.p->next->next==head B.p->next==head C.p->next->next==NULL D.p->next==NULL 4.在单链表中,要将s所指结点插入到p所指结点之后,其语句应为()。 A.s->next=p+1; p->next=s; B.(*p).next=s; (*s).next=(*p).next; C.s->next=p->next; p->next=s->next; D.s->next=p->next; p->next=s; 5.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾 元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为 ()。 A.r-f B.(n+f-r)%n C.n+r-f D.(n+r-f)%n 6.设有数组A[0..7][0..9],数组的每个元素长度为2字节,数组从内存首地址 1000开始顺序存放,当用以行为主存放时,元素A[5][8]的存储首地址为()。 A.1116 B.1094 C.1138 D.1120 7.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上 所有元素)依次存放于一维数组B[1..n(n+1)/2]中,则在B中确定a ij(i

数据结构(C语言版)第三版__清华大学出版社_习题参考答案

附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表(Hash)存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下: 数据:数据是信息的载体,是计算机程序加工和处理的对象,包括数值数据和非数值数据。数据项:数据项指不可分割的、具有独立意义的最小数据单位,数据项有时也称为字段或域。数据元素:数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理,一个数据元素可由若干个数据项组成。 数据逻辑结构:数据的逻辑结构就是指数据元素间的关系。 数据存储结构:数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型:是指变量的取值范围和所能够进行的操作的总和。 算法:是对特定问题求解步骤的一种描述,是指令的有限序列。 1.4 语句的时间复杂度为: (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 参考程序: main() { int X,Y,Z; scanf(“%d, %d, %d”,&X,&Y,Z); if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d”,X,Y,Z);} else { printf(“%d, %d, %d”,X,Z,Y);}

数据结构C语言版第2版课后习题答案

数据结构(C语言版)(第2版) 课后习题答案 李冬梅

目录 第1章绪论............................................. 错误!未定义书签。第2章线性表........................................... 错误!未定义书签。第3章栈和队列......................................... 错误!未定义书签。第4章串、数组和广义表................................. 错误!未定义书签。第5章树和二叉树....................................... 错误!未定义书签。第6章图................................................ 错误!未定义书签。第7章查找............................................. 错误!未定义书签。第8章排序............................................. 错误!未定义书签。

第1章绪论 1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案: 数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构:数据对象在计算机中的存储表示,也称为物理结构。 抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案: 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。 即相同的逻辑结构,可以对应不同的存储结构。 3.简述逻辑结构的四种基本关系并画出它们的关系图。

数据结构C语言版第2版课后习题答案

数据结构C语言版第2版课后习题答案 本页仅作为文档封面,使用时可以删除 This document is for reference only-rar21year.March

数据结构(C语言版)(第2版) 课后习题答案 李冬梅

目录 第1章绪论 ............................................................................ 错误!未定义书签。第2章线性表......................................................................... 错误!未定义书签。第3章栈和队列 ..................................................................... 错误!未定义书签。第4章串、数组和广义表 ........................................................ 错误!未定义书签。第5章树和二叉树 .................................................................. 错误!未定义书签。第6章图 ................................................................................ 错误!未定义书签。第7章查找 ............................................................................ 错误!未定义书签。第8章排序 ............................................................................ 错误!未定义书签。 I

广东工业大学 数据库 真题 附答案 (1)

广东工业大学试卷用纸,共 页,第 页 学 院 : 专 业: 学 号: 姓 名 : 装 订 线 广东工业大学考试试卷 ( ) 课程名称: 考试时间: 年 月 日 (第 周 星期 ) 题 号 一 二 三 四 五 六 七 八 九 十 总分 评卷得分 评卷签名 复核得分 复核签名 一、填空题(每题1分,共10分) 1、数据库领域中最常用的数据模型有 层次模型 、 网状模型 、 关系模型 和面向对象模型。 2、数据库设计包括需求分析、概念结构设计、 逻辑结构设计 、 物理结构设计 数据库实施、数据库运行和维护六个阶段。 3、事务的特性包括 原子性 、 持续性 、隔离性和一致性。 4、 并发调度的可串行性 是并发事务正确性的准则。 5、F 逻辑蕴涵的全体函数依赖构成的函数依赖的集合,称为F 的 闭包 。 6、数据是 描述事物的符号记录 。 二、选择题(每题2分,共20分) 1、 在数据库的三级模式结构中,描述数据库中全体数据的全局逻辑结构和特性的是_____。 A 、外模式 B 、内模式 C 、存储模式 D 、模式 2、 实体完整性是指关系中 ____。 A 、元组值不允许为空 B 、属性值不允许空 C 、主属性值不允许为空 D 、主码值不允许为空 3、数据库系统的逻辑独立性是指____。 A 、不会因为数据的变化而影响应用程序 B 、不会因为系统数据存储结构预数据逻辑结构的变化而影响应用程序 C 、不会因为存取策略的变化而影响存储结构 D 、不会因为某些存储结构的变化而影响其他的存储结构。 4、候选关键字中属性称为 。 A.非主属性 B.主属性 C.复合属性 D.关键属性

数据结构(c语言版)第三版清华大学出版社习题参考答案

不管怎样,生活还是要继续向前走去。有的时候伤害和失败不见得是一件坏事,它会让你变得更好,孤单和失落亦是如此。每件事到最后一定会变成一件好事,只要你能够走到最后。附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B. C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表(Hash)存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下: 数据:数据是信息的载体 是计算机程序加工和处理的对象 包括数值数据和非数值数据 数据项:数据项指不可分割的、具有独立意义的最小数据单位 数据项有时也称为字段或域 数据元素:数据元素是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据逻辑结构:数据的逻辑结构就是指数据元素间的关系 数据存储结构:数据的物理结构表示数据元素的存储方式或者数据元素的物理关系 数据类型:是指变量的取值范围和所能够进行的操作的总和 算法:是对特定问题求解步骤的一种描述 是指令的有限序列 1.4 语句的时间复杂度为: (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1)

2014年数据结构补考试题

一填空题 1.已知一N*N三角矩阵按行序为主序存放,下标从1开始,每个元素占l字节,则a[i][j]地址为当i≥j时,地址为i(i+1)/2+j-1;当i=i;j--) s; 13.在单链表中设置头结点的作用是使所有链表的头指针非空,并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行,从而与其他位置的插入、删除操作一致(插入和删除首元结点时不用进行特殊处理)。 14.中缀式a+b*3+4*(c-d)对应的前缀式为 ++a×b3×4-cd,若a=1,b=2,c=3,d=4,则后缀式db/cc*a-b*+的运算结果为18 。 15.有向图G的强连通分量是指有向图的极大强连通子图。 18.设单链表的结点结构为(data,next),next为指针域,已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点 , 若将结点y插入结点x之后,则需要执行以下语句: py->next=px->next; px->next=py; 19. 数组的存储结构采用顺序存储方式。 二选择题 1.以下数据结构中,哪一个是线性结构(D) A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串 2.对稀疏矩阵进行压缩存储目的是(C)。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D.降低运算的时间复杂度 3.非空的循环单链表head的尾结点p↑满足(A)。 A.p↑.link=head B.p↑.link=NIL C.p=NIL D.p= head

数据结构(c语言版)课后习题答案完整版

第1章绪论 5.选择题:CCBDCA 6.试分析下面各程序段的时间复杂度。 (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.选择题 babadbcabdcddac 2.算法设计题 (6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; } return pmax->data; (7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。 void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; }

} (10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。 [题目分析] 在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动(删第i个元素,第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素,并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1,j=n),从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为item的数据元素位置。 void Delete(ElemType A[ ],int n) ∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素。 {i=1;j=n;∥设置数组低、高端指针(下标)。 while(i

全国2014年4月自考数据结构真题

绝密★考试结束前 全国2014年4月高等教育自学考试 数据结构试题 课程代码:02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ..的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素,若第一个元素的存储地址是1000,则最后一个元素地址是1036,第5个元素的地址是 A.1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空,元素1、2、3、4、5、6依次入栈,得到的出栈序列是(2,4,3,6,5,1),则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ..的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 1

D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 B.1 C.2 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 11.对序列(15,9,7,8,20,-1,4)进行排序,若一趟排序后的结果为(-1,15,9,7,8,20,4),则采用的排序方法是 A.归并排序 B.快速排序 C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误 ..的是 2

2014《数据结构》试卷( C 卷)

《数据结构》试卷(C卷) 一、单项选择题 1. 空串与空格字符组成的串的区别在于(B )。 A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指( D )。 A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中,只有( C )是正确的。 A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中,则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是( D )。 A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等,并且两串包含的字符相同 D.两串的长度相等,并且对应位置上的字符相同 5. 若SUBSTR(S,i,k)表示求S中从第i个字符开始的连续k个字符组成的子串的操作,则对于S=“Beijing&Nanjing”,SUBSTR(S,4,5)=( B )。 A. “ijing” B. “jing&” C. “ingNa” D. “ing&N” 6. 若INDEX(S,T)表示求T在S中的位置的操作,则对于S=“Beijing&Nanjing”,T=“jing”,INDEX(S,T)=( C )。 A.2 B.3 C.4 D.5 7. 若REPLACE(S,S1,S2)表示用字符串S2替换字符串S中的子串S1的操作,则对于

S=“Beijing&Nanjing”,S1=“Beijing”,S2=“Shanghai”,REPLACE(S,S1,S2)=( D )。 A. “Nanjing&Shanghai” B. “Nanjing&Nanjing” C. “ShanghaiNanjing” D. “Shanghai&Nanjing” 8. 在长度为n的字符串S的第i个位置插入另外一个字符串,i的合法值应该是( C )。 A.i>0 B. i≤n C.1≤i≤n D.1≤i≤n+1 9. 字符串采用结点大小为1的链表作为其存储结构,是指(D )。 A.链表的长度为1 B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 10. 在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为(C )个。 A. 4 B. 5 C. 6 D. 7 11. 假设在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为( B )个。 A. 15 B. 16 C. 17 D. 47 12. 假定一棵三叉树的结点数为50,则它的最小高度为( C )。 A. 3 B. 4 C. 5 D. 6 13. 在一棵二叉树上第4层的结点数最多为( D )。 A. 2 B. 4 C. 6 D. 8 14. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n],结点R[i]若有左孩子,其左孩子的编号为结点(B )。 A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 15. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为( D )。 A. 24 B. 48 C. 72 D. 53 16. 线索二叉树是一种( C )结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 17. 线索二叉树中,结点p没有左子树的充要条件是( B )。

严蔚敏数据结构题集(C语言版)完整

严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果:销毁复数C Get(C,k,&e) 操作结果:用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果:改变复数C 的第k 元的值为e

武汉理工大学数据结构2014复习题

复习题集 一判断题 ()1. 在决定选取何种存储结构时,一般不考虑各结点的值如何。 ()2. 抽象数据类型与计算机内部表示和实现无关。 ()3. 线性表采用链式存储结构时,结点和结点内部的存储空间可以是不连续的。 ()4. 链表的每个结点中都恰好包含一个指针。 ()5.链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。()6. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 ()7. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 ()8. 线性表在物理存储空间中也一定是连续的。 ()9. 顺序存储方式只能用于存储线性结构。 ()10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ()11.对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 ()12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ()13.两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。 ()14.二叉树的度为2。 ()15.若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。 ()16.二叉树中每个结点的两棵子树的高度差等于1。 ()17.用二叉链表法存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。 ()18.具有12个结点的完全二叉树有5个度为2的结点。 ()19.二叉树的前序遍历序列中,任意一个结点均处在其孩子结点的前面。 ()20.在冒泡法排序中,关键值较小的元素总是向前移动,关键值较大的元素总是向后移动。 ()21.计算机处理的对象可以分为数据和非数据两大类。 ()22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 ()23.算法必须用程序语言来书写。 ()24.判断某个算法是否容易阅读是算法分析的任务之一。 ()25.顺序表是一种有序的线性表。 ()26.分配给顺序表的内存单元地址必须是连续的。 ()27.栈和队列具有相同的逻辑特性。 ()28.树形结构中每个结点至多有一个前驱。 ()29.在树形结构中,处于同一层上的各结点之间都存在兄弟关系。 ()30.如果表示图的邻接矩阵是对称矩阵,则该图一定是无向图。 ()31.如果表示图的邻接矩阵是对称矩阵,则该图一定是有向图。 ()32.顺序查找方法只能在顺序存储结构上进行。

02142数据结构导论201410试题及答案

2014年10月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码02142) 本试卷共5页,满分l00分,考试时间l50分钟。 考生答题注意事项: 1.本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作草稿纸。2.第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡"的相应代码涂黑。3.第二部分为非选择题。必须注明大、小题号,使用0.5毫米黑色字迹签字笔作答。4.合理安排答题空间,超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。 1.下列算法的时间复杂度为B 2.根据数据元素之间关系的不同特性,通常将数据结构分为四类基本结构,即 A.集合、顺序结构、树形结构、图结构 B.集合、线性结构、链式结构、图结构 C.集合、线性结构、树形结构、图结构 D.线性结构、顺序结构、链式结构、图结构 3.在表长为101的顺序表中做删除运算,平均移动元素的次数为 A.25 B.50 C.5l D.100 4.在表长为n的顺序表中做插入运算的时间复杂度为A 5.单链表与顺序表相比,其特点是 A.运算算法实现简单 B.便于随机存取数据 C.不需要预先分配存储空间 D.结点个数受到限制 6.关于链栈的说法,正确的是 A.链栈不用预先考虑容量的大小 B.链栈出栈时不需要判断栈空 C.链栈进栈时需要判断栈满 D.链栈出栈时需要判断栈满 7.循环队列存储在数组A[m]中,则入队列操作中队列尾指针rear的变化为 A.rear=rear+1 B.rear=(rear+1)%(m一1)

数据结构复习题-第1章答案2014-5-16

第1章绪论 一、选择题(每小题2分,共20分) 1.以下哪一个不是算法的特性()。 A.有穷性 B.确定性 C.简洁性 D.可行性 2.数据结构的定义为(D,S),其中D是( )的集合。 A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 3.设n是描述问题规模的非负整数,下面程序片段的时间复杂度是()。 x=2; while(x

2014第一学期数据结构复习题

7数据结构复习题 一、填空题 (1)若已知一个栈的输入序列为1 ,2, 3 ,...n ,其输出序列为p1,p2,p3,....pn。若p1=n,则pi 为n-i+1。 (2) 在单循环链表中,指针p 所指结点为最后一个结点的条件是p->link==first。 (3)具有32有结点的完全二叉树的深度为 6 。 (4) L是带有头结点的单链表的头指针,第一个元素结点的指针是 first 。 (5)从逻辑关系上讲,数据结构主要分为两大类,它们是线性结构和非线性结构。 (6)有序表中元素为1,2,3,4,5,6,7,8,9.11采用二分查找方法进行查找,共有 2 个元素的查找长度为2。 (7)从无向图中的某个顶点出发,进行一次广度优先搜索,即可访问图的每个顶点,则该图一定是连通图。 (8)归并排序的时间复杂性为O(nlog2n)。 (9) 在一个长度为n的顺序表中删除第m个元素时,需向前移动n-m个元素。 (10) 多维数组实际上是由__一维数组的扩展实现的。 (11) 链接存储的特点是利用__指针___来表示数据元素之间的逻辑关系。 (12) 后缀表达式“4 5 * 3 2 + -”的值为__ 15______。 (14) 一个算法的复杂性可分为_ 时间 ___复杂性和空间复杂性。 (16) 在一棵树中,叶结点没有后继结点。 (17) (18) 在单链表中,指针p 所指结点为最后一个结点的条件是p->next=NULL。 (19) 栈是一种限定在表的一端进行插入和删除的线性表,又被称为后进先出的线性表。 (20) 设图G=(V,E),V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>,<2,3>},从顶点1出发,对图G进行广度优先搜索的序列有___2 __种。 (21)已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有_____ 12_______ 个叶子的结点。n0=n2+2n3+1 (22) 设指针变量p指向单链表中结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X需要执行的语句序列:s->next=p->next; _____p->next = s___________;。 (23) 在无向图的邻接矩阵A中,若A[i,j]等于1,则A[j,i]等于__ 1 ______。 (24) (25) 设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为____s->left_____=p;s->right=p->right;__p->right______=s;

广东工业大学期末考试试题及答案

广东工业大学考试试卷 ( A ) 课程名称:机械设计基础 考试时间:第21周星期二(05年1月18日) 班 级: 学 号: 姓 名: 一、填空题(共20分每空1分) 1. 某轴的截面受非对称循环变应力作用,已知其最大应力σmax =200 MP a ,最小应力σmin =100 MP a ,则其平均应力σm = 150 MP a ,应力幅σa = 50 MP a ,应力循环特性r= 0.5 。 2. 紧联接螺栓按拉伸强度计算时, 考虑到拉伸和扭转的复合作用, 应将拉伸载荷增大至原来___1.3___倍。 3. 普通平键的截面尺寸b ?h 是按 轴径 从标准中查取。 4. V 带传动由于有 弹性滑动 的影响,所以不可能有恒定的传动比。 5. 带传动、链传动、齿轮传动、蜗杆传动中,传动平稳性最好的 是 蜗杆传动 ,?附加动载荷最大的是 链传动 。 6. 带传动工作时,带中的最大应力发生在 紧边进入小轮 处。 7. 链节数一般应取 偶 数,链轮齿数应取 奇 数。 8. 一对直齿圆柱齿轮传动,其轮齿弯曲疲劳强度,主要取决 于 模数 。 9. 在齿轮弯曲强度计算中,对于标准直齿圆柱齿轮,齿形系数(Y F )仅决定 于 齿数 。 10.高速重载齿轮传动中,当散热条件不良时, 齿轮的主要失效形式 _________________________姓 名______________________学 号______________________班 级

是胶合。 11.在蜗杆传动中,失效主要发生在蜗杆和蜗轮中的蜗轮上。 12.蜗杆传动除了作强度计算外,还须作热平衡计算 13.非液体润滑的滑动轴承,其直径增加一倍、宽径比B/d不变,载荷不变,则轴承的平均压强变为原来的1/4 倍。 14.对于某一个轴承来说,正常的实际使用中,未达到额定寿命而提前发生疲劳点蚀的概率是 10% 。 15.按轴所受的载荷性质的不同,汽车变速箱至后桥的连接轴是传动轴;车床主轴是转轴。 二、简答题(共20分每题4分) 1. 螺栓联接(包括普通螺栓联接和铰制孔用螺栓联接)、双头螺柱联接和螺钉联接各自适用什么场合? 答: 普通螺栓联接:被联接件较薄,以承受轴向载荷为主; 铰制孔用螺栓联接:被联接件较薄,以承受横向载荷为主; 螺钉联接:一被联接件较厚,不需经常拆卸; 双头螺柱联接:一被联接件较厚,可经常拆卸; 2 有一由V带传动、链传动和齿轮传动组成的减速传动装置,试合理确定其传动布置顺序,并简要说明其原因。 答: 布置顺序:V带传动——齿轮传动——链传动。 V带传动在最高速级,过载时保护电机;齿轮传动在中间级过渡;链传动在最低速级,惯性力较小。 3 简述开式齿轮传动的设计准则。 答: 按轮齿弯曲疲劳强度设计,将模数放大20-30%考虑磨损对齿厚的影响。

相关主题
相关文档 最新文档