数据结构试题
一、单项选择
1、若某线性表中最常用的操作是在最后一个元素之后插入和删除元素，则采用___________最节省运算时间.
A、单链表
B、仅有头指针的单循环链表
C、仅有尾指针的单循环链表
D、双链表
2、哈夫曼树的带权路径长度WPL等于___________.
A、除根以外的所有结点的权植之和
B、所有结点权值之和
C、各叶子结点的带权路径长度之和
D、根结点的值
3、设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是___________.
A、1,2,3,4,5
B、1,4,3,2,5
C、4,1,3,2,5
D、1,3,2,5,4
4、20个结点的完全二叉树，其高度为___________.
A、3
B、2
C、4
D、5
5、栈和队列都是___________.
A、顺序存储的线性结构
B、链式存储的线性结构
C、限制存储点的线性结构
D、限制存储点的非线性结构
6、已知完全二叉树有30个结点，则整个二叉树有___________个度为1的结点.
A、0
B、1
C、2
D、不确定
7、对于N个结点的完全无向图，其边数是___________
A、N
B、N2
C、N(N-1)/2
D、N(N-1)
8、队列的特点是
A、先进先出
B、先进后出
C、后进先出
D、不进不出
9、连通分量是的极大连通子图。
A、有向图
B、树
C、无向图
D、图
10、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................
A、向量
B、树
C、图
D、二叉树
11、栈和队列都是（）.
A、线性结构
B、链式存储的线性结构
C、线性结构或非线性结构
D、非线性结构
12、二叉树第J层有（）个结点
A、J
B、2J
C、J+1
D、不能确定
13、若图G中（）是有向的，则称此图为有向图.
A、至少有一条边
B、每一条边
C、有一条边
D、有些边
14、在二叉树中，若已知先根序遍历和后根序遍历顺序，则（）
A、能唯一确定一棵二叉树
B、不能唯一确定一棵二叉树
C、能唯一确定二棵二叉树
D、不存在这样的遍历
15、冒泡排序是（）的排序方法
A、稳定
B、不稳定
C、外部
D、选择
16、归并排序是（）的排序方法
A、稳定
B、不稳定
C、外部
D、选择
17、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R.若在逻辑上看一个环，则队列中元素的个数为（）.
A、R-F
B、n+R-F
C、(R-F+1)mod n
D、(n+R-F)mod n
18、用9个数据构造出的霍夫曼树共有（）个结点
A、9
B、18
C、16
D、17
19、N个结点的顺序查找的平均查找次数为（）
A、N
B、N/2 C（N+1）/2 D、与N无关
20、在无向图的邻接链表中，若表结点个数为M，则边数为（）
A、M
B、M+1
C、与M无关
D、M/2
21、设输入序列为1,2,3,4,5,6,7，借助一个栈不可能得到的输出序列是（）.
A、1,2,3,4,5,6,7
B、1,4,3,2,5 ,7,6
C、4,1,3,2,7,5,6
D、1,3,2,5,4 ,7,6
22、栈和队列都是（）.
A、散列存储的线性结构
B、链式存储的线性结构
C、限制存储点的线性结构
D、索引存储的非线性结构
23、已知完全二叉树有8个结点，则整个二叉树有（）个度为1的结点.
A、0B、1
C、2
D、不确定
24、下列排序方法中，最好情况下，时间复杂度最坏的算法是（）.
A、选择排序
B、归并排序
C、冒泡排序
D、直接插入排序
25、下列排序方法中，排序所花费时间复杂度最小的算法是___________。
A、直接插入排序
B、冒泡排序
C、直接选择排序
D、快速排序
26、在二叉树中，若已知先根序遍历和中根序遍历顺序，则（）
A、能唯一确定一棵二叉树
B、不能唯一确定一棵二叉树
C、能唯一确定二棵二叉树
D、不存在这样的遍历
27、在有向图的邻接链表中，若表结点个数为M，则边数为（）
A 、M
B 、M+1
C 、与M 无关
D 、M/2 28、完全二叉树（ ）二叉树
A 、是满
B 、不一定是满
C 、不是
D 、不适合顺序存储的 29、高度为h 的二叉树（仅含根结点的二叉树高度为0）的结点最少是（ ）
A 、h+1
B 、12+h
C 、 121-+h
D 、 h 2
30、下列排序方法中，时间复杂度为O （NlogN ）的算法是___________。 A 、快速排序 B 、冒泡排序 C 、选择排序 D 、归并排序
二、判断题
（ ）1、线性表的长度是线性表占用的存储空间的大小.
（ ）2、双循环链表中，任一结点的后继指针均指向其逻辑后继. （ ）3、队列只能采用链式存储方式.
（ ）4、树（或森林）可以转化为二叉树.
（ ）5、由二叉树的先序序列和中序序列能唯一确定一棵二叉树. （ ）6、图中一个顶点i 的出度等于其邻接矩阵中第i 列的非0元个数.
（ ）7、在用线性探查法解决冲突所构造的闭散列表中，每组同义词中至少有一个元素的地址正好等于其散列地址.
（ ）8、所谓冲突即是两个关键字的值相同的元素，其散列地址相同.
（ ）9、对n 个元素的有序表用快速排序方法进行排序，时间复
杂是O(n 2
).
（ ）10、存在有偶数个结点的满二叉树.
（ ）11、线性的数据结构可以顺序存储，也可以链接存储.非线性的数据结构只能链接存储.
（ ）12、单链表从任何一个结点出发，都能访问到所有结点. （ ）13、深度优先生成树唯一.
（ ）14、设串S 的长度为n,则S 的子串个数为n(n+1)/2. （ ）15、希尔排序和快速排序都是不稳定的. （ ）16、队列只能采用链式存储方式.
（ ）17、树（或森林）与二叉可以相互转化. （ ）18、由二叉树的先序序列和后序序列能唯一确定一棵二叉树. （ ）19、所谓冲突即是两个关键字的值相同的元素，其散列地址相同.
（）20、存在有偶数个结点的满二叉树.
（）21、网络的最小代价生成树是唯一的.
（）22、用相邻矩阵表示图所用的存储空间大小与图的边数成正比.
（）23、霍夫曼树一定是满二叉树.
（）24、栈是一种线性结构.
（）25、二叉树中任何一结点的度都为２.
（）26、霍夫曼树中不存在度为１的结点.
（）27、宽度优先生成树不唯一.
（）28、利用二分查找法，查找表可按关键字有序，也可无序. （）29、装填因子越大，冲突的可能性越小.
（）30、队列不是一种线性结构.
三、填空题
1、在单链表中，若要删除指针P所指结点的后继结点，则需执行下列三条语句：；P->next=U->next；free(U).
2、设有一个链队列，结点结构为：队尾指针为p（≠null），则执行入队操作时， p->next=q(新结点)；______________.
3、单链表中指针P所指结点不为尾结点的条件是___________.
4、设数组B[1..4,1..5]中的任一元素均占3个单元，从首地址SA=100开始把数组B按行优先存储，则元素B[2,1]的地址为___________.
5、在有n（n>0）个结点的二叉链表中，非空链域的个数为___________.
6、深度为12（根的层次号为0）的完全二叉树至多有___________个结点.
7、一个具有n个顶点的连通有向图至多有___________条边.
8、一棵二叉查找树有17个结点，则有___________个结点其成功的查找长度=4.
9、在对有14个数据的有序表作二分查找时，有___________个结点的查找长度是4.
10、在完全二叉树中，编号为i的结点的父结点的编号为___________.
11、设数组B[1..3,1..5]中的任一元素均占4个单元，从首地址
SA=2001开始把数组B按列优先存储，则元素B[2,2]的地址为.
12、一个具有r个顶点的连通图至少有___________条边.
13、串S=“bcdfkux”共有子串.
14、设根结点的层数为１，定义树的高度为树中层数最大的结点
的层数.则高度为k 的二叉树具有的结点数目，最少为 ,最多为 .
15、单链表中指针q 所指结点不为尾结点的条件是___________. 16、设数组B[1..4,1..5]中的任一元素均占3个单元，从首地址SA=100开始把数组B 按行优先存储， 则元素B[1,3]的地址为___________.
17、在对有20个数据的有序表作二分查找时，有___________个结点的查找长度是3.
18
、2,100,log n n n 中渐近时间复杂度最小的是 .
19、含有10个结点的树有 边.
20、一棵19个结点的二叉排序树中，查找成功的查找长度最多
是 ，查找长度为３的结点共有 .
21、在完全二叉树中，编号为j （j>1）的结点的双亲结点的编号为___________.
22、含有3个2度结点和4个叶结点的二叉树可含___________个1度结点.
23、含有2的n 次方个结点的二叉树高度至少是 ，至
多是 （仅含根结点的二叉树高度为1）. 24、
222,,log ,35n
n
n n ??
?? ? ?
????
中渐近时间复杂度最小的
是 .
25、含有1100个结点的树有 边. 26、一棵完全二叉树有50个结点，按顺序存放在一维数组B[1..50]
中，则此树的最下层的最左边的元素在数组B 中位置是 .
27、一棵二叉树中有37个结点，其中所有结点的度是0或2，则此二叉树中度为2的结点总数是
四、解答下列各题
1、 以数据集{2，4，7，11，15，19，24，36}为叶子结点的权值， （1） 构造一棵哈夫曼树；（2）计算其带权路径长度.
2、已知无向图的邻接矩阵如下：
0111001000101001111010010110010
1
1
1
0??????????????????
⑴请画出此无向图.
⑵请给出此图的广度优先和深度优先遍历序列. (3)请求出每一结点的度.
3、设散列函数H(K)=K%17，若输入序列为 {80,90,100,60,68,35,32,31,15,20,22,12,16,27}，用线性解决冲突的方法：
(1)构造出闭散列表.
(2)求出在等概率查找情况下查找成功的平均查找长度. 4、已知无向网的邻接矩阵如下：
617653152647223664
2
6
∞∞∞????∞∞∞??∞????∞∞∞????∞∞∞??∞
∞
∞??
⑴请画出此无向网.
⑵请用普母算法(从0此开始)画出此无向网的一棵最小生成树. 5、已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，请填上已缺的数据（5分）,并画出该二叉树 先序序列 B E F X C G H 中序序列 B D X A G R H 后序序列 E D R G C A 6、二叉树t 的中根序遍历序列为CEDFBGARTSOXP ，后根序遍历序列为EFDCGBTSROPXA ，请画出此二叉树.
7、已知无向网的邻接矩阵如下： 0243002060204
605433050020240030
3
2
3
0?????????
?????????
⑴请画出此无向网（）。
⑵请用普里母算法画出此网的最小树生成的过程（从0号结点出发）（）。 8、已知有向网的邻接矩阵如下：
0615000050300000640060070000060
0??????????????????
⑴请画出此有向网（）。
⑵请求出此网的关键路径（）。
五、算法设计题：
1．#define maxisize 20 typedef struct node {
int key;
int otherinformation; }Node;
typedef struct {
node data[maxisize];
int num;//有序表中实际结点的个数 }Seqlist;
int Binresearch(SeqList g, int k)
//在有序表中查找，若查找成功，则返回该结点的序号，否则返回0； {
int low, high, mid; low=1; high=g.num;
whle( )
{
mid=(low+high)/2;
if ( ) return mid;
if (g.data[mid].key>k) ;
if ( ) low=mid+1;
}
return ;
}
2．typedef struct node
{ int data;
struct node *next;
}listnode;
typedef listnode *list;
listnode* getnode(list l,int i)
//此函数是查找链表L的第i个结点,若查找成功返回该结点,否则返回空结点.
{ int j;
listnode *p;
p=l;
j=0;
while(p->next&&j { p=p->next; j++; } if (i= =j) { printf("%d",p->data); ；//返回该结点 } else ;//返回失败信息 } void insertlist(list *l, int x, int i) //此函数是生成一个新的结点,其数据为X,并将其插在L的第I个结点之后. { listnode *p,*s;//*q; p=getnode(*l,i-1); if (p==0) return; s=(listnode*)malloc(sizeof(listnode)); if (s==NULL) return; //在下面插入此结点S } 用类C语言写出算法 3．设计一个带头结点的单链表的尾插法实现算法.结点定义如下：(10分) typedef struct node { int data; struct node *next; }Bnode; 4、与出直接插入排序算法,其中表的结构定义如下。（10分） typedef struct { int key; int otherimformation; }Node; typedef struct { Node data[100]; int num; }SeqList; 5、与出二分查找算法,其中查找表的结构定义如下。 typedef struct { int key; int otherimformation; }Node; typedef struct { Node data[100]; int num; }SeqList; 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、 数据结构习题 第一章绪论 1.1数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_ 和运算等的学科。 ①A.数据元素B.计算方法C.逻辑存储D.数据映像 ②A.结构 B.关系 C.运算 D.算法 1.2 算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。 ① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求该进 D.分析算法的易懂性和文档性 ② A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 1.3 计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。 ① A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 ② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性 C.确定性、有穷性和可行性 D.易读性、稳定性和安全性 1.4数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。 1.5数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。 1.6 线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。 1.7 数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。 1.8顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。 第二章线性表 2.1 链表不具备的特点是____ 。 A.可随机访问任一结点 B.插入删除不需移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 2.2 不带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head !=null 2.3带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head!=null 2.4 非空的循环单链表head 的尾结点（由p所指向）满足____。 A. p->next==null B. p==null C. p->next==head D. p==head 2.5 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 2.6线性链表中各个结点之间的地址不一定连续。 2.7线性表中数据元素之间具有__一对一__，除第一个和最后一个元素外，其他数据元素有且只有_一个后 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构习题集(自编) 第一章绪论 一、选择题 1.数据结构就是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的()与运算的学科。 A.结构 B.关系 C.运算 D.算法 2.在数据结构中,从逻辑上可以把数据结构分成()。 A.动态结构与静态结构 B.紧凑结构与非紧凑结构 C.线性结构与非线性结构 D.逻辑结构与存储结构 3.线性表的逻辑顺序与存储顺序总就是一致的,这种说法()。 A.正确 B.不正确 C.无法确定 D.以上答案都不对 4.算法分析的目的就是()。 A.找出算法的合理性 B.研究算法的输人与输出关系 C.分析算法的有效性以求改进 D.分析算法的易懂性 5、算法的时间复杂度取决于( ) A.问题的规模B待处理数据的初态 C、 A与B 6.一个算法应该就是( )。 A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A与C、 7、下面关于算法说法错误的就是( ) A.算法最终必须由计算机程序实现 B、为解决某问题的算法与为该问题编写的程序含义就是相同的 C、算法的可行性就是指指令不能有二义性 D、以上几个都就是错误的 8.以下与数据的存储结构无关的术语就是( )。 A.循环队列 B、链表 C、哈希表D、栈 9.在下面的程序段中,对x的赋值语句的频度为( ) for(i=0;i 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第1章概论 1.数据、数据元素、数据结构、数据类型的含义分别是什么？ 数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。 数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。 数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？ 逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息： ①数据元素的信息； ②各数据元素之间的关系。 物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些？ 对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有： ●创建：建立一个数据结构； ●清除：清除一个数据结构； ●插入：在数据结构中增加新的结点； ●删除：把指定的结点从数据结构中删除； ●访问：对数据结构中的结点进行访问； ●更新：改变指定结点的值或改变指定的某些结点之间的关系； ●查找：在数据结构中查找满足一定条件的结点； ●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。 4.什么是抽象数据类型？如何定义抽象数据类型？ 抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。 对抽象数据类型的描述一般用（D,R,P)三元组表示，抽象数据类型的定义格式为： ADT<抽象数据类型名> { 数据对象D：<数据对象的定义> 数据关系R：<数据关系的定义> 基本操作P：<基本操作的定义> 《数据结构》习题集 第一章序论 思考题： 1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型 作业题： 1.2设有数据结构（D，R），其中 D={d1, d2, d3, d4 } R={r1, r2} r1={ (5) x=n; y=0; //n是不小于1的常数 while(x>=(y+1)*(y+1)){ △y++; } (6) x=91; y=100; while ( y>0 ) { △if(x>100) { x-=10; y--; } else x++ ; } (7) for( i=0; i 一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为 第7章图 一、单选题 01、在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2 B．1 C．2 D．4 02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A．1/2 B．1 C．2 D．4 03、有8个结点的无向图最多有条边。 A．14 B．28 C．56 D．112 04、有8个结点的无向连通图最少有条边。 A．5 B．6 C．7 D．8 05、有8个结点的有向完全图有条边。 A．14 B．28 C．56 D．112 06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。 A．栈 B．队列 C．树 D．图 08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。 A．O(n) B．O(e) C．O(n+e) D．O(n2) 09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。 A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2 C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 2 10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。 A．0 2 4 3 6 5 1 B．0 1 2 3 4 5 6 C．0 4 2 3 1 5 6 D．0 1 3 4 2 5 6 11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。 A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。 A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2 13、图的深度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历14、图的广度优先遍历类似于二叉树的。 A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历15、任何一个无向连通图的最小生成树。 A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在 ( )16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。 A．n、2e B．n、e C．n、n+e D．2n、2e 17、判断有向图是否存在回路，可以利用算法。 A．关键路径 B．最短路径的Dijkstra C．拓扑排序D．广度优先遍历 18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。 A．图中每个顶点的入度 B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 19、求最短路径的Dijkstra算法的时间复杂度是___。A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。 A．O(n) B．O(n+e) C．O(n2) D．O(n*e) 21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。 A．第i行非∞的元素之和 B．第i列非∞的元素之和 C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数 22、一个有n个顶点的无向图最多有条边。 A．n B．n(n-1) C．n(n-1)/2 D．2n 23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。 A．n B．(n-1)2 C．n-1 D．n2 24、对某个无向图的邻接矩阵来说，。 A．第i行上的非零元素个数和第i列的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第i行上，第i列上非零元素总数等于顶点v i的度数D．矩阵中非全零行的行数等于图中的顶点数 25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。 第1章 1.下面（B ）方式可以查看“cp”命令的帮助。 A：cp -? B：cp -h C：cp -a D：cp --h 2.在vi 中从“可视模式”切换到“命令模式”使用（ B）。A：: B：ESC C：Ctrl+L D：Ctrl+Q 3.下面（D ）是“ssh”命令正确的使用方法。 A：ssh -l 192.168.159.159 B：ssh -o 192.168.159.159 C：ssh -a 192.168.159.159 D：ssh 192.168.159.159 4.关于“mkdir -p /fringe/oliva”命令说法正确的是（C ）。A：“-p”是该命令的参数B：该命令没有使用选项C：“-p”是该命令的选项D：该命令没有使用参数5.使用（ A）可以使当前行出现上一行的最后一组参数。A：Ctrl+K B：ESC+. C：Ctrl+L D：ESC+> 6.下列不属于Linux 桌面环境的是（AB ）。 A：Fluxbox B：JDK C：GNOME D：KDE 7.下列关于Linux 桌面环境说法正确的是（D ）。 A：在虚拟终端可以使用Ctrl+F1可以回到Linux桌面环境B：一个系统中只可以安装一种Linux桌面环境 C：Linux桌面环境是Linux运行不可缺少的内容 D：Linux桌面环境不是Linux运行不可缺少的内容 8.在vim 中使用（ D）可以保存并退出当前编辑的文件。A：:w B：:q! C：:q D：:wq 9.使用（D ）可以清除屏幕所有内容。 A：ESC B：ESC+C C：Ctrl+U D：Ctrl+L 10.下列关于telnet 服务说法正确的是（ D）。 A：在RHEL5中默认就安装了telnet 服务 B：telnet 服务在数据传输过程中会对数据进行加密 C：telnet 服务只能在Linux 系统之间使用 D：telnet 服务在数据传输过程中不会对数据进行加密 第2章 1.下面（）命令可以分屏显示“/var/log/message”的内容。A：cat B：file 2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？ 答：主要有：顺序存储结构和链式存储结构两种。 区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。 （1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i 2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。 （2）缺点 顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。 链表：不易于查询，索引慢。 （3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。 答：（1）优点 单向链表：耗存储空间小； 双向链表：可以从任何一点开始进行访问; （2）缺点： 单向链表：访问时必须从头开始，耗时。 双向链表：耗存储空间大。 （3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态： （1）d,e,h,g,入队； （2）d,e出队； （3）I,j,k,l,m入队； （4）b出队； 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 数据结构习题及解答 SANY标准化小组 #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN# Chap1 一、选择题 1. 算法的计算量的大小称为计算的（B ）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2.计算机算法指的是（1） C，它必须具备（2）B这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 3. 下面关于算法说法正确的是（ D ）。 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性(基本运算执行有限次)是指指令不能有二义性 D. 以上几个都是错误的 4．从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 5．以下数据结构中，哪一个是线性结构（ D ） A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 6．在下面的程序段中，对x的赋值语句的频度为（ C ） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 7．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（C）。 A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 8．以下哪个数据结构不是多型数据类型（D） A．栈 B．广义表 C．有向图 D．字符串（始终是字符型 的，不会存在其他类型） 9．以下数据结构中，（A）是非线性数据结构 A．树 B．字符串 C．队 D．栈 二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( A ) 2．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述， 则算法实际上就是程序了。( W ) 3．程序一定是算法。( W ) 4．数据的物理结构是指数据在计算机内的实际存储形式。( W ) 数据结构在计算机中的表示 5. 数据结构的抽象操作的定义与具体实现有关。( W ) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( A ) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( W 第7章图 一、选择题 1.一个有n 个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2.具有6 个顶点的无向图至少有（）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 3.具有n 个顶点且每一对不同的顶点之间都有一条边的图被称为（）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4.具有4个顶点的无向完全图有（）条边。 A、6 B、12 C、16 D、20 5.G是一个非连通无向图，共有28 条边，则该图至少有（）个顶点。 A、6 B、7 C、8 D、9 6.存储稀疏图的数据结构常用的是（）。 A、邻接矩阵 B、三元组 C、邻接表 D、十字链表 7.对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。 A、n B、(n-1)2 C、(n+1)2 D、n2 8.设连通图G的顶点数为n，则G 的生成树的边数为（）。 A、n-1 B、n C、2n D、2n-1 9.对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（（1））；所有邻接表 中的结点总数是（（2））。 （1）A、N B、N+1 C、N-1 D、N+E （2）A、E/2 B、E C、2E D、N+E 10.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表 的结点总数为（）。 A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11.在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。 A、顶点v 的度 B、顶点v 的出度 C、顶点v 的入度 D、依附于顶点v 的边数 12.已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（） （1） A、abecdf B、acfebd C、acebfd D、acfdeb （2） A、abcedf B、abcefd C、abedfc D、acfdeb 13.采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 14.已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发， 数据结构习题 第一章绪论 数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_ 和运算等的学科。 ①A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 ②A.结构 B.关系 C.运算 D.算法 算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。 ① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求该进 D.分析算法的易懂性和文档性 。 ② A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。 ① A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 ② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性 C.确定性、有穷性和可行性 D.易读性、稳定性和安全性 数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。 数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。 线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。 | 数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。 顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。 第二章线性表 链表不具备的特点是____ 。 A.可随机访问任一结点 B.插入删除不需移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 不带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head !=null , 带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head!=null 非空的循环单链表head 的尾结点（由p所指向）满足____。 A. p->next==null B. p==null C. p->next==head D. p==head 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。 数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【A 】是数据的最小单位，【B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系 5.算法分析的目的是【C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 第一章绪论 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x数据结构习题及答案——严蔚敏
数据结构习题集(答案)
数据结构习题与答案
数据结构习题集包含全部答案
作业-《数据结构习题集(C语言版)严蔚敏》答案汇编
数据结构习题参考答案
数据结构习题
数据结构复习题集与答案解析(12级)
最新数据结构习题与答案--图
习题集
第二章数据结构习题作业
数据结构习题及答案
数据结构习题及解答
数据结构习题集第章图
数据结构习题集(答案)
数据结构题集答案
严蔚敏数据结构习题集答案
相关主题
文本预览