数据结构(本)形考作业答案

题目：如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

选项A：一棵树选项B：有回路选项C：连通图选项D：完全图答案：连通图题目：下列有关图遍历的说法不正确的是（）。

选项A：非连通图不能用深度优先搜索法选项B：图的遍历要求每一顶点仅被访问一次选项C：连通图的深度优先搜索是一个递归过程选项D：图的广度优先搜索中邻接点的寻找具有“先进先出”的特征答案：非连通图不能用深度优先搜索法题目：无向图的邻接矩阵是一个（）。

选项A：对称矩阵选项B：对角矩阵选项C：上三角矩阵选项D：零矩阵答案：对称矩阵题目：图的深度优先遍历算法类似于二叉树的（）遍历。

选项A：后序选项B：先序选项C：层次选项D：中序答案：先序题目：已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

/pluginfile.php/67710/question/questiontext/2988635/7/108770/01 .png选项A：V1V2V4V8V3V5V6V7选项B：V1V2V4V8V5V3V6V7选项C：V1V2V4V5V8V3V6V7选项D：V1V3V6V7V2V4V5V8答案：V1V2V4V8V5V3V6V7题目：在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选项A：1选项B：1/2选项C：4选项D：2答案：2题目：邻接表是图的一种（）。

选项A：顺序存储结构选项B：索引存储结构选项C：散列存储结构选项D：链式存储结构答案：链式存储结构题目：已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

/pluginfile.php/67710/question/questiontext/2988635/8/108771/02 .png选项A：aebcfd选项B：abcefd选项C：acfdeb选项D：abcedf答案：abcefd题目：已知如图3所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。

题目：一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始化堆为（）。

选项A：39，80，46，47，41，57选项B：41，39，46，47，57，80选项C：39，47，46，80，41，57选项D：39，41，46，80，47，57答案：39，41，46，80，47，57题目：一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。

选项A：31，29，37，47，77，85选项B：31，29，37，85，47，70选项C：31，29，37，70，47，85选项D：29，31，37，47，70，85答案：31，29，37，47，77，85题目：下述几种排序方法中，要求内存量最大的是（）。

选项A：归并排序选项B：插入排序选项C：快速排序选项D：选择排序答案：归并排序题目：若待排序序列在排序前已按关键字递增排列，则采用（）方法比较次数最多。

选项A：归并排序选项B：归并排序选项C：直接选择排序选项D：直接插入排序答案：直接插入排序题目：将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。

选项A：n-1选项B：2n-1选项C：n选项D：2n答案：n题目：就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（）。

选项A：堆排序快速排序归并排序选项B：堆排序归并排序快速排序选项C：堆排序归并排序快速排序选项D：堆排序快速排序归并排序答案：堆排序快速排序归并排序题目：设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。

选项A：堆排序选项B：冒泡排序选项C：基数排序选项D：快速排序答案：堆排序题目：对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。

标准答案1：以顺序存储方式，且数据元素有序
标准答案2：(n+1)/2
标准答案3：29/10
标准答案4：5
标准答案5：37,24,12,30,53,45,96
标准答案6：4
标准答案7：直接选择排序
标准答案8：插入排序
标准答案9：归并排序
标准答案10：交换排序
标准答案11：快速排序
标准答案12：40，20,30,38，46，56，79，84,90,110
标准答案13：3
标准答案14：5
标准答案15：选择
标准答案16：18，20，25，59，26，36
标准答案17：16，25，35，48，23，40，79，82，36，72 标准答案18：28，16，34，54，62，73，60，26，43，95 标准答案19：40，38，46，56，79，84
标准答案20：39，46，41，57，80，47
标准答案21：{NULL} {k} {p=p->left} {p=p->right} {p}
标准答案22：{n} {(s+j)/2} {j=m-1} {s=m+1} {a[k+1]}
标准答案23：子问题1：C; 子问题2：B
标准答案24：子问题1：B; 子问题2：A
标准答案25：子问题1：C; 子问题2：D
标准答案26：子问题1：D; 子问题2：A
标准答案27：子问题1：C; 子问题2：D。

题目：数据结构中，与所使用的计算机无关的是数据的（）。

选项A：物理和存储结构选项B：存储结构选项C：物理结构选项D：逻辑结构答案：逻辑结构题目：组成数据的基本单位是（）。

选项A：数据项选项B：数据类型选项C：数据变量选项D：数据元素答案：数据元素题目：一个顺序栈一旦被声明，其占用空间的大小（）。

选项A：已固定选项B：不能固定选项C：可以改变选项D：动态变化答案：已固定题目：链栈和顺序栈相比，有一个比较明显的缺点，即（）。

选项A：插入操作更加方便选项B：通常不会出现栈满的情况选项C：删除操作更加方便选项D：不会出现栈空的情况答案：通常不会出现栈满的情况题目：用单链表表示的链式队列的队头在链表的（）位置。

选项A：链头选项B：链尾选项C：链中选项D：任意位置答案：链头题目：在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。

选项A：堆栈选项B：数组选项C：线性表选项D：队列答案：队列题目：循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。

选项A：（rear+1)%m=front选项B：（rear =front+1选项C：（rear=front选项D：（rear+1)%m-1=front答案：（rear+1)%m=front题目：在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。

选项A：p-next=top-next; top=top-next;选项B：p-next=top; top=p;选项C：top-next=p;选项D：p-next=top-next; top-next=p;答案：p-next=top; top=p;题目：在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。

选项A：x=top;top=top-next;选项B：x=top-data;选项C：top=top-next; x=top-data;选项D：x=top-data; top=top-next;答案：x=top-data; top=top-next;题目：在一个链队中，设front和rear分别为队首和队尾指针，则插入p所指结点时，应执行（）。

国开02272《数据结构》形成性考核(1-4)试题及解答1. 选择题问题 1.1:在数据结构中，以下哪种结构是最基本的数据结构？- A. 栈- B. 队列- C. 树- D. 图解答 1.1:正确答案是 A. 栈。

栈是一种后进先出（LIFO）的数据结构，它是通过在一端进行插入和删除操作来实现的。

问题 1.2:在二叉树中，一个节点的最大孩子数目是？- A. 1- B. 2- C. 3- D. 无穷大解答 1.2:正确答案是 B. 2。

在二叉树中，每个节点最多有两个子节点，即左子节点和右子节点。

2. 填空题问题 2.1:在线性表中，如果一个元素在表中的位置是 i，那么它之前有 i - 1 个元素。

_____解答 2.1:正确答案是 "正确"。

在线性表中，如果一个元素在表中的位置是 i，那么它之前有 i - 1 个元素，因为它是从位置 1 开始计数的。

问题2.2:在_____结构中，删除操作的平均时间复杂度是O(n)。

_____解答 2.2:正确答案是 "链表" 和 "O(n)"。

在链表结构中，删除操作的平均时间复杂度是 O(n)，因为需要找到要删除的元素的前一个元素来进行删除操作。

3. 简答题问题 3.1:请解释什么是深度优先搜索（DFS）算法，并给出一个应用场景。

解答 3.1:深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。

它从根节点开始，沿着树的深度遍历树的节点，尽可能深地搜索树的分支。

当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

它适用于解决迷宫问题、求解最大子矩阵问题等。

问题 3.2:请解释什么是堆，并给出两种类型的堆。

解答 3.2:堆是一种特殊的完全二叉树，用于实现优先队列。

堆分为两种类型：最大堆和最小堆。

- 最大堆：在一个最大堆中，每个节点的值都大于或等于其子节点的值。

最大堆的根节点具有最大值。

题目：一维数组A采用顺序存储结构，每个元素占用4个字节，第8个元素的存储地址为120，则该数组的首地址是（）。

选项A：88选项B：92选项C：32选项D：90答案：92题目：稀疏矩阵采用压缩存储的目的主要是（）。

选项A：减少不必要的存储空间的开销选项B：表达变得简单选项C：去掉矩阵中的多余元素选项D：对矩阵元素的存取变得简单答案：减少不必要的存储空间的开销题目：一个非空广义表的表头（）。

选项A：不可能是原子选项B：只能是原子选项C：可以是子表或原子选项D：只能是子表答案：可以是子表或原子题目：常对数组进行的两种基本操作是（）。

选项A：建立与删除选项B：查找与索引选项C：查找和修改选项D：索引与、和修改答案：查找和修改题目：在二维数组A[8][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（）。

选项A：80选项B：270选项C：100选项D：240答案：240题目：设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A10,8在一维数组B中的下标是（）。

选项A：58选项B：18选项C：45选项D：53答案：53题目：广义表((a))的表尾是（）。

选项A：(a)选项B：0选项C：((a))选项D：a答案：0题目：设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（）。

选项A：41选项B：85选项C：32选项D：33答案：33题目：设广义表类（(a,b,c)），则L的长度和深度分别为（）。

选项A：1和3选项B：1和1选项C：2和3选项D：1和2答案：1和2题目：广义表( a , a ,b , d , e ,( (i ,j ) ,k ) )的表头是________。

国开电大数据结构(本)形考作业3参考答案题目 1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。

A. 16B. 17C. 47D. 15【答案】：16题目2.二叉树第k层上最多有（）个结点。

A. 2k-1B. 2k-1C. 2k-1D. 2k【答案】：2k-1题目 3.将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。

A. 35B. 34C. 36D. 33【答案】：34题目4.如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

A.完整二叉树B.二叉树C.哈夫曼树D.均衡二叉树【答案】：哈夫曼树题目 5.在一棵度具有5层的满二叉树中结点总数为（）。

A. 32B. 33C. 31D. 16【答案】：31问题6.一棵完整二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。

A. 31B. 37C. 38D. 72【答案】：37题目7.利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。

A. 16B. 30C. 12D. 18【答案】：18问题8.在一棵树中，（）没有先驱结点。

A.分支结点B.树根结点C.XXXD.空结点【答案】：树根结点问题9.设一棵接纳链式储备的二叉树，除叶结点外每一个结点度数都为2，该树结点中共有20个指针域为空,则该树有（）个叶结点。

A. 22B. 21C. 9D. 10【答案】：10题目10.在一个图G中，所有顶点的度数之和等于所有边数之和的（B. 2C. 1D. 4【答案】：2问题11.毗邻表是图的一种（）。

A.索引存储结构B.按次储备布局C.散列存储结构D.链式存储结构【答案】：链式储备布局题目12.图的深度优先遍历算法类似于二叉树的（）遍历。

A.条理B.后序C.中序）倍。

《数据结构》形成性考核册第1次作业参考答案第一章绪论一、填空题1、数据操作2、集合结构线性结构树型结构图形结构3、引用类型4、1：1 1：n n：m5、不对6、多个7、O（m*n）8、时间复杂度空间复杂度9、顺序链接索引散列10、O（n2）11、O（n）12、O（n）O（m*n）二、选择题1~8：DBABADDD三、应用题（1）功能：判断n是否是一个素数，若是则返回数值1，否则返回0。

时间复杂度：O（n）。

（2）功能：计算S=1！+2！+…+n!的值。

时间复杂度：O（n）。

（3）功能：计算S=1！+2！+…+n!的值。

时间复杂度：O（n2）。

（4）求出满足不等式1+2+…+i≥n的最小i值。

O（n）。

第二章线性表四、填空题1、A[P-1]2、1083、前驱后继4、最后一个表头5、p->next=q->nextq->next=p6、HL->next=NULLHL->next=HL7、P->next8、Q->next9、P->next s10、从前向后前移n-i11、O（1）O（n）12、（n+1）/213、O（n）O（1）14、A[P].next15、a[j].next=a[i].nexta[i].next=j16、数据值指针五、选择题1~5：BDDBC六、应用题1、（1）、（79，62，34，57，26，48）（2）、（26，34，48，57，62，79）（3）、（48，56，57，62，79，34）（4）、（56，57，79，34）（5）、（26，34，39，48，57，62）2、（1）将类型为List的线性表L中第i个元素移至表尾位置的算法，L中的元素类型为ElemType，假定不需要对i的值进行有效性检查。

void move (List& L, int i){ElemType x=L.list[ i-1];for(int j=i; j<L.size; j++)L.list[ j-1]=L.list[ j ];L.list[L.size-1]=x;}·将线性表L中的第i个元素移入表头的算法与上类似。

题目：以下陈述中正确的是（）。

选项A：串中元素只能是字母选项B：串是一种特殊的线性表选项C：空串就是空格串选项D：串的长度必须大于零答案：串是一种特殊的线性表题目：设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（）。

选项A：求串长选项B：连接选项C：匹配选项D：求子串答案：匹配题目：串是（）。

选项A：不少于一个字母的序列选项B：不少于一个字符的序列选项C：有限个字符的序列选项D：任意个字母的序列答案：有限个字符的序列题目：串的长度是指（）。

选项A：串中所含非空格字符的个数选项B：串中所含字符的个数选项C：串中所含不同字母的个数选项D：串中所含不同字符的个数答案：串中所含字符的个数题目：在C语言中，存储字符串“ABCD”需占用（）字节。

选项A：2选项B：3选项C：4选项D：5答案：5题目：下面关于串的叙述中，不正确的是（）。

选项A：模式匹配是串的一种重要运算选项B：空串是由空格构成的串选项C：串即可以采用顺序存储，也可以采用链式存储选项D：串是字符的有限序列答案：空串是由空格构成的串题目：串与普通的线性表相比较，它的特殊性体现在（）。

选项A：数据元素可以任意选项B：顺序的存储结构选项C：数据元素是一个字符选项D：链接的存储结构答案：数据元素是一个字符题目：空串与空格串（）。

选项A：相同选项B：不相同选项C：无法确定选项D：可能相同答案：不相同题目：两个字符串相等的条件是（）。

选项A：两串包含的字符相同选项B：两串的长度相等，并且对应位置上的字符相同选项C：两串的长度相等选项D：两串的长度相等，并且两串包含的字符相同答案：两串的长度相等，并且对应位置上的字符相同题目：在实际应用中，要输入多个字符串，且长度无法预定。

则应该采用（）存储比较合适（）。

选项A：无法确定选项B：顺序选项C：链式选项D：堆结构答案：链式题目：下列关于串的叙述中，不正确的是（）。

选项A：串既可以采用顺序存储，也可以采用链式存储选项B：模式匹配是串的一种重要运算选项C：空串是由空格构成的串选项D：串是字符的有限序列答案：空串是由空格构成的串题目：串是一种特殊的线性表，其特殊性体现在（）。

国开电大数据结构(本)形考作业4参考答案1.对于二分查找，要求线性表必须以顺序存储方式，并且数据元素有序。

2.在采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为(n+1)/2.3.对于一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为29/10.4.已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较5次。

5.对于数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是37,24,12,30,53,45,96.6.对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，则查找元素26的比较次数是4次。

7.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是直接选择排序。

8.插入排序是一种将未排序序列中的元素依次取出与已经排好序的序列中的元素作比较，将其放入已排序序列的正确位置上的排序方法。

9.归并排序是一种依次将每两个相邻的有序表合并成一个有序表的排序方法。

10.交换排序是一种当两个元素出现逆序的时候就交换位置的排序方法。

if(kkey)p=p->left;elseif(k>p->key)p=p->right;elsereturn (p);return (NULL);答案】：(NULL)，(p->key)题目26.1) 对关键字序列(36,69,46,28,30,74)采用快速排序，以第一个关键字为分割元素，经过一次划分后的结果序列为正确答案：C。

28，30，46，36，69，74改写后：对关键字序列(36,69,46,28,30,74)进行快速排序，以第一个关键字36为分割元素，经过一次划分后的结果序列为28，30，46，36，69，74.2) 用冒泡法对上述序列排序，经两趟冒泡的结果序列为正确答案：A。

国家开放大学《数据结构（本）》形考作业1-4参考答案形考作业1一、单项选择题（每小题3分，共60分）1.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

A. 算法的具体实现B. 物理结构C. 逻辑结构D. 给相关变量分配存储单元2.下列说法中，不正确的是（）。

A. 数据项是数据中不可分割的最小可标识单位B. 数据元素是数据的基本单位C. 数据项可由若干个数据元素构成D. 数据可有若干个数据元素构成3.一个存储结点存储一个（）。

A. 数据结构B. 数据元素C. 数据类型D. 数据项4.数据结构中，与所使用的计算机无关的是数据的（）。

A. 物理和存储结构B. 物理结构C. 逻辑结构D. 存储结构5.在线性表的顺序结构中，以下说法正确的是（）。

A. 逻辑上相邻的元素在物理位置上不一定相邻B. 逻辑上相邻的元素在物理位置上也相邻C. 进行数据元素的插入、删除效率较高D. 数据元素是不能随机访问的6.对链表, 以下叙述中正确的是（）。

A. 结点占用的存储空间是连续的B. 插入删除元素的操作一定要要移动结点C. 可以通过下标对链表进行直接访问D. 不能随机访问任一结点7.下列的叙述中，不属于算法特性的是（）。

A. 可读性B. 输入性C. 可行性D. 有穷性8.算法的时间复杂度与（）有关。

A. 算法本身B. 计算机的操作系统C. 数据结构D. 所使用的计算机9.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。

A. n-i+1B. n-i-1C. n-iD. i10.设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

A. iB. n-iC. n-i-1D. n-i+111.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

A. p->next=q->nextB. p=q->nextC. p->next=qD. q->next=NULL12.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。

准答案1：物理结构
标准答案2：数据项可由若干个数据元素构成
标准答案3：数据元素
标准答案4：逻辑结构
标准答案5：逻辑上相邻的元素在物理位置上也相邻
标准答案6：不能随机访问任一结点
标准答案7：可读性
标准答案8：算法本身
标准答案9：n-i+1
标准答案10：n-i
标准答案11：p->next=q->next
标准答案12：s->next=p->next; p->next=s;
标准答案13：p->next==head
标准答案14：可随机访问任一元素
标准答案15：head->next==NULL
标准答案16：20
标准答案17：除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继
标准答案18：63.5
标准答案19：100
标准答案20：q->next=p
标准答案21：对
标准答案22：错
标准答案23：错
标准答案24：错
标准答案25：错
标准答案26：错
标准答案27：错
标准答案28：对
标准答案29：对
标准答案30：对
标准答案31：错
标准答案32：对
标准答案33：对
标准答案34：对
标准答案35：{p->data} {p=p->next} {p!=NULL}
标准答案36：{q->next!=NULL} {p=p->next} {q->next=s}。

1.数据结构中，与所使用的计算机无关的是数据的（B）。

选择一项：A. 物理和存储结构B. 逻辑结构C. 物理结构D. 存储结构2.组成数据的基本单位是（B）。

选择一项：A. 数据类型B. 数据变量C. 数据元素D. 数据项3.研究数据结构就是研究（D）。

选择一项：A. 数据的逻辑结构B. 数据的逻辑结构和存储结构C. 数据的存储结构D. 数据的逻辑结构和存储结构以及其数据在运算上的实现4.在数据结构中，从逻辑上可以把数据结构分成（A）。

选择一项：A. 线性结构和非线性结构B. 动态结构和静态结构C. 内部结构和外部结构D. 紧凑结构和非紧凑结构5.数据结构是一门研究计算机中（B）对象及其关系的科学。

选择一项：A. 数值运算B. 非数值运算C. 非集合D. 集合6.下列说法不正确的是（C ）。

选择一项：A. 数据元素是数据的基本单位B. 数据项是数据中不可分割的最小可标识单位C. 数据项可由若干个数据元素构成D. 数据可由若干个数据元素构成7.设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是（D）结构。

选择一项：A. 线性B. 集合C. 树形D. 图状8.算法的时间复杂度与（B）有关。

A. 所使用的计算机B. 算法本身C. 算法的程序设计D. 数据结构9.算法分析的两个主要方面是（C）。

选择一项：A. 数据复杂性和程序复杂性B. 正确性和简明性C. 时间复杂性和空间复杂性D. 可读性和文档性10.数据的存储结构包括数据元素的表示和（B）。

选择一项：A. 相关算法B. 数据元素间关系的表示C. 数据处理的方法D. 数据元素的类型11.数据元素是数据的最小单位（错）。

选择一项：对错12.数据的逻辑结构是指数据的各数据项之间的逻辑关系（错）。

对错13.算法的优劣与算法描述语言无关，但与所用计算机有关（错）。

选择一项：对错14.算法是在数据结构的基础上对特定问题求解步骤的一种描述，也是若干条指令组成的优先序列（对）。

数据结构（本）形成性考核作业答案作业1一、单项选择题1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D二、填空题1．n-i+12．n-i3．集合线性结构树形结构图状结构4．物理结构存储结构5．线性结构非线性结构6．有穷性确定性可形性有零个或多个输入有零个或多个输出7．图状结构8．树形结构9．线性结构10． n-1 O(n)11．s->next=p->next;12．head13．q->next=p->next;14．p->next=head;15．单链表16．顺序存储链式存储17．存储结构18．两个直接后继直接前驱尾结点头结点19．头结点的指针指向第一个结点的指针20．链式链表三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。

数据在计算机中的存储表示称为数据的存储结构。

可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。

尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。

采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

数据结构（本）形考作业1参考答案:一、单项选择题1．C 2．D 3．C 4．C 5．D 6．C 7．C 8．C 9．A 10．B二、填空题1．n-i+1 2．n-i 3.集合、线性表、树、图 4. 存储结构、物理结构 5.线性表图6. 有穷性、确定性、可行性、有输入、有输出7. 图8.树9. 线性表 10． n-1 O(n)11．s->next=p->next; 12．head 13．q->next=p->next; 14．p->next=head; 15．单链表 16．顺序存储链式存储 17．存储结构 18.两个后继结点前驱结点尾结点头结点19．指向头结点的指针指向第一个结点的指针 20．链式链表三、问答题1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。

数据在计算机中的存储表示称为数据的存储结构。

可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。

尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。

采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。

2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。

答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。

优点：一般情况下，存储密度大，存储空间利用率高。

缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。

链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

数据结构（本）一、单选题1.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

A.逻辑结构B.物理结构C.算法的具体实现D.给相关变量分配存储单元正确答案: B2.下列说法中，不正确的是（）。

A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可有若干个数据元素构成D.数据项可由若干个数据元素构成正确答案: D3.一个存储结点存储一个（）。

A.数据项B.数据元素C.数据结构D.数据类型正确答案: B4.数据结构中，与所使用的计算机无关的是数据的（）。

A.存储结构B.物理结构C.逻辑结构D.物理和存储结构正确答案: C5.在线性表的顺序结构中，以下说法正确的是（）。

A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高正确答案: C6.对链表, 以下叙述中正确的是（）。

A.不能随机访问任一结点B.结点占用的存储空间是连续的C.插入删除元素的操作一定要要移动结点D.可以通过下标对链表进行直接访问正确答案: A7.下列的叙述中，不属于算法特性的是（）。

A.有穷性B.输入性C.可行性D.可读性8.算法的时间复杂度与（）有关。

A.所使用的计算机B.计算机的操作系统C.算法本身D.数据结构正确答案: C9.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。

A.n-i+1B.n-iC.n-i-1D.i正确答案: A10.设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

A.n-i+1B.n-iC.n-i-1D.i正确答案: B11.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

A.p=q->nextB.p->next=qC.p->next=q->nextD.q->next=NULL正确答案: C12.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。

1.数据结构中，与所使用的计算机无关的是数据的（B）。

选择一项：A. 物理和存储结构B. 逻辑结构C. 物理结构D. 存储结构2.组成数据的基本单位是（B）。

选择一项：A. 数据类型B. 数据变量C. 数据元素D. 数据项3.研究数据结构就是研究（D）。

选择一项：A. 数据的逻辑结构B. 数据的逻辑结构和存储结构C. 数据的存储结构D. 数据的逻辑结构和存储结构以及其数据在运算上的实现4.在数据结构中，从逻辑上可以把数据结构分成（A）。

选择一项：A. 线性结构和非线性结构B. 动态结构和静态结构C. 内部结构和外部结构D. 紧凑结构和非紧凑结构5.数据结构是一门研究计算机中（B）对象及其关系的科学。

选择一项：A. 数值运算B. 非数值运算C. 非集合D. 集合6.下列说法不正确的是（C ）。

选择一项：A. 数据元素是数据的基本单位B. 数据项是数据中不可分割的最小可标识单位C. 数据项可由若干个数据元素构成D. 数据可由若干个数据元素构成7.设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是（D）结构。

选择一项：A. 线性B. 集合C. 树形D. 图状8.算法的时间复杂度与（B）有关。

A. 所使用的计算机B. 算法本身C. 算法的程序设计D. 数据结构9.算法分析的两个主要方面是（C）。

选择一项：A. 数据复杂性和程序复杂性B. 正确性和简明性C. 时间复杂性和空间复杂性D. 可读性和文档性10.数据的存储结构包括数据元素的表示和（B）。

选择一项：A. 相关算法B. 数据元素间关系的表示C. 数据处理的方法D. 数据元素的类型11.数据元素是数据的最小单位（错）。

选择一项：对错12.数据的逻辑结构是指数据的各数据项之间的逻辑关系（错）。

对错13.算法的优劣与算法描述语言无关，但与所用计算机有关（错）。

选择一项：对错14.算法是在数据结构的基础上对特定问题求解步骤的一种描述，也是若干条指令组成的优先序列（对）。

数据结构（本）形成性考核作业（一）分校名称：学号：姓名：成绩：日期：数据结构（本）课程作业作业1（本部分作业覆盖教材第1-2章的内容）一、单项选择题1．在数据结构中，从逻辑上可以把数据结构分为（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部机构2．下列说法中，不正确的是（）。

A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小可标识单位C．数据可有若干个数据元素构成D．数据项可由若干个数据元素构成3．一个存储结点存储一个（）。

A．数据项B．数据元素C．数据结构D．数据类型4．每个存储结点只存储一个数据元素，各结点存储在连续的存储空间，该存储方式是（）存储方式。

A．顺序B．链接C．索引D．散列5．每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（）存储方式。

A．顺序B．链接C．索引D．散列6．数据结构中，与所使用的计算机无关的是数据的（）。

A．存储结构B．物理结构C．逻辑结构D．物理和存储结构7．下列的叙述中，不属于算法特性的是（）。

A．有穷性B．输入性C．可行性D．可读性8．算法分析的目的是（）。

A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性9．数据结构是一门研究计算机中（）对象及其关系的科学。

A．数值运算B．非数值运算C．集合D．非集合10．算法的时间复杂度与（）有关。

A．所使用的计算机B．与计算机的操作系统C．与算法本身D．与数据结构11．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

A．逻辑结构B．物理结构C．算法的具体实现D．给相关变量分配存储单元12．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（）。

A．n-i+1 B．n-i C．n-i-1 D．i13．设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

题目：一个存储结点存储一个（）。

选项A：数据元素选项B：数据项选项C：数据结构选项D：数据类型答案：数据元素题目：数据结构中，与所使用的计算机无关的是数据的（）。

选项A：物理和存储结构选项B：逻辑结构选项C：物理结构选项D：存储结构答案：逻辑结构题目：在线性表的顺序结构中，以下说法正确的是（）。

选项A：逻辑上相邻的元素在物理位置上不一定相邻选项B：进行数据元素的插入、删除效率较高选项C：数据元素是不能随机访问的选项D：逻辑上相邻的元素在物理位置上也相邻答案：逻辑上相邻的元素在物理位置上也相邻题目：对链表, 以下叙述中正确的是（）。

选项A：不能随机访问任一结点选项B：可以通过下标对链表进行直接访问选项C：结点占用的存储空间是连续的选项D：插入删除元素的操作一定要要移动结点答案：不能随机访问任一结点题目：下列的叙述中，不属于算法特性的是（）。

选项A：有穷性选项B：输入性选项C：可读性选项D：可行性答案：可读性题目：把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

选项A：逻辑结构选项B：给相关变量分配存储单元选项C：物理结构选项D：算法的具体实现答案：物理结构题目：下列说法中，不正确的是（）。

选项A：数据元素是数据的基本单位选项B：数据项可由若干个数据元素构成选项C：数据项是数据中不可分割的最小可标识单位选项D：数据可有若干个数据元素构成答案：数据项可由若干个数据元素构成题目：算法的时间复杂度与（）有关。

选项A：所使用的计算机选项B：计算机的操作系统选项C：算法本身选项D：数据结构答案：算法本身题目：设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i 个元素），插入一个元素，则移动元素个数为（）。

选项A：i选项B：n-i-1选项C：n-i选项D：n-i+1答案：n-i+1题目：设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

选项A：n-i-1选项B：n-i+1选项C：i选项D：n-i答案：n-i题目：在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。