华师《数据结构》在线作业15春满分答案

第1 章绪论1.简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，… }，字母字符数据对象是集合C={‘A’，‘B’，… ，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2.试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。

东师《数据结构》15春在线作业1一、单选题（共20 道试题，共60 分。

）V 1. 由3个结点可以构造出多少种不同的二叉树？( )A. 15B. 21C. 30D. 33满分：3 分2. 有n个顶点的无向图的边数最少为()。

A. 0B. 1C. n-1D. n满分：3 分3. 判断线索二叉树中某结点p有右子女的条件是( )。

A. p->rtag = = 0B. p->rtag = = 1C. p ! = NULLD. p->lchild ! = NULL满分：3 分4. 下列哪一种图的邻接矩阵是对称矩阵？()A. 有向图B. 无向图C. AOV 网D. AOE 网满分：3 分5. head指向的不带表头结点的单链表为空的判定条件是( )。

A. head = = NULLB. head->next = = headC. head ! = NULLD. head->next = = NULL满分：3 分6. 线索二叉树是一种( ) 结构。

A. 逻辑B. 物理C. 逻辑和存储D. 线性满分：3 分7. 排序趟数与序列的原始状态有关的排序方法是() 排序法。

A. 直接插入B. 直接选择C. 冒泡D. 归并满分：3 分8. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。

A. nB. (n-1)/2C. n/2D. (n+1)/2满分：3 分9. 顺序查找法适合于存储结构为下列哪一种方式的线性表()。

A. 散列存储B. 顺序存储或链接存储C. 压缩存储D. 索引存储满分：3 分10. 采用邻接表存储的图的深度优先遍历类似于二叉树的()。

A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历满分：3 分11. 已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为( )。

A. LOC(a0)+(i-1)*cB. LOC(a0)+i*cC. LOC(a0)-i*cD. LOC(a0)+(i+1)*c满分：3 分12. 在k叉树中，结点度数的最大值为( )。

第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={<r,i>} 基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（ㄨ）（3）数据元素是数据的最小单位。

（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。

（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（7）数据的存储结构是数据的逻辑结构的存储映像。

|（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。

（ㄨ）（9）数据的逻辑结构是依赖于计算机的。

（√）（10）算法是对解题方法和步骤的描述。

二．填空题（1）数据有逻辑结构和存储结构两种结构。

（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。

（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

（4）树形结构和图形结构合称为非线性结构。

（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。

（6）>（7）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。

（8）数据的存储结构又叫物理结构。

（9）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。

（10）线性结构中的元素之间存在一对一的关系。

（11）树形结构结构中的元素之间存在一对多的关系，（12）图形结构的元素之间存在多对多的关系。

（13）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。

（14）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。

（15）算法是一个有穷指令的集合。

（16）算法效率的度量可以分为事先估算法和事后统计法。

（17）！（18）一个算法的时间复杂性是算法输入规模的函数。

（19）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。

1．第1 题下列编码中属前缀码的是( ) 。

A. {1, 01, 000, 001} B. {1, 01, 011, 010} C. {0, 10, 110, 11} D. {0, 1, 00, 11} 您的答案：A 题目分数：2 此题得分：2. 0 2．第2 题下列各式中，按增长率由小至大的顺序正确排列的是( ) 。

A．n1/2，n!，2n ，n3/2 B．n3/2，2n，nlogn，2100 C．2n，logn，nlogn，n3/2 D．2100，logn, 2n, nn A. A B. B C. C D. D 您的答案：D 题目分数：2 此题得分：2. 0 3．第3 题设p 指向单链表中的一个结点，s 指向待插入的结点，则下述程序段的功能是( ) 。

s->next=p->next; p->next=s; t=p->data; p->data=s->data; s->data=t; A. 结点*p 与结点*s 的数据域互换B. 在p 所指结点的元素之前插入元素 C. 在p 所指结点的元素之后插入元素 D. 在结点*p 之前插入结点*s 您的答案：D 题目分数：2 此题得分：2. 0 4．第4 题设S=”abc”; T=”xyz”，则strcmp(S, T) 的值为( ) 。

A. 正数B. 负数C. 零D. 不确定您的答案：B 题目分数：2 此题得分：2.0 5．第5 题以下广义表关系正确的是( ) 。

A. 线性表<再入表<纯表<递归表B. 线性表<纯表<递归表<再入表 C. 纯表<线性表<再入表<递归表 D. 线性表<纯表<再入表<递归表您的答案：D 题目分数：2 此题得分：2. 0 6．第6 题假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要进行( ) 次探侧。

华师《数据结构》在线作业一、单选题（共30 道试题，共60 分。

）1. 判定一个循环队列QU(最多元素为m0)为满队列的条件是()A. QU->front==QU->rearB. QU->front!=QU->rearC. QU->front==(QU->rear+1)％m0D. QU->front!=(QU->rear+1)％m0正确答案：C2. 对于一组结点，从空树开始，把它们插入到二叉排序树中，就建立了一棵二叉排序树。

这时，整个二叉排序树的形状取决于()。

A. 结点的输入顺序B. 结点的存储结构C. 结点的取值范围D. 计算机的硬件正确答案：A3. 线性表采用链式存储时，其地址()A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续与否均可以。

正确答案：D4. 广义表A=(()，(a)，(b，(c，d)))的深度为( )A. 2B. 3C. 4D. 5正确答案：B5. 设单循环链表中结点的结构为(date，link)且rear是指向非空的带表头结点的单循环链表的尾结点指针。

若想删除链表的第一个结点,则应执行下列哪一个操作?( )A. s=rear;rear=rear->link;delete sB. rear=rear->link;delete rearC. rear=rear->link->link;delete rearD. s=rear->link->link;rear->link->link=s->link;delete s;正确答案：B6. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间复杂度是（）。

东师《数据结构》15春在线作业2一、单选题（共20 道试题，共60 分。

）V 1. n个结点的线索二叉树上含有的线索数为( )。

A. n-1B. nC. n +1D. 2n满分：3 分2. 有n个顶点的无向图的边数最多为()。

A. nB. n(n-1)C. n(n-1)/2D. 2n满分：3 分3. 下列排序方法中，哪一个是稳定的排序方法？()A. 直接选择排序B. 直接插入排序C. 希尔排序D. 快速排序满分：3 分4. 设有n个结点的二叉排序树，对于成功的查找，最少的比较次数为()。

A. Ο( 1 )B. Ο(log2n)C. Ο(n)D. Ο(nlog2n)满分：3 分5. 设二维数组A[0..m-1][0..n-1]按列优先顺序存储且每个元素占c 个单元，则元素A[i][j]的地址为()。

A. LOC(A[0][0]) + (j*m+i)*cB. LOC(A[0][0]) + (i*n+j)*cC. LOC(A[0][0]) + [(j-1)*m+i-1]*cD. LOC(A[0][0]) + [(i-1)*n+j-1]*c满分：3 分6. 在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是() 。

A. G中有弧＜Vi , Vj >B. G中有一条从Vi到Vj 的路径C. G中没有弧＜Vi , Vj >D. G中有一条从Vj到Vi 的路径满分：3 分7. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。

A. 逆拓扑有序B. 拓扑有序C. 无序的D. 部分有序的满分：3 分8. 采用邻接表存储的图的广度优先遍历类似于二叉树的()。

A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历满分：3 分9. 倒排文件中倒排表是指()。

A. 主关键字索引B. 次关键字索引C. 物理顺序与逻辑顺序不一致D. 多关键字索引满分：3 分10. 若设根结点的层数为0，则具有37个结点的完全二叉树的深度(或高度)为( )。

东师《数据结构（高起专）》15秋在线作业2一、单选题（共20 道试题，共60 分。

）V 1. “堆积”问题是由于()引起的。

A. 同义词之间发生冲突B. 散列函数C. 不同的同义词子表结合在一起D. 散列表“溢出”满分：3 分2. 用折半查找法查找表的元素的速度比顺序查找法()。

A. 必定快B. 必定慢C. 相等D. 不能确定满分：3 分3. 下面哪些方法可以判断出一个有向图是否有环（回路）? ()A. 广(宽)度优先遍历B. 拓扑排序C. 求最短路径D. 求关键路径满分：3 分4. ISAM文件和VSAM文件属于()。

A. 索引非顺序文件B. 索引顺序文件C. 顺序文件D. 散列文件满分：3 分5. 有n个顶点的无向连通图的边数最少为()。

A. n/2B. n-1C. nD. n+1满分：3 分6. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值()。

A. 同等概率B. 最大概率C. 最小概率D. 平均概率满分：3 分7. 采用邻接表存储的图的广度优先遍历类似于二叉树的()。

A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历满分：3 分8. 广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是()。

A. ( c , d )B. c , dC. ( ( c , d ) )D. d满分：3 分9. 有n个顶点的有向图的边数最多为()。

A. nB. n(n-1)C. n(n-1)/2D. 2n满分：3 分10. 快速排序算法在下述哪种情况下效率最高()。

A. 被排序的数据已完全有序B. 被排序的数据中含有多个相同的排序码C. 被排序的数据已基本有序D. 被排序的数据完全无序满分：3 分11. 求顶点间的最短路径问题，考虑的是下面的哪一种图()。

A. 无向图B. 有向图C. 带权的无向图D. 带权的有向图满分：3 分12. 用ISAM组织文件适合于()。

一、选择题1、下面关于线性表的叙述错误的是（ C ）。

A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现2、栈是一种特殊的线性表，具有（ B ）性质A．先进先出 B.先进后出 C.后进后出 D.顺序进出3、顺序循环队列中（数组大小为n），队头指示front指向队列的第一个元素，队尾指示rear指向队列最后一个元素的后一个位置，则循环队列中存放了n-1个元素，即循环队列满的条件是（B）。

A．(rear+1)%n=front-1 B.(rear+1)%n=frontC. (rear)%n=frontD.rear+1=front4、在一个单链表中，若删除p所指结点的后续结点，则执行（A）。

A． p->next=p->next->nextB. p=p->next;p->next->nextC.p->next=p->nextD.p=p->next->next5、设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ A ）。

A. N0=N2+1B.N0=Nl+N2C. N0=N1+1D.N0=2N1+l6、设有6个结点的无向图，该图至少应有（ D ）条边才能确保是一个连通图。

A.8B.6C.7D.57、设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（A）。

A.1，2，3，4B. 2，3，4，1C.1，4，2，3D. 1，2，4，38、已知一个有向图如下所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为（A）。

A.a d b e f cB. a d c e f bC.a d c e b fD.a d e f b c9、适用于折半查找的表的存储方式及元素排列要求是（ D ）A.链式方式存储，元素无序B.链式存储方式，元素有序C.顺序存储方式，元素无序D.顺序存储方式，元素有序10、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ C ）趟的分配和回收才能使得初始关键字序列变成有序序列。