背景：期末数据结构复习题
绪论和线性表判断题The Fibonacci number sequence {F N } is defined as: F 0 =0, F 1 =1, F N =F N−1 +F N−2 , N=2, 3, .... The time complexity of the function which calculates F N recursively is Θ(N!).F根据递推我们可以直到时间复杂度为O(N);
(logn)^2 is O(n).
T
之前对渐进时间复杂度理解有误
An algorithm may or may not require input, but each algorithm is expected to produce at least one result as the output.T概念题
NlogN^2 and NlogN^3 have the same speed of growthT只有前面的系数常数不一样，显然正确
N2logN和NlogN2具有相同的增长速度。F显然不对，一个系数是平方，一个是线性系数
2^N 和N^N 具有相同的增长速度F太简单的咱就不说了哈算法分析的两个主要方面是时间复杂度和空间复杂度的分析T
对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)T
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。T
对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。F时间复杂度反了，删除第一个元素线性表会把所有的元素向前移动
线性表L如果需要频繁地进行不同下标元素的插入、删除操作，此时选择顺序存储结构更好。F链表更好
队列的特性队列是后进先出的线性表。F队列先进先出
具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。F时间复杂度反了
将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)。F线性表才是O（logN）
若用链表来表示一个线性表，则表中元素的地址一定是连续的。F
链表 - 存储结构链表中逻辑上相邻的元素，其物理位置也一定相邻。F
链表 - 存储结构链表是一种随机存取的存储结构。F线性表才是随机存取
单选题在数据结构中，从逻辑上可以把数据结构分成（ ）。(1分)A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构
与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。(1分)A.存储结构B.存储实现C.逻辑结构D.运算实现数据的逻辑结构跟其相对位置无关
通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。(1分)A.数据在同一范围内取值B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等
以下数据结构中，（ ）是非线性数据结构。(1分)A.树B.字符串C.队列D.栈
求整数n(n>=0)的阶乘的算法如下，其时间复杂度为（ ）。
long fact(long n){if (n0)int func ( int n ){ int i = 1, sum = 0; while ( sum < n ) { sum += i; i *= 2; } return i;}A.O(logn)B.O(n)C.O(nlogn)D.O(2^n)因为有个i*=2
Suppose A is an array of length N with some random numbers. What is the time complexity of the following program in the worst case?
void function( int A[], int N ) { int i, j = 0, cnt = 0; for (i = 0; i < N; ++i) { for (; j < N && A[j] B ) { for ( i=0; ii; j-- ) A += B;}else { for ( i=0; ii; j-- ) A += B;}时间复杂度是A.O(N)B.O(N^2 )C.O(N^3 )D.O(N^4 )如果都执行第一个循环是N^2 + N^2-1 + ....N^2-N = O(N^3);第二个是2N,那更不用说了；
多选题以下说法正确的是。(2分)A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B.顺序存储的线性表可以随机存取C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D.线性表的链式存储结构优于顺序存储结构
串，数组和广义表判断题假设模式串是abababaab，则KMP模式匹配算法中的next[j] = 0 1 1 2 3 4 5 6 2T想到这道题，我是真的无语我发现书上写的和在算法竞赛里的next数组定义是不一样的而且书上的相当复杂，关键是PTA就是用的书上的内容书上下标如果从0开始，那么j=1时，就是-1，后面就是相等前后缀的大小，关键是next[j]指的是j前面的最大相等前后缀，也就是0~j-1这样的话就是-1 0 0 1 2 3 4 5 1如果下标从1开始，那么每一个next都要向后移一位算法竞赛当中，next[j]指的就是从1~j的最大相等前后缀其实两者都能解决问题，但是书上定义的比较复杂
单选题设主串 T = abaabaabcabaabc，模式串 S = abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：A.9B.10C.12D.15ia b a a b a a b c a b a a b ca b a a b cj到此为止是6次，然后j回溯ia b a a b a a b c a b a a b ca b a a b cj之后再比较4次总共10次
设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）(2分)A.1和1B.1和3C.1和2D.2和3
由于在广义表方面个人掌握的不是特别好，所以就多说一些广义表，又称列表，也是一种线性存储结构。同数组类似，广义表中既可以存储不可再分的元素，也可以存储广义表，记作：LS = (a1,a2,…,an)其中，LS 代表广义表的名称，an 表示广义表存储的数据。广义表中每个 ai 既可以代表单个元素，也可以代表另一个广义表。原子和子表通常，广义表中存储的单个元素称为 "原子"，而存储的广义表称为 "子表"。例如创建一个广义表 LS = {1,{1,2,3}}，我们可以这样解释此广义表的构成：广义表 LS 存储了一个原子 1 和子表 {1,2,3}。以下是广义表存储数据的一些常用形式：A = ()：A 表示一个广义表，只不过表是空的。B = (e)：广义表 B 中只有一个原子 e。C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。注意，A = () 和 A = (()) 是不一样的。前者是空表，而后者是包含一个子表的广义表，只不过这个子表是空表。广义表的表头和表尾当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。强调一下，除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。例如在广义表中 LS={1,{1,2,3},5} 中，表头为原子 1，表尾为子表 {1,2,3} 和原子 5 构成的广义表，即 {{1,2,3},5}。再比如，在广义表 LS = {1} 中，表头为原子 1 ，但由于广义表中无表尾元素，因此该表的表尾是一个空表，用 {} 表示。长度广义表的长度就是看第一层所含的元素个数深度广义表的深度是max(每个元素深度) + 1A=（）：A是一个空表，长度为0，深度为1B=(e)：B只有一个原子e，B的长度为1，深度为1C=(a,(b,c,d))：C的长度为2，深度为2D=(A,B,C)=((),(e),(a,(b,c,d)))：D的长度为3，深度为3E=(a,E)：E是一个递归的表，长度为2，深度无限。
广义表((a,b,c,d))的表头、表尾是（ ）。(2分)A.表头：a 表尾：(b,c,d)B.表头： ( ) 表尾：(a,b,c,d)C.表头：(a,b,c,d) 表尾：( )D.表头：(b,c,d) 表尾：(a)
对n阶对称矩阵压缩存储时，需要表长为（）的顺序表。(2分)A.n/2B.n×n/2C.n(n+1)/2D.n(n-1)/2由于矩阵是对称的，所以只需要储存1+2+3+....+n = n(n+1)/2
有一个n×n的对称矩阵A，将其下三角部分按行存放在一维数组B中，而A[0][0]存放于B[0]中，则第i行的对角元素A[i][i]存放于B中的（）处。(2分)A.(i+3)i/2B.(i+1)i/2C.(2n-i+1)i/2D.(2n-i-1)i/2[i][i]前面有i行，一共有1+2+....+i个元素，然后第i行第i个总共是(1+i)i/2 + i + 1,由于下标从B[0]开始，刚开始算的时候是算了B[0]的所以还要-1就是(i+3)i/2
二维数组 A 的每个元素是由 10 个字符组成的串，其行下标 i=0,1,…,8，列下标 j=1,2,…,10。若 A 按行序优先存储，元素 A[8,5] 的起始地址与当 A 按列序优先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]行序优先就是横着存，列序优先就是竖着存，行序优先是[8,5]那么这是810+5个元素；对应的列序优先存储是99+4也就是A[3,10]
对于 C 语言的二维数组 int A[m][n]，每个元素占 2 个字节，数组中元素 a[i,j]的存储位置可由( )式确定。(2分)A.Loc[i, j]=A[m, n]+(n×i + j )×2B.Loc[i, j]=Loc[0, 0]+[ (m+n)×i+j ]×2C.Loc[i, j]=Loc[0, 0] + (n×i+j)×2D.Loc[i, j]= (n×i+j)×2
数组 A[0..5, 0..6] 的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5, 5] 的地址是( )。(2分)A.1175B.1180C.1205D.1210（5*6+5 ） *5 = 175这里指的是存储的起始地址
稀疏矩阵一般的压缩存储方式有两种，即（）。(2)A. 二维数组和三维数组B. 三元组和散列C. 三元组和十字链表D. 替换为错散列和十字链表误项
设二维数组A[1… m,1… n]按行存储在数组B中，则二维数组元素A[i,j]在一维数组B[1…m*n]中的下标为 ( )。(分)A.n(i-1)+j**B.n(i-1)+j-1**C.i(j-1)D.jm+i-1这个题也是第二个我感到有点问题的题，按照道理来讲应该选A的，但是答案选B比如A[1][1]理论上应该在B[1]的，但是按照公式计算就是B[0]了评论区如果有知道的小伙伴欢迎指出
带行表的三元组表是稀疏矩阵的一种( )(2)A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构
广义表与稀疏矩阵都是线性表的扩展，它们的共同点为（）。(2分)A.都可以用