思考题
一、填空题：（20分，每空1分）
1、数据的基本单位是数据元素，最小单位是 s数据项。
2、 x=91; n=100;
while(n>0)
{if (x>100)
{ x=x-10; n=n-1;
}
else x=x+1;
}
上述算法中语句x=x+1的执行次数T(n)= O(N^3) 。
3、已知二维数组A[21][11]采用行序为主方式存储，每个元素占4个存
储单元，并且A[0][0]的存储地址为1016，则A[10][5]的存储地址是。
4、在进出规则上，队列的特点是，堆栈的特点是。
5、深度为5（根层次为1）的二叉树最多有个结点；第4层最多有
个结点。
6、在长度为n的顺序表（即顺序存储结构的线性表）中插入一个元素，需要平均移动
个元素。
7、在无向图中, 若对于任意一对顶点v i和v j, 都存在 , 则称此图是连通图。
8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行为主存储，a00为第一个元素，其存储地址为1，每个元素占1个地址空间，则a75的地址为。
9、线性表的两种常用存储结构有存储结构和存储结构。
10、当增量d为1时，该趟希尔排序与排序基本一致。
11、数据结构是研究数据的，和算法。
12、常用图的存储结构有：邻接矩阵，邻接表，
十字链表，邻接多重表；
13、顺序表的插入算法
int Insert(elemtype List[],int *num,int i, elemtype x) {int j;
if(i<0| | i>*num+1)
{printf(“\n i值不合法 !”);
return 0;
}
for (j=*num;j>=i;j--)
; /*数据元素依次后移*/
List[ i]=x; (*num)++;
return 1;
}
1在单链表中设置头结点的作用是___ 简化操作_____________________________________。
2顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻。因此，这种表便于
访问，
3设输入元素的顺序为1,2,3,4,5，要在栈S的输出端得到43521，则应进行栈的基本运算表示应为：Push(S,1)，Push(S,2)，Push(S,3)，Push(S,4)，Pop(S)，________________ ，Pop(S)，Pop(S)，Pop(S)。
4由下标0开始且元素个数为n的一维数组实现循环队列时，为实现下标变量m加1后在该数组的有效下标范围内循环，可采用的表达式是m________。
5对行下标由1到50、列下标由1到80的二维数组a，若该数组的起始地址为2000且每个元素占2个存储单元，并以行为主序顺序存储，则元素a[45][68]的存储地址为__ ___；
若以列为主序顺序存储，则元素a[45][68]的存储地址为___ ___。
6设F是由T1、T2、T3三棵树组成的森林，与F对应得二叉树为B。已知T1、T2、T3的结点
数分别为n1、n2和n3，则二叉树B的左子树中有_____结点，二叉树右子树中有__ _
个结点。
设n0为哈夫曼树叶子结点的数目，则该哈夫曼树共有__ __个结点。
7具有10个顶点的无向图，边的总数最多为_____。
8分块查找中，若索引表对各块内均采用顺序查找，有900个元素的线性表若分成25块，其平均查找长度为____ _。
9若一个待散列存储的线性表长度为n，用于散列的散列表长度为m，则装填因子α为__ __。
10在堆排序和快速排序中，若初始记录接近正序或反序，则选用____，若初始记录无序，则最好用____。
11从一个无序序列建立一个堆的方法是：首先将待排序的所有关键字分放到一棵
___________的各个结点中，然后从i= 的结点k i开始，逐步把k i-1,k i-2,…,k1为根的
子树排成堆，直到以k1为根的树排成堆，就完成了建堆的过程。
12算法的重要特性有有穷性、确定性、可行性、输入和输出。
二、单选题：（每题1分，共10分）
1、对于一个头结点为head的带头结点的单链表，判定该表为空表的条件（）
A. head= =NULL;
B. head->next= =NULL;
C. head->next= = head;
D. head!=NULL
2、下述排序算法中，稳定的（）
A. 直接选择排序
B. 直接插入排序
C. 快速排序
D. 堆排序
3、具有线性结构的数据结构是（）
A. 树
B. 图
C. 栈和队列
D. 以
上都不是
4、评价一个算法时间性能的主要标准是( )
A. 算法易于调试
B. 算法易于理解
C. 算法的稳定性和正确性
D. 算法的时间复杂度
5、若用冒泡排序对关键字序列{18，16，14，12，10，8}进行
从小到大的排序,所需进行的关键字比较总次数是
( )
A. 10
B. 15
C. 21
D. 34
6、对稀疏矩阵进行压缩是为了（）
A. 便于进行矩阵运算
B. 便于输入和输出
C. 节省存储空间
D. 降低运算的时间复杂度
7、设以数组A[m]存放循环队列的元素,其头指针、尾指针分别为front
和rear，则当前队列中的元素个数为（）
A. (rear -front + m)%m !!!!!!!
B. rear-front+1
C. (front - rear + m)%m
D. (rear-front)%m
8、已知二叉树如图所示，则其顺序存储结构为（）
9、在有n个叶子结点的哈夫曼树中，其结点总数为（）
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
10、一个有n个顶点的无向图最多有（）条边。
A. n
B. n(n-1)
C. n(n-1)/2
D.
2n
11.数据的存储结构包括顺序、链接、散列和____4种基本类型。
A. 向量
B. 数组
C.集合
D.索引
1.下面关于线性表叙述中的错误是__ __。
A. 线性表采用顺序存储，必须占用一段地址连续的单元
B. 线性表采用顺序存储，便于进行插入和删除操作
C. 线性表采用链式存储，不必占用一段地址连续的单元
D. 线性表采用链式存储，便于进行插入和删除操作
2.栈和队列都是特殊的线性表，其特殊性在于____。
A. 它们具有一般线性表所没有的逻辑特性
B. 它们的存储结构比较特殊
C. 对它们的使用方法作了限制!!!!!!!!!
D. 它们比一般线性表更简单
4.已知二维数组的行下标i=-3,-2,-1,0,…,5，列下标j=0,1,…,10，则该数组含有
的元素个数为__ ___。
A. 88
B. 99
C. 80
D. 90
5．若对n个元素进行插入排序，则进行第i趟排序之前有序表中的元素个数为____。。
A. i
B. i+1
C. i-1
D. 1
6．一棵完全二叉树上有1001个结点，其叶子结点的个数是_____。
A. 250
B. 500
C. 505
D. A～C都不对
7．设无向图的顶点个数为n，则该无向图最多有_____条边。
A. n-1
B.
2)1
(-
n
n C.
2)1
(+
n
n D. n2
8.存放元素的数组下标由1开始，对有18个元素的有序表作二分（折半）查找，则查找A[3]时比较的下标序列为____。
A. 1,2,3
B. 9,5,2,3
C. 9,5,3
D. 9,4,2,3
三、判断题：（请在题干的括号内正确的打“√”，错的打“×”。每题1
分，共10分）
1、顺序表中的结点类型不能为结构体。………………………………………（cuo ）
2、在单链表中，头结点是必不可少的。………………………………………（ cuo）
3、循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不
同。……………………………………………………………………………（dui ）
4、希尔排序方法是不稳定的。………………………………………………（ dui ）
5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。……（）
6、二叉排序树查找和折半查找的时间性能相
同。……………………………（）
7、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。………（dui ）
8、多维数组元素之间的关系是线性的。………………………………………（dui ）
9、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（）
10、在任何情况下，快速排序的效率总是最高的。…………………………（）
四、简答题：（30分，共6道小题，每题5分）
1、已知一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，请画出该二叉树，并写出其后序序列。
2、已知待排序文件各记录的排序码顺序如下
72 73 71 23 94 16 05 68
请列出快速排序中第一趟排序过程及结果。
3、下图所示的树中根结点为哪个？树的深度为多少？请将下图中的树转换为二叉树。
4、已知一稀疏矩阵如下图所示，试画出该稀疏矩阵的三元组顺序表和三元组单链表。
0 8 10 0 0 0
0 0 0 0 0 0
-3 0 0 0 0 11
0 0 0 0 0 0
0 1 0 0 0 0
5、给定叶结点权值：（1，3，5，7，8），构造哈夫曼树，并计算其带权路径长度。
6、从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树：
（25，66，40，97，22，15，8，11）
五、算法设计题：（30分，共3题，每题10分）
要求：每题都要求先写出算法的设计思路，再写出实现该算法的C语言函数。函数名自定。
1、编写链队列的进队列操作算法，链队列的定义如下：
typedef struct SLNode
{ elemtype Data;
struct SLNode *Next;
}slnodetype;
typedef struct
{ slnodetype *Head;
slnodetype *Rear;
}slqtype;
2、编写函数InsertL(bt，x，Parent)，其功能为：将数据域为x的结点插入二叉树bt中作为结点Parent的左孩子结点。如果结点Parent原来有左孩子则将结点Parent原来的左孩子作为结点x的左孩子结点。二叉树中结点的数据类型和头结点定义如下：
typedef struct BTreeNode
{ elemtype Data;
struct BTreeNode *Lchild;
struct BtreeNode *Rchild;
}nodetype;
3、有n个记录，编写select算法，用直接选择排序法对它们进行排序。记录的数据结构定义如下：
#define MAXSIZE 20
struct Record
{
int key;
char name[10];
float data;
}s[MAXSIZE]; /*待排记录放在s[0]到s[MAXSIZE-1]中*/
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 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，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 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）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。
习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对
数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?)
8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法
东北农业大学网络教育学院 数据结构作业题（一） 一、选择题（每题2分，共20分） 1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A、O(n) B、O (n/2) C、O (1) D、O (n2) 2．带头结点的单链表first为空的判定条件是（）。 A、first == NULL; B、first->link == NULL; C、first->link == first; D、first != NULL; 3．在一棵树中，（）没有前驱结点。 A、分支结点 B、叶结点 C、树根结点 D、空结点 4．在有向图中每个顶点的度等于该顶点的（）。 A、入度 B、出度 C、入度与出度之和 D、入度与出度之差 5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。 A、20 B、18 C、25 D、22 6．下列程序段的时间复杂度为（）。 s=0； for(i=1；i .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 《数据结构》填空作业题答案 第 1 章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。 4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7.在树形结构中，数据元素之间存在一对多的关系。 8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向 图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑 关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑 关系由附加的指针域来体现。 12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14.数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数 据的实现方法。 16.数据元素可由若干个数据项组成。 17.算法分析的两个主要方面是时间复杂度和空间复杂度。 18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂 度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为㏒ 3n 。 1 数据结构试题? 一、?单选题（每题 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 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.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(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 1．数据的最小单位是（ A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．下面关于线性表的叙述错误的是（D）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 (A) BADC(B)BCDA (C) CDAB (D) CBDA 5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。 (A) 9 (B) 10 (C) 11(D) 12 6．下面程序的时间复杂为（B） for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2)(C) O(n3) (D) O(n4) 7．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（C）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 8．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A)O(n) (B) O(nlog2n) (C) O(1)(D) O(n2) 9．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 10．设用链表作为栈的存储结构则退栈操作（ B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l 13．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B ）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 14. 深度为k的完全二叉树中最少有（ B ）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1(D) 2k-1 《数据结构与算法》复习题 选择题 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 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三） （四） （五） （六） （七 ）（八 ） （九 ） （十 ） 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三 ） （四 ） （五 ） （六） （七） （八） （九） （十 ） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设 个空间，问 676(10)，每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ） 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二 分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count经典数据结构面试题(含答案)
《数据结构》填空作业题(答案)
数据结构试题及答案
经典数据结构面试题(含答案)
数据结构习题及参考答案 .
数据结构习题与答案
数据结构模拟卷(含答案)经典习题培训讲学
数据结构试题(含答案)
数据结构作业(附答案)
数据结构(C语言)【经典题库】含标准答案
数据结构试题及答案
数据结构经典题目c语言代码
数据结构作业及答案
十套数据结构试题与答案
数据结构经典例题
相关主题
文本预览