数据结构算法题汇总_对于大文件的排序要研究在外设上的排序技术

1. 在计算机中，算法是指什么？
答案：解题方案的准确而完整的描述。

2. ，算法的四个基本特征是？
说明：可行性、确定性、有穷性和输入输出。

3. 算法一般都可以用哪几种控制结构组合而成？
答案：顺序、选择、循环。

4. 算法的时间复杂度是指？
答案：算法执行过程中所需要的基本运算次数。

5. 算法的空间复杂度是指？
答案：执行过程中所需要的存储空间。

6. 算法分析的目的是？
答案：分析算法的效率以求改进。

7. 下列叙述正确的是（C）
A．算法的执行效率与数据的存储结构无关
B．算法的空间复杂度是指算法程序中指令（或语句）的条数
C．算法的有穷性是指算法必须能在执行有限个步骤之后终止
D．算法的时间复杂度是指执行算法程序所需要的时间

8. 数据结构作为计算机的一门学科，主要研究什么？
答案：主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构。

9. 数据结构中与所使用的计算机无关的是数据的（C）
A．存储结构 B．物理结构
C．逻辑结构 D．物理和存储结构

10. 下列叙述中，错误的是（B）
A．数据的存储结构与数据处理的效率密切相关
B．数据的存储结构与数据处理的效率无关
C．数据的存储结构在计算机中所占的空间不一定是连续的
D．一种数据的逻辑结构可以有多种存储结构

11. 数据的存储结构是指什么？
答案：数据的逻辑结构在计算机中的表示。

12. 数据的逻辑结构是指？
答案：反映数据元素之间逻辑关系的数据结构。

13. 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为？
答案：线性结构和非线性结构

14. 下列数据结构具有记忆功能的是（C）
A．队列
B．循环队列
C．栈
D．顺序表

16. 递归算法一般需要利用什么实现？
答案：队列

20. 下列叙述中，正确的是（D）
A．线性链表中的各元素在存储空间中的位置必须是连续的
B．线性链表中的表头元素一定存储在其他元素的前面
C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的

21. 下列叙述中正确的是（A）
A．线性表是线性结构
B．栈与队列是非线性结构    是线性结构）
C．线性链表是非线性结构   
D．二叉树是线性结构           非线性结构，可能有多个后继

22. 线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D）
A．每个元素都有一个直接前件和直接后件
B．线性表中至少要有一个元素
C．表中诸元素的排列顺序必须是由小到大或由大到小
D．除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前驱和直接后继

23. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址怎么样？
答案：连续不连续都可以。

24. 链表不具有的特点是（B）
A．不必事先估计存储空间
B．可随机访问任一元素
C．插入删除不需要移动元素
D．所需空间与线性表长度成正比

25. 在（D）中，只要指出表中任何一个结点的位置，就可以从它出发依次访问到表中其他所有结点。
A．线性单链表
B．双向链表
C．线性链表
D．循环链表

26. 以下数据结构属于非线性数据结构的是（C）   //数据结构只有俩种，非信息结构和线性结构
A．队列
B．线性表
C．二叉树
D．栈

27. 树是结点的集合，它的根结点数目是多少？
答案：有且只有1

28. 在一棵二叉树上第8层的结点数最多是？         2的（n-1）次方
答案：128

29. 在深度为5的满二叉树中，叶子结点的个数为？
答案：16

30. 在深度为5的满二叉树中，共有多少个结点？ 1+2+4+8+16=31
答案：31

31. 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为？
答案：350
完全二叉树总结点数为N，若N为奇数，则叶子结点数为（N+1）/2；若N为偶数，则叶子结点数为N/2。

33. 若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是？
答案：gdbehfca

 

34. 串的长度是？
答案：串中所含字符的个数。

35. 设有两个串p和q，求q在p中首次出现位置的运算称做？
答案：模式匹配。

36. N个顶点的连通图中边的条数至少为？
答案：N-1

37. N个顶点的强连通图的边数至少有？
答案：N

38. 对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为？
答案：N                   n/1=n

39. 最简单的交换排序方法是？  
答案：冒泡排序    两个for  第一个范围为n-1  第二个为n-1-i  然后j和j+1比较  交换

40. 假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为？
答案：n(n-1)/2

41. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是？
答案：冒泡排序

42. 在最坏情况下，下列顺序方法中时间复杂度最小的是？
答案：堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆是具有以下性质的完全二叉树：

• 每个结点的值都大于或等于其左右孩子结点的值，称为大根堆；
• 或者每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。 

实现网址：https://blog.csdn.net/l577217/article/details/80516654 

 

43. 希尔排序法属于？
答案：插入类排序

44. 堆排序法属于？
答案：选择类排序

45. 排序方法中，要求内存量最大的是？
答案：归并排序

46. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采用？
答案：直接插入排序

（1）交换类排序法：

交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类排序方法。冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n–1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。快速排序法也是一种交换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。其关键是对线性表进行分割，以及对各分割出的子表再进行分割。

（2）插入类排序法：

插入类排序法主要有简单插入排序法和希尔排序法。简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。在这种排序方法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n–1)/2次比较。希尔排序法对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。

（3）选择类排序：

选择类排序主要有简单选择类排序法和堆排序法。简单选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的线性表，在最坏情况下需要比较n(n–1)/2次。堆排序法也属于选择类排序法。具有n个元素的序列（h1, h2, …, hn），当且仅当满足条件：  或  (i=1, 2, …, n/2）时称之为堆。可见，堆顶元素（即第一个元素）必为最大项。堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。

 

1.栈和队列的共同特点是（只允许在端点处插入和删除元素）

2.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（e2,e4,e3,e1）

13.树是结点的集合，它的根结点数目是（有且只有1）

15.具有3个结点的二叉树有（5种形态）

16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（13

17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba）

(凑合看吧，就这水平了)

 

18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（DGEBHFCA）

（这个就很完美）

20.数据库保护分为：安全性控制、 完整性控制 、并发性控制、数据的恢复。

1. 在计算机中，算法是指（解题方案的准确而完整的描述）

2算法一般应该具有的基本特征
算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。ps老师整理的是拥有足够的情报，我查的是输入和输出

18.当循环队列非空且队尾指针等于对头指针时，说明循环队列已满，不能进行入队运算。这种情况称为 上溢

19.当循环队列为空时，不能进行退队运算，这种情况称为 下溢 

20. 在一个容量为25的循环队列中，若头指针front=16，尾指针rear=9，则该循环队列中共有 18 个元素。注：当rear<front时，元素个数＝总容量－（front－rear）；
当rear>front时，元素个数＝rear－front。

1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环：
例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link
 
{
         int data;
         link* next;
};
bool IsLoop(link* head)
 
{
         link* p1=head, *p2 = head;
 
          if (head ==NULL || head->next ==NULL)
 
          {
                   return false;
          }
         do{
             p1= p1->next;
             p2 = p2->next->next;
         } while(p2 && p2->next && p1!=p2);         
          if(p1 == p2)
                    return true;
          else
                    return false;
}
 

2,链表反转 单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：

struct linka {
          int data;
          linka* next;
};
 
void reverse(linka*& head)
{
          if(head ==NULL)
               return;
          linka*pre, *cur, *ne;
          pre=head;
          cur=head->next;
          while(cur)
          {
               ne = cur->next;
               cur->next = pre;
               pre = cur;
               cur = ne;
          }
          head->next = NULL;
          head = pre;
}

还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：

linka* reverse(linka* p,linka*& head)
 
{
          if(p == NULL || p->next == NULL)
 
          {
               head=p;
               return p;
          }
          else
          {
               linka* tmp = reverse(p->next,head);
               tmp->next = p;
               return p;
          }
}

4.

abstract class Something {
   private abstract String doSomething ();
} 

该段代码有错吗？

答案: 错。abstract的methods不能以private修饰。abstract的methods就是让子类implement(实现)具体细节的，怎么可以用private把abstract method封锁起来呢? (同理，abstract method前不能加final)。

 

5.看看下面的代码段错在哪里？
 

public class Something {
   void doSomething () {
       private String s = "";
       int l = s.length();
   }
} 

答案: 错。局部变量前不能放置任何访问修饰符 (private，public，和protected)。final可以用来修饰局部变量
(final如同abstract和strictfp，都是非访问修饰符，strictfp https://baike.baidu.com/item/strictfp 只能修饰class和method而非variable)。

6. 下面该段代码是否有错，若是有错错在哪里？

abstract class Name {
   private String name;
   public abstract boolean isStupidName(String name) {}
} 

答案: 错。abstract method必须以分号结尾，且不带花括号。

 

 

-------------------------------单项选择题------------------------------

1.算法分析的目的是(    C  )

A.找出数据结构的合理性     B.研究算法中的输入/输出关系

C.分析算法的效率以求改进     D.分析算法的易读性

 

2.在需要经常查找结点的前驱与后继的场合中，使用(  B   )比较合适。

A.单链表           B.双链表

C.顺序表           D.循环链表

 

3.下面关于线性表的叙述中，错误的为(  D    )

A.顺序表使用一维数组实现的线性表

B.顺序表必须占用一片连续的存储单元

C.顺序表的空间利用率高于链表

D.在链表中，每个结点只有一个链域          // 一个指针域，一个数据域（循环，双向链表有俩个指针域）

 

4.带头结点的单链表head为空的判断条件是(   B   )

A. head=NIL                      B. head->next=NIL

C. head->next=head                D. head<>NIL

 

5.队列通常采用两种存储结构是(   A   )

A.顺序存储结构和链表存储结构         B.散列方式和索引方式

C.链表存储结构和数组                 D.线性存储结构和非线性存储结构

 

6.按照二叉树的定义，具有3个结点的二叉树有(  C  )种。

  A.3          B.4          C.5          D.6

 

8.深度为5的二叉树至多有(  C  )个结点。 (2^n-1)

A.16          B.32          C.31          D.10

 

9.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为 (  A  )

A.n          B.n+1          C.n-1          D.n+边数

 

10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要(  C  )条边。

A.n          B.n+1          C.n-1          D.n/2

 

11.静态查找表与动态查找表二者的根本差别在于(  B  )

A.它们的逻辑结构不一样

B.施加在其上的操作不同

C.所包含的数据元素的类型不一样

D.存储实现不一样

 

12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的( D  )方法是散列文件的关键。

A.散列函数              B.除余法中的质数

C.冲突处理              D.散列函数和冲突处理

 

散列表：https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E8%A1%A8/5981869?fromtitle=%E6%95%A3%E5%88%97%E8%A1%A8&fromid=10027933    网页最后的Data_structures有数据结构的内容链接

散列文件：https://baike.baidu.com/item/%E6%95%A3%E5%88%97%E6%96%87%E4%BB%B6/8597321

 

13.对于大文件的排序要研究在外设上的排序技术，即(   C  )

A.快速排序法              B.内排序法

C.外排序法              D.交叉排序法

 

14.设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用(  C  )法。

A.冒泡排序                     B.快速排序

C.堆排序                       D.基数排序

 

二、判断题

 

1.所谓数据的逻辑结构指的是数据元素之间的逻辑关系。(    ×  )   逻辑关系的整体

 

2.在线性结构中，每个结点都有一个直接前驱和一个直接后继。(   ×   )  head  和  end 没有

 

3.插入和删除是数组的两种基本操作。(  ×    )     查找和修改

 

4.在链栈的头部必须要设置头结点。(   ×   )     栈都是在头部进行操作的，加了头结点等于对头结点后的结点进行操作，使算法复杂，只需要头指针就可以了

 

5.在二叉树中插入结点则该二叉树便不再是二叉树。(    ×  )   不改变性质就可以  每个节点最多含有两个子树的树称为二叉树

 

6.查找表的逻辑结构是集合。( √ )

 

7.静态查找表的检索与修改被分成两个不交叉的阶段分别进行。(  √    )

 

8.在索引顺序文件中插入新的记录时，必须复制整个文件。(     × )

记录存放是按照写入顺序的，排序后索引将顺序记录各记录的位置，相对于索引来说，是记录排序第1记录在文件中实际位置(存放的第几条记录)，因此避免重新移动记录的麻烦，同时还能对同一个文件建立多个索引。
因此在添加新的记录时，仅需要添加到文件末尾，重新计算并写入索引部分即可。

 

9.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。(  ×    )   排序的时间复杂度是不同的，要选择合适的

 

10.对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是0(n2)(   √   )

https://blog.csdn.net/qq_41835813/article/details/88969912   最后有表格

 

45. 冒泡排序算法在最好的情况下的元素交换次数为 0 。
46. 在最坏情况下，冒泡排序的时间复杂度为 n(n-1) /2 。
47. 对于长度为n的线性表，在最坏情况下，快速排序所需要的比较次数为 n(n-1) /2 。
48.在最坏情况下，简单插入排序需要比较的次数为 n(n-1) /2 。
49.在最坏情况下，希尔排序需要比较的次数为 O(n1.5) 。注：括号里是n的1.5次方。
50. 在最坏情况下，简单选择排序需要比较的次数为 n(n-1) /2 。
51. 在最坏情况下，堆排序需要比较的次数为 o(nlog2n) 。
52.对于输入为N个数进行快速排序算法的平均时间复杂度是 O(Nlog2 N)。

三、填空题

1.程序设计的实质是___数据表示_____和____数据处理____。

 

2.设由字符串a=′data′、b=′structure′、c=′-′,则a与c连接然后与b连接的结果为：____data-structure____。

 

3.通常单链表的头结点指的是___在单链表第一个结点之前增设的一个类型相同的结点_____；单链表的首结点指的是____表结点中的第一个结点____。

 

4.一个队列的入队序列是a、b、c、d，则队列的输出序列为____ a、b、c、d____。

 

5.栈结构通常采用的两种存储结构是____线性存储____和____链式存储____。

 

6.具有N个结点的完全二叉树的深度为____〔log2N〕+1____。

 

7.树的三种主要的遍历方法是：____先序____、____后续____和层次遍历。    还有中序

 

8.在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于____1___。

 

9.采用散列技术实现散列表时，需要考虑的两个主要问题是：构造___散列函数_____和解决____冲突____。

 

10.索引顺序表上的查找分两个阶段：(1)____确定待查元素所在块____；(2)____在块中查找待查元素____。

 

11.散列文件中的记录通常是成组存放的。若干的记录组成一个存储单位，称作____桶____。

 

12.就文件而言，按用户的观点所确定的基本存储单元称为____逻辑结构____。按外设的观点所确定的基本存储单元称为____物理结构____。

 

13.文件的检索有三种方式：____顺序____存取、____直接____存取和按关键字存取。

 

14.最简单的交换排序方法是____冒泡____排序。

 

15.外排序的基本方法是_____归并___。