下载文档原格式
期末考试《数据结构》A 卷一、单项选择题(请将正确答案的字母填写在每 题对应的括号内，每小题1分，共20分)1、下面关于串的叙述中，哪一个是不正确的？()A .串是字符的有限序列B .空串是由空格构成的串C .模式匹配是串的一种重要运算D .串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ,则该图最多有()条边。
A . n-1B . n(n-1)/2C . n(n+1)/2D . 0 3、以下数据结构中，()是非线性数据结构。
A .树B .字符串C .队列D .栈4、下面关于线性表的叙述中，错误的是哪一个？()A .线性表采用顺序存储，必须占用一片连续的存储单元。
B .线性表采用顺序存储，便于进行插入和删除操作。
C .线性表采用链接存储，不必占用一片连续的存储单元。
D .线性表采用链接存储，便于插入和删除操作。
5、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front 和rear ,则当前队列中的元素个数为()。
A . (rear-front+m)%mB . rear-front+1C . (front-rear+m)%mD . (rear-front)%m6、在单链表指针为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; 7、设栈的输入序列是1, 2, 3, 4,则()不可能是其出栈序列。
A .1,2,4,3 B .2,1,3,4C .1,4,3,2D .4,3,1,2,8、广义表(a,(b,c),d,e )的表头和表尾分别为()。
A . a 和(b,c),d,eB . (a )和(b,c),d,eC . a 和((b,c), d,e)D . (a) 和((b,c), d,e)得分评卷人二、判断题，在正确的题后括号内打“J”，在错误的题后括号内打“X”(每小题1分，共10分)1、算法是由若干条指令组成的有穷序列，而一个程序不一定满足有穷性。
《数据结构》期末考试试题及答案一、单项选择题1. 数据结构是计算机科学的基础学科之一。
下列哪个选项正确描述了数据结构的定义？A. 数据结构是一种计算机程序B. 数据结构是一种存储和组织数据的方法C. 数据结构是一种人工智能技术D. 数据结构是一种操作系统答案：B2. 链表和数组是常见的数据结构，它们之间的主要区别是：A. 数组可以存储不同类型的数据，而链表只能存储相同类型的数据B. 数组的元素在内存中是连续存储的，而链表的元素在内存中是分散存储的C. 链表可以随机访问元素，而数组只能顺序访问元素D. 链表的插入和删除操作更高效，而数组的访问操作更高效答案：B3. 在二叉树中，每个节点最多可以有多少个子节点？A. 1B. 2C. 3D. 无限多个答案：B二、填空题1. 假设有一组数据 [5, 8, 3, 2, 9]，按照从小到大的顺序进行冒泡排序的过程中，经过三次交换后的结果是__2__，__3__，__5__，__8__，__9__。
2. 请完成以下代码，实现栈的入栈和出栈操作：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():return self.stack.pop()def is_empty(self):# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False ```答案：```pythonclass Stack:def __init__(self):self.stack = []def push(self, item):self.stack.append(item)def pop(self):if not self.is_empty():def is_empty(self):return len(self.stack) == 0# 示例代码s = Stack()s.push(1)s.push(2)s.push(3)print(s.pop()) # 输出 3print(s.pop()) # 输出 2print(s.is_empty()) # 输出 False```三、简答题1. 请简要介绍树的基本概念及常见的树结构。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题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. 编写一个函数，实现链表的插入操作。
2012 年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上能够把数据结构分为C。
A．动向结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外面结构2．数据结构在计算机内存中的表示是指A。
A ．数据的储存结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机没关的是数据的A结构。
A．逻辑B．储存C．逻辑和储存D．物理4．在储存数据时，往常不单要储存各数据元素的值，并且还要储存C。
A．数据的办理方法B．数据元素的种类C．数据元素之间的关系D．数据的储存方法5．在决定选用何种储存结构时，一般不考虑A。
A．各结点的值怎样B．结点个数的多少C．对数占有哪些运算D．所用的编程语言实现这类结构能否方便。
6．以下说法正确的选项是D。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的会合D．一些表面上很不同样的数据能够有同样的逻辑结构7．算法剖析的目的是C，算法剖析的两个主要方面是A。
（1）A ．找出数据结构的合理性B．研究算法中的输入和输出的关系C．剖析算法的效率以求改良C．剖析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简洁性C．可读性和文档性D．数据复杂性和程序复杂性8．下边程序段的时间复杂度是O（n2）。
s＝0；for（ I ＝ 0； i ＜ n； i＋＋）for（ j＝0；j ＜n；j＋＋）s ＋＝ B[i][j] ；sum ＝ s ；9．下边程序段的时间复杂度是O（n*m ）。
for（ i ＝ 0； i ＜n； i＋＋）for（ j＝0；j ＜m；j ＋＋）A[i][j] ＝ 0；10．下边程序段的时间复杂度是O（log3n）。
i ＝ 0；while（i ＜＝ n）i ＝ i * 3 ；11．在以下的表达中，正确的选项是B。
A．线性表的次序储存结构优于链表储存结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．行列的操作方式是先进后出12．往常要求同一逻辑结构中的全部数据元素拥有同样的特征，这意味着B。
《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。
6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。
7. 树的根结点的度为______，度为0的结点称为______。
8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。
三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。
10. 简述二叉树的遍历方法。
11. 简述图的存储结构及其特点。
四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。
13. 编写一个算法，实现队列的出队操作。
五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。
15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。
答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。
班 姓 学 考试时 考场（教室装 线《数据结构》期末考试试卷(A)一、判断题：（正确者在括号内打“√”，错误者打“×”。
每小题1分，共10分）1．线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ ） 2．栈和队列是一种非线性数据结构。
（ ） 3．十字链表是无向图的一种存储结构。
（ ） 4．Hash 表的平均查找长度与处理冲突的方法无关。
（ ） 5．数据元素是数据的最小单位。
（ ） 6．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
（ ） 7. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i 层上最多能有2i-1个结点。
（ ） 8．有e 条边的无向图，在邻接表中有e 个结点。
（ ） 9．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ ） 中插入一个新结点,总是插入到叶结点下面。
（ ） 二、选择题：（将每小题正确答案的选项填写在题后的横线上，每小题2分，共20分） x 的赋值语句的频度为___________。
FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A ． O(2n)B ．O(n)C ．O(n 2) D ．O(log2n) 2．下面关于串的的叙述中，哪一个是不正确的？___________。
A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 3．栈和队列的共同特点是___________。
A ．只允许在端点处插入和删除元素B ．都是先进后出C ．都是先进先出D ．没有共同点4．一个向量第一个元素的存储地址是50，每个元素的长度为4，则第5个元素的地址是___________。
A. 70 B. 66 C. 50 D. 785．设abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为？___________。
数据结构期末考试题及答案一、选择题（每题2分，共10题）1. 数据结构是指（）A. 存储和组织数据的方式B. 对数据进行计算和处理的方法C. 数据的物理表示形式D. 数据的逻辑结构答案：A. 存储和组织数据的方式2. 在数据结构中，栈是一种（）A. 先进先出的数据结构B. 后进先出的数据结构C. 随机存取的数据结构D. 按键值查找的数据结构答案：B. 后进先出的数据结构3. 下列哪种数据结构不支持随机访问？（）A. 队列B. 栈C. 数组D. 链表答案：D. 链表4. 在二叉树中，每个节点最多可以有几个子节点？（）A. 0B. 1C. 2D. 无限多答案：C. 25. 在图的表示方法中，邻接矩阵适用于（）A. 稠密图B. 稀疏图C. 有向图D. 无向图答案：A. 稠密图6. 下列排序算法中，最坏情况时间复杂度为O(nlogn)的是（）A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C. 快速排序7. 广度优先搜索算法用于（）A. 求最短路径B. 求全排列C. 求最小生成树D. 求图的连通分量答案：A. 求最短路径8. 哈希表的查找时间复杂度为（）A. O(1)B. O(n)C. O(logn)D. O(n^2)答案：A. O(1)9. AVL树是一种（）A. 无序树B. 有序树C. 平衡树D. 非平衡树答案：C. 平衡树10. 以下哪个不属于基本的查找算法？（）A. 二分查找B. 插值查找C. 散列查找D. 顺序查找答案：C. 散列查找二、填空题（每题4分，共4题）11. 下列不是线性表的是（）答案：二叉树12. 在冒泡排序中，每一轮的比较次数是________答案：n-113. 在堆排序中，堆的建立时间复杂度为________答案：O(n)14. 从一个顶点到其余各顶点的最短路径算法是________答案：Dijkstra算法三、简答题（每题10分，共3题）15. 请简要说明栈的应用场景，并给出一个具体实例。
“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。
A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。
A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。
A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。
2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。
3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。
4．在一棵高度为h的3叉树中，最多含有——结点。
5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。
7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。
《数据结构》期末考试试卷（含答案）《数据结构》期末考试试卷（ 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. 100D. 1206．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：CA. 2h B .2h-1C. 2h+1D. h+1软件开发网/doc/d818218954.html,8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。
下列结论哪个正确？AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2D. 411．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（A）A．左子树的叶子结点B．左子树的分支结点C．右子树的叶子结点D．右子树的分支结点软件开发网/doc/d818218954.html,12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41B.23和39C.15和44D.25和51二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。
