下载文档原格式
. . . . .一、单选题第1章绪论1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构C、线性结构和非线性结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性C、可读性和文档性3、数据的不可分割的最小单位是B、紧凑结构和非紧凑结构D、内部结构和外部结构B、正确性和简明性D、数据复杂性和程序复杂性A、结点B、数据元素C、数据项D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则B、集合C、结构D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模C、机器执行速度二、判断题1、数据结构是带有结构的数据元素的集合。
2、程序越短，运行的时间就越少。
3、处理同一问题的算法是唯一的。
B、机器代码质量的优劣D、语句的执行次数4、一个完整算法可以没有输入，但必须有输出。
三、填空题1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
2、______________结构的数据元素之间存在一对多的关系。
3、数据结构的形式化定义为(D，S)，其中D 是______________的有限集，S 是 D 上关系的有限集。
4、数据结构在计算机中的______________称为存储结构。
5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此- 1 -得到两种不同的存储结构是______________存储结构和______________存储结构。
6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。
7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。
四、解答题1、设n 为正整数。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）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来记录当前栈中的最小值。
数据结构综合练习一、选择题1．数据的存储结构包括顺序、链接、散列和（）4种基本类型。
A索引B数组C集合D向量2．下面程序的时间复杂性的量级为（）。
int i=0，s1=0，s2=0；while（i++<n）{if (i%2)s1+=i;…else s2+=i;}(1) (1bn) （n）(2n)3．下面程序段的时间复杂度为（）。
for(int i=0;i<m;i++)for(int j=0;j<n;j++)a[i][j]=i*j;(m2) (n2) (m+n) (m*n)4．在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要从后向前依次后移（）个元素。
+l<5．在一个长度为n的顺序存储结构的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次后移（）个元素。
+l6．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。
A.(n+1)/2 2 +17．在一个顺序表中的任何位置插入一个元素的时间复杂度为（）。
A. O(n)B. O(n/2)C. O(1)D. O(n2)8. 线性表的链式存储比顺序存储更有利于进行（）操作。
A.查找B.表尾插入和删除C.按值插入和删除D.表头的插入和删除…9. 线性表的顺序存储比链式存储更有利于进行（）操作。
A.查找B.表尾插入和删除C.按值插入和删除D.表头的插入和删除10. 在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。
A. ph=p; p->next=ph;B. p->next=ph; ph=p;C. p->next=ph; p=ph;D. p->next=ph->next; ph->next=p;11. 在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。
一、单项选择题1.逻辑关系是指数据元素间的（）A．类型B．存储方式C．结构D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。
A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。
A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。
( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。
A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。
A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。
A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。
数据结构练习题数据结构练习题第⼀章绪论⼀．选择题1、在数据结构的讨论中把数据结构从逻辑上分为（）。
A.内部结构与外部结构B.静态结构与动态结构C.线性结构与⾮线性结构D.紧凑结构与⾮紧凑结构2、采⽤线性链表表⽰⼀个向量时，要求占⽤的存储空间地址（）。
A: 必须是连续的 B 部分地址必须是连续的C: ⼀定是不连续的C: 可连续可不连续3、采⽤顺序搜索⽅法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
A: n B: n/2 C: (n-1)/2 D: (n+1)/24、在⼀个单链表中，若q结点是p结点的前驱结点，若在q与p之间插⼊结点s，则执⾏（）。
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.从⼀个⼆维数组b[m][n]中找出最⼤值元素的时间复杂度为A. mB. nC. m+nD. mn6.在以下时间复杂度的数量级中，数量级最⼤的是log B. 2n C. n2 D. !nA. n27.若需要利⽤形参直接访问实参，则应把形参变量说明为________参数A、指针B、引⽤C、值8.下⾯程序段的时间复杂度为____________。
for(int i=0; ifor(int j=0; ja[i][j]=i*j;A、 O(m2)B、 O(n2)9.执⾏下⾯程序段时，执⾏S语句的次数为____________。
for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/2⼆．填空题1.通常，评价⼀个算法有正确性、健壮性、_________、时间复杂度、空间复杂度五个⽅⾯。
2.在数据结构中，数据的逻辑结构有线性结构、图结构、________________、_______________四种，物理实现上有顺序结构、索引结构、___________、_____________四种。
第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。
A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B3. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)4. 以下数据结构中，哪一个是线性结构（）A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串5. 在下面的程序段中，对x的赋值语句的频度为（）for (int i=1; i<=n; i++)for (int j=1; i<=n;j++)x+=1;A．2n B．n C．n2D．log2n二、判断题1. 数据元素是数据的最小单位。
( )2. 算法的优劣与算法描述语言无关，但与所用计算机有关。
( )3. 数据的物理结构是指数据在计算机内的实际存储形式。
( )4. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
( )5. 数据结构的抽象操作的定义与具体实现有关。
( )三、填空1．数据的物理结构包括的表示和的表示2. 数据结构中的逻辑结构有（1），（2），（3），__（4）_四种。
3. 一个数据结构在计算机中称为存储结构4. 数据结构中评价算法的两个重要指标是5. 一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。
6. 已知如下程序段, 语句1执行的频度为（1）；语句2执行的频度为（2）；for (int i=n; i>=1; i--) {x = x+1; //语句1for (int j = n; j>=1; j--)y = y+1; //语句2}7. 下面程序段中带下划线的语句的执行次数的渐进时间复杂度为int i=1; while (i<n) i = i*2;四、应用题1. 解释和比较以下各组概念（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度2. 若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？3. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好.4. 下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。
二、填空题1. 线性表是一种典型的___线性______结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。
3. 顺序表中逻辑上相邻的元素的物理位置__相邻______。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向__前___移一个位置，移动过程是从_前____向_后____依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链域的指针值_____决定的。
6. 在双向链表中，每个结点含有两个指针域，一个指向___前趋____结点，另一个指向____后继___结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序__存储结构为宜。
相反，当经常进行的是插入和删除操作时，则采用__链接___存储结构为宜。
8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。
9. 线性表、栈和队列都是__线性_____结构，可以在线性表的___任何___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为__单链表_______和__双链表_____；而根据指针的联接方式，链表又可分为__循环链表______和__非循环链表______。
11. 在单链表中设置头结点的作用是__使空表和非空表统一______。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_o(1)_____，在给定值为x的结点后插入一个新结点的时间复杂度为__o(n)_____。
13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为_栈空______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为___m____。
《数据结构》练习题一、解答题（共50分）1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所示。
请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算WPL 。
2. （8分）若一棵二叉树中序遍历和后序遍历序列分别为：DBEHGAFIC 和DHGEBIFCA 。
试画出这棵二叉树，并写出其先序遍历和层序遍历序列。
3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的顶点表按字母a 、b 、c 、d 、e 、f 、g 、h 的顺序依次存储，邻接表的边表结点按顶点的下标由小到大链接）。
请画出其邻接表，并写出从顶点f 出发，分别进行深度和广度优先遍历的序列，写出用Prime 方法从顶点c开始产生最小生成树的边的序列。
4.（8分）已知键值序列为(44，39，67，25， 52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。
⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（ ）。
⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进行排序，第一趟的排序结果是（ ）。
二、完善程序（共20分，每空2分）1.假设一组递减有序的原始数据存储在数组r 中，存放元素的下标下限为low,下标上字符 出现频率 a 0.05 b 0.03 c 0.24 d 0.16 e 0.08 f 0.24 g 0.18 h0.02限为high,以下是在数组中查找数值为k的折半查找算法。
请填空完善程序。
int BinSearch(int r[ ], int low,int high,int k){ int l,h,m;l= low; h= high;while ( ⑴){m= ⑵;if (k < r[m]) ⑶;else if (k > r[m]) ⑷;else return m;}return 0;}2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。
1. 什么是栈？什么是队列？试分别举两个应用实例。
2. 已知二叉树T的数组表示法为下图所示，请用二叉链表表示法表示此树。
3. 初始关键字序列如下：{49，38，65，97，76，13，27，49，55 04}，请写出它们的希尔排序的全过程(其中d=5,3,1）
4．假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：0.34，0.05，0.12，0.23，0.08，0.18，试为这6个字符设计哈夫曼编码。
请先画出你所构造的哈夫曼树(要求树中左孩子节点的权值小于右孩子节点的权值，左分支表示字符“0”，右分支表示字符“1”)，然后分别写出每个字符对应的编码。
5．设哈希（Hash）表的地址范围为0～13，哈希函数为：H（K）＝K MOD 13。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
（23，24，32，4，31，30，46，47）造出Hash表，试回答下列问题：
（1）画出哈希表的示意图；
（2）若查找关键字30，需要依次与哪些关键字进行比较？
（3）若查找关键字14，需要依次与哪些关键字比较？
假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
1.将下面的森林F=﹛T1，T2，T3﹜转换为对应的二叉树。
T1. T2. T3。
2. 请用序列（45，24，53，12，37，93）建立一棵二叉排序树，画出该树，并求在等概率情况下，查找成功的平均查找长度。
3.A,B,C,D,E的权值为{3, 2, 4, 5, 1}，用此权值构造哈夫曼（Huffman）树，并求此哈夫曼（Huffman）树和各个字符的哈夫曼编码（左分支为0，右分支为1）
4. 给定的关键字序列21，22，27，78，40，05，47，69，12，99，要按升序排序，请写出采用冒泡排序法前3趟的结果，和用堆排序法选择出最大和次大关键字的结果（图）
5. 选取哈希函数H(key)＝key Mod 11，用线性探测再散列开放定址法解决冲突。
试在0～10的散列地址空间内对关键字序列{19、11、31、23、17、27、41、13、91、61}构造哈希表，并计算在等概率下成功查找的平均查找长度。
1.什么是顺序表？什么是链表？比较二者的优缺点。
2．将下列由三棵树组成的森林转换为二叉树。
（只要求给出转换结果）
3. 假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树，并写出8个字符的哈夫曼编码
4. 已知某文件的记录关键字集为{50，10，75，40，45，85，80}，写出快速排序方法进行排序的前2趟排序结果。
5. 设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。
要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
1. 顺序队的“假溢出”是怎样产生的？什么是循环队列？如何知道循环队列是空还是满？2．已知树T的数组表示法为下图所示，请用二叉链表表示法表示此树。
3. 假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码（左0，右1，左边比右边小）。
4. 已知某文件的记录关键字集为{50，10，30，40，45，85，80}，要从小到大进行排序，请分别写出直接插入排序的前2趟结果和直接选择排序的前3趟结果。
5. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H （K）=K MOD 16，K为关键字，用线性探测再散列法处理冲突，输入关键字序列：{10，24，32，17，31，30，46，47，40，63，49}造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较?
（3）若查找关键字60，需要依次与哪些关键字比较?
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
1．对于序列：12，16，23，34，45，57，78，91，95，100，112进行二分法查找：
（1）画出二分查找判定树
（2）求出等概率情况下，该二分查找的ASL？
（3）查找元素95需要经过几次比较？和哪些元素比较？
（4）查找元素20需要经过几次比较确定找不到？和哪些元素比较？
2．设一棵二叉树的先序序列为：A B D F C E G H 中序遍历序列为：B F D A G E H C （1）画出这棵二叉树。
（2）将这棵二叉树转换成对应的树（或森林）。
3. 给定集合{15,3,14,2,6,9,16,17}
（1）构造相应的huffman树（规定：二叉树中两个结点，权值小的结点居左）
（2）计算它的带权路径长度
（3）写出它的huffman编码：（规定：左子树编码为0，右子树编码为1,左小右大）
4．设要将序列（17,8,3,25,16,1,13,19,18,4,6,24）中的关键字按升序重新排列，请给出对该序列进行冒泡排序的第一趟排序结果、及以第一个元素为枢轴的快速排序的第一次划分的结果。
5．已知如下所示长度为12的表(34,25,68,72,21,15,49,29,77,8,19,102)
（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树
（2）并求其在等概率的情况下查找成功的平均查找长度。
1、循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。
试分别编写顺序循环队列中出队操作的函数。
（注：）循环顺序队列存储结构类描述如下:
class CircleSqQueue_num {
private Object[] queueElem; // 队列存储空间
private int front;// 队首的引用，若队列不空，指向队首元素，初值为0
private int rear;// 队尾的引用，若队列不空，指向队尾元素的下一个位置,初值为0
private int num; // 计数器用来记录队列中的数据元素个数
……
} // CircleSqQueue_num类结束
2、设一顺序表容量为整型数maxSize,顺序表中数据元素个数为size，顺序表中数据用数组listArray存放，编写算法，实现顺序表中元素的删除。
3、编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x的所有结点的操作。
要求函数返回被删除结点的个数。
4、编写算法计算树(基于孩子兄弟链表存储结构)的深度。
5、循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。
试分别编写顺序循环队列中入队操作的函数。
（注：）循环顺序队列存储结构类描述如下:
class CircleSqQueue_num {
private Object[] queueElem; // 队列存储空间
private int front;// 队首的引用，若队列不空，指向队首元素，初值为0
private int rear;// 队尾的引用，若队列不空，指向队尾元素的下一个位置,初值为0
private int num; // 计数器用来记录队列中的数据元素个数
……
} // CircleSqQueue_num类结束。
