下载文档原格式
数据结构期末试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构和链式存储结构的主要区别在于：A. 数据元素的存储关系B. 数据元素的存储空间C. 数据元素的存储顺序D. 数据元素的存储位置答案：A2. 下列关于栈的描述中，错误的是：A. 栈是一种后进先出（LIFO）的数据结构B. 栈只能进行插入和删除操作C. 栈顶元素可以被访问D. 栈可以进行顺序存储和链式存储答案：B3. 在二叉树的遍历算法中，不使用递归算法的遍历方式是：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：D4. 哈希表的冲突解决方法中，不包括以下哪种：A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D5. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于：A. 搜索的顺序B. 存储结构C. 遍历的深度D. 遍历的宽度答案：A6. 快速排序算法的时间复杂度最坏情况下为：A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C7. 下列关于二叉搜索树的描述中，正确的是：A. 每个节点的左子树只包含小于该节点的键值B. 每个节点的右子树只包含大于该节点的键值C. 以上两个选项都正确D. 以上两个选项都不正确答案：C8. 在非递归的二叉树遍历算法中，通常需要使用的数据结构是：A. 栈B. 队列C. 链表D. 数组答案：A9. 一个有n个顶点的无向图，其边数最多为：A. nB. n(n-1)/2C. n(n+1)/2D. n^2答案：B10. 一个长度为n的数组进行归并排序时，需要的辅助空间大小为：A. O(1)B. O(n)C. O(nlogn)D. O(n^2)答案：B二、填空题（每题2分，共10分）1. 在数据结构中，______是一种特殊的线性表，它的元素个数是固定的。
答案：数组2. 链表中，每个节点包含数据域和______。
第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的（）【北方交通大学 2001 一、5（2分）】A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index (S2,‘8’),length(S2)))其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】4．已知串S=‘aaab’,其Next数组值为（）。
【西安电子科技大学 1996 一、7 （2分）】A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。
【中山大学 1999 一、7】A．0 B．012121111212 C．0 D．06．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、1（2分）】7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）1. 单选题1) 数据结构是一种（）。
a) 存储结构b) 算法c) 数据模型d) 网络答案：c) 数据模型解析：数据结构是一种用于组织和存储数据的方式，描述了数据之间的关系以及对数据的操作。
2) 以下哪种数据结构可以通过索引直接访问元素？a) 链表b) 队列c) 栈d) 数组答案：d) 数组解析：数组是一种线性数据结构，可以通过索引直接访问指定位置的元素。
2. 多选题1) 哪些数据结构属于非线性结构？（）a) 队列b) 树c) 栈d) 图答案：b) 树d) 图解析：线性结构中的元素存在一对一的关系，非线性结构中的元素存在一对多或多对多的关系，树和图属于非线性结构。
2) 下列哪些操作可以在栈上进行？（）a) 入栈b) 出栈c) 查找d) 删除答案：a) 入栈b) 出栈解析：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
3. 简答题1) 请简要介绍线性表和非线性表。
答案：线性表是数据元素的一个有限序列，元素之间存在一对一的关系。
非线性表是指元素之间存在一对多或多对多的关系，如树和图。
2) 请解释什么是时间复杂度和空间复杂度。
答案：时间复杂度是衡量算法执行效率的度量，表示算法的运行时间随输入规模增长的速度。
空间复杂度是指算法执行过程中所需的存储空间随输入规模增长的速度。
4. 编程题题目：实现一个栈，包含push、pop和getMin三个操作，要求时间复杂度为O(1)。
答案：class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, x):self.stack.append(x)if not self.min_stack or x <= self.min_stack[-1]:self.min_stack.append(x)def pop(self):if self.stack.pop() == self.min_stack[-1]:self.min_stack.pop()def getMin(self):return self.min_stack[-1]解析：在栈的基础上，使用一个辅助栈min_stack来记录当前栈中的最小值。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）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. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。
2. 二叉树的节点最多有______个子节点。
3. 堆是一种特殊的______。
4. 散列表的查找效率取决于______。
5. 图的遍历算法包括______和______。
6. 快速排序算法的平均时间复杂度为______。
7. 哈希表中的冲突解决方法有______和______。
8. 最小树算法包括______和______。
9. 最短路径算法包括______和______。
10. 并查集算法用于解决______问题。
第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。
2. 请简述二叉搜索树的特点。
3. 请简述哈希表的原理。
4. 请简述图的深度优先搜索算法。
5. 请简述最小树算法的原理。
第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。
第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（）【北方交通大学 2001 一、5（2分）】A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,i ndex(S2,‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】4．已知串S=‘aaab’,其Next数组值为（）。
【西安电子科技大学 1996 一、7 （2分）】A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next数组为（）。
【中山大学 1999 一、7】A．9 B．2 C．6 D．456．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、1（2分）】7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。
数据结构试卷（一）一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
模拟试题四模拟试题四一、选择题（20分）1。
由两个栈共享一个存储空间的好处是（)。
A）减少存取时间，降低下溢发生的几率B）节省存储空间，降低上溢发生的几率C)减少存取时间，降低上溢发生的几率D)节省存储空间,降低下溢发生的几率2。
设有两个串p和q，求q在p中首次出现位置的运算称做（)。
A）连接B）模式匹配 C）求子串D)求串长3。
n个顶点的连通图中边的条数至少为（)。
A)0 B）l C）n—l D）n4.对一个具有n个元素的线性表,建立其有序单链表的时间复杂度为( ）。
A)O(n）B）O(1）C）O（n2） D) O(log2n）5.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是( ）。
A) p—>next=s; s—〉prior=n；p->next—>prior=s；s-〉next:p->next。
B) s—〉priOFp；s->next—p->next；p—>next=s; p—〉next->priOFS.C) p-〉next=s；p-〉next—〉priOFS; s->prior=p; s-〉next=p—〉next.D) s—>prior=p; s-〉next=p—〉next; p-〉next—〉priOFS；p-〉next=S.6，串的长度是( ）.A）串中不同字符的个数 B)串中不同字母的个数C)串中所含字符的个数n（n>0) D)串中所含字符的个数n（n≥0)7.若有一个钱的输入序列是l,2,…,n，输出序列的第一个元素是n，则第i个输出元素是（）。
A) n—i B) n—i—l C）n—i+l D）不确定8.设有一个栈，元素的进栈次序为A，B，C，D，E，下列( )是不可能的出栈序列。
A) A，B，C,D，E B）B，C, D，E,AC）E，A, B，C,D D)E，D, C，B,A9。
在一棵度为3的树中,度为3的结点数有2个，度为2的结点数有1个，度为l的结点数有2个，那么度为0的结点数有（)个。
数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。
A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。
答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。
答案：队尾、队头11. 二叉树中的节点包括______和______。
答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。
答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。
习题一、单项选择题1.空串与空格字符组成的串的区别在于（）。
A.没有区别B.两串的长度不相等C.两串的长度相等D.两串包含的字符不相同2.一个子串在包含它的主串中的位置是指（）。
A.子串的最后那个字符在主串中的位置B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置D.子串的第一个字符在主串中首次出现的位置3.下面的说法中，只有（）是正确的。
A.字符串的长度是指串中包含的字母的个数B.字符串的长度是指串中包含的不同字符的个数C.若T包含在S中，则T一定是S的一个子串D.一个字符串不能说是其自身的一个子串4.两个字符串相等的条件是（）。
A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（）。
A.“ijing”B.“jing＆”C.“ingNa”D.“ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）。
A.2B.3C.4D.57. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanj ing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。
A.“Nanjing＆Shanghai”B.“Nanjing＆Nanjing”C.“ShanghaiNanjing”D.“Shanghai＆Nanjing”8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（）。
A.i＞0B. i≤nC.1≤i≤nD.1≤i≤n+19.字符串采用结点大小为1的链表作为其存储结构，是指（）。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。
A nB n/2C (n-1)/2D (n+1)/2？4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。
A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
）A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（ A ）的表示等价。
《数据结构》模拟题1一、单项选择题1．连续存储设计时，存储单元的地址（）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续2．以下属于逻辑结构的是（）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A. BA+141B. BA+180C. BA+222D. BA+225 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。
A．O（i） B．O（1） C．O（n） D．O（i-1）7．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 8. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。
A. iB. n-iC. n-i+1D. 不确定9. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）。
A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 610. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。
A. 散列函数B. 除余法中的质数C. 冲突处理D. 散列函数和冲突处理二、填空题1．数据的物理结构包括的表示和的表示。
2．数据结构中评价算法的两个重要指标是。
3．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
4．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
5．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
6．链接存储的特点是利用________来表示数据元素之间的逻辑关系。
7. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。
8．区分循环队列的满与空，只有两种方法，它们是______和______。
三、判断题1．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。
( )2. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。
( )3. 稀疏矩阵压缩存储后，必会失去随机存取功能。
（）4. 数组是同类型值的集合。
（）5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
（）6. 稀疏矩阵压缩存储后，必会失去随机存取功能。
（）7. 二维以上的数组其实是一种特殊的广义表。
（）8. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
（）三、解答题1. 数据结构是一门研究什么内容的学科？2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即C第一个且D第二个出栈）的次序有哪几个？四、程序阅读题1.请阅读以下程序，写出此程序所要完成的功能，及时间复杂度。
int compare( SqList A, SqList B ){ j=0;while ( j<A.length && j<B.length )if ( A.elem[j] < B.elem[j] ) return(-1);else if ( A.elem[j] > B.elem[j] ) return(1);else j++;if ( A.length == B.length ) return (0);else if ( A.length < B.length ) return(-1);else return(1);}2.将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。
typedef struct node{int data ; struct node *lchild, *rchild; }btnode;void EXCHANGE(btnode *bt){btnode *p, *q;if (bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q); q=(1)_; p->rchild=(2)___; (3)___=q;if(p->lchild) (4)___; if(p->rchild) (5)___;}}}五、算法设计题1．写出广度优先搜索遍历的遍历算法。
《数据结构》模拟题2一、单项选择题1．以下与数据的存储结构无关的术语是（）。
A．循环队列 B. 链表 C. 哈希表 D. 栈2．以下数据结构中，哪一个是线性结构（）。
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串3．以下那一个术语与数据的存储结构无关？（）。
A．栈 B. 哈希表 C. 线索树 D. 双向链表4．在下面的程序段中，对x的赋值语句的频度为（）。
FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)5.下面关于线性表的叙述中，错误的是哪一个（）。
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
6．线性表是具有n个（）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项7.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表8.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表9.下面给出的四种排序法中( )排序法是不稳定性排序法。
A. 插入B. 冒泡C. 二路归并D. 堆积10.下列排序算法中，其中（）是稳定的。
A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序二、填空题，在横线处填写合适内容1. 数据结构的存储结构包括顺序、________、索引和散列等四种。
2. 在程序运行过程中可以扩充的数组是__________分配的数组。
这种数组在声明它时需要使用数组指针。
3. 在链表中进行插入和操作的效率比在顺序存储结构中进行相同操作的效率高。
4. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________表。
5. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_________的对象。
6. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为_________。
假定树根结点的层数为0。
7. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。
8. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的________上。
9. 设图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G 进行广度优先搜索的序列有________种。
10. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做__________排序。
三、判断题，1.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（）2. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树（）3. 对于AOE网络，加速任一关键活动都能使整个工程提前完成（）4. 直接选择排序是一种稳定的排序方法（）5. 闭散列法通常比开散列法时间效率更高（）6.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（）7.顺序表和一维数组一样，都可以按下标随机（或直接）访问（）8.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置（）四、运算题1. 设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。
A[6][2]的存储字地址：2. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的结点个数。
中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a求解一下问题：高度：度为2的结点数：度为1的结点数：度为0的结点数：3. 假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为空的一棵AVL树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？左单旋转结点个数：右单旋转结点个数：先左后右双旋转结点个数：先右后左双旋转结点个数：不调整结点个数：4. 已知一个带权图的顶点集V和边集G分别为：V={0,1,2,3,4,5,6};E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12};试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，在下面填写对应的路径长度。
