在线练习1

1、单选题：
‍在数据结构中，与所使用的计算机无关的是数据的（    ）结构。‍
选项：
A: 逻辑
B: 存储
C: 逻辑和存储
D: 物理
答案: 【 逻辑】

2、单选题：
‎数据结构在计算机内存中的表示是指（    ）。‏
选项：
A: 数据的存储结构
B: 数据结构
C: 数据的逻辑结构
D: 数据元素之间的关系
答案: 【 数据的存储结构】

3、单选题：
‍在数据结构中，从逻辑上可以将之分为（   ）结构。‎
选项：
A: 动态和静态结构
B: 紧凑和非紧凑结构
C: 线性和非线性结构
D: 内部和非内部结构
答案: 【 线性和非线性结构】

4、单选题：
​在数据结构中，从存储上可以将之分为（    ）结构。‍
选项：
A: 动态和静态结构
B: 紧凑和非紧凑结构
C: 顺序和非顺序结构
D: 线性和非线性结构
答案: 【 顺序和非顺序结构】

5、单选题：
‍算法的时间复杂度取决于（    ）。‍
选项：
A: 问题的规模
B: 待处理数据的初态
C: 问题的规模以及待处理数据的初态
D: 没有正确答案
答案: 【 问题的规模以及待处理数据的初态】

6、单选题：
‏某算法的时间复杂度是O(n^2)，表明该算法的（   ）。‍
选项：
A: 执行时间与n^2成正比
B: 问题规模是n^2
C: 执行时间等于n^2
D: 问题规模与n^2成正比
答案: 【 执行时间与n^2成正比】

7、单选题：
‌衡量算法效率优劣的不包括（  ）。‌
选项：
A: 正确性和可读性
B: 健壮性/鲁棒性
C: 高效率与低存储
D: 现实性
答案: 【 现实性】

8、单选题：
​算法指（  ）。​
选项：
A: 计算方法
B: 排序方法
C: 解决问题的步骤序列
D: 调度方法
答案: 【 解决问题的步骤序列】

9、单选题：
下面的程序段时间复杂度为（   ）。​ for(i=1;i<n;i++)​    for(j=1;j<n;j++)   ​        x=x+1;​​​
选项：
A: O(2n)
B: O(n)
C: O(n^2)
D: O(log2n)
答案: 【 O(n^2)】

10、单选题：
‏算法效率分析的两个主要方面是（    ）。‎
选项：
A: 空间复杂度和时间复杂度
B: 正确性和简明性
C: 可读性和文档性
D: 数据复杂性和程序复杂性
答案: 【 空间复杂度和时间复杂度】

11、单选题：
‎有如下递归函数fact(n)，分析其时间复杂度为（    ）。‎‎int fact(int n)‎‎{‎‎   if(n<=1)  return 1;‎‎   else return(n*fact(n-1));‎‎}‎
选项：
A: O(n)
B: O(1)
C: O(n^2)
D: O(logn)
答案: 【 O(n)】

12、单选题：
‍下面程序段的时间复杂度为（    ）。​‍for(i=0;i<n;i++)​‍  for(j=0;j<m;j++)​‍    A[i][j]=0;​
选项：
A: O(n*m)
B: O(n^2)
C: O(m^2)
D: O(1)
答案: 【 O(n*m)】

13、单选题：
‏下面程序段的时间复杂度为（     ）。‏‏void sum(int n) //n为正整数‏‏{‏‏  int p=1,sum=0,i;‏‏  for(i=1;i<=n;i++)‏‏  {‏‏    p*=i;‏‏    sum+=p;‏‏  }‏‏}‏
选项：
A: O()
B: O(n)
C: O(1)
D: O(n^2)
答案: 【 O(n)】

14、判断题：
‌顺序存储方式的优点是存储密度大，且插入、删除运算效率高。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
‏算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
‏链式存储的优点是可以随机存储。​
选项：
A: 正确
B: 错误
答案: 【 错误】

17、判断题：

​在相同的数据规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O()的算法。

‌选项：
A: 正确
B: 错误
答案: 【 正确】

18、判断题：
‍数据的逻辑结构分为线性结构、树型结构、图状结构和集合。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

19、判断题：
‎数据的存储结构表示的是数据元素之间的逻辑关系。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

测验

1、判断题：
‎一个算法包含的循环嵌套的层数越多，该算法的时间复杂度越高。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

测验1

1、单选题：
‌数据的逻辑结构包括？‏
选项：
A: 线性结构和非线性结构
B: 顺序结构和非顺序结构
C: 静态结构和非静态结构
D: 动态结构和非动态结构
答案: 【 线性结构和非线性结构】

在线练习2

1、单选题：
‍下述哪一条是顺序存储结构的优点（ ）。‎
选项：
A: 存储密度大 
B: 插入运算方便 
C: 删除运算方便 
D: 可方便地用于各种逻辑结构的存储表示
答案: 【 存储密度大 】

2、单选题：
‎下面关于线性表叙述中错误的是（  ）。‎
选项：
A: 线性表采用顺序存储，必须占用一片连续的存储单元。
B: 线性表采用顺序存储，便于进行插入和删除操作。
C: 线性表采用链式存储，不必占用一片连续的存储单元。
D: 线性表采用链式存储，便于插入和删除操作。    
答案: 【 线性表采用顺序存储，便于进行插入和删除操作。】

3、单选题：
‌若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。‏
选项：
A: 顺序表 
B: 双链表
C: 带头结点的双循环链表
D: 单循环链表
答案: 【 顺序表 】

4、单选题：
​设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（ ）。​
选项：
A: Base+(i+1)×m
B: Base+i×m
C: Base+(i-1)×m
D: Base-i×m 
答案: 【 Base+(i-1)×m】

5、单选题：
‎某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。‌
选项：
A: 单链表  
B: 仅有头指针的单循环链表
C: 双链表        
D: 仅有尾指针的单循环链表    
答案: 【 仅有尾指针的单循环链表    】

6、单选题：
‎设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(  )最节省时间。​
选项：
A: 单链表 
B: 带尾指针的单循环链表
C: 单循环链表    
D: 带头结点的双循环链表    
答案: 【 带头结点的双循环链表    】

7、单选题：
‌链表不具有的特点是（ ）。‎
选项：
A: 插入、删除不需要移动元素
B: 可随机访问任意元素     
C: 不必事先估计存储空间 
D: 所需空间与线性表长度成正比  
答案: 【 可随机访问任意元素     】

8、单选题：
​线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。​
选项：
A: 必须是连续的 
B: 部分地址必须是连续的
C: 一定是不连续的 
D: 连续或不连续都可以
答案: 【 连续或不连续都可以】

9、单选题：
‏完成在双循环链表结点p之后插入s的操作是（  ）。​
选项：
A: p->next=s ; s->prior=p; p->next->prior=s ; s->next=p->next;   
B: p->next->prior=s; p->next=s; s->prior=p; s->next=p->next; 
C: s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ;
D: s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;
答案: 【 s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;】

10、单选题：
‏若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 （）。​
选项：
A: O(0)  
B: O(1)  
C: O(n)  
D: O() 
答案: 【 O(n)  】

11、单选题：
‏对于顺序表，访问结点和删除结点的时间复杂度分别为（ ）。‌
选项：
A: O(n)  O(n)  
B: O(n)  O(1)     
C: O(1)  O(n)     
D: O(1)  O(1)
答案: 【 O(1)  O(n)     】

12、单选题：
‍在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）。​
选项：
A: p->next=s;s->next=p->next; 
B: s->next=p->next;p->next=s;
C: p->next=s;p->next=s->next;  
D: p->next=s->next;p->next=s;
答案: 【 s->next=p->next;p->next=s;】

13、单选题：
‎对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）。    ‍
选项：
A: head==NULL 
B: head→next==head   
C: head→next==NULL 
D: head!=NULL
答案: 【 head→next==NULL 】

14、单选题：
‏将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数是（ ）。‎
选项：
A: n 
B: 2n-1      
C: 2n     
D: n-1
答案: 【 n 】

15、单选题：
在双向链表中，在p所指向的结点前插入一个q所指向的结点，相应的操作语句是（ ）。‏注：双向链表的结点结构为(prior，data，next)。‏
选项：
A: p->prior=q;q->next=p;p->prior->next=q;q->prior=q;
B: p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;
C: q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;
D: q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;
答案: 【 q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;】

16、单选题：
‏线性表（a1,a2,…,an）以链式方式存储时，访问第i个元素的时间复杂度为（    ）​
选项：
A: O（i）
B: O（1）
C: O（n）
D: O（i-1）
答案: 【 O（n）】

17、单选题：
​头指针为H的循环单链表中尾结点P的特点是（    ）。‏
选项：
A: P->next==H        
B: P->next==H->next     
C: P==H     
D: P==H->next
答案: 【 P->next==H        】

18、单选题：
两个指针P和Q，分别指向单链表的两个结点，P是Q的前驱结点的条件是（    ）。‏
选项：
A: P->next==Q->next
B: P->next==Q
C: Q->next==P   
D: P==Q
答案: 【 P->next==Q】

19、单选题：
‍在单链表中，增加头结点的目的是（    ）。‍
选项：
A: 使单链表至少有一个结点
B: 标志表中首结点的位置
C: 链表判空、插入第一个结点以及删除第一个结点等运算方便
D: 说明该单链表是线性表的链式存储结构
答案: 【 链表判空、插入第一个结点以及删除第一个结点等运算方便】

20、单选题：
下面关于线性表的叙述中，错误的是（     ）。‏
选项：
A: 顺序表必须占一片地址连续的存储单元
B: 顺序表可以随机存取任一元素
C: 链表不必占用一片地址连续的存储单元    
D: 链表可以随机存取任一元素
答案: 【 链表可以随机存取任一元素】

21、单选题：
设p为指向长度为n的单循环链表上某结点的指针，则找到p的直接前驱（     ）。‎
选项：
A: 找不到 
B: 时间复杂度为O（1）
C: 时间复杂度为O（n）
D: 不一定找到
答案: 【 时间复杂度为O（n）】

22、单选题：
以下关于线性表的论述，不正确的是（    ）。‎
选项：
A: 线性表中的元素可以是数字、字符、记录等不同类型。
B: 顺序表中包含的元素个数是有限的。
C: 线性表中的每个结点都有且仅有一个直接前趋和一个直接后继。
D: 存在这样的线性表，即表中没有任何结点。
答案: 【 线性表中的每个结点都有且仅有一个直接前趋和一个直接后继。】

23、单选题：
在（    ）的运算中，使用顺序表比链表好。‍
选项：
A: 插入        
B: 根据序号查找      
C:  删除         
D: 根据元素查找
答案: 【 根据序号查找      】

24、判断题：
‎双循环链表中，任一结点的后继指针均指向其逻辑后继。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

25、判断题：
‎线性表的特点是每个元素都有一个前驱和一个后继。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

26、判断题：
‎若长度为n的线性表采用顺序存储结构，找到其中第i个元素的时间复杂度为O(n)。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

27、判断题：
‌已知带头结点的双向循环链表L，判断其为空表的条件是L->next==L && L->prior==L。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

28、判断题：
顺序表的插入、删除运算更方便。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

29、判断题：
‏链表的性能优于顺序表。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

30、判断题：
‍顺序表适宜于顺序存取，而链表适宜于随机存取。​
选项：
A: 正确
B: 错误
答案: 【 错误】

31、判断题：
‍顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。​
选项：
A: 正确
B: 错误
答案: 【 错误】

32、判断题：
插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

33、判断题：
‏线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

测验

1、判断题：
‎在双向链表中查找某一结点的前驱或者后继，都非常方便。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

单元测试1

1、单选题：
‍栈和队列的共同点是（ ）。​
选项：
A: 都是先进先出
B: 都是先进后出
C: 只允许在端点处插入和删除元素
D: 没有共同点
答案: 【 只允许在端点处插入和删除元素】

2、单选题：
栈和队都是（ ）。‌
选项：
A: 顺序存储的线性结构
B: 链式存储的非线性结构
C: 限制存取点的线性结构   
D: 限制存取点的非线性结构
答案: 【 限制存取点的线性结构   】

3、单选题：
‎依照六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个出栈序列不可能（ ）。‎
选项：
A: 543612
B: 453216
C: 346521  
D: 234156 
答案: 【 346521  】

4、单选题：
‍设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后随即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是( )。​
选项：
A: 6
B: 4
C: 3
D: 2
答案: 【 3】

5、单选题：
‎设计一个判别表达式中括号是否匹配出现的算法，采用（ ）的数据结构最佳。‎
选项：
A: 顺序表
B: 队列
C: 单链表
D: 栈
答案: 【 栈】

6、单选题：
表达式a*(b+c)-d的后缀表达式是(  ）。‏
选项：
A: bc+a*d-
B: abc+*d-  
C: ab*c+d-   
D: dabc+*-
答案: 【 abc+*d-  】

7、单选题：
‍函数递归调用时，处理参数及返回地址需要用一种（   ）的数据结构。‎
选项：
A: 队列
B: 多维数组         
C: 栈         
D: 线性表
答案: 【 栈         】

8、单选题：
‌若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为3和1，当从队列中删除一个元素再加入两个元素后，rear和front的值为(   )。‍
选项：
A: 0和5
B: 2和4                 
C: 5和2
D: 5和1  
答案: 【 5和2】

9、单选题：
最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件是（ ）。‌
选项：
A: (rear+1)%n==front         
B: rear==front                                                        
C: rear+1==front       
D: (rear-l)%n==front
答案: 【 rear==front                                                        】

10、单选题：
假设以数组A[m]存放循环队列的元素,其头、尾指针分别为front和rear，front指示实际的队头元素，rear指向实际队尾元素的下一个元素位置，则当前队列中的元素个数为（   ）。‍
选项：
A: (rear-front+m)%m
B: rear-front+1
C: (front-rear+m)%m               
D: (rear-front+1)%m
答案: 【 (rear-front+m)%m】

11、单选题：
用带头结点的表长大于1的单链表表示队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时(    )。​
选项：
A: 仅修改队头指针
B: 仅修改队尾指针
C: 队头、队尾指针都要修改
D: 队头,队尾指针都可能要修改
答案: 【 仅修改队头指针】

12、单选题：
下列说法正确的是（  ）。​(1)只有使用了局部变量的递归函数在转换成非递归函数时才必须使用栈。​(2)队列是插入与删除操作在表的两端进行的线性表，具有先进后出的特点。​(3)队列是一端进行删除另外一端进行插入的线性表。​(4)循环队列也存在空间溢出问题。​
选项：
A: (1)(2)(4)
B: (1)(2)(3)      
C: (3)(4)     
D: (1)(2)
答案: 【 (3)(4)     】

13、单选题：
以下程序的输出结果为（  ）。‍          int f( int x)         {  ‍              return (x>0)?x*f(x-1):2;‍          }          void main()‍          { ‍             int i  ;             i=f(f(1));‍             printf("%d",i);‍          }‍