提示:内容已经过期谨慎付费，点击上方查看最新答案
数据结构与算法
- 若对n个顶点、e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（ ）。
- 用Prim算法和Kruskal 算法构造图的最小生成树，所得到的最小生成树（ ）。
- 设a ,b, c, d, e, f以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为（ ）。
- 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）
有下列算法片段，请分析算法的时间复杂度是( )
void test(int n)
{ int i,sum;
for (i=0,s=0; s<=n; )
{ i=i+1;
sum=sum+i;
}
}
为提高散列表的查找效率，可以采取的正确措施是（ ）
I.增大装填（载）因子
II.设计冲突（碰撞)少的散列函数
III．处理冲突（碰撞）时避免产生聚集（堆积）现象
- 要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是（ ）。
- 具有6个顶点的无向图，当有（ ）条边时能确保是一个连通图。
- 允许对队列进行的操作有（ ）。
- 含有20个结点的平衡二叉树的最大深度为（ ）。
- 在有11个元素的有序表A[ 1,2,...,11]中进行折半查找查找元素A[11]时，被比较的元素下标依次是（ ）。
- 以下算法复杂度中，最小的是( )。
- 在一个长度为n 的顺序表中删除第i (1
）个元素时，需向前移动（ ）个元素。 - 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234， 为了得到1342的出栈顺序，相应的和X的操作序列为（ ）。
- 在森林的二叉树表示中，结点M和结点N是同一父结点的左儿子和右儿子，则在该森林中（ ）。
- 下列关于二分查找的叙述中，正确的是（ )。
- 下列关于排序的叙述中，正确的是 ( )
对下图所示的有向带权图，若采用Dijkstra算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（ ）。
- 若用冒泡排序算法对序列 {10, 14, 26, 29, 41, 52} 从大到小排序，则需进行（ ）次比较。
- 单链表中，增加一个头结点的目的是为了（ ）。
- 对关键码序列 {23, 17, 72, 60, 25, 8, 68, 71, 52} 进行堆排序，输出两个最小关键码后的剩余堆是（ ）。
- 以下排序算法中，稳定的是（ ）。
- 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。
- 对n个记录进行堆排序，最坏情况下其时间复杂度为（ ）。
- 具有15个叶子节点的二叉树中有（ ）个度为2的结点。
- 已知字符集｛a,b,c,d,e,f｝，若各字符出现的次数分别6,3,8,2,10,4,则对应字符集中各字符的哈夫曼编码可能是（ ）。
- 一个线性表最常用的操作是：存取任一指定序号的元素，并在表最后进行插入删除操作，则利用（ ）存储方式可以节省时间。
- 在一个链队列中，假设队头指针为front, 队尾指针为rear, x所指向的元素需要入队，则需要执行的操作为（ ）。
- 假设一个循环队列Q [MaxSize]的队头指针为front， 队尾指针为rear，队列的最大容量为Maxsize，除此之外，该队列再没有其他数据成员，则判断该队的列满条件是（ ）。
- 若序列的原始状态为 {1,2,3,4,5,10,6,7,8,9}，要想使得排序过程中的元素比较次数最少，则应该采用（ ）。
- 一个具有513个结点的二叉树的高h为（ ）。
- 带头结点的双循环链表为空的条件是（ ）。
- 假设一棵二叉树的结点个数为50，则它的最小高度是（ ）。
- 任何一个无向连通图的最小生成树（ ）。
- 希尔排序的组内排序采用的是（ ）。
- 己知一棵二叉树的先序遥历结果为ABCDEF，中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
- 假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top-=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（ ）。
- 一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79}，用链地址法构造散列表，散列函数为H(key) =key MOD 13，散列地址为1的链中有( )个记录。
- 栈是（ ）。
- 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定只有一个叶结点（ ）
- 表达式a*（b+c）-d的后缀表达式是abcd*+-。（ ）
- 算法至少有1个输入（ ）
- 有向图中顶点V的度等于其邻接矩阵中第V行中1的个数。（ ）
- 消除递归一定需要使用栈这种数据结构。（ ）
- 在图G的最小生成树G中，某条边的权值可能会超过未选边的权值。（ ）
- 链表的物理存储结构具有同链表一样的顺序。（ ）
- 若散列表的装填因子α＜1，则可避免碰撞的产生。（ ）
- 在常用的描述二叉排序树的存储结构中，关键字值最大的结点右指针一定为空。（ ）
- 顺序存储结构和链式存储结构都可以进行顺序存取。（ ）
A:O(ne) B:O(n + e) C:O(n) D:O(n2)
答案:O(n+e)
A:相同 B:无法比较 C:不相同 D:可能相同，可能不同
答案:对
A:fedcba B:cabdef C:bcafed D:deefba
答案:ba
A:257 B:384 C:385 D:258
答案:正确答案:C
A:O(sqrt(n)) B: O(n) C:O(n^2) D:O(logn)
A:仅I、II B:仅II C:仅II、III D: 仅I
A:只有左子树 B:结点的度为1 C:结点的度为2 D:只有右子树
A:11 B:10 C:8 D:9
A:在队列元素之间插入元素 B:取出最后进队的元素 C:删除队头元素 D:对队列中的元素排序
A:5 B:7 C:4 D:6
A:6,8,9,11 B:6,8,10,11 C:6,9,10,11 D:6,7,9,11
A:O(n^2*logn) B:O(2^n) C:O(n^3) D:O(3^n)
A:n - i + 1 B:i - 1 C:n D:n - i
A:SSSXXSXX B:SXSSXXSX C:SXSSXSXX D:SXSXSSXX
A:M是N的左兄弟 B:M是N的儿子 C:M和N可能无公共祖先 D:M和N有同一双亲
A:表必须有序，而且只能从小到大排列 B:表必须有序，表可以顺序方式存储，也可以链表方式存储 C:表必须有序且表中数据必须是整型、实型或字符型 D:表必须有序，且表只能以顺序方式存储
A:稳定的排序方法优于不稳定的排序方法 B:排序方法都是在顺序表上实现的，在链表上无法实现排序方法 C:对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同 D:在顺序表上实现的排序方法在链表上也可以实现
A:d, e, f B:f, d, e C:f, e, d D: e, d, f
A:10 B:15 C:25 D:3
AI参考:答案：C解释：冒泡排序算法是一种简单的排序算法，它会反复地遍历待排序的序列，每次比较相邻的两个元素，如果顺序不对就交换它们的位置，直到所有元素都排好序为止。对于给定的序列 {10, 14, 26, 29, 41, 52}，我们按照从大到小的顺序进行冒泡排序。每次遍历序列时，都会将最大的元素"浮"到序列的末尾。因此，冒泡排序需要进行n-1次遍历，其中n是序列的长度。对于给定的序列，共有6个元素，因此需要进行5次遍历。但在最后一次遍历时，最大的元素已经在末尾了，因此无需再进行比较。所以总共需要进行25次比较。因此，正确选项为C：25次比较。'
A:说明单链表是线性表的链式存储 B:方便运算的实现 C:标识表结点中首结点的位直 D:使单链表至少有一个结点
A:{71, 25, 23, 52, 60, 72, 68} B:{23, 25, 52, 60, 71, 72, 68} C:{23, 25, 68, 52, 60, 72, 71} D:{23, 72, 60, 25, 68, 71, 52}
AI参考:输出两个最小关键码后的剩余堆是：D:{23, 72, 60, 25, 68, 71, 52}。堆排序是一种基于二叉堆数据结构的排序算法，它首先将待排序序列构造成一个大顶堆，然后将堆顶元素与堆尾元素交换，并调整剩余元素形成新的堆。在题目中，首先将序列{23, 17, 72, 60, 25, 8, 68, 71, 52}构造成一个大顶堆，然后交换堆顶元素（23）和堆尾元素（25），得到剩余堆{72, 60, 68, 71, 8, 52}。再将堆顶元素（68）和堆尾元素（8）交换，得到最终的剩余堆{72, 60, 52, 68, 71, 8}。因此，正确选项为D:{23, 72, 60, 25, 68, 71, 52}。'
A:快速排序 B:直接插入排序 C:简单选择排序 D:堆插入排序
AI参考:答案是B：直接插入排序。稳定排序算法的特点是，等值元素的相对位置在排序后保持不变。直接插入排序、二分查找排序、基数排序和就地排序都是稳定的排序算法。而快速排序、堆排序、计数排序、基数排序和桶排序是不稳定的排序算法。因此，正确答案是B：直接插入排序。'
A:2h+1 B:h C:h+1 D:2h-1
A:O(n) B:O(n2) C:O(log2n) D:O(nlog2n)
A:13 B:15 C:16 D:14
A:00,1011,01,1010,11,100 B:10,1011,11,0011,00,010 C:00,100,110,000,0010,01 D:0011,10,11,0010,01,000
AI参考:已知字符集｛a,b,c,d,e,f｝，各字符出现的次数分别为6,3,8,2,10,4，那么字符a和f出现的次数较少，应使用较短的哈夫曼编码；字符b、c、d出现的次数较多，应使用较长的哈夫曼编码。按照以上原则，结合给出的选项，答案为B：10,1011,11,0011,00,010。这个答案中，只有B选项包含了较短和较长两种编码，且满足上述出现次数较少和较多的字符编码原则。其中，字符a的编码为“10”，字符b的编码为“1011”，字符c的编码为“11”，字符d的编码为“0011”，字符e的编码为“00”，字符f的编码为“010”。所以，B选项是正确答案。'
A:双链表 B:顺序表 C:带头结点的双循环链表 D:单循环链表
A:x-＞next= front-＞next；front=x； B:front=x； front= front-＞next； C:rear-＞next=x; x-＞next=NULL; rear=x; D:rear-＞next=x; rear=x ;
AI参考:正确答案是D：rear-＞next=x; rear=x ;在一个链队列中，队头指针为front，队尾指针为rear，需要入队操作的操作为 rear->next=x; rear=x;。此时队尾指针rear后移一位，指向新元素x，新元素x作为新队尾插入到链队列中。所以选项D是正确的。'
A:Q. rear= (Q. front+1) %MaxSize B:Q. front==(Q. rear+1) %MaxSize C:Q. front==Q. rear D:Q. front+Q. rear＞=MaxSize
A:选择排序 B:希尔排序 C:起泡排序 D:插入排序
AI参考:正确答案是D：插入排序。原始状态为{1,2,3,4,5,10,6,7,8,9}，要想使得排序过程中的元素比较次数最少，应采用插入排序。插入排序是一种简单直观的排序方法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在处理小规模数据时速度较快，但当数据量较大时，时间复杂度可达到O(n²)。选择排序、希尔排序、起泡排序时间复杂度均大于O(n²)。故答案为D。'
A:9 B:10~513 C:9~512 D:10
A:L-＞prior==L&&L-＞next==NULL B:L-＞prior==L& &L-＞next==L C:L-＞prior==NULL&&L-＞next==L D:L-＞prior==NULL& &L-＞next==NULL
A:4 B:7 C:6 D:5
A:只有一棵 B:可能不存在 C:一定有多棵 D:有一棵或多棵
A:归并排序 B:折半插入排序 C:快速排序 D:直接插入排序
A:FEDCBA B:CBEDFA C:不确定 D:CBEFDA
A:a[--top]=x B:a[top--]=x C:a[++top]=x D:a[top++]=x
A:4 B:2 C:1 D:3
A:顺序存储的线性结构 B:链式存储的非线性结构 C:限制存取点的线性结构 D:限制存储点的非线性结构
AI参考:正确答案是A：顺序存储的线性结构。栈是一种基本的数据结构，它只允许在某一端进行插入和删除操作，这一端称为栈顶，另一端称为栈底。因此，栈是一种顺序存储的线性结构。故选A。'
A:对 B:错
A:错 B:对
AI参考:答案：B：对。后缀表达式中，运算符的优先级由离其位置的远近决定，越靠后的运算符优先级越低。在这个表达式中，乘法和加法具有相同的优先级，且高于减法。所以，表达式的后缀表达式应该是“abcd*+”。因此，该题判断为正确选项“B：对”。'
A:错 B:对
A:对 B:错
A:对 B:错
A:错 B:对
A:错 B:对
A:错 B:对
A:对 B:错
A:对 B:错
温馨提示支付 ￥2.10 元后可查看付费内容,请先翻页预览!
