数据结构练习1

综合练习

一、全面复习所要求的课程内容和所做过的作业题

（以下是题型示例。要掌握各种结构的基本概念和基本原理，学会各种结构的灵活应用）二、填空

1、连通图是指任意两个结点之间都有路径的图。

2、对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素，在队头删除元素。

3、线性表中数据元素的个数称为线性表的长度。

4、删除带头结点的单链表L中的第一个元素结点的语句是head->next=head->next->next; 。

5、有向图G用邻接矩阵A[ n ][ n ]存储，结点i的入度是矩阵A[][]中第i列权值在0~MaxWeight 之间的元素个数的和。

6、所有结点的前驱和后继的个数都没有限制的数据结构是图结构。

7、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是___0~n(n-1)/2_______条。

8、具有10个结点的无向图边的总数最多为45 。

9、在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head = = p->next->next 。

10、栈顶的位置是随着出栈操作而变化的。

11、从任何一个结点开始都能成功查找其他结点的单链表是循环单链表。

12、满二叉树里，分支结点（非树叶结点）个数等于树叶的个数减1 。

13、任何包括n个结点的二叉树的二叉链存储表示中，2n 个指针中只有n-1 个用来指示结点的左右孩子，而另外n+1 个为空指针。

14、一个不带权的无向图采用邻接矩阵存储方法，其邻接矩阵是一个____对称______矩阵。

15、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着

一对一、一对多和多对多的关系。

16、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有33 个。

17、一棵哈夫曼树有19个结点，则其叶子结点的个数是_____10_______。

18、设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳___4__个元素。

19、假设以S和X分别表示进、出栈操作，则对输入序列a、b、c、d、e进行一系列栈操作SSXSXSSXXX 之后，得到的输出序列为bceda 。

20、无向图中的极大连通子图称为该无向图的连通分量。

三、选择

1、判定一个循环队列QU（最多元素为m）为满队列的条件是 B 。

A、QU.front = = QU.rear

B、QU.front = = (QU.rear + 1) % m

C、QU.front != QU.rear

D、QU.front != (QU.rear + 1) % m

2、在数据结构中，从逻辑上可以把数据结构分成C 。

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、内部结构和外部结构

3、带头结点的单链表head为空的判定条件是 B 。

A、head = = NULL

B、head -> next = = NULL

C、head != NULL

D、head -> next != NULL

4、有n个结点的二叉树采用二叉链表存储结构，该链表中共有 D 个指针域用于链接孩子结点。

A、n

B、2n

C、n+1

D、n-1

5、一个有n个结点的无向图最多有 A 条边。

A、n(n-1)/2

B、n(n-1)

C、2n

D、n

6、在一非空二叉树的中序遍历序列中，根结点的左边 D 。

A、只有右子树上的部分结点

B、只有左子树上的部分结点

C、只有右子树上的所有结点

D、只有左子树上的所有结点

7、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为 D 。

A、front = front + 1

B、front = ( fron + 1 ) % ( m – 1 )

C、front = (front - 1 ) % m

D、front = ( front + 1 ) % m

8、在含n个结点和e条边的无向图邻接矩阵中，零元素的个数为 D 。

A、e

B、2e

C、n2 - e

D、n2 - 2e

9、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的(3)

①A、B、C、D、E ②B、C、D、E、A

③E、A、B、C、D ④D、C、B、A、E

10、与链表不相适宜的叙述是 D 。

A、动态存储分配

B、可表示任何类型的数据结构

C、插入和删除操作灵活

D、查找速度快

11、若长度为n的线性表采用顺序存储结构，删除它的第i个数据元素需要依次向前移动__A____个数据元素。

A、n - i

B、n + i

C、n - i - 1

D、n - i + 1

12、在一个单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 D 。

A、q -> next = p -> next ; p -> next = q ;

B、p -> next = q -> next ; q = p ;

C、q -> next = p -> next ; p -> next = q ;

D、p -> next = q -> next ; q -> next = p ;

13、链式栈与顺序栈相比，一个比较明显的优点是 B 。

A、插入操作更加方便

B、通常不会出现栈满的情况

C、不会出现栈空的情况

D、删除操作更加方便

14、下列有关线性表的叙述中，正确的是 A 。

A、线性表中的元素之间是线性关系

B、线性表中任何一个元素有且仅有一个直接前趋

C、线性表中至少有一个元素

D、线性表中任何一个元素有且仅有一个直接后继

15、以数组Q[m]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是 D 。

A、( rear – qulen ) % m

B、( rear - qulen + m ) % m

C、( m – qulen ) % m

D、1 + ( rear + m – qulen ) % m

16、设结点x和结点y是二叉树T中的任意两个结点，若在前序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是 C 。

A、x是y的左兄弟

B、x是y的右兄弟

C、x是y的祖先

D、x是y的后代

17、已知某二叉树的前序遍历序列是ABDC，中序遍历序列是DBAC，它的后序遍历序列是

(2) 。

①ABCD ②DBCA ③BCAD ④CABD

18、对线性表L适合于使用链式存储结构的是 B 。

A、L中含有大量结点

B、需不断对L进行插入删除

C、需经常修改L中结点值

D、需经常访问L中数据元素

19、一棵满二叉树同时又是一棵 C 。

A、无序树

B、哈夫曼树

C、完全二叉树

D、度为2的树

20、按照二叉树的定义，具有3个结点的二叉树有 B 种不同形状。

A、4

B、5

C、6

D、7

四、简要回答下列问题

1、在顺序表上如何进行插入、删除操作？在单链表上又如何进行？

2、循环单链表有何特点？

3、线性表的两种存储结构——顺序结构和链式结构各有哪些优缺点？

4、为什么队列又称为先进先出表？堆栈？

5、为什么在顺序队列中可能会出现假溢出现象？

6、分别简述顺序堆栈和链式堆栈元素进栈、出栈的基本步骤。

7、分别简述顺序队列和链式队列元素进队、出队的基本步骤。

8、为了区分顺序循环队列的队空和队满情况，通常可以采用哪些方法？怎样区分？

9、什么是树中结点的度、树的度？

10、如果用双亲表示法存储一棵树，如何找到编号为i的结点的双亲和孩子结点？孩子表示法？

11、什么叫满二叉树？什么叫完全二叉树？

12、将一棵有n个结点的完全二叉树按层次顺序对所有结点从0开始编号，如何求编号为i的结点的双亲、左右孩子？若是一棵一般二叉树情况又怎样？

13、简述层序遍历二叉树的算法基本步骤。

14、简述非递归的二叉树前序遍历算法的基本步骤。

15、如何构造哈夫曼树？

16、如果图用邻接矩阵存储怎样判断两点是否为邻接点？用邻接矩阵存储又怎样？

17、如果有向图G用邻接矩阵、邻接表存储，分别如何求得结点i的出度和入度？无向图？

18、为什么说图的遍历比树的遍历复杂？

19、分别简述图的深度和广度优先遍历算法的基本思想。

20、从初始结点出发一定能遍历全图吗？为什么？

五、应用题

1、根据问题写相关的几个语句（如：在一个链式队列中，队首和队尾指针分别为front和rear，现要插入由s所指向的结点，给出应该执行的几步操作。分别对无头结点和有头结点的情况解答。）

2、画结构图（如某树的双亲表示法、孩子表示法等对应的结构图。）

3、完成相应的操作

（如：（1）某二叉树的结点数据采用顺序存储表示如下：

画出该二叉树的图形表示；写出该二叉树的前序、中序和后序遍历结点序列；将此二叉树看作森林的二叉树表示，试将它还原为森林。

（2）若对某二叉树前序遍历结点序列为ABDGCEFH，中序遍历的结点访问顺序是DGBAECHF，画出该二叉树的图形表示，画出它的顺序存储结构图、二叉链存储结构图、仿真二叉链存储结构图。

（3）根据给定的权集合设计哈夫曼树和哈夫曼编码。

（4）对应某图（有向、无向）写出它的邻接链表（邻接矩阵），据此给出由某点起始的深度优先遍历序列和广度优先遍历序列。对应某无向连通网写出它的邻接矩阵（邻接表），给出利用Kruskal算法、Prim算法生成最小生成树的过程。）

4、作业中的题型

六、算法设计题

1、关于单链表的基本操作（如：已知一带头结点的单链表头指针为head，设计一算法求出该单链表中结点的个数）。

2、关于链式堆栈的基本操作

3、关于链式队列的基本操作

4、关于二叉树的遍历操作

（假设结点结构都为

，其data域为整型，要求:定义所用结构、用程序设计语言描

述算法。）

上述各问题要分清带头结点和不带头结点的结构在设计算法时的不同。

数据结构单元练习4

单元测验4 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）队列是限制在两端进行操作的线性表。 （√）（2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 （×）（3）在链队列上做出队操作时，会改变front指针的值。（√）（4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。 （×）（5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。 （√）（6）链队列在一定范围内不会出现队满的情况。 （×）（7）在循环链队列中无溢出现象。 （×）（8）栈和队列都是顺序存储的线性结构。 （×）（9）在队列中允许删除的一端称为队尾。 （×）（10）顺序队和循环队关于队满和队空的判断条件是一样的。 二．填空题 （1）在队列中存取数据应遵循的原则是先进先出。（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 （3）在队列中，允许插入的一端称为队尾。 （4）在队列中，允许删除的一端称为队首（或队头）。（5）队列在进行出队操作时，首先要判断队列是否为空。 （6）顺序队列在进行入队操作时，首先要判断队列是否为满。 （7）顺序队列初始化后，front=rear= -1 。 （8）解决顺序队列“假溢出”的方法是采用循环队列。（9）循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front == rear 。

（10）链队列LQ为空时，LQ->front->next= NULL 。（11）设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O（n）。 （12）设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0（1）。 （13）在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。 （14）设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间 为MAXLEN，则队满标志为： front==(rear+1)%MAXLEN 。 （15）在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为： front==rear && front !=NULL 。 ( 或front==rear && front <>NULL ) （16）向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。（17）读队首元素的操作不改变（或不影响）队列元素的个数。 （18）设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。 （L= (N＋rear－front)% N=（40＋19－11）% 40=8）（19）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0 。 （20）队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。 三．选择题 （1）队列是限定在（ D ）进行操作的线性表。

数据结构试题及答案10套

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）

数据结构练习题(含答案)

数据结构练习题(含答案)

数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输 入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂

性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序 复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ ,

数据结构试卷带答案

数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s

数据结构单元练习参考答案

单元测验4 一．判断题<下列各题，正确的请在前面的括号内打√；错误的打╳） <√）<1）队列是限制在两端进行操作的线性表。 <√）<2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。 <×）<3）在链队列上做出队操作时，会改变front指针的值。 <√）<4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。 <×）<5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。 <√）<6）链队列在一定范围内不会出现队满的情况。 <×）<7）在循环链队列中无溢出现象。 <×）<8）栈和队列都是顺序存储的线性结构。 <×）<9）在队列中允许删除的一端称为队尾。 <×）<10）顺序队和循环队关于队满和队空的判断条件是一样的。 二．填空题 （1）在队列中存取数据应遵循的原则是先进先出。 （2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 （3）在队列中，允许插入的一端称为队尾。 （4）在队列中，允许删除的一端称为队首<或队头）。 （5）队列在进行出队操作时，首先要判断队列是否为空。 （6）顺序队列在进行入队操作时，首先要判断队列是否为满。 （7）顺序队列初始化后，front=rear= -1 。 （8）解决顺序队列“假溢出”的方法是采用循环队列。 循环队列的队首指针为front，队尾指针为rear，则队空的条件为front == rear 。 （10）链队列LQ为空时，LQ->front->next= NULL 。 （11）设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O%MAXLEN 。

空间数据结构

空间数据结构 摘要：空间数据模型和空间数据结构是地理信息系统（GIS）课题的中心内容。本文对空间数据结构的定义、分类进行了一定的研究性的归纳与总结。 关键词：空间数据结构，矢量数据，栅格数据 引言 GIS中空间数据结构和空间数据模型是紧密相关的。数据模型的建立必须通过一定的数据结构，但两者之间也有非常大的区别。数据模型是一个总得概念，是人为概念化的真实，是对现实世界的提取，对现实世界的认识和选择。而数据结构指数据元素之间的相互关系，它是软件常规内涵，根据空间数据结构和数据模型的特点及其关系，可以建立空间数据库系统。 空间数据结构定义 空间数据结构是带有空间数据单元的集合。这些数据单元是数据的基本单 位，一个数据单元可以有几个数据项组成，数据单元之间存在某种联系叫做结构。 所以，研究空间数据结构，是指空间目标间的相互关系，包括几何和非几何的关 系，数据结构是数据模型的表述，数据结构往往通过一系列的图表和矩阵，以及 计算机码的数据记录来说明。 空间数据结构的分类 矢量数据结构 定义 矢量数据结构是基于矢量模型，利用欧几里得(EUCLID)几何学中的点、线、 面及其组合体来表示地理实体的空间分布，是通过记录坐标的方式，尽可能精确 地表示点线多边形等地理实体，自然地理实体的位置是用其在坐标参考系中的空 间位置来定义的，坐标空间设为连续，允许任意位置长度和面积的精确定义，其 特点是定位明显，属性隐含。 GIS采用的矢量数据结构模型，是将空间地质实体抽象成点、线、面三种几 何要素，矢量数据结构通过优化拓扑结构表达空间实体的相关关系，为空间数据 库建立基本框架。 矢量数据结构的特点 优点：数据按照点、线或多边形为单元进行组织，结构简单、直观、易实现 以实体为单位的运算和显示。 缺点：

数据结构试卷带答案

数据结构试卷带答案 问题说明 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。

（13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟

数据结构题库教材

2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12

3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。

数据结构练习试题和答案解析

第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点．

数据结构试题及答案

第一章概论 一、选择题 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

数据结构相关题库及答案

第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next

数据结构习题及答案-第1章 绪论

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 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) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1]

数据结构试卷B卷(含答案)

《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈 只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

【精选】数据结构单元10练习参考答案

单元测验10 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （ㄨ）（1）如果某种排序算法不稳定，则该排序方法就【没】有实用价值。 （√）（2）希尔排序是不稳定的排序。 （ㄨ）（3）冒泡排序是【不】稳定的排序。 （√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。 （ㄨ）（5）堆排序所需的时间与待排序的记录个数【无】有关。 （√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。 （ㄨ）（7）快速排序不是在任何情况下都比其它排序方法速度快。 （√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。 （√）（9）采用归并排序可以实现外排序。 （√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高 （√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。 （√）（12）冒泡排序的时间复杂度是O（n2）。 二．填空题 （1）大多数排序算法都有两个基本的操作：比较和移动。 （2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。 （3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。 （5）对n个关键字进行冒泡排序，其可能的最小比较次数为：n-1次。 （6）在最坏情况下，在第i趟直接插入排序中，要进行i-1次关键字的比较。 （7）对n个关键字进行冒泡排序，时间复杂度为 O(n2) 。 （8）快速排序在最坏情况下的时间复杂度是 O(n2) 。 （9）对于n个记录的集合进行归并排序，所需要的平均时间为： O(log2n) 。 （10）对于n个记录的集合进行归并排序，所需要的附加空间是 O(n) 。 （11）若原始数据接近无序，则选用快速排序最好。 （12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。 （13）在插入排序和选择排序中，若初始数据基本正序，则选用插入排序较好。 （14）当增量为1时，该趟希尔排序与直接插入排序基本一致。 （15）第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。（16）依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。（17）在插入排序、选择排序和归并排序中，排序是不稳定的为：选择排序。 （18）在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。

数据结构试题(含答案)

数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。

数据结构题库汇总

数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j

数据结构单元1练习参考答案

单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。 （3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。 （9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。（14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。（18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O（nlog2n）。（19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O（n2）。（20）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。