数据结构试题（数据结构考试试题）

本文目录

• 数据结构考试试题
• 【数据结构试卷A】数据结构 试题
• 我有一套计算机数据结构方面的试题,请各位哥哥,弟弟,姐姐,妹妹帮忙看一下,帮助我解答一下,非常感谢了!
• 求一些JAVA数据结构的试题及答案解析
• 数据结构面试题整理学生收藏
• 数据结构试题
• 求下面数据结构试题的答案
• 数据结构（C#语言版）笔试试题与答案
• 寻一份《数据结构》试题及答案
• 经典数据结构笔试题和面试题答案及答案分享

数据结构考试试题

一.判断题（）1.某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。正确。第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。（）2.在任何一种线性链表上都无法进行随机访问。错误。比如只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。（）3.顺序栈是一种规定了元素进栈顺序的栈。错误。按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规定元素进栈顺序。（）4.循环列表中每一个元素都有后继。正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。（）5.删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。错误。二.填空题。6.下面程序的时间复杂度为___________。for(inti=1;i《=m;i++)for(intj=1;j《=n;j++)S+=i法则1：for循环：一个for循环的运行时间至多是该for循环内语句（包含测试）的运行时间乘以迭代的次数。法则2：嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。对于此处嵌套的for循环，根据以上法则，时间复杂度为O(m*n)。7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是____________。从第i个元素（原来的）到第n个元素，每个元素后移一位，一共需要n+1-i次。8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为______。找到节点位置，O(n)；单链表插入操作，O(n)；总的时间复杂度为O(n+n)=O(n)。9.若用s作为两个顺序栈的共同存储空间，左右两个栈的栈顶分别为t1和t2，则判断某个栈是否可以插入新元素的条件是_________________。当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。此处判断某个栈是否可以插入新元素的条件是&t1!=&t210.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。将一个森林转换为二叉树的具体方法是：①将森林中的每棵树变为二叉树；②因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。个人认为此处可以填3个答案，n1-1或者n2-1或者n3-1。11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。12.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。散列（Hash）查找。

【数据结构试卷A】数据结构 试题

河南理工大学万方学院 2006-2007学年第 1. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插2 学期 入一个新元素的算法的时间复杂度为( )。(1≤i≤n+1) 数据结构》试卷 (1) O(0) (2) O(1) (3) O(n) (4) O(n2 《) （A 卷） 2. 在单链表中p 所指结点后插入s 所指结点, 则下列语句正确的 是( ) 考试方式： 闭卷 本试卷考试分数占学 生总评成绩的 80 % (1) p→next=s; s→next=p; (2) s→next=p→next; p→next=s; (3) s→next=p; p→next=s; (4) p→next=s→next; s→next=p; 3. 设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的 输出序列不可能是( ) （1）A ，B ，C ，D （2）D ，C ，B ，A （3）A ，C ，D ，B （4）D ，A ，B ，C 复查总分 总复查人 4. 若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） （1） 根结点无右子树的二叉树 （2） 根结 点无左子树的二叉树 （3） 根结点可能有左二叉树和右二叉树 （4） 根结 一、单选题（本题的每一备选答案中，只有一个是正确的，请点只有一个孩子结点的二叉树 把你认为正确的答案的题号填入题干的括号内，每小题2分，5．设二叉树的根为第一层，则深度为i 的二叉树结点数最多为共30分） （ ） （1）2i （2） 2 i +1 （3）2 i -1 《数据结构》试卷 第3 页（共3 页） （4）2 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( ) （1）前序遍历 （2）后序遍历 （3）中序遍历 （4）层次遍历 7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（ ） （1）12534 （2）12435 （3） 14325 （4）12345 i -1 （3）一定是不连续的 （4）连续或不连续都可以 10．下面程序段的时间复杂度为（ ） for (int i=1;i (1) O(m2) (2) O(n2) (3) O(m*n) (4) O(m+n) 11．当利用大小位的数组顺序存储一个队列时，该队列的最大长度为（ ） （1）n-2 (2) n-1 (3) n (4)n+1 8．散列表中的冲突是指（ ） （1） 两个元素具有相同的序号 （2） 两个元素的关键字相同，而其他属性相同 （3） 不同的关键字对应相同的存储地址 （4） 数据元素的地址相同 9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（ ） （1）必须是连续的 （2）部分地址必须是连续的 12．对线性表进行折半搜索时，要求线性表必须（ ） （1）顺序存储 （2）顺序存储且结点按关键字有序 （3）链式存储 （4）链式存储且结点按关键字有序 13．采用线性探查法解决冲突时所产生的一系列后续地址（ ） （1）必须大于等于原散列地址 （2）必须小于等于原散列地址 （3）可以大于或小于但不等于原散列地址 （4） 对地址在何处没有限制 14．栈的插入和删除操作在（ ）进行。 （1）栈顶 （2）栈底 （3）任意位置 （4） 《数据结构》试卷 第3 页（共3 页） 指定位置 15．在一个顺序存储的循环队列中，对头指针指向队列的（ ）位置。 （1）前一个 （2）后一个 （3）当前 （4）后面 二、填空题（每空1分，共20分） 点的关键码值，而右子树中所有结点的关键字值都_________该结点的关键码值。 8. 在一个小顶堆中，堆顶元素的值是所有结点中的______________，在一个大顶堆中，堆顶元素的值是所有结点中的______________。 9. 假定一组纪录的关键字为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为__________________________________。 10. 在一个网络的所有生成树中，各边权值之和最小的生成树，称为该网络的______________。 三、判断题（判断下列各题是否正确，若正 确在（）内打“√”，否则“×”。每小题1分，共10分） （ ）1. 栈和队列的存储方式既可是顺序方式，也可是链接方 式。 （ ）2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）3. 二叉树中任何一个结点的度都是2。 （ ）4. 有回路的有向图不能完成拓扑排序。 （ ）5. 按先根次序遍历森林等同于按先序法遍历对应的二叉树。 1. 数据的逻辑结构被分为___0__________， ________________，_________________，________________。 2. 单链表与循环链表_______________________________。 的 区 别 是 3. 在一个循环队列中，判断对空的条件是串是____________________，判断对满的条件是串是_______________________________ 4. 从有序表（12，18，30，43，56，78，82，95）中一次折半搜索43和56元素是，其比较次数分别为_______和_______。 5. 与哈西表的平均查找长度有关的三个因素分别是_____________________________，____________________ ，_____________________。 6. 对于一个具有n 个顶点和e 条边的连通图，其生成树中的顶点数个边数分别为_________和__________。 7. 在二叉排序树中，左子树所有结点的关键字值都________该结 《数据结构》试卷 第3 页（共3 页） （ ）6.n （n》1）个顶点的无向连通图最少由n-1条边。 （ ）7. 有向图的邻接表表示中边表中结点的总数与有向图中有向边的条数相等。 （ ）8. 一个无向图的邻接矩阵中各元素之和与图中边的条数相等。 （ ）9. 归并排序要求待排序文件已部分排序。 （ ）10. 顺序检索时数据的存储方式可以是顺序的，也可以是链接的。 四、综合题（共40分） 1．已知某系统在通信联络中只可能出现8种 字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11 ，试设计哈夫曼编码。(7分) 2．设待排序的记录的关键字序列为{12，2，16，30，10，20，18}，写出使用链式基数排序每趟的结果。(6分) 3、拓扑排序的结果不是唯一的，对于下图的结点进行拓扑排序，试写出其中的任意5个。 (5分) 3 V V 9 7 5 《数据结构》试卷 第3 页（共3 页） 4．分别按前序、后序、对称序列写出下图二叉树的结点，并转化为树林，分别按先根次序、后根次序列出其结点。(6分) 5. 已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key)=key MOD 13, 表长为13，分别用线性探查法和链地址法处理冲突构造哈希表，并计算各平均查找长度。(10分) 6. 程序填空(6分) 对有序表R进行二分查找，成功时返回记录在表中的位置，失败时返回0. Struct sqlist { keytype key; }; int binsrch(sqlist R,keytype k) //在表R 中查找关键字k { int low ,high,mid; low=0; high=n-1; while( ) 《数据结构》试卷 第3 页（共3 页） mid=(low+high)/2; if (k==R.key) return mid; else if( k 《数据结构》试卷 第3 页（共3 页） }

我有一套计算机数据结构方面的试题,请各位哥哥,弟弟,姐姐,妹妹帮忙看一下,帮助我解答一下,非常感谢了!

数据结构试题一、填空题1、数据类型分为（线性）数据类型和（非线性）数据类型。2、算法是一个有关指令的有限集合，它须符合（有穷性）、（正确性）、（可行性）等准则。3、若英文字母表（A，B，C，——Z）是一个线性表。其结点是单个字母，该线性表共有（26）个结点。通常用前缀和后继来描述数据间逻辑关系。A称为B的（前驱），B称为A的（后继）。4、若满二叉树的高度为K，则些二叉树共有（2^k^）个结点。每个结点都有（2）个孩子。5、栈是一种限定在表的一端进行插入和删除的线性表，又被称为（后进先出的线性）表。6、文件按照其记录类型不同，可分为两类，一类是记录本身的（原子类型），另一类是记录本身是（有结构类型）。7、图的结构复杂，根据实际问题的不同，可以采用不同的存储结构。常用的三种结构为：邻接矩阵、临界表、有向图十字链表8、链表是使用（链式）存储的线性表。在链存储结构中，每个结点有二个域。一个域存放结点的值，称为（数据域），另一个是存放后继结点的地址，称为（指针域）。9、如果一个对象部分地包含自己，或自己定义自己，则称这种对象为（递归定义）的对象。10、如据结构的存储结构包括顺序、（链式）、索引、散列等四种。二、选择题1、对于下图描述二叉树，其后序遍历序列为：CA a,b,c,d,e,f B a,b,d,c,e,f C c,b,e,f,d,a D a,b,d,c,e,fab dc e f2、对于下图的图，按深度优先遍历序列为：看不见图A V1，V2，V4，V5，V7，V3，V6 B V1，V2，V4，V7，V5，V3，V6C V1，V2，V3，V4，V5，V6，V7 D V1，V2，V3，V4，V7，V6，V5V1V2 V3V4 V5 V6 V73、线性表不具有特点是DA随机访问 B不必事先估计所需存储空间大小 C插入与删除时不必移动元素 D所需空间与线性表长度成正比4、具有65个结点的完全二叉树的高度为（注：根的层次号为0）AA 8 B 7 C 6 D 55、下列存储形式中，不是树的存储形式的是DA双亲表示法 B 左子女右兄弟表示法 C 广义表表示法 D顺序表表示法6、在一个顺序存储的循环队列中，队头指针指向的队头元素的CA 前一个位置 B 后一个位置 C队头元素位置 D 队尾元素的前一位置7、若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个DA上三角矩阵 B稀疏矩阵 C 对角矩阵 D 对称矩阵8、若需要得用形参直接该问实参，则应把形参变量说明为BA指针 B 引用 C 传值 D常值9、图的广度优先搜索类似于对的（）次序遍历DA先根 B 中根 C 后根 D层次10、一个顺序表有255个对象，采用顺序搜索法查表，搜索长度为AA 128 B 127 C 126 D 255

求一些JAVA数据结构的试题及答案解析

1 下列数据结构中，能用二分法进行查找的是__A____。 A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表 解析：二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)。 2 在软件设计中，不属于过程设计工具的是__D____。 A、PDL(过程设计语言) B、PAD图 C、N-S图 D、DFD图 解析：软件设计工具包括：程序流程图、N-S、PAD、HIPO，判定表，PDL(伪码)。而DFD(数据流图)属于结构化分析工具。 3 在switch(expression)语句中，expression的数据类型不能是__A____。 A、double B、char C、byte D、short 解析：表达式expression只能返回这个几种类型的值：int、byte、short和char。多分支语句把表达式返回的值依次与每个case子句中的值相比较，如果遇到匹配的值，则执行该case子句后的语句序列。 4 下列叙述中，错误的是__D____。 A、父类不能替代子类 B、子类能够替代父类 C、子类继承父类 D、父类包含子类 5 通过继承实现代码复用： Java中所有的类都是通过直接或间接地继承java.lang.Object类得到的。继承而得到的类称为子类，被继承的类称为父类。子类不能继承父类中访问权限为private的成员变量和方法，子类可以重写父类的方法，及命名与父类同名的成员变量。 子类通过隐藏父类的成员变量和重写父类的方法，把父类的状态和行为改变为自身的状态和行为。注意：子类中重写的方法和父类中被重写的方法要具有相同的名字，相同的参数表和相同的返回类型，只是函数体不同。 由于子类继承了父类所有的属性(私有的除外)，所以子类对象可以作为父类对象使用。程序中凡是使用父类对象的地方，都可以用子类对象来代替。一个对象可以通过引用子类的实例来调用子类的方法。 java运行时系统根据调用该方法的实例，来决定调用哪个方法。对子类的一个实例，如果子类重写了父类的方法，则运行时系统调用子类的方法;如果子类继承了父类的方法(未重写)，则运行时系统调用父类的方法。 6 自定义表格类中的model部分应实现的接口是___A___。 A、AbstractTableModel B、JTable C、TableModel D、TableModelable 7 下列代码中，将引起编译错误的行是__B____。 1)public class Exercise{ 2) public static void main(String args){ 3) float f=0.0; 4) f+=1.0; 5) } 6) } A、第2行 B、第3行 C、第4行 D、第6行 解析：float定义变量赋值时，需要在数值后面加f以标识它为浮点型，让系统知道该给它精确到多少位。

数据结构面试题整理学生收藏

面试真题数据结构面试题整理题目+答案

一、什么是数据结构?

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。

数据的逻辑结构包括4种

(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系

(2)线性结构：数据元素之间是一对一的关系——线性表、栈、队列

(3)树形结构：数据元素之间是一对多的关系

(4)图状结构：数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。

二、解释一下顺序存储与链式存储

顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

三、头指针和头结点的区别?

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

四、线性结构的特点

(1)集合中必存在唯一的一个"第一个元素"；

(2)集合中必存在唯一的一个"最后的元素"；

(3)除最后元素之外，其它数据元素均有唯一的"后继"；

(4)除第一元素之外，其它数据元素均有唯一的"前驱"。

五、数组和链表的区别?

从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。

六、单链表结构和顺序存储结构的区别?

当进行插入和删除操作时，顺序存储结构每次都需要移动元素，总的时间复杂度为O(n^2)，而链式存储结构确定i位置的指针后，其时间复杂度仅为O(1)。由于顺序存储结构需要进行预分配存储空间，所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间，元素个数不受限制。

七、栈和队列的区别

队列是允许在一段进行插入另一端进行删除的线性表，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。

栈是只能在表尾进行插入和删除操作的线性表。附于播入到栈的元素据，“后进先出”的规则处理，插入和删除操作都在栈顶进行。

一由于进栈和出栈都是在栈顶进行， 所以要有一个size变量

来记录当前栈的大小， 当进栈时size不能超过数组长度，

size+1， 出栈时栈不为空， size-1。

八、介绍一下字符串匹配算法：

朴素的匹配算法和KMP算法

1.BF算法(BruteForce)

·目标串t(待匹配串)

·模式串p(短的那个串)

①t的第一个字符和S的第一个比较， 相等则继续t-2VSp-2， 相等则继续t-3VSp 

②不等则t-1VSp-2， t-2VSp-3

2.KMP算法：快速从主串找到子串

①上下子串前缀匹配

②找到公共前后缀(取最长且小于比较的上下字串长度)

(3将下面的p子串前缀移动到后缀位置

Brute-Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等， 但最后一个字符比较不相等时， 主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退，从而可以大大提高效率。

九、深度优先搜索和广度优先搜索是如何实现的?

深度优先搜索：(1)访问起始点v0

(2)若v0的第一个邻接点没有被访问过，则深度遍历该邻接点；

(3)若v0的第一个邻接点已经被访间，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止

广度优先搜索：(1)访问起始点v0

(2)依次遍历v0的所有未访问过得邻接点

(3)再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止

十、如何构造哈夫曼树?

找w最小求和，再找w最小；左小右大；构造结束后，左0右1

十一、最小生成树

最小生成树是要找到最小的边可以把所有的节点都连接起来，而最短路径是

要求某个节点到其余节点的最短的路径。

最小生咸树：

在一给定的无向图G=(V，E)中，(u，v)代表连接顶点u与顶点v的边(即)，而w(u，v)代表此边的权重，若存在T为E的子集(即)且为无循环图，使得w(T)最小，则此T为G的最小生成树。

w(t)=w(u，u)

最小生成树其实是最小(u，u)et

普里姆(prim) 算法的基本思想为：顶点集到其他点权值最小边， 加入新的顶点集，再找边…直到遍历所有点

从联通网络N={V，E}中某一顶点u0出发，选择与它关联的最小权值的边，将其顶点加入到顶点集S中，此后就从一个顶点在S集中，另一个顶点不在S集中的所有顶点中选择出权值最小的边，把对应顶点加入到S集中，直到所有的顶点都加入到S集中为止。

克鲁斯卡尔(kruskal) 算法的基本思想为：依次选择最小边， 使得无环且所有点遍历结束

假设有一个有n个顶点的联通网络N={V，E]，初试时建立一个只有n个顶点，没有边的非连通图T，T中每个顶点都看作是一个联通分支，从边集E中选择出权值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到T中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。

十二、最短路径的算法

Dijkstra时间复杂度为O(n~2)

Fly od时间复杂度为O(n^3) 空间复杂度为O(n^2) ；

最短路径：用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

迪杰斯特拉(dij astra) 算法

经典的单源最短路径算法主要是其采用的动态规划思想.

弗洛伊德(floyd) 算法

经典的求任意顶点之间的最短路径，采用贪心思想。

十三、介绍一下拓扑排序以及是如何实现的?

拓扑排序的步骤：

(1)在有向图中任意选择一个没有前驱的节点输出

(2)从图中删去该节点以及与它相连的边

(3)重复以上步骤，直到所有的顶点都输出或者当前图中不存在无前驱的顶点为止，后者代表该图是有环图，所以可以通过拓扑排序来判断一个图是否存在环。

十四、简述各种查找方法

查找分为静态查找表和动态查找表

静态查找表包括：顺序查找、折半查找、分块查找；

动态查找包括：二叉排序树和平衡二叉树。

(1) 顺序查找：把待查关键字key放入哨兵位置(i=0) ， 再从后往前依次把表中元素和key比较， 如果返回值为0则查找失败， 表中没有这个key值， 如果返回值为元素的位置i(il=0)则查找成功，设置哨兵的位置是为了加快执行速度，时间复杂度为O(n)，其特点是：结构简单，对顺序结构和链式式结构都适用，但查找效率太低

(2)折半查找：要求查找表为顺序存储结构并且有序，若关键字在表中则返回关键字的位置，若关键字不在表中时停止查找的典型标志是：查找范围的上界《=查找范围的下界

(3)分块查找：先把查找表分为若干子表，要求每个子表的元素都要比后面的子表的元素小，也就是保证块间是有序的(但是子表内不一定有序)，把各子表中的最大关键字构成一张索引表，表中还包含各子表的起始地址。特点是：块间有序，块内无序，查找时块间进行索引查找，块内进行顺序查找。

(4)二又排序树：二叉排序树的定义为：一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树

(5) 平衡二叉树：平衡二叉树又称为AVL树， 它或者是一棵空树或者具有如下特点：他的左子树和右子树的高度差的绝对值不能大于1，且他的左右子树也都是平衡二叉树。

如果再一个平衡二叉树中插入一个节点可能造成失衡，这时就要进行树结构的调整，即平衡旋转。包括4中情况：在左子树的左子树上插入节点时向右进行单向旋转；在右子树的右子树上插入节点时向左进行单向旋转；在左子树的右子树插入节点时先向左旋转再向右旋转；在右子树的左子树插入节点时先向右旋转再向左旋转。

十五、简述各种排序算法(一)

内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。

其中插入排序包括：直接插入排序、折半插入排序、希尔排序；

选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

(1)直接插入排序(稳定)：基本思想为：将序列分为有序部分和无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应位置上。时间复杂度为：O(n~2)，空间复杂度为O(1)

(2) 折半插入排序(稳定) ：基本思想为：设置三个变量low high mid， 令

mid=(low+high) /2， 若a 》key， 则令high=mid-1， 否则令low=mid+1， 直到low》high时停止循环， 对序列中的每个元素做以上处理， 找到合适位置将其他元素后移进行插入。比较次数为O(nlog2n) ， 但是因为要后移， 因此时间复杂度为O(n~2)，空间复杂度为O(1)。优点是：比较次数大大减少。

(3)希尔排序(不稳定)：基本思想为：先将序列分为若干个子序列，对各子序列进行直接插入排序，等到序列基本有序时再对整个序列进行一次直接插入排序。优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多，空间复杂度为O(1)。

(4)简单选择排序(不稳定)：基本思想为：将序列分为2部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是：实现简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。时间复杂度为O(n^2)，空间复杂度为O(1)。

(5)堆排序(不稳定)：设有一个任意序列，k1，k2，“

kn，当满足下面特点时称之为堆：让此序列排列成b

完全二叉树，该树具有以下特点，该树中任意节点均

大于或小于其左右孩子，此树的根节点为最大值或者

最小值。优点是：对大文件效率明显提高，但对小文件

效率不明显。时间复杂度为O(nlog2n) ， 空间复杂度为O(1)。

十六、简述各种排序算法(一)

内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。

其中插入排序包括：直接插入排序、折半插入排序、希尔排序；

选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

(6)冒泡排序(稳定)：基本思路为：每一趟都将元素进行两两比较，并且按照“前小后大”的规则进行交换。优点是：每一越不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O(n~2)，空间复杂度为O(1)。

(7)快速排序(不稳定)：基本思路为：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。优点是：每一趟不仅能确定一个元素，时间效率较高。时间复杂度为O(nlog2n) ， 空间复杂度为O(log2n) .

(8)归并排序(稳定)：基本思想为：把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为O(n logn) ， 空间复杂度和待排序的元素个数相同。

(9)基数排序：时间复杂度为：对于n个记录进行链式基数排序的时间复杂度为O(d(n+rd))，其中每一趟分配的时间复杂度为O(n)，回收的时间复杂度为O(rd)。

“前小后大”的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O(n^2)，空间复杂度为O(1)。

数据结构试题

本文出自数据结构十套笔试题之第一套，本站为原创作品，转载请注明出处，谢谢！

• 一、选择题

• 1、栈和队列的共同特点是(      )。A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

参考答案是：A

• 2、用链接方式存储的队列，在进行插入运算时(   ).A. 仅修改头指针  　         B. 头、尾指针都要修改 C. 仅修改尾指针               D.头、尾指针可能都要修改

参考答案是：D

• 3、以下数据结构中哪一个是非线性结构？(   )A. 队列   　　  B. 栈        C. 线性表  　　  D. 二叉树

参考答案是：D

• 4、设有一个二维数组A(10)存放在什么位置？脚注(10)表示用10进制表示。

  A．688          B．678        C．692        D．696

参考答案是：C

• 5、树最适合用来表示(      )。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据    D.元素之间无联系的数据

参考答案是：C

• 6、二叉树的第k层的结点数最多为(  ).

  A. 2k-1       B.2K+1      C.2K-1  　　　D. 2k-1

参考答案是：D

• 7、若有18个元素的有序表存放在一维数组A中，现进行二分查找，则查找A［3］的比较序列的下标依次为(      )A. 1，2，3                                           B. 9，5，2，3C. 9，5，3                                           D. 9，4，2，3

参考答案是：D

• 8、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（      ）

  A. O（1）   　　B. O（n）　　   C. O（1og2n）       D. O（n2）

参考答案是：C

• 9、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）= K %9作为散列函数，则散列地址为1的元素有（   ）个。A．1         B．2           C．3           D．4

参考答案是：D

• 10、设有6个结点的无向图，该图至少应有(      )条边才能确保是一个连通图。A.5       B.6         C.7      D.8

参考答案是：A

• 二、填空题

• 1、通常从四个方面评价算法的质量：_________、_________、_________和_________。

参考答案是：

正确性 易读性 强壮性 高效率

• 2、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

参考答案是：

O(n)

• 3、假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_______个，树的深度为_______，树的度为_________。

参考答案是：

9 3 3

• 4、后缀算式9 2 3 + - 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_________________。

参考答案是：

-1   3 4 X * + 2 Y * 3 / -

• 5、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有 ________个指针域， 其中有________个指针域是存放了地址，有________________个指针是空指针。

参考答案是：

2n n-1 n+1

• 6、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。

参考答案是：

e 2e

• 7、AOV网是一种_____________的图。

参考答案是：

有向无回路

• 8、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

参考答案是：

n(n-1)/2 n(n-1)

• 9、假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为__________________、 ___________________、_______________________和__________________________。

参考答案是：

（12，40） （ ） （74） （23,55，63）

• 10、向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。

参考答案是：

增加1

• 11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。

参考答案是：

O(log2n) O(nlog2n)

• 12、在快速排序、堆排序、归并排序中，_________排序是稳定的。

参考答案是：

归并

求下面数据结构试题的答案

一．

1,复杂性   2.线性结构  非线性结构

3．可以按序号随机存取  4.数据元素   

5.后进先出  6.n    7.只能在队头进行

9.长度 1  深度  1

10  -+A*BC/DE

11

12 顶点Vp到顶点Vq之间的路径是指定的序列Vp，Vi1，Vi2•••Vim，Vq。

13 n（n-2）/2    14  n—1     15   2n—1

17 一种存储结构

19可以从表中任意结点开始遍历整个链表；只用一个指向尾结点的指针对链表头、尾进行操作，提高了效率。

20栈是仅限制在表的一端进行插入和删除的运算的线性表，是一种操作受限的线性表。

二．

1算法 的时间复杂度和空间复杂度

2.队列

3.

4嵌套集合表示法，广义表表示法，凹入表示法

5. 45    6.S(1) X(1) S(2)S(3)X(3)S(4)X(4)X(2)

7（1） O（nˆ2） 

 （2） O（nˆ2）

8.

哈夫曼树：

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.邻接矩阵：

邻接表：

10.二叉树：

前序：ABCEFD

中序：BEFCDA

后序：FEDCBA

数据结构（C#语言版）笔试试题与答案

《数据结构》期末考试试卷（ A ）一、 选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据 B.数据元素C.数据结构 D.数据类型2．栈和队列都是（ A ）A．限制存取位置的线性结构 B．顺序存储的线性结构C．链式存储的线性结构 D．限制存取位置的非线性结构 3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串 B.顺序串和链串C.目标串和模式串 D.变量串和常量串5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100 D. 120 6．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： CA. 2h B .2h-1C. 2h+1 D. h+1软件开发网 www.mscto.com8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2 D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2 D. 4 11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）A．左子树的叶子结点 B．左子树的分支结点C．右子树的叶子结点 D．右子树的分支结点软件开发网 www.mscto.com12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41 B.23和39C.15和44 D.25和51 二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）原理见课本128页三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分) 深度优先；C0-C1-C3-C4-C5-C2宽度优先：C0-C1-C2-C3-C4-C5四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）原理见课本250页五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）0 1 2 3 4 5 6 7 812 23 45 66 76 88 93 103 166过程：mid=(0+8)/2=4high=3,low=0 mid=1high=0,low=0 mid=0（找到12）high=8,low=5,mid=6（找到93）high=8,low=7,mid=7high=8 low=8 mid=8算法：见课本84页上六、知单链表的结点结构为Data next下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)void SelectSort(LinkedList L){ LinkedList p,q,min; DataType rcd; p= (1) ; while(p!=NULL) { min=p; q=p-》next; while(q!=NULL){ if( (2) )min=q; q=q-》next; } if( (3) ){ rcd=p-》data; p-》data=min-》data; min-》data=rcd; } (4) ; }} 本题不会。嘿嘿。。。。七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分) 输入：四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入 2：输出：算法产生至少一个量作为输出 3.：确定性：组成算法的每条指令是清晰的，无歧异的。 4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的八、何谓队列的"假溢"现象？如何解决？（5分）队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。 九、说明并比较文件的各种物理结构。（6分）

寻一份《数据结构》试题及答案

《数据结构》试题一、选择题（每小题2分，共30分）1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C、字符构成的序列 D、字符构成的集合3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i《j, l≤i, j≤ 10)现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A; //求出哪一层结点数最多 return (h*maxn)} // Width

经典数据结构笔试题和面试题答案及答案分享

分享：典型的数据结构笔试题。 1. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。 A.随机存取 B.索引存取 C.顺序存取 D.散列存取 2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作： q=head; while (q-》next!=p) q=q-》next; s= new Node; s-》data=e; q-》next= ; //填空 s-》next= ; //填空 4. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。 A. s-》next=p-》next; p-》next=s; B. p-》next=s-》next; s-》next=p; C. q-》next=s; s-》next=p; D. p-》next=s; s-》next=q; 5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。 A. s-》next=p; p-》next=s; B. s-》next=p-》next; p-》next=s; C. s-》next=p-》next; p=s; C. p-》next=s; s-》next=p; 6. 在一个单链表中，若删除p所指结点的后续结点，则执行____。 A. p-》next= p-》next-》next; B. p= p-》next; p-》next= p-》next-》next; C. p-》next= p-》next; D. p= p-》next-》next; 7. 链表不具备的特点是 ____ 。 A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素 C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比 8. 在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果要在第i个元素前插入一个元素，要后移( )个元素。 N-I N-I+1 9. 以下关于线性表的说法不正确的是 。 A 线性表中的数据元素可以是数字、字符、记录等不同类型。 B 线性表中包含的数据元素个数不是任意的。 C 线性表中的每个结点都有且只有一个直接前趋和直接后继。 D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。 答案 1.A/C(这题是考察对概念的理解，可参考第7题，“顺序表才能随即存取，而链表不可以”) 2.D 3.q-》next=s; s-》next=p; 4.C 5.B 6.A 7.A(此题绝对选A，因为链表只能根据他的前一个结点才能找到下一个结点，不具备随即访问元素的功能) 8.n-i; n-i+1 9.C 相关文章推荐： 建设银行笔试考什么（笔试真题） 索尼招聘笔试真题分享