最全最新版专升本《数据结构》试题答案

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行(A )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（D）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（D）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

一、单选题（每题 2 分，共20分）1.1.对一个算法的评价,不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.2。

在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（A ）。

A。

p—>next=HL->next；HL—>next=p; B. p->next=HL；HL=p；C。

p—>next=HL；p=HL；D。

HL=p; p—〉next=HL;3.3.对线性表，在下列哪种情况下应当采用链表表示？( B ）A。

经常需要随机地存取元素 B.经常需要进行插入和删除操作C。

表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4.4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ C ）A. 2 3 1B. 3 2 1C。

3 1 2 D。

1 2 35.5。

AOV网是一种（D )。

A．有向图B．无向图C．无向无环图D．有向无环图6.6。

采用开放定址法处理散列表的冲突时，其平均查找长度（B）.A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A ）。

A．行号B．列号C．元素值D．非零元素个数9.9。

快速排序在最坏情况下的时间复杂度为（D )。

A．O（log2n）B．O（nlog2n）C．0（n) D．0（n2)10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。

A。

O（n) B。

O(1）C。

O(log2n）D。

O（n2）二、运算题（每题6 分，共24分)1.1。

数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M:N）的联系时，称这种结构为_____________________。

专升本数据结构试卷答案一、选择题（每题 2 分，共 30 分）1、在数据结构中，从逻辑上可以把数据结构分为（）。

A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构答案：C解析：数据结构从逻辑上分为线性结构和非线性结构。

线性结构是数据元素之间存在一对一的关系，如线性表、栈、队列等；非线性结构是数据元素之间存在一对多或多对多的关系，如树、图等。

2、以下数据结构中，（）是非线性数据结构。

A 栈B 队列C 线性表D 二叉树答案：D解析：二叉树是一种非线性数据结构，每个节点最多有两个子节点。

栈、队列和线性表都属于线性数据结构。

3、一个顺序存储的线性表的第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（）。

A 108B 110C 106D 104答案：A解析：第一个元素地址为 100，每个元素长度为 2，所以第 5 个元素的地址为 100 ＋ 2×（5 1) ＝ 108。

4、在单链表中，增加头结点的目的是（）。

A 方便运算的实现B 使单链表至少有一个结点C 标识表结点中首结点的位置D 说明单链表是线性表的链式存储实现答案：A解析：头结点的作用是方便运算的实现，比如在插入和删除操作时，可以避免对第一个元素的特殊处理。

5、设栈的顺序存储空间为 S(1:m)，初始状态为 top ＝ 0。

现经过一系列入栈与退栈运算后，top ＝ 20，则当前栈中有（）个元素。

A 20B 21C m 20D m 19答案：A解析：栈是一种先进后出的数据结构，top 指向栈顶元素的位置，top ＝ 20 说明当前栈中有 20 个元素。

6、循环队列的存储空间为 Q(1:50)，初始状态为 front ＝ rear ＝ 25。

经过一系列入队与退队运算后，front ＝ 15，rear ＝ 10，则循环队列中的元素个数为（）。

A 5B 6C 16D 49答案：B解析：循环队列中元素个数的计算公式为：（rear front ＋ 50) ％ 50。

(专升本)《数据结构》试题(模A)一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,答题写在其它地方无效；每小题1分,共11分)1.A.元素B.结点C.数据类型D.数据项2.下列算法suanfa2的时间复杂度为____。

int suanfa2(int n){ int t=1；while(t<=n)t=t*2；return t；}A.O(log2n)B.O(2n)C.O(n2)D.O(n)3.____又称为FIFO表。

A.队列B.散列表C.栈D.哈希表4.若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。

A.1086B.1032C.1068D.答案A,B,C都不对5.广义表(a,((b,( )),c),(d,(e)))的深度是____。

A.5B.4C.3D.26.有n(n>0)个结点的完全二叉树的深度是____。

A.⎡log2(n)⎤B.⎡log2(n)+1⎤C.⎣log2(n+1)⎦D.⎣log2(n)+1⎦7.与中缀表达式a+b*c-d等价的前缀表达式是____。

A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素____进行比较,。

A.65,15,37B.68,30,37C.65,15,30D.65,15,30,379.对长度为10的表作选择(简单选择)排序,共需比较____次关键字。

A.45B.90C.55D.11010.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为____。

A.O(log2 n)B.O(nlog2 n)C.O(n2)D.O(2n )共5 页第1页11.对长度为10的表作2_路归并排序,共需移动____次(个)记录。

程序设计与数据结构与算法专升本试题精选与解析一、选择题1. 下列不能直接在代码中定义的数据结构是：A. 数组B. 栈C. 队列D. 字符串答案：D解析：字符串是一种抽象数据类型，不能直接在代码中定义，而需要通过现有的数据结构（如数组）来表示和操作。

2. 在二叉搜索树中，某节点的左子树的所有节点值均小于该节点的值，右子树的所有节点值均大于该节点的值。

下列哪个操作时间复杂度最坏情况下为O(n)？A. 查找指定节点B. 插入新节点C. 删除指定节点D. 中序遍历答案：C解析：删除指定节点时，需要先找到指定节点，时间复杂度为O(logn)，然后需要调整二叉搜索树的结构，最坏情况下需要遍历整棵树，时间复杂度为O(n)。

3. 下列排序算法中，不稳定的是：A. 冒泡排序B. 插入排序C. 快速排序D. 归并排序答案：C解析：快速排序在每次分割时选择一个基准元素，并将小于基准元素的元素放在左侧，大于基准元素的元素放在右侧，这可能改变相等元素的相对顺序，因此是不稳定的排序算法。

二、填空题1. 以下数据结构中，能够快速查找最大值和最小值的是_______________。

答案：平衡二叉搜索树解析：平衡二叉搜索树（如AVL树、红黑树）可以保持树的平衡性，从而能够在O(logn)的时间内查找最大值和最小值。

2. 在树的遍历中，先序遍历的访问顺序是_______________。

答案：根节点 -> 左子树 -> 右子树解析：先序遍历先访问根节点，然后先序遍历左子树，最后先序遍历右子树。

三、简答题1. 请简述动态规划算法的基本思想和步骤。

答案：动态规划算法的基本思想是将原问题分解为相互重叠的子问题，先求解子问题，再逐步解决更大的问题，最终得到原问题的解。

动态规划算法的基本步骤为：定义状态，构建状态转移方程，计算最优解。

2. 请简述堆排序算法的基本思想和步骤。

答案：堆排序算法的基本思想是通过构建最大堆或最小堆来实现排序。

第2部分习题解析第1章绪论1.1选择题1. 算法的时间复杂度取决于（C）A）问题的规模 B）待处理数据的初态 C） A和B【答案】C2.计算机算法指的是解决问题的步骤序列，它必须具备（B）这三个特性。

A）可执行性、可移植性、可扩充性B）可执行性、确定性、有穷性C）确定性、有穷性、稳定性D）易读性、稳定性、安全性【答案】B5．从逻辑上可以把数据结构分为（C）两大类。

A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构【答案】C6．在下面的程序段中，对x的赋值的语句频度为（C）for(i=0;i<n;i++)for(j=0;j<n;j++) x=x+1;A） O(2n) B）O(n) C．O(n2) D．O(log2n)【答案】C7．下面的程序段中， n为正整数，则最后一行的语句频度在最坏情况下是（D）for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if (A[j]>A[j+1])A[j]与A[j+1]对换；A. O（n）B） O(nlog2n) C） O(n3) D） O(n2)【答案】D1.2填空题2. 对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________，_____________，_____________四种。

【答案】（1）集合（2）线性结构（3）树形结构（4）图状结构或网状结构4．数据结构中评价算法的两个重要指标是_____________。

【答案】算法的时间复杂度和空间复杂度。

5. 数据结构是研讨数据的_____________和_____________，以与它们之间的相互关系，并对与这种结构定义相应的_____________，设计出相应的_____________。

【答案】（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。

6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。

专升本)数据结构A卷参考答案:简答题1,数据结构是相互之间存在一种或多种特定关系的数据元素的集合.这种数据元素相互之间的关系称为结构.可以将数据结构形式化地定义为二元组:Data_Structure=(D,S)其中:D是数据元素的有限集,S是D上关系的有限集.数据结构课程主要讨论数据的逻辑结构,物理结构和操作三个方面的问题.2,算法的时间复杂度是指算法中各语句的频度之和T(n),其中频度指语句的执行次数,n指问题的规模,一般为数据的输入量.渐近时间复杂度:当问题的规模n趋于无穷大时,T(n)的数量级(阶).记为T(n)=O( f(n) ).这里"O"是一种近似表示法,其含义是:在n较大时,该算法的运行时间和f(n)成正比,或者说,T(n)的数量级和f(n)的数量级相同.实际中,将渐近时间复杂度简称为时间复杂度,用以描述算法的时间特性.3,顺序表的优点:(1)可直接求出存储地址(随机存储结构),结构简单,便于随机访问表中的任一元素.(2)存储密度高.顺序表的缺点:(1)不便于插入和删除.(移动元素次数多,平均约需移动一半元素)(2)不便于扩充表的容量.(3)不能有效地利用内存空间.单链表的优点:(1)结点空间可动态申请动态释放.(2)每个结点有指针域指示逻辑顺序,进行插入删除操作时不需移动元素.单链表的缺点:(1)不能随机访问表中任一元素,效率低.(2)存储量可随意扩充,但新增加的存储空间可能与以前的不邻接,故需要设立一些存放地址用的存储单元.4,入栈算法:int push (qstype *s, elemtype x){if (s→top==MAXNUM-1)return 0;else { s→top++;s→stack [s→top]=x;return 1; }}出栈算法:elemtype pop(qstype *s){if (s→topnext!=NULL)if (p->data!=p->next->data)p=p->next;else{ q=p->next;p->next=q->next;free(q);}}return head;}2,#define m 100typedef struct btreenode{ elemtype data;struct btreenode *left;struct btreenode *right;} btree; /*二叉链表的形式化定义*/ void postorder(btree * b){btree * stack[m],*p;int tag[m],top=0;p=b;do{while (p!=NULL){ top++;stack[top]=p;tag[top]=0;p=p->left;}if (top>0){ p=stack[top];if (tag[top]==1){ top--;printf("%d",p->data);}if (top>0){ p=p->right;tag[top]=1;}}}while (p!=NULL&&top!=0)}。

［试题分类］旁升本《数据结构》_08004150圉型］单选份数]: 2个顶点的无向连通网的最小成本树，至少有（）个边。

(n-1)(n-1)/2答案：C个顶点的连通无向图，至少有（）个边。

(m-1)(m1)/2答案：C3. 空串的长度是（）。

答案：A4. 假设以数组A[O .. n1]存放循环队列的元素，其头指针fr o n t指向队头元素、尾指针re a r指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）。

A{ f ro n t+ 1) %n==re a rB { re a r+1) %n==fro n tl==fron t==fro n t答案：D5. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。

A集合B栈C. 队列D树答案：C6钱性表的顺序存储结构是一种（）的存储结构。

A随机存取存取C顺序存取D索引存取答案：A7. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。

答案：D8. 队列的出队操作是指（）操作。

A. 队头删除B队尾删除C. 队头插入D. 队尾插入答案：A9在关键字序列C l O,15,20,25, :}O中，采用折半法查找25,关键字之间比较需要（）次。

答案：B10.串下列关于串的叙述中，正确的是（）。

个串的长度相等，则2个串相等B.替换操作可以实现字符的删除C.空串至少包一个空格D. 一个串的长度至少是1答案：B11. 若二叉树对应的二叉链表共有n个非空链域，则该二叉树有（）个结点的二叉树。

+l答案：D12. 下面叙述错误的是（）。

A在无向图的邻接矩阵中每行1的个数等于对应的顶点度B借助于队列可以实现对二叉树的层遍历C对于单链表进行插入操作过程中不会发生上溢现象D. 栈的特点是先进后出答案：C13. 算法是对某一类问题求解步骤的有限序列。

其中，（）是算法具有的5个特性之一。

A. 可读性B有穷性C. 正确性D健壮性答案：B14. 队列的入队操作是在（）进行的。

2007年山东省专升本考试数据结构真题一、判断题（10分。

本大题共10小题，每小题1分，在小题左面用√表示是，×表示否）1. 线性表的顺序存储结构是一种随机存储结构。

（）2. 一个栈的入栈序列是a, b, c, d, e，则dceab是一个不可能的输出序列。

（）3. 广义表(a, (a,b), d, e, ((i, j), k)) 的深度是2。

（）4. 树是一种重要的线性数据结构。

（）5. 按照二叉树的定义，具有三个结点的二叉树有5种。

（）6. 已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是求矩阵第i列非零元的个数。

（）7. 将递归算法转换为对应的非递归算法时，通常需要使用队列。

（）8. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。

（）9. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

（）10. （101，88，46，70，34，39，45，58，66，10）是堆。

（）二、填空题（15分。

本大题共5小题，5个空，每个空3分，将正确答案填在空格处）。

1. 将下三角矩阵A[1..8, 1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7, 5]的地址为___________。

2. 若某二叉树有20个叶结点，有30个只有一个孩子的结点，则该二叉树的总结点数为___________。

3. 如果以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。

4. 在顺序存储的二叉树中，编号为i和编号为j的结点处在同一层的条件是___________。

5. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的结点时，___________次比较后查找成功。

三、（10分）已知关键字序列为{46，57，84，32，73，36，15，48，90，20}，要求：（1）构造一棵二叉排序树；（2）在等概率情况下，该二叉排序树查找成功的平均查找长度。

数据结构试题及答案(10套最新)数据结构试题及答案(10套最新)第一套试题：问题一：什么是数据结构？数据结构的作用是什么？回答：数据结构是一种组织和存储数据的方式，它关注数据元素之间的关系以及对数据元素的操作。

数据结构的作用包括提供高效的数据存储和访问方式，减少资源消耗，简化问题的解决方法，提高算法的性能和程序的可读性。

问题二：请列举几种常见的线性数据结构，并简要介绍它们的特点。

回答：常见的线性数据结构包括数组、链表和栈。

数组是一种连续存储数据元素的结构，具有随机访问的特点；链表是一种通过指针相连的数据元素，可以灵活地插入和删除元素；栈是一种遵循先进后出原则的数据结构，常用于解决递归问题。

问题三：请说明二叉树的定义及其性质。

回答：二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点。

二叉树具有以下性质：每个节点最多有两个子节点，分别称为左子节点和右子节点；左子树和右子树都是二叉树；二叉树的节点个数为n，边的个数为n-1。

问题四：在数组中查找一个元素的时间复杂度是多少？为什么？回答：在数组中查找一个元素的时间复杂度是O(n)，其中n是数组的长度。

因为在数组中查找元素需要按照索引一个一个比较，最坏情况下需要比较n次才能找到目标元素。

问题五：请解释堆排序算法的原理及时间复杂度。

回答：堆排序算法利用堆这种数据结构进行排序。

首先将待排序的元素构建成一个大顶堆，然后将堆顶元素与最后一个元素交换，继续调整堆，再取出堆顶元素与倒数第二个元素交换，依次执行，最后得到从小到大排序的序列。

堆排序的时间复杂度为O(nlogn)。

第二套试题：问题一：请解释图的邻接矩阵和邻接表表示法。

回答：图的邻接矩阵表示法是使用二维数组来表示图的连接关系，数组中的元素表示相应节点之间的边的关系。

邻接表表示法使用链表来表示图的连接关系，链表中的元素表示相邻节点之间的边的关系。

问题二：请说明深度优先搜索算法的原理及其应用。

回答：深度优先搜索（DFS）算法是一种遍历或搜索图的算法，其原理是从起始节点开始，依次深入到尽可能远的节点，直到无法继续深入为止，然后回溯到上一个节点，再继续深入其他未访问过的节点。

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第一章）1、计算机算法必须具备（）这三个特性。

A、可执行性、可移植性、可扩充性B、可执行性、确定性、有穷性C、确定性、有穷性、稳定性D、易读性、稳定性、安全性2、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A、结构B、关系C、运算D、算法3、具有线性结构的数据结构是（）。

A、图B、树C、广义表D、栈4、设数据结构A=(D, R)，其中D={1, 2, 3, 4}，R={r}, r={<I, 2>, <2, 3>,<3,4>, <4,1>}，则数据结构A是( )。

A、线性结构B、树结构C、图D、集合5、数据结构是指()。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义6、给定有n个元素的向量，建立一个有序单链表的时间复杂度是( )。

A、O(1)）B、O(n)C、O(n2)D、O(n*log2n)7、下列程序段的时间复杂度为（）。

x=n;y=0;while(x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(根号n)C、O(1)D、O(n2)8、计算机算法指的是（）.A、计算方法B、排序方法C、解决问题的步骤序列D、调度方法9、（）是具有相同特性数据元素的集合，是数据的子集。

A、数据符号B、数据对象C、数据D、数据结构10、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为( )。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构11、算法分析的两个主要方面是：A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性12、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构13、数据结构是一门研究非数值计算的程序设计问题中,数据元素的逻辑结构，数据信息在计算机中的()以及一组相关的运算等的课程。

答案第一章1.1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

数据：指能够被计算机识别、存储和加工处理的信息载体。

● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。

数据元素有时可以由若干数据项组成。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：指的是数据之间的相互关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

● 逻辑结构：指数据元素之间的逻辑关系。

● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.● 线性结构：数据逻辑结构中的一类。

它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

栈、队列、串等都是线性结构。

● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

1.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。

这张登记表中，每个学生的各项体检信息排在一行上。

这个表就是一个数据结构。

每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。

这几个关系就确定了这个表的逻辑结构是线性结构。

这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。

课程：数据结构(专升本)--试题和答案1. (单选题) 一棵满二叉树共有64个叶子结点,则其深度为( )。

(本题3.5分)A、 4B、 6C、7D、8学生答案：未答题标准答案：C解析：得分：2. (单选题) 线性表的静态链表存储结构与顺序存储结构相比,优点是( )。

(本题3.5分)A、所有的操作算法实现简单B、便于随机存取C、便于插入和删除D、便于利用零散的存储器空间学生答案：未答题标准答案：C解析：得分：3. (判断题) 在单链表中,可以从头结点开始查找任何一个结点。

( )(本题3.0分)A、正确B、错误学生答案：未答题标准答案：A解析：得分：4. (单选题) ( )不是算法的基本特性。

(本题3.5分)A、可行性B、长度有限C、在规定的时间内完成D、确定性学生答案：未答题标准答案：B解析：得分：5. (单选题) 一个有n个顶点的有向图最多有( )条边。

(本题3.5分)A、nB、n(n-1)C、n(n-1)/2D、2n学生答案：未答题标准答案：B解析：得分：6. (单选题) 数据的逻辑结构可以分为( )。

(本题3.5分)A、动态结构和静态结构B、紧凑结构和非紧凑结构C、内部结构和外部结构D、线性结构和非线性结构学生答案：未答题标准答案：D解析：得分：7. (单选题) 某算法的时间复杂度为O(n2),表明该算法的( )。

(本题3.5分)A、问题规模是n2B、执行时间等于n2C、执行时间与n2成正比D、问题规模与n2成正比学生答案：未答题标准答案：C解析：得分：8. (单选题) 线性表是具有n个( )的有限序列。

(本题3.5分)A、表元素B、字符C、数据项D、数据元素学生答案：未答题标准答案：D解析：得分：9. (单选题) 数据结构在计算机内存中的表示是指( )。

(本题3.5分)A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系学生答案：未答题标准答案：A解析：得分：10. (单选题) 带头结点的单链表L为空的判定条件时( )。

数据结构本科试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的划分依据是（）。

A. 结构的形状B. 是否有分支C. 是否有子结构D. 是否有层次关系2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高3. 在二叉树的遍历中，先序遍历的顺序是（）。

A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左4. 哈希表解决冲突的方法不包括（）。

A. 分离链接法B. 开放定址法C. 链地址法D. 顺序存储法5. 在图的遍历中，深度优先搜索（DFS）算法使用的是（）。

A. 栈B. 队列C. 链表D. 数组6. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)7. 以下哪个排序算法是稳定的（）。

A. 快速排序B. 堆排序C. 归并排序D. 选择排序8. 一个有n个顶点的无向图中，其边的最大数量是（）。

A. n(n-1)/2B. n(n+1)/2C. n^2D. 2n9. 以下哪个数据结构适用于实现稀疏矩阵（）。

A. 顺序存储B. 链式存储C. 压缩存储D. 散列存储10. 以下哪个算法不是动态查找算法（）。

A. 二分查找B. 顺序查找C. 斐波那契查找D. 平衡二叉树查找答案：1. B2. B3. A4. D5. A6. C7. C8. A9. C10. B二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度是指算法执行过程中所需要的基本操作的______与输入数据量之间的关系。

2. 一个长度为n的线性表采用顺序存储结构时，其最后一个元素的存储地址为LOC(n)，则第i个元素的存储地址LOC(i)为______。

3. 堆是一种特殊的完全二叉树，其中每个父节点的值都______其子节点的值（填“大于”或“小于”）。

数据结构试卷（一）一、单选题（每题2分,共20分）1.栈与队列得共同特点就是( )。

A、只允许在端点处插入与删除元素Ｂ、都就是先进后出C、都就是先进先出D、没有共同点2.用链接方式存储得队列,在进行插入运算时（）、A、仅修改头指针B、头、尾指针都要修改C、仅修改尾指针Ｄ、头、尾指针可能都要修改3.以下数据结构中哪一个就是非线性结构？( )Ａ、队列Ｂ、栈C、线性表Ｄ、二叉树4.设有一个二维数组A[m］［n］，假设Ａ［0］[０］存放位置在644（10）,A［２］［2］存放位置在６76（１0）,每个元素占一个空间，问A[3］[3](10)存放在什么位置？脚注(１0）表示用10进制表示。

A.6８8 B．６７8 C.6９2D．69６5.树最适合用来表示（)。

Ａ、有序数据元素B、无序数据元素C、元素之间具有分支层次关系得数据D、元素之间无联系得数据6.二叉树得第k层得结点数最多为( )、Ａ。

２ｋ—１ B、2K+1 C、2K-1 D、 2k-１7.若有１8个元素得有序表存放在一维数组A［19]中，第一个元素放A［１]中,现进行二分查找，则查找Ａ［3］得比较序列得下标依次为( )A、1,2,3 ﻩﻩＢ、9，5，2，３C、9，５,3 ﻩﻩﻩD、9,4，2，38.对ｎ个记录得文件进行快速排序，所需要得辅助存储空间大致为A、Ｏ(1）Ｂ、O（ｎ） C、 O（1og2n) D、 O(n２)9.对于线性表(7,34,5５，25,64，４6，20,10）进行散列存储时，若选用H（K）=K %9作为散列函数,则散列地址为1得元素有（）个，A。

1 B．2 C．3 D．410.设有6个结点得无向图,该图至少应有（)条边才能确保就是一个连通图。

A、5B、6C、7 Ｄ、8二、填空题（每空1分,共26分）1.通常从四个方面评价算法得质量：__＿＿＿_＿__、_________、______＿__与____＿_＿__.2.一个算法得时间复杂度为（n３＋ｎ2ｌog２n+14n）／n２,其数量级表示为________.3.假定一棵树得广义表表示为A(C，Ｄ（E,F，G），H(I，J）），则树中所含得结点数为__＿_______个，树得深度为________＿__，树得度为__＿______。