数据结构复习题集
一、判断题
1.线性表的长度是线性表所占用的存储空间的大小。( F )
2.双循环链表中,任意一结点的后继指针均指向其逻辑后继。( F )
3.在对链队列做出队操作时,不会改变front指针的值。( F )
4.如果两个串含有相同的字符,则说它们相等。( F )
5.如果二叉树中某结点的度为1,则说该结点只有一棵子树。(T )
6.已知一棵树的先序序列和后序序列,一定能构造出该树。( F )
7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。(T )
8.图G的拓扑序列唯一,则其弧数必为n-1(其中n为顶点数)。( F )
9.对一个堆按层次遍历,不一定能得到一个有序序列。(T )
10.直接选择排序算法满足:其时间复杂度不受数据的初始特性影响,为O(n2)。(T )
11. 线性表的逻辑顺序与物理顺序总是一致的。( F )
12. 线性表的顺序存储表示优于链式存储表示。( F )
13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。(T )
14. 二维数组是其数组元素为线性表的线性表。( F )
15. 每种数据结构都应具备三种基本运算:插入、删除和搜
索。(T )
16.(101,88,46,70,34,39,45,58,66,10)是堆;(T )
17.将一棵树转换成二叉树后,根结点没有左子树;( F )
18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所得的输出序列也一定相同;(F)
19.哈夫曼树是带权外部路径长度最短的树,路径上权值较大的结点离根较近( T )
20.用一组地址连续的存储单元存放的元素一定构成线性表。(F)
21.堆栈、队列和数组的逻辑结构都是线性表结构。( T )
22.给定一组权值,可以唯一构造出一棵哈夫曼树。( F)
23.相对于索引文件的基本数据,索引表包含的信息量相对少得多,因此。索引表可以常驻内存。( T)
24.在平均情况下,快速排序法最快,堆积排序法最节省空间。( T)
25.快速排序法是一种稳定性排序法。( F )
二.选择题:
1.一个栈的输入序列为12345,则下列序列中是栈的输出序列的是(A)。
A.23415
B.54132
C.31245
D.1425 3
2.设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r,则其元素个数为(D)。
A.r-f
B.r-f+1
C.(r-f) mod n +1
D.(r-f+n) mod n
3.二叉树在线索化后,仍不能有效求解的问题是(D)。
A.先序线索二叉树中求先序后继
B. 中序线索二叉树中求中序后
继
C.中序线索二叉树中求中序前驱
D. 后序线索二叉树中求后序后继
4.求最短路径的FLOYD算法的时间复杂度为(D)。
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
5.一棵左右子树不空的二叉树在先序线索化后,其空指针域数为(B)。
A.0
B.1
C.2
D.不确定
6.数组A[1..5,1..6]的每个元素占5个单元,将其按行优先顺序存储在起始地址为1000的连续的内存单元中,则元素A[5,5]的地址为(A)。
A.1140
B.1145
C.1120
D.1125
7.在下列排序算法中,在待排序的数据表已经为有序时,花费时间反而最多的是(A)。
A.快速排序
B.希尔排序
C.冒泡排
序 D.堆排序
8. 某算法的空间花费s(n)=100nlog2n+1000n+2000,其空间复杂度为
[ D ]
A.O(1)
B.O(n)
C.O(n1.5)
D.O(nlog2n)
9.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是(D)。
A.堆排序
B.冒泡排序
C.快速排
序 D.直接插入排序
10.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡点为A,并已知A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则做(B)型调整以使其平衡。
A.LL
B.LR
C.RL
D.RR
设单链表中结点的结构为
typedef struct node { //链表结点定义
ElemType data; //数据
struct node * Link; //结点后继指针
} ListNode;
11. 已知指针p所指结点不是尾结点,若在*p之后插入结点*s,则应执行下列哪一个操作?[B]
A. s->link = p; p->link = s;
B. s->link = p->link; p->link = s;
C. s->link = p->link; p = s;
D. p->link = s; s->link = p;
12. 非空的循环单链表first的尾结点(由p所指向)满足:[C ]
A. p->link == NULL;
B. p == NULL;
C. p->link == first;
D. p == first;
13.在单项链表中删除一个指定结点的后继的时间复杂度为 [ C ]
A.O(n)
B.O(nlog2n)
C.O(1)
D.O(√n)
14.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为 [ D ]
A.O(1)
B.O(√n)
C.O(nlog2n)
D.O(n)
15.广义表的深度是 [ C ]
A.广义表中子表个数
B.广义表括号个数
C.广义表展开后所含的括号层数
D.广义表中元素个数
16.高度为h(h>0)的二叉树最少有________个结点 [ C ]
A.h
B.h-1
C.h+1
D.2h
17.n个顶点的带权无向连通图的最小生成树包含___A_____个顶点 [ ]
A.n-1
B.n
C.n/2
D.n+1
18.冒泡排序在最好情况下时间复杂度为 [ C ]
A.O(1)
B.O(nlog2n)
C.O(n)
D.O(n2)
19.采用拉链法解决冲突的散列表中,查找的平均查找长度 [ C ]
A.直接与关键字个数有关
B.直接与装填因子a有关
C.直接与表的容量有关
D.直接与散列函数有关
20. 下列图示的顺序存储结构表示的二叉树是(A )
21. n个顶点的连通图中至少含有(A )
A. n-1条边
B. n条边
C. n(n-1)/2条边
D. n(n-1)条边
22. 对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为( D)
A. (19,23,56,34,78,67,88,92)
B. 23,56,78,66,88,92,19,
34)
C. (19,23,34,56,67,78,88,92)
D. (19,23,67,56,34,78,92,
88)
23.某二叉树的先序序列和后序序列正好相同,则该二叉树一定是( A )的二叉树。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
24.下列排序算法中,时间复杂度不受数据初始状态影响,恒为O(nlog2n)的是( A )
A.堆排序
B.冒泡排序
C.直接选择排序
D.快速排序
25.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为( D );
Head(Tail(Head(Tail(Tail(A)))))
A.(g) B.(d) C.c D.d
26.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中,用二分法查找关键码12需做多少次关键码比较。( C)
A、2
B、3
C、4
D、5
27. 下面关于图的存储的叙述中,哪一个是正确的。( A)
A.用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
B.用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
C.用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
D.用邻接表法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
28.给定一个整数集合{3,5,6,9,12},下列二叉树哪个是该整数集合对应的霍夫曼(Huffman)树。( C )
29.对线性表采用折半查找法,该线性表必须(C)。
A.采用顺序存储结构
B.采用链式
存储结构
C.采用顺序存储结构,且元素按值有序
D.采用链式存储结构,且元素按值有序
30.已知二叉树的前序序列为ABDCEFG,中序序列为DBCAFEG,则后序序列
为( B)。
A. DCBAFGE
B. DCBFGEA
C.
DCBFEGA D. DCBGFEA
31.下列各式中,按增长率由小至大的顺序正确排列的是( D )
A. log n,n!,2n ,
n3/2B.n3/2,2n,n logn,2100
C.2n,log n,n logn,
n3/2D.2100,logn, 2n, n n
32.若要在单链表中的结点*p之后插入一个结点*s,则应执行的语句是
( A )
A.s->next=p->next; p->next=s; B.p->next=s;
s->next=p->next;
C.p->next=s->next; s->next=p; D.s->next=p;
p->next=s->next;
33.若要在O(1)的时间复杂度上实现两个循环链表头尾相接,则应对两个循环链表各设置一个指针,分别指向( B )
A.各自的头结点
B.各自的尾结点
C.各自的第一个元素结点
D.一个表的头结点,另一个表的尾结点
34.二维数组A[20][10]采用列优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为
( 200+(20*9+8)*2=576//首地址应该为200,此时答案为B )
A.574
B.576
C.594
D.580
35.对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是( D )
A.(c,d)
B.(d)
C.b
D.(b)
36.已知一棵树的前序序列为ABCDEF,后序序列为CEDFBA,则对该树进行层次遍历得到的序列为( D )
A.ABCDEF
B.ABCEFD
C.ABFCDE
D.ABCDFE
37.在一个长度为n的顺序存储的线性表中,删除第i个元素(1<=I<=n)时,需要从前向后依次前移(A)个元素。
A、n-i
B、n-I+1
C、n-I-1
D、I
38.假定一个顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为( D)
A、f+1==r
B、r+1==f
C、f==0
D、f==r
39.某带头结点的单链表的头指针为head,判定该链表为非空的条件是( D )
A.head==NULL
B.head->next==NULL
C.head!=NULL
D.head->next!=NULL
40.导致栈上溢的操作是( B )
A.栈满时执行的出栈
B.栈满时执行的入栈
C.栈空时执行的出栈
D.栈空时执行的入栈
41.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中,其中根结点存放在BT[0],若BT[i]中的结点有左孩子,则左孩子存放在( D )
A. BT[i/2]
B. BT[2*i-1]
C. BT[2*i]
D. BT[2*i+1]
42.连通图是指图中任意两个顶点之间( A )
A.都连通的无向图
B.都不连通的无向图
C.都连通的有向图
D.都不连通的有向图
三、名词解释
1.描述线性表中三个概念的区别:头指针、头结点、首元结点(第1个元素结点)。
2.满二叉树、完全二叉树、二叉排序树、平衡二叉树
3.连通图、强连通图
4.哈希表,广义表,线性表
5.内排序与外排序
四 .填空:
1.已知完全二叉树的第8层有8个结点,则其叶子结点数是68。68+8-4 2.将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中,已知每个元素占4个单元,则A[7,5]的地址是1100 。
3.有n个顶点的强连通有向图G至少有n 条弧。
4.有n个结点并且其高度为n的二叉树的数目是2^(n-1)。
5.高度为8的平衡二叉树的结点数至少是54 。
6.3个结点可构成5 棵不同形态的树。
7.某算法需要的辅助空间为s(n)=10log2n+2000/n+5,则该算法的空间复杂度为_______O(log2n)________。
8.在n个结点的单链表中,在P指向的结点之后插入一个结点的时间复杂度为_________O(1)______。
9.设SQ为循环队列,存储在数组d[m]中,则SQ出队操作对其队头指针front 的修改是______(front+1) mod m_________。
10.串中所含字符个数称为该串的_____串长__________。
11.tail(tail(a,b))=_____()__________。
12.n(n>0)个结点二叉树对应的森林最多包含____n___________棵非空树。
13.深度为n(n>0)的二叉树最多有_____2n-1__________个结点。
14.n(n>0)个结点、(n-1)条边的连通无向图中,顶点度数最大值为___n-1____________。
15.堆排序的空间复杂度______O(n)_________。
16.一棵深度为5,18个结点的完全二叉树,编号为10的结点的右儿子的编号空,其双亲结点的编号为5。
17.在一棵有14个结点的完全二叉树中,所含叶子结点的数目为7个。
在一棵有k个结点的完全二叉树中:设n0为叶子节点数,n1为度为1的节点数,n2为度2的节点数,则有:
k为奇数时: n1=0,n2=(k-1)/2,n0=(k+1)/2
k为奇数时: n1=1,n2=(k-2)/2,n0=k/2
18.已知在结点个数大于1的单循环链表中,指针p指向表中某个结点,则下列程序段执行结束时,指针q指向结点*p的_____前驱______结点。
q=p;
while(q->next!=p) q=q->next;
19、在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为p->next。
20、假定一棵树的广义表示为 A(B(C,D(E,F,G),H(I,J))),则树中所含的结点数为10 个,树的深度为 4 ,树的度为3。
21. 已知完全二叉树T的第5层只有7个结点,则该树共有___11_________个叶子结点。
22 在有向图中,以顶点v为终点的边的数目称为v的_____入度_______。
23. 产生冲突现象的两个关键字称为该散列函数的____同义词________。
24.在有n个叶子结点的哈夫曼树中,总结点数是__2n-1_____。
25.一棵树T采用二叉链表存储,如果树T中某结点为叶子结点,则在二叉链表BT中所对应的结点一定___没有左子树____。
26、假定一个二叉树广义表表示为a(b(c),d(e,f(,g))),分别写出对它进行
先序、中序、后序、按层遍历的结果。
先序:abcdefg
中序:cbaedfg
后序: cbegfda
按层:abdcefg
27.已知指针P指向双向链表的中间结点,填空:
结点的结构定义为:
typedef struct {
type data;
struct Node * pre, next; /*pre指向前驱,next指向后继*/
} Node
1)在P结点后插入S结点的语句序列是:s->pre=p;s->next=p->next;
p->next->pre=s; p->next=s;
2)在P结点前插入S结点的语句序列是:s->next=p; s->pre=p->pre;
p->pre->next=s; p->pre=s;
3)删除P结点的直接后继结点的语句序列是:
p->next->next->pre=p;p->next=p->next->next;
删除P结点的直接前驱结点的语句序列是是:p->pre->pre->next=p;p->pre=p->pre->pre
五、综合题
1.图1是用邻接表存储的图,画出此图,并写出从C点开始按深度优先遍历该
图的结果。(CDEABF)
2.判别下面的一个序列是否为堆。如果不是,则把它调整为堆,画出生成堆的调整过程(要求记录交换次数最少,且堆顶元素为最小值)。
(12,70,48,86,24,56,30,92,65,38)
(12,70,48,86,24,56,30,92,65,38)不是堆,
过程:1.(12,70,48,86,24,56,30,92,65,38)
2. (12,70,48,65,24,56,30,92,86,38)
3. (12,70,30,65,24,56,48,92,86,38)
4. (12,24,30,65,38,56,48,92,86,70)
3.有一个完全二叉树按层次顺序存放在一维数组中,如下所示:
请指出结点P的父结点,左子女,右子女。
P的父结点A,左子女Z,右子女为空
4.请画出下面的广义表所对应的有向图。
K 1(a,K
2
(a, b), K
3
(c, d), K
4
(c, d))
6.若杂凑表的地址范围为[0:9],杂凑函数为H(key)=(key*2+2) MOD 10,并且采用线性探测方法处理冲突,请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后,该杂凑表的状态。
4,9,5, 空,6,1,7,2 ,3,8
7.已知图G=(V,E),其中:
V={a,b,c,d,e},
E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。
(1)画出图G;
(2)画出图G的邻接表。
8.设有一个顺序栈S,元素s1, s2, s3, s4, s5, s6依次进栈,如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1,则顺序栈的容量至少应为多少?(3)
9.设有一个线性表 (e
0, e
1
, …, e
n-2
, e
n-1
) 存放在一个一维数组A[arraySize]
中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的
前n个原址内容置换为 (e
n-1, e
n-2
, …, e
1
, e
)。
算法:
void inverse ( Type A[ ], int n ) {
Type tmp;
for ( int i = 0; i <= ( n-1 ) / 2; i++ ) {
tmp = A[i]; A[i] = A[n-i-1]; A[n-i-1] = tmp;
}
}
10.设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链接方向逆转,如下图所示。要求逆转结果链表的表头指针h 指向原链表的最后一个结点。
【解答1】
void Inverse ( ) {
if ( first == NULL ) return;
ListNode *p = first->link, *pr =NULL;
while ( p != NULL ) {
first->link = pr;//逆转first指针
pr = first; first = p; p = p->link;//指针前移
}
first->link = pr;
}
【解答2】
void Inverse ( ) {
ListNode *p, *head = new ListNode ;//创建表头结点, 其link域默认为NULL
while ( first != NULL ) {
p = first; first = first->link;//摘下first 链头结点
p->link = head->link; head->link = p; //插入head链前端
}
first = head->link; delete head; //重置first, 删去表头结点
}
11. 写出下列程序段的输出结果( 栈的元素类型为char )
void main()
{
stack s;
char x=‘c’,y=‘k’;
InitStack(s);
push(s,x); push(s,’a’); push(s,y);
pop(s,x); push(s,’t’); push(s,x);
pop(s,x); push(s,’s’);
while ( ! StackEmpty(s) )
{ pop(s,y); printf(y); }
printf(x);
}
stack
12. 设二维数组A[m][n]按行优先存放,元素A[i][j]位置 LOC( i, j ) = x, 每个元素占用 d 个存储单元,则元素A[p][q]位置 LOC( p, q ) = ?
[ (p-i)*n+(q-j) ]*d +x
13.画出下列广义表的图形表示和它们的存储表示:
(1) D(A(c), B(e), C(a, L(b, c, d)))
(2) J1(J2(J1, a, J3(J1)), J3(J1))
14.下面函数diff的功能是:根据两个由整数(都大于-32768)按升序构成的单链表L1和L2(分别由A,B指向)构造一个单链表L3(由*r指向),要求L3中的所有整数都是L1并且不是L2中的整数,还要求L3中的所有整数都两两不等。在空缺处填上适当字句,使其能正确工作。
#include
typedef struct node {
int d;
struct node *next
} Node;
void diff (Node *A, Node *B, Node **r)
{
int lastnum;
Node * p;
*r=NULL;
if(!A)return;
while(_____________)
if (A->d < B->d)
_____________;
p=(Node*) malloc (sizeof(Node));
p->d=lastnum;
p->next=*r,_____________;
do A=A->next;while(_____________);
}
else if (A->d > B->d)
B=B->next
else {
_____________;lastnum=A->d;
while (A&&A->d==lastnum)A=A->next;
}
while (A) {
lastnum=A->d;
p=(Node*) malloc (sizeof(Node));
p->d=lastnum;
_____________,*r=p;
while (A&&A->d==lastnum) A=A->next;
}
}
15.设带表头结点的双向链表的定义为
typedef int ElemType;
typedef struct dnode { //双向链表结点定义
ElemType data; //数据
struct dnode * lLink, * rLink; //结点前驱与后继指针
} DblNode;
typedef DblNode * DblList; //双向链表
16.试设计一个算法,改造一个带表头结点的双向链表,所有结点的原有次序保持在各个结点的右链域rLink中,并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。
算法如下:
void sort( DblNode * L ){
DblNode * s=L->rlink;
第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.组成数据的基本单位是() (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.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度参考答案: 选择题1. C 2.C 3. C 4. A、B 5. C 6.C、B
人生难得几回搏,此时不搏更待何时? 第1章绪论 1.1 简述下列术语:数据 数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型 解:数据是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的基本单位 在计算机程序常作为一个整体进行考虑和处理 数据对象是性质相同的数据元素的集合 是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 存储结构是数据结构在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 解:抽象数据类型包含一般数据类型的概念 但含义比一般数据类型更广、更抽象 一般数据类型由具体语言系统部定义 直接提供给编程者定义用户数据 因此称它们为预定义数据类型 抽象数据类型通常由编程者定义 包括定义它所使用的数据和在这些数据上所进行的操作 在定义抽象数据类型中的数据部分和操作部分时 要求只定义到数据的逻辑结构和操作说明 不考虑数据的存储结构和操作的具体实现 这样抽象层次更高 更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中
试按图论中图的画法惯例画出其逻辑结构图 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数) 解: ADT Complex{ 数据对象:D={r i|r i为实数} 数据关系:R={
第一章绪论 一、选择题 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.算法的五个重要特性是_______、_______、______、_______、
清华数据结构习题集答案(C语言版严蔚敏) 第1章绪论 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解:
试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i为实数} 数据关系:R={
《一定能摸到红球吗?》说课稿 林银花 一、教材说明: 1、课题:《一定能摸到红球吗?》 2、本节内容的地位和作用 在现代社会中,人们面临着更多的机会和选择,常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. 3、教学目标设计: (1)认知目标: (A)经历猜测.实验.收集与分析试验结果等过程 (B)体会事件的发生的不确定性知道事情发生的可能性有多大。 (2)、能力目标: (A)经历游戏等的活动过程,初步认识确定事件和不确定事件 (B)在与其它人交流的过程中,能合理清晰地表达自己的思维过程; (3)、情感目标: (A)通过创设游戏情境,让学生主动参与,做“数学实验”,激发学生学习的热情和兴趣,激活学生思维。 (B)在与他人的合作过程中,增强互相帮助、团结协作的精神。 (C)体会到在生活中我们可以从确定和不确定两方面分析一件事情. 4、本课重点、难点分析: 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析: 1、初一学生性格开朗活泼,对新鲜事物特别敏感,且较易接受,因此,教学过程中创设的问题情境应较生动活泼,直观形象,且贴近学生的生活,从而引起学生的有意注意。 2、初一学生的概括能力较弱,推理能力还有待不断发展,所以在教学时,可让学生充分试验,收集,分析,帮助他们直观形象地感知。 3、初一学生已经具备了一定的学习能力,所以本节课中,应多为学生创造自主学习、
、 清华数据结构习题集答案(C 语言版严蔚敏) 第1章 绪论 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 : 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: : 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={
1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x 第一章绪论 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x 数据结构(C语言版)(第2版) 课后习题答案 李冬梅 2015.3 目录 第1章绪论 0 第2章线性表 (4) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (42) 第7章查找 (54) 第8章排序 (65) 第1章绪论 1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案: 数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构:数据对象在计算机中的存储表示,也称为物理结构。 抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案: 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。 即相同的逻辑结构,可以对应不同的存储结构。 第1章 绪论 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={ 清华数据结构习题集答案(C 语言版严蔚敏) 第1章 绪论 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={ 第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 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 1.5 试画出与下列程序段等价的框图。 (1) product=1; i=1; while(i<=n){ product *= i; i++; } (2) i=0; do { i++; } while((i!=n) && (a[i]!=x)); (3) switch { case x 保持平常心,营造好环境,扬起常笑脸,轻松迎高考。 第1章绪论 1.1 简述下列术语:数据 数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型 解:数据是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 数据对象是性质相同的数据元素的集合 是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 存储结构是数据结构在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 解:抽象数据类型包含一般数据类型的概念 但含义比一般数据类型更广、更抽象 一般数据类型由具体语言系统内部定义 直接提供给编程者定义用户数据 因此称它们为预定义数据类型 抽象数据类型通常由编程者定义 包括定义它所使用的数据和在这些数据上所进行的操作 在定义抽象数据类型中的数据部分和操作部分时 要求只定义到数据的逻辑结构和操作说明 不考虑数据的存储结构和操作的具体实现 这样抽象层次更高 更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中 试按图论中图的画法惯例画出其逻辑结构图 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数) 解: ADT Complex{ 数据对象:D={r i|r i为实数} 数据关系:R={ 数据结构习题集答案C语 言版严蔚敏 This model paper was revised by the Standardization Office on December 10, 2020 第1章绪论 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={ 第1章绪论 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={ 第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 Co mpl ex{ ?数据对象:D={r,i |r,i为实数} 数据关系:R={<r,i>} 基本操作: ? I nitC om ple x(&C,re ,im) 操作结果:构造一个复数C,其实部和虚部分别为re 和im ? ?DestroyCmoplex(&C) 操作结果:销毁复数C ?Get(C ,k,&e) ? 操作结果:用e 返回复数C 的第k 元的值 ? Put(&C,k,e) ??操作结果:改变复数C 的第k 元的值为e IsAs cen di ng(C) ??操作结果:如果复数C 的两个元素按升序排列,则返回1,否则返回0 《数据结构(C语言版第2版)》(严蔚敏著) 第一章练习题答案 第1章绪论 1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、 抽象数据类型。 答案: 数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。 如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声 音、动画等通过特殊编码定义后的数据。 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况 下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录, 树中棋盘的一个格局(状态)、图中的一个顶点等。 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表 中的学号、姓名、性别等都是数据项。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合 N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…, ‘z’},学生基本信息表也可是一个数据对象。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是 带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据 的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构:数据对象在计算机中的存储表示,也称为物理结构。 抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组 操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集 合。 2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案: 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本 信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对 于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的 结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻 辑结构,即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示) 来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用 指针进行链接,则称为链式存储结构。 即相同的逻辑结构,可以对应不同的存储结构。 3.简述逻辑结构的四种基本关系并画出它们的关系图。 答案:严蔚敏数据结构习题集答案
数据结构(C语言版)第2版习题答案—严蔚敏
数据结构-习题集答案-(C语言版严蔚敏)
清华数据结构习题集答案C语言版严蔚敏
数据结构习题集(C语言版严蔚敏)第一二三章
数据结构习题集答案(C语言版严蔚敏)
数据结构习题集答案C语言版严蔚敏
严蔚敏版数据结构课后习题答案-完整版
数据结构习题集答案(C语言版严蔚敏)
《数据结构(C语言版 第2版)》(严蔚敏 著)第一章练习题答案