2002级数据结构期末试卷A

《数据结构》期末考试试题及答案一、单项选择题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. 请简要介绍树的基本概念及常见的树结构。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】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)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2)【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、3（1分）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。

A. 执行算法所需要的计算工作量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高答案：B3. 栈的基本运算中，不包括（）。

A. 入栈B. 出栈C. 取栈顶元素D. 排序答案：D4. 在二叉树的遍历中，先序遍历的顺序是（）。

A. 先根后子B. 先子后根C. 先左后右D. 先右后左答案：A5. 哈希表解决冲突的方法不包括（）。

A. 分离链接法B. 线性探测法C. 链地址法D. 二分查找法答案：D6. 一个图的邻接矩阵表示法中，若第i行第j列的元素为1，则表示（）。

A. 顶点i和顶点j之间有一条边B. 顶点i和顶点j之间没有边C. 顶点i和顶点j之间有n条边D. 顶点i和顶点j之间有m条边答案：A7. 在查找算法中，二分查找法适用于（）。

A. 线性表B. 哈希表C. 树形结构D. 图结构答案：A8. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C9. 一个有n个顶点的无向图，其边数最多为（）。

A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B10. 以下哪个不是排序算法（）。

A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中所需要的___________。

答案：存储空间2. 线性表的链式存储结构中，每个节点包含___________和___________。

答案：数据元素，指针3. 栈的特点是___________，___________。

《数据结构》试题（开卷）（电信系本科2002级2003年12月）一、回答下列问题（每题4分，共32分）姓名_________ 班级 ____________________题号—二三总分题分32 38 30 100得分I.对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？签：最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。

2.已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA,则该二叉树的前序序列是什么？答：是：ABDEGCFH3・设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为0（nlog2n）; 即0 （ 10001og21000） =0（10000）锦标赛排序的准确比较次数为：堆排序的准确比较次数为：若用冒泡排序也较快，最多耗费比较次数为（n・l+n・2+……+n-10） =10n-55=10000-55=9945 （次）4•在KMP算法中，已知模式串为ADABCADADA ,请写出模式串的next[j]函数值。

答：01121123435・中序遍历的递归算法平均空间复杂度为多少？签：要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为0（log2n）6.欲将无序序列（24, 79, 13, 36, 70, 96, 12, 10, 36*, 49, 100, 27）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。

另外请画出堆排序（小根堆）的初始堆。

答：①快速排序第_趟排序的结果序列为：|10, 12, 13, [24], 70, 96, 36, 79, 36*, 49, 100,万（注意要按振荡式逼近算法实现）② 堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整，而且要排成小根堆！初始堆序列为：| 10, 24, 12, 79, 49, 27, 13, 36, 36笃70, 100, 96）无序堆有序初始堆7.已知一组关键字为（1（）, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49）,设哈希函数H （key） =key MOD 13。

《数据结构》期末考试试卷试题及答案一、选择题（每题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）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。

计算机2002-123数据结构试题参考答案一、单项选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共10小题，每小题2分，总计20分）1、D2、B3、B4、B5、C6、B7、C8、D9、A 10、D二、二、填空（本大题共10小题，每小题1分，总计10分）1、连通分量2、结点个数/23、6 14、（n-1）/25、EF-G*ABC-/+D*6、11407、2K-1 2K-18、堆栈9、动态查找表10、先序遍历中序遍历三、解答下列问题（本大题共6小题，每小题5分，总计30分）1、因为：H（19）=19 MOD 13=6H（14）=14 MOD 13=1H（23）=23 MOD 13=10H（1）=1 MOD 13=1 冲突所以（H（1）+1）MOD 16=2H（68）=68 MOD 13=3H（20）=20 MOD 13=7H（84）=84 MOD 13=6 冲突所以（H（84）+1）MOD 16=7 冲突所以（H（84）+2）MOD 16=8H（27）=27 MOD 13=1 冲突所以（H（27）+1）MOD 16=2 冲突所以（H（27）+2）MOD 16=3 冲突所以（H（27）+3）MOD 16=4H（55）=27 MOD 13=3 冲突所以（H（55）+1）MOD 16=4 冲突所以（H（55）+2）MOD 16=5 冲突H（11）=11 MOD 13=11H（10）=10 MOD 13=10 冲突所以（H（10）+1）MOD 16=11 冲突所以（H（10）+2）MOD 16=12 冲突H（79）=79 MOD 13=1 冲突所以（H（79）+1）MOD 16=2 冲突所以（H（79）+2）MOD 16=3 冲突所以（H（79）+3）MOD 16=4 冲突所以（H（79）+4）MOD 16=5 冲突所以（H（79）+5）MOD 16=6 冲突所以（H（79）+6）MOD 16=7 冲突所以（H（79）+7）MOD 16=8 冲突所以（H（79）+8）MOD 16=9 冲突（2）查找成功的平均查找长度为：2、30 10 1 0 10 1 0 10 1 0 1编码为：7为：00008为：000118为：00132为：013为：10005为：100112为：10126为：114、iclosedg23456U V-U KAdjvex lowcost 1161∞1∞119121{1}{2，3，4，5，6}2Adjvex lowcost 02516119211{1，2}{3，4，5，6}3Adjvex lowcost 0026119211{1，2，3}{4，5，6}4Adjvex lowcost 000418211{1，2，3，4}{5，6}6Adjvex lowcost0004180{1，2，3，4，6}{5 }5 61313 78141282352010304050601020301020304050所以最小生成树为：5、第一趟：[68 11 69 23 18] 70 [93 73]第二趟：[18 11 23 ] 68 [ 69 ] 70 [93 73 ]第三趟：11 18 23 68 69 70 [ 93 73]第四趟：11 18 23 68 69 70 73 93四、算法设计题（本大题共2小题，总计15 分）1、（7分）#define size 100int correct(char exp[size],int len){ char s[size];int top=0,I=0,tag=1;while(I<len && tag!=0){ if(exp[I]==’(‘ || exp[I]==’[‘ || exp[I]==’{‘}{ top++;s[top]=exp[I];}if(exp[I]==’)’){ if(s[top]==’(‘) top--;else tag=0;}if(exp[I]==’)’){if(s[top]==’[‘ ) top--;else tag=0;}if(exp[I]==’)’){if(s[top]==’{‘ } top--;else tag=0;}I++;}if(top>0)top=0;return tag;}2、（8分）#include "iostream.h"#define NULL 0#define N 10typedef struct node{ ELEMTP data;struct node *lchild,*rchild;}TNode;//求给定结点的所有祖先和祖先数int count_zx(TNode *t,ELEMTP x){ struct {TNode *pp; int tag; }s[N],ss;int top,n;TNode *p; top=0; n=0; p=t;while( p || top>0){ while(p){ top++;s[top].pp=p;s[top].tag=0;p=p->lchild; }ss=s[top]; top--;if(ss.tag==0){ ss.tag=1; top++;s[top]=ss; p=ss.pp->rchild;}else {if(ss.pp->data==x)break; p=NULL;} }cout<<"the zx wei:"<<endl;for(n=1;n<=top;n++) {p=s[n].pp;cout<<p->data<<" "; }return top;}五．（10分）已知二叉树每个非终端节点都有左孩子和右孩子，试回答下列问题：解：（1）由已知：因为二叉树的每个非终端结点都有左右孩子，可知此二叉树的所有非终端结点的度都为2，无度为1的结点，又因为此树有n个叶结点，根据二叉树的性质3知度都为2的结点数为n-1个，所以此二叉树共有n+n-1=2n-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分，共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．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

数据结构期末考试试题(含答案)题目一请写出快速排序算法的递归实现。

解答一public class QuickSort {public void sort(int[] arr, int low, int high) {if (low < high) {int partitionIndex = partition(arr, low, high);sort(arr, low, partitionIndex - 1);sort(arr, partitionIndex + 1, high);}}private int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}题目二请解释什么是二叉搜索树，并给出一个例子。

解答二二叉搜索树是一种有序的二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。

下面是一个二叉搜索树的例子：6/ \3 9/ \ \1 4 12题目三请写出深度优先搜索(DFS)算法的递归实现。

解答三import java.util.*;public class DFS {private int numVertices;private List<List<Integer>> adjList;public DFS(int numVertices) {this.numVertices = numVertices;adjList = new ArrayList<>();for (int i = 0; i < numVertices; i++) {adjList.add(new ArrayList<>());}}public void addEdge(int src, int dest) { adjList.get(src).add(dest);}public void DFSUtil(int start, boolean[] visited) { visited[start] = true;System.out.print(start + " ");List<Integer> neighbors = adjList.get(start);for (int neighbor : neighbors) {if (!visited[neighbor]) {DFSUtil(neighbor, visited);}}}public void DFS(int start) {boolean[] visited = new boolean[numVertices];DFSUtil(start, visited);}}以上是数据结构期末考试试题及其答案。