数据结构[后续有重构计划]

1.最小生成树问题是构造连通网的最小代价生成树(对)

构造网的最小生成树必须解决下面两个问题:

1、尽可能选取权值小的边,但不能构成回路;

*2、选取n-1条恰当的边以连通n个顶点;


MST性质:假设G=(V,E)是一个连通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。

2.将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为(55)

  • 主对角线都存:10个,剩下的90个只存一半45个,共55个

3.线性表是具有 n 个(数据元素)的有限序列(n>0)

 数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成,数据项是构成数据元素的不可分割的最小单位。例如,学生记录就是一个数据元素,它由学号、姓名、性别等数据项组成。

4.最坏情况下 insert sort, quick sort ,merge sort 的复杂度分别是多少

  • O(nn),O(nn),O(nlogn)

softTime.png

5.一个网(带权图)都有唯一的最小生成树(错 ,不唯一,最小生成树可以有多个, 他们的权值相等且最小即可)

6.某二叉树共有4个结点,前序(先根序)遍历该二叉树的4个结点并记录各结点取值,得到的结果是“abcd”。那么,该二叉树有多少种可能的拓扑结构?(14)

    递推公式:
    递推时每次固定根节点再考虑
    规定f(0)=1
    f(n) = f(n-1)f(0) + f(n-2)f(1)...f(0)f(n-1)
    解:
    f(1) = 1
    f(2) = f(1)f(0) + f(0)f(1) = 2
    f(3) = f(2)f(0) + f(1)f(1) + f(0)f(2) = 5
    f(4) = f(3)f(0) + f(2)f(1) + f(1)f(2) + f(0)f(3) = 14

不要被先序遍历迷惑,其实就是4个结点的二叉树有多少种

7.一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足(其中只有一个叶结点)

一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足只有左子树或只有右子树。

8.下标从1开始,在含有n个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在([n/2]+2)位置上

    小根堆中最大的数一定是放在叶子节点上,堆本身是个完全二叉树,完全二叉树的叶子节点的位置大于[n/2]


    首先要明白:中括号取整,就是不大于这个数的最大整数
    第二要看清下标是从1开始的。那么
                                              1
                                         2       3
                                    4     5   6    7
                                  ...............n
    n不论是左子树还是右子树,n的父结点一定是 [n/2],注意中括号的取整规则,正数就是下取整
    那么 [n/2] 这个结点还是有子结点的,从 [n/2] + 1 开始一直到 n 都是叶子结点,叶子结点就可能会是最大值,所以选D
    看见前边有人回答说没有考虑n ==2 这种情况,诚然,如果n == 2的话,d选项就是3了,但是人家说的是可能。只要具备可能性就行了。

9.下列哪一个关键码序列不符合堆的定义?(A、D、P、R、C、Q、X 、M、H、G)

    可以看出答案都是小堆关键码序列,根据小堆的定义,
    K[i]<= K[2i]
    K[i]<= K[2i+1]
    C选项中关键码序列用完全二叉树表示后很容易看出,结点值d大于了左子结点值c

10.在n个结点的线性表的数组实现中,算法的时间复杂性是O(1)的操作是(访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n))

    注意题目强调的是用 数组 实现的线性表,所以A答案就是访问数组的第i和i-1个元素,B和C是对数组进行插入和删除,需要移动后面的元素,复杂度为O(n)

11.现有一棵无重复关键字的平衡二叉树(AVL 树),对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中,正确的是 (树中最大元素一定是无左子树)

    排序树有两种排序方法:
    1.左孩子 < 根节点 < 右孩子(常见)
    这种情况中序遍历得到的是一个升序序列
    2.左孩子 > 根节点 > 右孩子
    这种情况中序遍历得到的是一个降序序列

12.在二叉排序树中插入一个结点最坏情况下的时间复杂度为(O(n))

    最差情况下是O(n) 如果是最一般最基础的二叉树的话, 因为深度不平衡,所以会发展成单链的形状,就是一条线 n个点那么深
    如果是深度平衡的二叉树 o(logn)

13.哈夫曼树的结点个数不能是偶数()

  对,假设哈夫曼树是二叉的话,则度为0的结点个数为N,度为2的结点个数为N-1,则结点总数为2N-1。

14. n个结点的线索二叉树上含有的线索数为 n+1

    通过考察各种二叉链表,不管二叉树的形态如何,空链域的个数总是多过非空链域的个数。
    ,n各结点的二叉链表共有2n个链域,非空链域为n-1个,但其中的空链域却有n+1个。
    因此,提出了一种方法,利用原来的空链域存放指针,指向树中其他结点。这种指针称为线索。
    因此线索二叉树的线索数为二叉链表中的空链域的值

15.稀疏矩阵一般的压缩存储方法有两种,即()

  • 三元组和十字链表
    1.三元组顺序表又称有序的双下标法,对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是,非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储空间。
    2.十字链表:是既带行指针又带列指针的链接存储方式,每个三元组结点处于所在行单链表与列单链表的交点处,当矩阵的非零元个数和位置在操作过程中变化较大时,用这种存储结构更为恰当。
    在十字链表中,每个非零元可用一个含五个域的结点表示,其中 i, j 和e 三个域分别表示该非零元所在的行、列和非零元的值,向右域 right 用以链接同一行中下一个非零元,向下域down 用以链接同一列中下一个非零元。同一行的非零元通过 right 域链接成一个线性链表,同一列的非零元通过 down 域链接成一个线性链表,每个非零元既是某个行链表中的一个结点,又是某个列链表中的一个结点,整个矩阵构成了一个十字交叉的链表,故称这样的存储结构为十字链表,可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。

16.在一个有向图的拓扑序列中,若顶点 a 在顶点 b 之前,则图中必有一条弧<a,b>。( 错误)

    该题考察的是拓扑排序的概念,如果从 a 到 b 有一条有向路径,则 a 一定排在 b 之前,反过来也应该以“路径”更准确。
    注意区分“路径”和“弧”:
    弧:指的是有向图里面的边,有明确方向的。如果是无向图的边,直接叫做“边”。比如有向图的 v1 结点到 v2 结点的弧可能是:<v1, v2>;

    路径:指的是图(包括有向图和无向图)里面连接两个结点之间的边的集合,也就是一个顶点序列。比如:v1 到 v3 的路径可能这样表示:<v1, v2>、<v2, v3>;
    如下图举例所示:顶点 a 在顶点 b 之前,但没有弧<a,b>,而是一条路径<a,c><c,b>

    a->c->b->e

17.设链式栈中结点的结构为(data ,link),且top是指向栈顶的指针,若想在链式栈的栈顶插入一个由指针s所指的结点,则应执行( C )操作

    s->link=top; top=s;

18.若有以下定义

    int c[4][5],( *pc)[5];
    pc=c;

那么,下列对数组C的元素引用正确的是( )。

  • (*pc+2)
    pc是一个数组指针(指向数组的指针),指向列数为5的二维数组,pc = c,表示pc指向二维数组的第一行,pc+1偏移一行,一行5个元素。*pc得到二维数组c的第一行数组的首地址,+2偏移到c[0][2]的地址,解引用就得到数据2。c[4][5]可以理解为4个长度为5的一位数组,这四个一维数组的地址要用数组指针存放。

19.一个非连通图(无自回路和多重边)有66条边,那么它至少有(13)个顶点

    既然是不连通图,那么就从节点中减去1个,然后剩下的节点有66条边,根据排列组合算,当节点数为12时,从中选取2个节点,边数是66,所以总得节点数是12+1=13

20.判断下列说法是否正确:平衡二叉树一定是二叉排序树。( 正确)

    平衡二叉树首先是二叉排序树。基于二叉排序树,发现树越矮查找效率越高,进而发明了二叉平衡树

21.下列说法正确的是(ABD)

    二维以上的数组其实是一种特殊的广义表
    数组一旦建立,结构的元素个数和元素间的物理存储关系就不再变化
    数组是一种线性结构,因此只能用来存储线性表
    数组采用顺序存储方式表示

    我们需要区分数据的物理结构与逻辑结构。物理结构主要是指存储方式,
    包含线性存储与链式存储,它是从计算机存储的角度去考虑。逻辑结构指的是数据之间的关系,
    有线性关系和链式关系等,主要是从人为定义角度去考虑。
    数组是一种被人们定义为线性关系的表,至于其存储结构,
    可以用线性存储也可以是链式存储去存储

22.已知一段文本有1382个字符,使用了1382个字节进行存储,这段文本全部是由a、b、c、d、e这5个字符组成,a出现了354次,b出现了483次,c出现了227次,d出现了96次,e出现了232次,对这5个字符使用哈夫曼(Huffman)算法进行编码,则以下哪些说法正确(ACD)

    使用哈夫曼算法编码后,用编码值来存储这段文本将花费最少的存储空间
    使用哈夫曼算法进行编码,a、b、c、d、e这5个字符对应的编码值是唯一确定的
    使用哈夫曼算法进行编码,a、b、c、d、e这5个字符对应的编码值可以有多套,但每个字符编码的位(bit)数是确定的
    b这个字符的哈夫曼编码值位数应该最短,d这个字符的哈夫曼编码值位数应该最长

    A正确,Huffman树就是求最优解。可以有多套方案,但最终每套方案生成的编码长度都相同且都是最优解。
    B错误,我们可以将左子树定为1右子树定为0也可以反之,不同的方案获得的编码值是不同的,但每个字符的编码长度是固定的。
    C正确,不同的方案影响的只是通向节点的路径为0还是1,而不会影响Huffman树的层次结构
    D正确,生成了Huffman树之后,我们就能看到,出现频率越高的节点越靠近根,深度越小即编码值尾数越短;出现频率越低的节点越远离根,深度越大即编码位数越长。

23.在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是

  • O(n)
    单链表插入时间应该是O(1),但要维持有序状态,就应该从头结点开始逐个进行比较扫描,最好情况O(1),最坏O(N),平均情况~N/2
    个人浅见,不知道是否正确。

24.对两棵具有相同关键字集合的而形状不同的二叉排序树,按中序遍历它们得到的序列的顺序却是一致的(对)

    二叉排序树中序遍历的结果是从小打大完全有序的序列。题目中说两棵树的关键字集合相同,所以得到的有序序列也是相同的

25.对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是(95,22,91,24,94,71)

25

26.对两个数组 a 和 b 进行如下初始化

char a[] = "ABCDEF";
char b[] = {'A','B','C','D','E','F'};
以下叙述正确的是(  D  )

    a 与 b 数组完全相同
    a 与 b 长度相同
    a 和 b 中都存放了字符串
    a 数组比 b 数组长

a中会多一个'\0'字符。

26.连通图上各边权值均不相同,则该图的最小生成树是唯一的(对)

设G是所有边权均不相同的无向联通图。

证明一:

首先,易证图G中权值最小的边一定是最小生成树中的边。(否则最小生成树加上权值最小的边后构成一个环,去掉环中任意一条非此边则形成了另一个权值更小的生成树)。



之后用反证法,假设G存在俩个不同的最小生成树

①.设G的俩个不同的最小生成树T1 T2,设这俩颗生成树的并集为子图G1,G1为连通图且T1 T2显然为G1的最小生成树,由首先可得知俩颗生成树至少包含一条公共边,将G1中两颗生成树的公共边删去,得到子图G2。G2由一个或多个连通分量组成,其中至少有一个连通分量的最小生成树不唯一(否则若所有连通分量的最小生成树唯一,则将删掉的公共边加上,则T1等于T2,这与假设相矛盾)。

②.对其中一个最小生成树不唯一的连通分量设为H,若H中点数>2,重复①的操作。否则H中只有俩个点,由于所有边权值不同,显然最小生成树唯一,这与①中的最后一句相矛盾。

综上,所有边权均不相同的无向图最小生成树是唯一的。

证明二:

设T,T’为G的俩个最小生成树,设T的边集E(T)={e1,e2,...,em},T'的边集 E(T')={e'1,e'2,...,e'm}。

设ek满足ek≠e'k且k最小,由于所有边权值不同,不妨假设weight(ek)



还有一个更强的结论:同一个图不同最小生成树的边权重序列相同。

27.在有序表(5,8,36,48,50,58,88)中二分查找字58时所需进行的关键字比较次数是(),对应的判定树高度为(2,3)

根据有序表建立二叉排序树
      48
     /    \
   8      58
  / \      /   \
5 36   50 88
58在第二层,也就是第二次比较就可以确定了
BST的高度为3,也就是最多要经过3次排序
所以最终结果为 2,3

28.单链表实现的栈,栈顶指针为Top(仅仅是一个指针),入栈一个P节点时,其操作步骤为

  • p->next=Top->next;Top->next=p;
栈的表示在不同的书上一般有两种表达方式:
1.top指针指向栈顶元素,这样下一个出栈的元素就是top指向的结点元素;此时入栈操作为p->next=Top; Top=p;
2.top指向下一个可以入栈的位置,这样就相当于top是带头结点的链表中的头节点,然后入栈的话就要插入到top的下一个节点位置;此时入栈操作为p->next=Top->next;Top->next=p;
因为题目中并没有明确表示有没有头节点(相对于链表来说),因此这里根据答案来选择,只有B项符合上面的第二种表达方式。

29.已知不带头结点的双向循环链表中的结点结构为(data,last,next) ,在指针p所指结点之后插入由指针s指向的新结点,相应操作为

  • p->next=s; p-> next->last=s; S-> last=p;s-> next=p->next
考察的是链表中插入新节点的步骤。
将新节点s指向的数据赋值给p的next。p->next=s
将新节点s指向的数据赋值给原链表p的next结点的last结点。p-> next->last=s
将新节点p指向的数据last指向p。S-> last=p
原链表中p的next指向新节点s的next。s-> next=p->next

30.已知二维数组A[1: 4, 1: 6]采用列序为主序方式存储,每个元素占用4个存储单元,并且A[3,4]的存储地址为1234,元素A[1, 1]的存储地址是

  • 1178
a11+(3*4+2)*4=1234。这样就可以得到a11

是按照 列序,不是行序。
首先计算a00的位置:a00+(4*4+3)*4=1234  求得:a00=1158
有了a00的位置在求a11位置:a00+(1*4+1)*4=a11 即a11=1178

首先,我们应该明白的是,按照行序求的话,应该使用待求数组的 行数*数组列的容量+待求数组的列值。
那么 按照列序的话   应该是  数组的  列数*数组行的容量+待求数组的行值

31.假设一棵完全二叉树含有456个结点,则度为0、1、2的结点个数分别为( )

  • 228,1,227
完全二叉树的性质:
n个节点的完全二叉树,当n为奇数,每一个分支节点都有左右儿子,也就没有度为1的点。
当n为偶数,编号最大的那个分支节点只有左儿子,其他分支节点左右儿子都有,也就是会有一个度为1的点。
另外,非空二叉树的叶子节点比度为2的节点数量多1,即n0 = n1 + 1 。所以选B

32.关键路径是AOE网中的______

  • 从源点到汇点的最长路径
在AOE网中,有些活动是可以并行进行的。从源点(有且仅有一个)到汇点(有且仅有一个)的有向路径可能有多条,并且这些路径的带权长度
可能不同。完成不同路径上的活动所需时间虽然不同,但是只有所有路径上的所有活动都完成了,才算是工程结束。
因此,从源点到汇点的所有路径中,具有最大路径长度的路径称为关键路径。并把关键路径上的活动称为关键活动。

完成整个工程所需的最短时间就是关键路径的长度,也就是关键路径上的活动开销总和

33.在对问题的解空间树进行搜索的方法中,一个结点有多次机会成为活结点的是:()

  • 回溯法
分支限界法:
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。
此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
回溯法:
不用多说了吧,一般先有一个bool型数组,标记每个记录是否被访问,在结束时,有一个恢复现场,即bool=false,代表这次访问结束,以后的dfs还可以继续访问这个结点。

34.有一个用数组C[1..m]表示的环形队列,m为数组的长度。假设f为队头元素在数组中的位置,r为队尾元素的后一位置(按顺时针方向)。若队列非空,则计算队列中元素个数的公式应为

  • (m+r-f)mod m
分情况讨论:
1. 若f<r<=m, 则有r-f <m,即队尾没有超出边界,则为r-f
2. 若r<f<=m, r-f < 0, 即队尾超出边界m,那么应为m+r -f
综合两种情况,得到答案 (m+r-f) mod m

35.下面关于m阶B树说法正确的是()

①每个结点至少有两棵非空子树
②树中每个结点至多有m-1个关键字
③所有叶子在同一层上
④当插入一个数据项引起B树结点分裂后,树长高一层
  • ②③

35

36.需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是

  • 静态链表

36

37.下列关于线性表,二叉平衡树,哈希表存储数据的优劣描述错误的是 D

  • 哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);
  • 线性表实现相对比较简单
  • 平衡二叉树的各项操作的时间复杂度为O(logn)
  • 平衡二叉树的插入节点比较快
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。
在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的,所以可能需要通过一次或多次树旋转来重新平衡这个树

38.希望用最快的速度从一个无序数组中挑选出其中前十个最大的元素,在以下的排序方法中()

  • 堆排序
用堆排序最好,因为堆排序不需要等整个排序结束就可挑出前50个最大元素,而快速排序和基数排序都需等待整个排序结束才能知道前50个最大元素。

39.设有一个10阶对称矩阵A[10][10],采用压缩存储方式按行将矩阵中的下三角部分的元素存入一维数组B[ ]中,A[0][0]存入B[0]中,则A[8][6]在B[ ]的( )位置

  • 42

42

40.二叉查找树的查找效率与二叉树的树型有关,在()时其查找效率最低

  • 是单枝树
二叉查询树变成一条链表效率最差。所以有AVL平衡树 限制节点深度差不超过1,避免产生链表一般的树。

43.消除递归不一定需要使用栈,此说法(对)

不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法:对于尾递归或单向递归,可以用循环结构算法代替;
另外一个才是栈的方法。

44.由3 个“1”和 5 个“0”组成的 8 位二进制补码,能表示的最小整数()

  • -125
既然求最小整数,那肯定先想到负数,则最高位(符号位)一定为1,原码中肯定是1所在的位数越高,值越小,而补码是由原码取反加1得到的,则在补码中1所在的位数一定要越低,即补码为1000 0011;由补码求得原码:1111 1101=-(64+32+16+8+4+1)=-125;

45.图示是一个网络流从s到t的某时刻快照。此时t处一共接收到10+13+16=39单位流量。每条横线上的数字表示当前流量和管道的容量。那么,该网络最大的流量是多少

45

  • 41
答案为41.

技巧:  按层计算,瞻前顾后

首先计算每一层向终点方向的最大输出能力,不包括回流的量
然后计算总体的最大流量,为各个层中流量最小的一层的流量

本题中分为三层:
第一层为s。                        朝终点最大输出量为11+22+10 = 43
第二层为节点1、2、3。      朝终点最大输出量为10+17+14 = 41(10是因为节点4最多接受10,出度为10,14是因为节点3的入度为14,所以是14而不是16)
第三层为节点4、5、6。      朝终点最大输出量为10+16+16 = 42
所以综合考虑总体最大的流量只能41.

46.在一棵具有15个关键字的4阶B树中,含关键字的结点数最多是 ()

  • 15
B树的基本知识
 B- 是一种多路搜索树(并不是二叉的):

       1.   定义任意非叶子结点最多只有   M   个儿子;且   M>2   ;

       2.   根结点的儿子数为   [2, M]   ;

       3.   除根结点以外的非叶子结点的儿子数为   [M/2, M]   ;

       4.   每个结点存放至少   M/2-1   (取上整)和至多   M-1   个关键字;(至少   2   个关键字)

       5.   非叶子结点的关键字个数   =   指向儿子的指针个数   -1   ;

       6.   非叶子结点的关键字:   K[1], K[2], …, K[M-1]   ;且   K[i] < K[i+1]   ;

       7.   非叶子结点的指针:   P[1], P[2], …, P[M]   ;其中   P[1]   指向关键字小于   K[1]   的子树,   P[M]   指向关键字大于   K[M-1]   的子树,其它   P[i]   指向关键字属于   (K[i-1], K[i])   的子树;

       8.   所有叶子结点位于同一层;

47.一棵二叉树进行层次遍历时,应借助于一个栈()

47

48.下列关于图的叙述中,正确的是

Ⅰ .回路是简单路径

Ⅱ .存储稀疏图,用邻接矩阵比邻接表更省空间

Ⅲ .若有向图中存在拓扑序列,则该图不存在回路
第一个顶点和最后一个顶点相同的路径称为回路;序列中顶点不重复出现的路径称为简单路径;回路显然不是简单路径,故 Ⅰ 错误;稀疏图是边比较少的情况,此时用邻接矩阵的空间复杂度为 O(n2) ,必将浪费大量的空间,而邻接表的空间复杂度为 O(n+e) ,应该选用邻接表,故 Ⅱ 错误。存在回路的有向图不存在拓扑序列,若拓扑排序输出结束后所余下的顶点都有前驱,则说明只得到了部分顶点的拓扑有序序列,图中存在回路,故 Ⅲ 正确。

49.广义表A=((x, (a ,b)), (x,(a,b),y)), 则运算Head(Head(Tail(A)))结果为( A )

  • X

49


0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注