数据结构选择题判断题（PTA）_可以用带表头附加结点的链表表示线性表,也可以用不带头结点的链表表示线性表,前者

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的（数据元素）（百度到的答案是数据元素）以及他们之间的关系和运算筹的学科。
2. 不带表头附加结点的单链表为空的判断条件是头指针head满足条件（head == NULL）。
3. 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是（使空表和非空表的处理趋于统一）。
4. 计算机算法必须具备输入、输出、有穷性、确定性、可行性（有效性）等五个特性。

5. 下面代码段的时间复杂度是（n的1/2次方）。(2分)

           x=n; //n>1
          y=0;
          while( x≥(y+1)*(y+1) )
           y++;
   1
   2
   3
   4

6. 下列代码

 if ( A > B ) {
          for ( i=0; i<N*N/100; i++ )
               for ( j=N*N; j>i; j-- )
                      A += B;
        }
       else {
            for ( i=0; i<N*2; i++ )
                  for ( j=N*3; j>i; j-- )
                       A += B;
     }
1
2
3
4
5
6
7
8
9
10

 的时间复杂度是：（O(N4)）(2分)
1

7.对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N).
8.（neuDs）线性表的顺序存储结构是一种（顺序存储的存储结构）。
9.(neuDS)要将一个顺序表{a​0​ ,a​1​​ ,……,a​n−1​​ }中第i个数据元素a
​i​​ (0≤i≤n-1)删除，需要移动（n-i-1 ）个数据元素。
解析：从i+1到n-1,一共是(n-1-(i+1))+1即（n-i-1）个元素
10.若长度为n的线性表采用顺序结构，在第i个数据元素之前插入一个元素，需要它依次向后移动（n-i+1）个元素。
11.将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(max(m,n)).
12.将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为(O(m)).
13.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？
仅有尾指针的单循环链表
分析：尾指针指向最后一个节点，循环链表最后一个节点的next是头节点。
14.将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构(带尾指针的单循环链表)
分析：带尾指针，可以快速找到最后一个节点，循环链表，尾节点的next就是头结点。
15.在最后一个节点插入和删除最后一个节点，（带头结点的双向循环链表）（或者双向链表）
16.在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行（删除单链表的最后一个元素）操作与链表的长度有关。
17.如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用（只有表头指针没有表尾指针的循环双链表）。
18.如果对线性表的运算只有2种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（只有表尾指针没有表头指针的循环单链表）。
19.若一个栈的入栈序列为1、2、3、…、N，其输出序列为p1​​ 、p​2​、p​3​​ 、…、p​N​​ 。若p​1​​ =N，则p​i​​ 为：(n-i+1).
20.所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。（F）
21.在用数组表示的循环队列中，front值一定小于等于rear值。 (F）
分析：rear在对max取余之后会从零开始，但这时front并不是零。所以会出现front>rear,（ >,=,<三种情况都有可能出现）。
22.如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为(m).
分析：数组空间为m，最后一个位置也放元素.
23.如果循环队列用大小为m的数组表示，队头位置为front、队列元素个数为size，那么队尾元素位置rear为：((front+size-1)%m).
分析：队尾元素位置不同于队尾下标，队尾下标是队尾元素位置的下一个位置。而队尾下标：size = rear - front。
24.已知一棵二叉树的先序遍历结果是ABC,　则CAB不可能是中序遍历结果。(T)
分析：根据中序遍历的顺序，C一定是左子树，所以先序遍历C应该在A后面
25.按照二叉树的定义，具有3个结点的二叉树有几种（5）
分析：
有且仅有一个节点
其余节点分为两个互不相交的集合，且t1,t2也都是二叉树
t1,t2是有序的
26.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是：(1,2) (3分)
1.父子关系； 2. 兄弟关系； 3. u的父结点与v的父结点是兄弟关系
分析：节点u是节点v的父节点的父节点，对应着可以有4个二叉树的略图，逐个判断。
27.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。（T）
分析：分支节点是度不为0的点（他指向别人的点）,带权路径长度是所有分支节点之和，即所有节点权值之和减去叶子节点的权值之和。
28.当一棵具有n 个叶子结点的二叉树的WPL 值为最小时，称其树为哈夫曼树，其二叉树的形状是唯一的.
分析：哈夫曼树的带权路径长度最小，但是 不是最小的就是带权路径长度，哈夫曼树的形状也不是唯一的。
29.若无向图G =（V，E）中含10个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是(37).
分析：10个顶点，先选9个构成完全无向图，再加一条边将完全无向图和最后一个点连起来。9*8/2+1=37.
30.强连通分量：有向图中任意两个点i,j之间都有一条路径相连（这两个顶点强连通），有这样的点组成的图是强连通图，有向图的极大强连通子图称为强连通分量。（一个点就是一个强连通分量）
具有N（N>0）个顶点的无向图至多有多少个连通分量？（N个，每个顶点都是一个联通分量）
31.在AOE网中，什么是关键路径？ （从第一个事件到最后一个事件的最长路径）（AOE网，点是状态，边是活动）