对
2、算法分析的目的是分析算法的易懂性和文档性。
错,算法分析的目的是分析算法的效率以求改进
3、顺序存储的线性表的插入和删除操作不需要付出很大的代价,因为平均每次操作只有近一半的元素需要移动。
错
4、不论线性表采用顺序存储结构还是链式存储结构,删除值为X的结点的时间复杂度均为O(N)。
对
5、链式存储的线性表可以随机存取。
错 顺序存储的特点(优点)才是随机存储,因为顺序表是用数组来存储的,每一个数据都有相应的数组下标,我们通过数组下标就能找到任意位置的数据。而链式存储就不同了,不管你找谁都要从头结点开始的。
6、线性表只能用顺序存储结构实现。
错 链式存储结构也可以实现。
7、以链表的头部作为栈顶是最方便的。
对 对栈来讲,进栈出栈都在栈顶进行,而对单链表来讲,始终在单链表的头部插入或删除一个结点最为方便,这是其一,其二,采用头插法,生成的链表,其里的数据元素刚好栈的特征相符。先进后出。所以链表的头部作为栈顶是最方便的
8、链栈采用动态分配,不会出现闲置或栈满溢出现象。
对
9、在括号匹配问题中,若读入的字符是左括号,则将其压入栈。
对 感兴趣的朋友可以去做下洛谷的括号匹配问题:洛谷P1739、UVA673 Parentheses Balance
10、若以链表作为栈的存储结构,则出栈需要判断栈是否空。
对
11、对于不同的特殊矩阵应该采用不同的存储方式。
对 特殊矩阵中元素有规律,采用数组存储。而像稀疏矩阵中元素没有规律,所以一般采用三元组或者伪地址表示法~
12、在一般情况下,采用压缩存储之后,对称矩阵是所有特殊矩阵中存储空间节约最多的。
错 压缩情况下,稀疏矩阵占用内存最少。
13、哈夫曼树是带权路径长度最短的树,所以已知叶子的权值求出的哈夫曼树一定是唯一的。
错,因为没有限定左右子树,并且如果有权值重复时,可能树的高度都不唯一,唯一的只是带权路径长度之和最小
14、将一棵树转换成二叉树后,根结点没有左子树。
错 没有右子树
15、完全二叉树的存储结构通常采用顺序存储结构。
对
16、连通图上各边权值均不相同,则该图的最小生成树是唯一的。
对
17、有e条边的无向图,在邻接表中有e个结点。
错 ,对于任意一条边 在用邻接表表示时都需要表示两次,每次都涉及到两个结点,所以有2e个结点
18、任何无向图都存在生成树。
错 只有图为无向连通图时才能生成树。多个连通分量无法构成树。
19、有n个数存放在一维数组A[1..n]中,在进行顺序查找时,这n个数的排列有序或无序其平均查找长度不同。
错
20、用顺序表和单链表表示的有序表均可使用折半查找方法来提高查找速度。
错
21、折半查找和二叉排序树的时间性能相同
错 不一定相同。
二叉排序树不一定是平衡树,它是只要求了左右子树与根结点存在大小关系,但是对左右子树之间没有层次差异的约束,因此通过二叉排序树进行查找不一定能够满足logn的,例如一棵只有多层左子树的而叉排序树。
只有是一棵平衡的二叉排序树时,其查找时间性能才和折半查找类似。
22、( 10,5,16,2,4 )是堆。
错 堆的定义:{k1,k2,k3,···kn},当满足(1)ki >= k2i且ki>=k2i+1
或 (2)ki next;p->data=q->data;p->next=q->next;delete q;
图解来源: 牛客网用户 phoenixfrank由图,刚开始P指向A。首先,q=p->next,意思是,将q变成(指向)p的next,也就是B。接着,p->data=q->data,意思是,简单来说,就是A结点变成B结点,如图。然后,p->next=q->next,意思是,p原来的next指向B,现在将它的next指向q的next,也就是指向C。最后。delete q。也就是将q指向的结点删除,也就是删除了B。(如果不懂的话,自己动笔跟着画画图就懂了)
数据的不可分割的基本单位是C.元素
题目说的是基本单位,就是元素。如果说的是不可分割的最小单位,那就是数据项。
某算法的时间复杂度为O(n^2),表明该算法的( )
A、问题规模是n^2
C、执行时间等于n^2
C.执行时间与n^2成正比
D、问题规模与n^2成正比
时间复杂度的表示无法对问题规模作出预估,而只能对操作次数作出预估,所以A、D错误。O(n2)表示的是执行次数是多项式计算的,只保留函数最高阶(平方阶),且去掉系数。并不一定绝对等于n2,所以B错误。O(n2),当n的值渐增,其算法时间复杂度执行的时间就越长,所以称正比关系。C正确
将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号最大的非叶结点的编号为________。D.50
完全二叉树对于偶数节点其父节点编号为其编号除以2,奇数节点其父节点编号为(其编号-1)/2。这边就是100/2 = 50。
设带有头结点的单向循环链表的头指针变量为head,则其判空条件是( )。B.head->next==head
画图即可知。
对于顺序表,以下说法错误的是( )。A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址
顺序表可以使用一维数组来实现。但不仅仅只是一维数组可以实现。顺序表指的是存储单元在内存中是连续存放。
单链表的存储密度( )。D.小于1
存储密度=单链表数据项所占空间/结点所占空间结点所占空间 由数据项所占空间和存放后继结点地址的链域构成,所以,存储密度小于1。
广义表A=(a),则表尾为( )。C.空表
这里表头是a,表尾是()。
循环队列存储在数组A[0..m]中,则入队时的操作为( )。D.rear=(rear+1)mod(m+1)
书上公式。
若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为3和0,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少?( )D.5和1
删除1个,队头+1;加入1个,队尾+1。当然如果这边rear值是5了,再加1,rear值变成0,因为是循环队列。
若INDEX(S,T)表示求T在S中的位置的操作,则对于S=“Beijing&Nanjing”,T=“jing”,INDEX(S,T)=( )。C.4
注意,“B”是第一个字母,不是第0个。
广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为( )。D.d
从里往外看,Tail(A)是(b,(c,d),(e,(f,g)));继续Tail,得到((c,d),(e,(f,g)));继续Head,得到
(c,d);继续Tail,得到(d);继续Head,得到d。
有一“遗传”关系,设x是y的父亲,则x可以把它的属性遗传给y,表示该遗传关系最适合的数据结构是_______.A.树
串是一种特殊的线性表,其特殊性体现在( )。B.数据元素是一个字符
数组A中,每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[8][5]的起始地址为( )。C.SA+222
下面算法的时间复杂度是 int p1( int n) { t = 1; while( t 1;i--) for(j=1;ja[j+1]) a[j]与a[j+1]对换; 其中 n为正整数,则最后一行的语句频度在最坏情况下是________。A.O(n^2)
最坏,就是两个for都循环遍历完才找到目标,所以答案就是O(n^2)。
以下关于栈和队列的叙述中,正确的是 () 。C.栈和队列都不允许在元素序列的中间插入和删除元素
栈,只能从栈顶开始插入或弹栈(删除),后进后出;队列是从队尾插入,队头删除,先来先出。
链式栈结点为:(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作( )。A.x=top->data;top=top->link;
先把top的值给x,然后再让top指向在它底下的一个值(就是摘除栈顶结点)
求循环链表中当前结点的后继和前驱的时间复杂度分别是( )。B.O(1)和O(n)
不难理解,解析略。
假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为( )。A.(rear-front+m)%m
背公式!公式本身不难理解,具体公式推导请自行搜索。
若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是( )。D.不确定的
栈的输入输出顺序是后进后出。因为这里题目没说是一次性全进栈,也没说是一次性全出栈,所以输出元素不确定。