数据结构专升本模拟题及参考答案讲课教案

作业题（一）一、单项选择题1. 从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2. 链表不具有的特点是（）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。

For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1) B．O(n)C．O(n²) D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。

A．2 B．3C．4 D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。

A．98 B．100C．102 D．1066、判定一个栈s（最多元素为m0）为空的条件是（）。

A．s-〉top! =0 B．s-〉top= =0C．s-〉top! =m0 D．s-〉top= =m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。

A．（rear-front+m）%m B．rear-front+1C．rear-front-1 D． rear-front8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。

A．连接 B．求子串C．模式匹配 D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。

山东:07年专升本考试数据结构模拟试题1一、填空题:(每小题2分,共10分1. 设有数据结构(D,R,其中 D 是数据元素的有限集,R 是的有限集。

2. 深度为 k 的二叉树其结点数至多有个。

3. 栈是一种特殊的线性表,它允许在表的一端进行操作。

4. 通常象交通、道路问题的数学模型是一种称为的数据结构。

5. 哈希表是一种查找表,可以根据哈希函数直接获得。

二、单项选择题:(每小题2分,共10分对于下列各题,在备选答案中选出一个正确的,并将其编号填在“”位置上。

1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值,则采用存储方式最节省运算时间。

A. 单链表B. 双链表C. 单循环链表D. 顺序表2. 下列排序算法中,算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

A. 直选择排序B. 冒泡排序C. 归并排序D. 堆排序3. 队列的操作原则是。

A. 先进后出B. 先进先出C. 只能进行插入D. 只能进行删除4. 在具有 n 个结点的二叉链表中,非空的链域个数为。

A. n-1B. nC. n+1D. 不确定5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值,其最坏比较次数的数量级为。

A. O(log2nB. O(nC. O(nlog2nD. O(n2三、判断题:(每小题2分,共10分判断下列各题是否正确,若正确,在题后的括号内填“T”,否则填“F”。

1. 在栈为空的情况下不能作出栈处理,否则,将产生下溢出。

(2. 如果有向图 G=(V, E 的拓扑序列唯一,则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。

(3. 在大根堆中,必定满足每个结点的键值大于其左右子树中所有结点的键值。

(4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。

(5. 在索引顺序表中,对索引表既可采用顺序查找,也可采用二分查找。

(四、解答下列各题:(每题10分,共40分1. 已知线性表 L 采用带头结点的的单向循环链表表示,试给出它的存储结构类型描述及相应的示意图。

《数据结构》模拟卷一、单项选择题1．数据结构是（ D ）。

A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．算法分析的目的是（B ）。

A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（ D ）。

A．插入B．删除C．排序D．定位4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ B ）。

A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，15．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ D ）。

A．15 B．16C．17 D．186．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（A ）。

A．1207 B．1209C．1211 D．12137．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ A ）。

A．队列B．栈C．线性表D．有序表8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B ）。

A．不一定相同B．都相同C．都不相同D．互为逆序9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（C ）。

A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（A ）。

A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（C ）。

A．无向图B．有向图C．稠密图D．稀疏图12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（D ）。

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

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

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

答案:A4.假设以数组A［0..n-1］存放循环队列的元素，其头指针front指向队头元素、尾指针rear 指向队尾元素一个，则在少用一个元素空间的前提下，队列空的判定条件为（）。

A.(front+1)％n==rearB.(rear+1)％n==front+1==front==front答案:D5.可以采用（）这种数据结构，实现二叉树的层次遍历运算。

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

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

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

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

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

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

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

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

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

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

A.任意位置B.指定位置C.队尾D.队头15.在关键字序列（10,15,20,25,30）中采用折半法查找20，依次与（）关键字进行了比较。

专升本⼗套-数据结构（试题及答案）数据结构试卷（⼀）⼀、单选题（每题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，５,3D、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）），则树中所含得结点数为__＿_______个，树得深度为________＿__，树得度为__＿______。

专升本数据结构试卷答案一、选择题（每题 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。

数据结构模拟试卷及参考答案一、简答题（共10题，每题10分，共计100分）1. 什么是数据结构？请简要解释。

数据结构是计算机中用于组织和存储数据的方式，它包含了一系列的数据元素，以及这些数据元素之间的关系和操作。

通过使用不同的数据结构，可以更高效地存储、查找和操作数据。

2. 请解释什么是栈，并给出一个栈的应用场景。

栈是一种具有特定操作限制的数据结构，它遵循"先进后出"（LIFO）的原则。

栈的应用场景包括函数调用、表达式求值、撤销操作以及浏览器中的历史记录。

3. 什么是队列？请给出一个队列的实际应用例子。

队列是一种具有特定操作限制的数据结构，它遵循"先进先出"（FIFO）的原则。

一个实际应用例子是操作系统的进程调度，进程按照到达时间加入队列，并按照一定规则出队执行。

4. 请解释什么是链表，并给出一个链表的优点和缺点。

链表是一种动态数据结构，它由一系列节点构成，每个节点包含数据和指向下一个节点的指针。

链表的优点是可以动态地分配内存空间，且插入和删除节点的时间复杂度为O(1)。

缺点是访问链表某个具体节点的时间复杂度为O(n)，且需要额外的内存空间存储指针。

5. 请解释什么是树，并给出一个树的实际应用例子。

树是一种分层次的数据结构，它由一系列节点和节点之间的关系构成。

一个实际应用例子是文件系统的目录结构，文件和文件夹通过树的结构进行组织和存储。

6. 请解释什么是图，并给出一个图的实际应用例子。

图是一种由节点和节点之间的连接关系组成的数据结构。

一个实际应用例子是社交网络，人与人之间的关系可以用图来表示，每个人是一个节点，节点之间的连接表示关系。

7. 请解释什么是散列（哈希）表，以及它的优势和劣势。

散列表是一种根据关键字直接访问的数据结构，它通过将关键字映射到表中的位置来实现快速的查找操作。

散列表的优势是查找操作的平均时间复杂度为O(1)。

劣势是如果存在多个关键字映射到同一个位置，就会发生冲突，需要解决冲突问题。

专升本《数据结构》模拟题试卷专升本《数据结构》模拟题试卷一. （共75题,共150分）1. 数据的基本单位是（）。

（2分）A.数据元素B.记录C.数据对象D.数据项★检查答案标准答案：A2. （）是数据的不可分割的最小单位。

（2分）A.数据对象B.数据元素C.数据类型D.数据项★检查答案标准答案：D3. 算法的空间复杂度是对算法（）的度量。

（2分）A.时间效率B.空间效率C.可读性D.健壮性★检查答案标准答案：B4. （）是限制了数据元素的内部结构仅为一个字符的线性表。

（2分）A.栈B.队列C.串D.数组★检查答案标准答案：B5. 串的长度是指串中所含（）的个数。

（2分）A.不同字符B.不同字母C.相同字符D.所有字符★检查答案标准答案：D（2采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。

6.分）A.1B.2C.3D.4★检查答案标准答案：B7. 线性表的顺序存储结构是一种（）的存储结构。

（2分）A.顺序存取B.随机存取C.索引存取D.Hash存取★检查答案标准答案：B8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占字节，则2分）。

是（）（2mA.64B.32C.16D.8A★检查答案标准答案：分）2（深度为h的二叉树，第h层最多有（）个结点。

9.A.hB.2h-1C.2h-1D.2hC★检查答案标准答案：分）个结点的二叉树，其对应的二叉链表共有（）个非空链域。

2（10. mA.mB.m+1C.2mD.m-1B★检查答案标准答案：分）。

11. 下面叙述错误的是（）（2顺序表是借助物理单元相邻表示数据元素之间的逻辑关系A.对于空队列进行出队操作过程中发生下溢现象B.C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的★检查答案标准答案：C12. 以下与数据的存储结构无关的术语是（）。

2007年山东省学分互认和专升本考试《数据结构》模拟试题(1)一、单项选择题(从下列各题四个备选答案中选出一个正确答案；每小题1分,共11分)1.数据的基本单位是____。

A.结点B.数据元素C.数据类型D.数据项2.下列算法suanfa1中语句"x=x*2；"的执行次数是____。

void suanfa1(int n){ int i,j,x=1；for(i=1；i<=n；i++)for(j=i；j<=n；j++)x=x*2；printf("%d",x)；}A.n(n-1)/2B.n(n+1)/2C.n2D.⎡nlog2n⎤3.当需要随机查找线性表的元素时,宜采用____作存储结构。

A.双向链表B.循环链表C.顺序表D.单链表4.若8行6列的数组以行序为主序顺序存储,基地址为2000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。

A.2086B.2032C.2068D.答案A,B,C都不对5.广义表(a,(b),c,(d,(e)))的表尾是____。

A.(d,(e))B.(d,(e))）C.(b),c,(d,(e))D.((b),c,(d,(e)))6.____是"Yu**Jia**Shan"的子串。

A.YuB."jia"C."**Shan"D."YuJiaShan"7.无向完全图的邻接矩阵是____矩阵。

A.对称B.上三角C.下三角D.稀疏8.有n(n>0)个结点的完全二叉树的深度是____。

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

A.-a+/bcdB./-+bcdC.+-/bcdD.abcd-/+10.对有3600个记录的索引顺序表(分块表)进行查找,最理想的块长为____。

专升本《数据结构》一、（共75题,共150分）1. 数据的基本单位是（）。

（2分）A.数据元素B.记录C.数据对象D.数据项.标准答案：A2. （）是数据的不可分割的最小单位。

（2分）A.数据对象B.数据元素C.数据类型D.数据项.标准答案：D3. 算法的空间复杂度是对算法（）的度量。

（2分）A.时间效率B.空间效率C.可读性D.健壮性.标准答案：B4. （）是限制了数据元素的内部结构仅为一个字符的线性表。

（2分）A.栈B.队列C.串D.数组.标准答案：B5. 串的长度是指串中所含（）的个数。

（2分）A.不同字符B.不同字母C.相同字符D.所有字符.标准答案：D6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。

（2分）A.1B.2C.3D.4.标准答案：B7. 线性表的顺序存储结构是一种（）的存储结构。

（2分）A.顺序存取B.随机存取C.索引存取D.Hash存取.标准答案：B8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。

（2分）A.64B.32C.16D.8.标准答案：A9. 深度为h的二叉树，第h层最多有（）个结点。

（2分）A.hB.2h-1C.2h-1D.2h.标准答案：C10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。

（2分）A.mB.m+1C.2mD.m-1.标准答案：B11. 下面叙述错误的是（）。

（2分）A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B.对于空队列进行出队操作过程中发生下溢现象C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的.标准答案：C12. 以下与数据的存储结构无关的术语是（）。

（2分）A.循环队列B.双向链表C.哈希表D.数组.标准答案：D13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。

专升本⼗套数据结构试题及答案专升本⼗套数据结构试题及答案数据结构试卷（⼀）⼀、单选题（每题 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-1D. 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（1ogn） D. O（n2）29.对于线性表（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.⼀般从四个⽅⾯评价算法的质量：_________、_________、_________和_________。

［试题分类］旁升本《数据结构》_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. 队列的入队操作是在（）进行的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

云南省统招专升本考试数据结构模拟题及答案一、选择题（每题4分，共40分）1. 下面哪一个不是线性结构的基本特征？A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素之间都是一对一的相邻关系D. 数据元素之间可以是多对多的关系答案：D2. 在单链表中，若要删除指针p所指的节点，则正确的操作是（）。

A. p = p->nextB. p->next = p->next->nextC. p->next = pD. p = p->next->next答案：B3. 设栈S的初始状态为空，元素a, b, c, d, e依次进栈，若每个元素进栈后立即输出，则以下哪一个序列是不可能得到的？A. abedcB. decbaC. acbdeD. acbed答案：C4. 下面关于二叉树的叙述中，正确的是（）。

A. 二叉树中的每个节点最多有两个子节点B. 二叉树中的每个节点最多有一个父节点C. 二叉树中的每个节点最多有一个子节点D. 二叉树中的每个节点可以有多个父节点答案：A5. 在顺序存储的二叉树中，若节点X的存储位置是i，则其右孩子的存储位置是（）。

A. 2iB. 2i + 1C. 2i - 1D. 2(i + 1)答案：B6. 下面哪一个不是排序算法的时间复杂度？A. O(n^2)B. O(nlogn)C. O(n)D. O(2^n)答案：D7. 下面哪一个算法的平均时间复杂度不是O(nlogn)？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序答案：D8. 在哈希表中，若哈希函数的值域为[0, m-1]，则下面哪一个不是解决冲突的方法？A. 开放地址法B. 链地址法C. 再散列法D. 查找表法答案：D9. 下面哪一个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 拓扑排序D. 最短路径算法答案：D10. 在二叉树中，度为0的节点数n0与度为2的节点数n2之间的关系是（）。

课程：数据结构(专升本)--试题和答案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为空的判定条件时( )。

《数据结构》模拟题2010年7月一、单选题（每空2分，共10分）1、队列的删除操作是在（）进行。

A．队首B．队尾C．队前D．对后2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。

A．top++; B．top=0; C．top--; D．top=N;3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A．51 B．23 C．53 D．744、在一棵二叉树中，第4层上的结点数最多为（）。

A．31 B．8 C.15 D．165、向堆中插入一个元素的时间复杂度为（）。

A．O(log2n) B．O(n) C．O(1) D．O(nlog2n)二、填空题（每空1分，共20分）1、数据的逻辑结构被分为____________、___________、____________和____________四种。

2、若对一棵二叉树的结点编号从1开始顺序编码，按顺序存储，把编号为1的结点存储到a[1]中，其余类推，则a[i]元素的左孩子元素为______，右孩子元素为_____，双亲元素(i>0)为________。

3、从一个栈删除元素时，首先取出，然后再前移一位。

4、后缀表达式“2 10 + 5 * 6 – 9 /”的值为。

5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为______、______、______和______个。

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

7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对应主表中的若干条记录，则称此索引为________索引。

8、对于二分查找所对应的判定树，它既是一棵_ ____，又是一棵_____ __ ___。

数据结构模拟试题（含答案）一、单选题（共100题，每题1分，共100分）1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。

A、5B、6C、7D、4正确答案：B2、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。

A、15B、47C、16D、17正确答案：C3、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A、100B、99C、102D、101正确答案：A4、一棵含18个结点的二叉树的高度至少为( )A、5B、4C、6D、3正确答案：A5、有关栈的描述，正确的是（）A、栈是一种先进先出的特殊的线性表B、只能从栈顶执行插入、删除操作C、只能从栈顶执行插入、栈底执行删除D、栈顶和栈底均可执行插入、删除操作正确答案：B6、若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A、中序遍历算法B、前序遍历算法C、后序遍历算法D、层次遍历算法正确答案：A7、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( ) typedef struct node { char data[8]; struct node *next; } LinkStrNode;A、s->next=p; p->next=s->next;B、s->next=p->next; p->next=s;C、p->next=s->next; s->next=p;D、p->next=s; s->next=p->next;正确答案：B8、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。

A、O(n)B、O(1)C、O(n2)D、O(n／2)正确答案：A9、执行一趟快速排序能够得到的序列是（）。

A、[45，34，12，41] 55 [72，63，27]B、[63，12，34，45，27] 55 [41，72]C、[12，27，45，41] 55 [34，63，72]D、[41，12，34，45，27] 55 [72，63]正确答案：D10、带权有向图G用邻接矩阵A存储，则顶点i 的入度等于A中（）。