数据结构（中国海洋大学）智慧树知到期末考试答案2024年

数据结构（中国海洋大学）智慧树知到期末考试答案2024年数据结构（中国海洋大学）已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为（）。

A:1341B:1340C:1339D:1342答案:1340线性表是具有n个（）的有限序列

A:数据元素B:字符C:关系D:数据项答案:数据元素串的长度是指（）。

A:串中所含不同字母的个数B:串中所含字符的个数C:串中所含不同字符的个数D:串中所含非空格字符的个数答案:串中所含不同字母的个数设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。

A:40,50,20,95B:45,40,15,20C:15,20,40,45D:15,40,60,20答案:15,40,60,20由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）

A:23B:44C:37D:46答案:44设循环队列的存储空间为a[0…20]，且当前队头指针和队尾指针的值分别为8和3，则该队列中的元素个数为（）

A:5B:6C:17D:16答案:16以下排序方法中，（）不需要进行关键字的比较。

A:快速排序B:堆排序C:归并排序D:基数排序答案:基数排序设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。

A:双向链表B:单向链表C:单向循环链表D:双向循环链表答案:双向循环链表设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A:99B:101C:102D:100答案:100在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍

A:1B:2C:0.5D:4答案:1对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为（）,在给定值为x的结点后插入一个新结点的时间复杂度为（)。

A:O(n2)，O(e)B:O(1)，O(e)C:O(n2)，O(n+e)D:O(1),O(n)答案:O(1),O(n)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()。

A:9，5,2,3B:1，2,3C:9，4,2,3D:9，5,3答案:9，4，2，3G是一个非连通无向图，共有28条边，则该图至少有(）个顶点。

A:8B:9C:7D:6答案:9三元组用来存储（）

A:广义表B:特殊矩阵C:稀疏矩阵D:稠密矩阵答案:稀疏矩阵某线性表中最常用的操作是读取序号为i的元素和在最后进行插入删除运算，则采用（）存储方式时间性能最好。

A:单向循环链表B:双向链表C:顺序表D:双向循环链表答案:顺序表非空循环单链表head的尾结点p满足（）

A:p.next==headB:p==headC:p==nullD:p.next==null答案:p.next==head一组记录的排列码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（）

A:84,79,56,38,40,46B:79,46,56,38,40,84C:84,79,56,46,40,38D:84,56,79,40,46,38答案:84,79,56,38,40,46树的先根序列等同于与该树对应的二叉树的（）

A:后序序列B:中序序列C:层序序列D:先序序列答案:中序序列一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF,则后序遍历序列为（）

A:不确定B:CBEDFAC:FEDCBAD:CBEFDA答案:CBEFDA设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

A:5B:8C:3D:4答案:3已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为

A:3，2，5，4，1，6B:1，4，6，5，2，3C:5，4，3，2，1，6D:2，3，5，6，1，4答案:3，2，5，4，1，6深度为k的完全二叉树中最少有（）个结点。

A:2k-1-1B:2k-1C:2k-1D:2k-1答案:2k-1以下关于线性表的叙述，正确的是（）

A:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个前驱和后继元素B:每个元素都有一个前驱和后继元素C:线性表中至少有一个元素D:线性表中元素的排列次序必须是由小到大或由大到小答案:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个前驱和后继元素广义表运算：tail(((a,b),(c,(d,e))))=（）。

A:c,(d,e)B:(d,e)C:((c,(d,e)))D:(c,(d,e))答案:((c,(d,e)))一棵二叉排序树是由关键字集合{18，43，27，44，36，39}构建的，其中序遍历序列是（）

A:44，43，39，36，27，18B:18，43，27，44，36，39C:18，27，36，39，43，44D:树形未定，无法确定答案:18，27，36，39，43，44设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

A:N0=2N1+lB:N0=Nl+N2C:N0=N1+1D:N0=N2+1答案:N0=N2+1二路归并排序的时间复杂度为（）。

A:O(n)B:O(n2)C:O(1og2n)D:O(nlog2n)答案:O(n)栈和队列的共同点是（）

A:没有共同点B:都是后进后出C:只允许在端点处插入和删除元素D:都是先进先出答案:只允许在端点处插入和删除元素对稀疏矩阵进行压缩存储的目的是（）

A:降低运算的时间复杂度B:便于输入和输出C:便于进行矩阵运算D:节省存储空间答案:节省存储空间一个栈的进栈序列是a,b,e.d,e,则栈的不可能的输出序列是（）

A:abcdeB:decbaC:dceabD:edcba答案:dceab设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。

A:15，25，35，50，80，20，85，40，70，85B:15，25，35，50，80，20，36，40，70，85C:15，25，35，50，20，40，80，85，36，70D:15，25，35，50，80，20，85，40，70，36答案:15，25，35，50，20，40，80，85，36，70一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比，会失去（）

A:随机存取B:以上都不对C:顺序存储D:输入/输出答案:随机存取已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（）

A:ABCDEFB:FEDCBAC:FDECBAD:FBDCEA答案:FEDCBA设有向图G中的有向边的集合E={，，，，，，}，则该图的一个拓扑序列为(）

A:124635B:123456C:124653D:146532答案:124653设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。

A:匹配B:联接C:求串长D:求子串答案:匹配设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。

A:head==0B:head->next==0C:head->next==headD:head!=0答案:head==0对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()

A:单链表B:用头指针表示的单循环链表C:顺序表D:用尾指针表示的单循环链表答案:用尾指针表示的单循环链表在含有27个结点的二叉排序树上查找关键字为35的结点，则依次比较的关键字有可能是（）

A:46，28，18，36，35B:46，36，18，28，35C:28，36，18，46，35D:18，36，28，46，35答案:46，36，18，28，35以下关于链式存储结构的描述中，（）是不正确的。

A:结点除自身信息外还包括指针域，因此存储密度不是很大。B:结点除自身信息外还包括指针域，因此存储密度不是很大C:可以通过计算直接确定第i个结点的地址。D:插入删除方便，不必移动结点。答案:可以通过计算直接确定第i个结点的地址。若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（）

A:SXSSXXXXB:SSSXXSXXC:SXXSXSSXD:SXSXXSSX答案:SSSXXSXX下列叙述中不符合m阶B树定义要求的是（）

A:各结点内关键字均升序或降序排列B:根结点最多有m个子树C:所有叶结点都在同一层上D:叶结点之间通过指针链接答案:叶结点之间通过指针链接对线性表进行二分查找时，要求线性表必须是（）

A:以链式方式存储B:以顺序方式存储，且结点按关键字有序排列C:以链式方式存储，其结点按关键字有序排列D:以顺序表存储答案:有序广义表(a,(a,b),d,e,((i,j),k))的长度是（），深度是（）。

A:6，3B:5，2C:6，2D:5，3答案:5设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。

A:40B:45C:20D:30答案:45稀疏矩阵的压缩存储一般采用（）存储方式。

A:三元组表B:二元组表C:数组D:链表答案:三元组表关键路径是事件结点网络中（）

A:最长的回路B:从源点到汇点的最短路径C:从源点到汇点的最长路径D:最短的回路答案:从源点到汇点的最长路径已知在顺序表中每个元素需占用8个存储单元，且LOC（a1）=100,则LOC（a5）=()

A:132B:148C:150D:140答案:132元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（）

A:B，C，D，E，AB:E，A，B，C，DC:E，D，C，B，AD:A，B，C，D，E答案:E，A，B，C，D在栈中进行插入和删除操作的一端称为（）

A:指定位置B:栈顶C:栈底D:任意位置答案:栈顶下列四种排序中（）的空间复杂度最大。

A:堆B:快速排序C:希尔排序D:冒泡排序答案:快速排序逻辑上通常可以将数据结构分为

A:顺序结构和链式结构B:线性结构和非线性结构C:初等结构和组合结构D:动态结构和静态结构答案:线性结构和非线性结构数据结构中评价算法的两个重要指标是时间复杂度、空间复杂度。

A:错B:对答案:对在n个结点的无向图中，若边数大于n-1,则该图必存在环路。

A:错B:对答案:对一个字符串中任意个连续字符成为该串的子串。

A:对B:错答案:对链式存储的特点是利用指针来表示数据元素之间的逻辑关系。

A:对B:错答案:对空格穿的长度为串中空格的个数。

A:对B:错答案:对串是一种特殊的线性表，其特殊性体现在（）

A:数据元素可以是多个字符B:数据元素是单个字符C:可以是顺序存储D:可以链接存储答案:AI参考:正确答案是B:数据元素是单个字符。\n\n串是一种特殊的线性表，其特殊性体现在数据元素是单个字符。串中的字符可以是任意类型的数据，可以是整数、浮点数、字符串等，但每个元素必须是单个字符。串的存储方式可以是顺序存储或链式存储，但这并不是其特殊性所在。因此，选项B是正确答案。'在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行

A:.q->next=p；p->next=qB:q->next=p->next；p->next=q；C:q->next=p->next；p=q；D:p->next=q；q->next=p；答案:AI参考:在非空线性链表中由p所指结点的后面插入一个由q所指的结点，正确的操作应该是：D:p->next=q；q->next=p；这是因为，首先将p的下一个节点指向q，然后再将q的下一个节点指向p，这样就完成了在p后面插入q的操作。选项A和B都是错误的，因为它们没有正确地处理p和q的链接关系。选项C也是错误的，因为它在插入q后，将p重新指向q，这会导致p链表出现环路。因此，正确答案是D：p->next=q；q->next=p。'线性表采用链式存储结构时，要求内存中可用存储单元的地址()

A:连续和不连续都可以B:一定是不连续的C:必须是部分连续的