《数据结构》练习测试题
一．选择题
1．在数据结构中，从逻辑上可以把数据结构分成（C ）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构
C．线性结构和非线性结构D．内部结构和非内部结构
2．若频繁地对线性表进行插入和删除操作，该线性表应该采用（C ）存储结构。
A．散列 B.顺序 C.链式 D.任意
3．若删除非空线性链表中由p所指链结点的直接后继结点的过程是依次执行(B ) A．r=p->next; p->next=r; call RET(r)
B．r=p->next; p->next=r->next; call RET(r)
C．r=p->next; p->next=r->next; call RET(p)
D．p->next=p->next->next; call RET(p)
4．下面的说法中，不正确的是（D ）。
A．只须存放对称矩阵中包括主对角线元素在内的下(或上)三角部分的元素即可
B．只须存放对角矩阵中的非零元素即可
C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储
D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储
5．串的长度是( D )。
A．串中不同字母的个数
B．串中不同字符的个数
C．串中所含字符的个数，且大于0
D．串中所含字符的个数
6．一个栈的人栈序列是a，b，c，d，e，则栈的不可能的输出序列是( C )。
A．edcba B．decba C．dceab D．abcde
7．广义表的长度是指（A ）
A，广义表中元素的个数 B。广义表中原子元素的个数
C．广义表中表元素的个数 D．广义表中括号嵌套的层数
8．某非空二叉树的前序序列和后序序列正好相反，则二叉树-定是( B )的二叉树。
A.空或只有一个结点 B．高度等于其结点数
C.任一结点无左孩子 D．任一结点无右孩子
9. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( A )。
A．n B．n+1 C．n-l D．n十e
10．在计算递归函数时，若不用递归则应借助数据结构( D )。
A. 数组
B. 队列
C. 链表
D. 栈
11．算法分析的目的是（C ）；
Ａ. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易懂性和文档性
12．在一个长度为n 的顺序表中，向第i个元素（1≤i≤n＋１）之前插入一个新元素时，需要向后移动（C ）个元素。
A.n-i
B.n-i-1
C.n-i+1
D.i
13．在一个双链表中结点p之后插入一个结点s的操作是( C )。
A. s->right=p;s->left=p->right;p->right->left=s;p->right=s
B. s->right=p->right;p->right->left=s;s->right=p;p->left=s
C. s->right=p->right;s->left=p;p->left->left=s;p->right=s
D. s->right=p;p->left->left=s;p->right=s;s->right=p->right
14．若将n阶对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，则该对称矩阵在B中占用了( C )个数组元素。 A．n/2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1)
15．设串s="ABUBG",len(s)返回串s的长度，则len(s)是( C )。
A．2 B．4 C．5 D．6
16．向一个栈顶指针为HS的链栈中插入—个s所指结点时，则执行( C )
A．HS->next=S；B．S->next=HS->next；HS->next=S；
C．S->next=HS；HS=S；D．S->next=HS；HS=HS->next；
17．广义表的深度是指 ( D )
A．广义表中元素的个数B．广义表中原子元素甜个数
C. 广义表中表元素的个数D．广义表中括号嵌套的层数
18．非空二叉树在线索化后，仍不能有效求解的问题是(D )。
A．前序线索二叉树中求前序后继 B．中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前趋 D．后序线索二叉树中求后序后继
19. 一个具有n个顶点的有向图最多有( B )条边。
A．nx(n-1)／2 B．nx(n-1)
C．nx(n+1)／2 D．nxn
20．依次将待排序膨0中的元素和有序子序列合并为一个新的有序子序列的是( A )。
A．插入排序B．冒泡排序 C.快速排序 D．堆排序
21．算法分析的两个主要方面是（B ）。
A. 空间复杂度和时间复杂度
B. 正确性和简单性
C．可读性和文档性 D. 数据复杂性和程序复杂性
22．若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间复杂度是（A）
Ａ.O(n) B.O(n*n) C.O(nlog2n) D.O(log2n)
23．非空的循环单链表head的尾结点（由p所指向）满足（C ）。
A.p->next=NULL;
B.p=NULL;
C.p->next=head;
D.p=head;
24．若将对称矩阵A按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组B中，那么，A中某元素ai(i<0)在B中的位置是( C )。
A．(i*(i-1))／2+j B．(i*(i-1))／2-j
C．(j*(j-1))／2+i D．(j*(j-1))/ 2-i
25．设串sI="ABCDEFG",s2="PQRST",函数con(x,y)返回x和y串的连接串,subs(s，山)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2))的结果串是( D )。
A．BCDEF B．BCDEFG C．BCPQRST n。BCDEFEF
26．中缀表达式A-(B+C／D)*E的后缀形式是( B )。
A．ABC+D／*E- B．ABCD／+E*-
C．AB-C+D／E* D．ABC-+D/E*
27．广义表A：<<)，(a)， A．2 B．3 C．4 D．5 28．对于一组结点，从空树开始，把它们插入到二叉排序树中，就建立了一棵二叉排序树。 这时，整个二叉排序树的形状取决于( A )。 A．结点的输入顺序 B．结点的存储结构 C.结点的取值范围 D．计算机的硬件 29. 导致图的遍历序列不惟一的因素是( D ) A．出发点的不同、遍历方法的不同 B．出发点的不同、存储结构的不同 C．遍历方法的不同、存储结构的不同 D．出发点的不同、存储结构的不同、遍历方法的不同 30．线性表采用链式存储时，其地址( D )。 A. 必须是连续的； B. 部分地址必须是连续的； C. 一定是不连续的； D. 连续与否均可以。 31．在数据结构中，从逻辑上可以把数据结构分成（C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和非内部结构 32．线性表的链式存储结构是一种（ B ）的存储结构。 A．随机存取B．顺序存取C．索引存取D．HASH存取 33．设单循环链表中结点的结构为(date，link)且rear是指向非空的带表头结点的单循环链表的尾结点指针。若想删除链表的第一个结点,则应执行下列哪一个操作?( B ) A. s=rear;rear=rear->link;delete s; B. rear=rear->link;delete rear; C. r ear=rear->link->link;delete rear; D. s=rear->link->link;rear->link->link=s->link;delete s; 34．稀疏矩阵一般的压缩存储方法有两种，即( C )。 A．二维数组和三维数组 B．三元组和散列 C. 三元组和十字链表D．散列和十字链表 35．设串sI="ABCDEFG",s2="PQRST",函数con(x,y)返回x和y串的连接串,subs(s，山)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2))的结果串是( D )。 A．BCDEF B．BCDEFG C．BCPQRST n。BCDEFEF 36．判定一个循环队列QU(最多元素为m0)为满队列的条件是( C ) A．QU->front==QU->rear B．QU->front!=QU->rear C．QU->front==(QU->rear+1)％m0 D．QU->front!=(QU->rear+1)％m0 37．广义表A=(()，(a)，(b，(c，d)))的深度为( B ) A．2 B．3 C．4 D．5 38．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( D )。 A．acbed B．decab C．deabc D．cedba 39. 任何一个带权无向连通图的最小生成树( B )。 A．是唯一的 B．是不唯一的 C．有可能不惟一 D．有可能不存在 40．快速排序在最好的情况下的时间复杂度是( B )。 A．O(n) B．0(nlog2n) C．O(n2) D．0(10g2n) 二．判断题 1. 线性表的逻辑顺序与存储顺序总是一致的。 ( F ) 2. 当字符集中的各字符使用频率不均匀时，等长编码是最优的前缀码。 ( F ) 3. 一个栈的输人序列是1，2，3，4，5，则栈的输出序列有可能式4,3,5,1,2。 ( F ) 4. 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。 ( T ) 5. 顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（ F ） 6. 邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 ( F ) 7. 在二叉树中插入结点则该二叉树便不再是二叉树。 ( F ) 8. 线性表中的数据元素必须具有相同的特性，即属于同一个数据对象，这种线性表称为同质的线性表。（T ） 9. 对二叉树中的结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍 历，遍历所得的结点序列称为二叉树的层次序列。 （T ）10. 任何一个关键活动提前完成，那么整个工程将会提前完成。 （ F ）11. 线性表中的数据元素必须具有相同的特性，即属于同一个数据对象，这种线性表称为同质的线性表。( T ) 12. 在选择排序中，关键字比较的次数与记录的初始排列次序无关。 ( T ) 13. 用循环链表作为存储结构的队列就是循环队列，这种说法是错误的。 ( T ) 14. 任何一棵二叉树中至少有一个结点的度为2。 ( F ) 15. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （F ）16. 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。 ( F ) 17. 队列和栈都是运算受限的线性表。 ( T ) 18. 循环链表判断表尾结点用的条件是该结点的后继指针是看它是否为空指针。 （F ）19. 哈夫曼树是访问叶子结点的外部路径长最长的二叉树。 （F ）20. 外部排序是指在排序的整个过程中，全部数据在计算机的外存储器中完成的排序。 （F ）21.一个直接调用自己或通过一系到的调用语句间接地调用自己的函数，称做递归函数。每 个递归函数必须有一个递归出口。 ( T ) 22. 顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建立的。( F ) 23. 广义表的深度是指广义表中元素的个数。 ( F ) 24. 要访问单链表中的第i个结点，必须从表头开始依次访问过该结点之前的所有结点后才 能够实现，即只能够采用顺序存取，而不能够随机存取任一个结点。 ( T ) 25. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（F ）26. 任何有向网络（AOV-网络）拓扑排序的结果是唯一的。 (T ) 27. 存储无向图的邻接矩阵是对称的，故只存储邻接矩阵的下(或上)三角部分即可。 ( F ) 28. 最先进入队列的数据元素最先推出队列。 （T ）29. n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。 （T ） 30. 快速排序是不稳定的排序算法，希尔排序是稳定的排序算法。（F ） 31.n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。 ( T ) 32. 在一个无向图中，所有顶点的度数之和等于所有边数的2倍。 ( T ) 33. 顺序文件是指文件中的物理记录按其在文件中的逻辑记录顺序依次存入存储介质而建 立的。( F ) 34. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完 成了对该矩阵的转置运算。（T ）35. 图的最小生成树的形状可能不唯一。 （T ） 36. 缩短关键路径上活动的工期一定能够缩短整个工程的工期。 ( T ) 37. 如果某种排序算法是不稳定的，则该方法没有实际的应用价值。 ( F ) 38. 一颗非空树中，有且仅有一个结点没有前驱。 （T ）39. 图的广度优先搜索算法类似于二叉树的前序遍历。 （ F ）40. 键树是一棵度大于2的树。（F ） 三、填空题 1.对于顺序表，当随机插入或删除一处元素时，约需要平均移动表长的一半元 素。 2.稀疏的三元组有_ 连续_列。 3. 堆栈的插入与删除操作都是在_栈顶_位置进行的，而队列的插入在_队尾_进行，删除在_队头_ 进行。 4.具有100个结点的完全二叉树的深度为___7___。 5.试写出如下所示的无前驱顶点优先算法求得的拓扑序列为V0 V1V5V2V3V6V4 _，无后继顶点优先算法求得的拓扑序列为_ V4 V6 V3 V2 V5 V1 V0_ _。 6.根据形成探查序列的不同，可以将开放地址法区分为：_线性探查法_,_二次探查法 __和__双重探查法__。 7.一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_ n*n _。 8. 在一个小根堆中，堆顶结点的值是所有结点中的最小值，在一个大根堆中，堆 顶结点的值是所有结点中的最大值。 9. 栈又称为先进后出表，队列又称为先进先出表。 10.已知一棵二叉树有50个叶子结点，则该二叉树总的结点个数至少是_ 99 _。 11. 删除由list所指的非空线性链表的第一个结点的操作是将list改为指向第二个结点， 然后释放第一个结点的空间 12. 稀疏的三元组中,第2列存储的是稀疏数组中非零元素所在的__列数_。 13. 在栈顶指针为HS的链栈中，判定栈空的条件是_ HS==NULL _。 14.已知一棵二叉树有50个叶子结点，则该二叉树总的结点个数至少是_ 99 _。 15.在一个具有n个顶点的无向完全图中，包含有_ n(n-1)/2 _条边，在一个具有n 个顶点的有向完全图中，包含有n(n-1) 条边。 16.键树的存储结构为_ 双链树_和_ Tire树。 17.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_ O(1) _，在表尾插入元素的时间复杂度为_ O(n) _。 18. 快速排序在平均情况下的时间复杂度为O(nlog(n)) ，在最坏情况下的时间 复杂度为O(n2) 。 19. 一棵深度为5的满二叉树中的结点数为25-1 个，一棵深度为3的满四叉树中的结点数为43-1 个。 20.树的存储结构分为_双亲链表表示法，孩子链表表示法，_孩子兄弟链表表示法 _，而二叉树的存储结构分为_ 顺序存储_，_链式存储_。 21.在双链表中，每个结点有两个指针域，一个指向_前驱结点_，另一个指向_后续结点。 22.二维数组A[10Ⅱ20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的 存储地址是200,则A[6][2]的地址是_ 332_。 23. 堆栈和队列都是特殊的线性表，其特殊性是_操作仅是一般线性表操作的子集，并且操作的位置受到限制_。 24.在顺序存储的二叉树中，编号为i和j的两个结点处于同一层的条件是_ [log2i=log2j] 。 25.表示图的三种存储结构为_邻接矩阵_、_邻接表_和_ 邻接多重表。 26.直接存取文件是用_ 哈希__的方法组织的。 27.构成抽象数据类型的三个要素为：_数据对象、_数据结构和_ 数据操作_。 28. 假设带头结点的单循环链表中头指针L指向链表中最后一个结点，则在第一个结点之前 插入指针s 所指结点的语句组是s->next=L->next; L->next=s 。 29. 栈又称为先进后出表，队列又称为先进先出表。 30.键树的存储结构为_ 双链树和_ Tire树。 31.己知一个图的邻接矩阵表示，计算第i个结点的人度的方法是_ 求矩阵第i 列非零元素之和_。 32.在散列技术中，处理冲突的方法有：_开放定址法_和_ 拉链法_。 33.根据形成探查序列的不同，可以将开放地址法区分为：_线性探查法_,_二次探查法__和 __双重探查法 34.中缀形式的算术表达式A+(B-C／D)XE的后缀形式是ABCD／-EX+ _。 35.若某线性表采用顺序存储结构，每个数据元素占用k个存储单元，第一个数据元素的存 储地址为LOC（a1）,则第I 个数据元素的存储地址LOC（ai）=___ LOC(a1)+(I-1)*k。 36.判定一个双链表的结点p为第一个结点的条件是__ p->left=NULL_ __。 37.二维数组A[10Ⅱ20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的 存储地址是200,则A[6][2]的地址是_ 332_。 38. 具有100个结点的完全二叉树的深度为_ 7 _。 39. 有向图进行拓扑排序的两种方法是无前趋的顶点优先_和_无后继的顶点优先。 40.已知一个待排序的序列已基本有序，则在直接选择排序、堆排序、快速排序和直接插入 排序中最省时间的是_直接插入排序_。 四、简答题 1. 请分别简答顺序存储结构与链式存储结构的构造原理以及它们的特点。 答：线性表的顺序存储结构是在存储器中用一片地址连续的存储单元依次存放线性表中的数据元素，数据元素之间的逻辑关系通过数据元素的存储地址直接反映。在这种存储结构中，逻辑上相邻的两个数据元素在物理位置上也一定相邻。 2. 对二叉树中的结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。 【解答】 3. 已知无向图G=(V,E)，其中，顶点集合为V={v1,v2,v3,v4,v5,v6,v7},，边的集合为 {(v1,v2),(v1,v3),(v2,v1),(v2,v4),(v2,v6),(v3,v1),(v4,v2),(v4,v7),(v5,v4),(v5,v6),(v6,v2),(v6,v2 ),(v7,v4)},请先给出邻接表结构，然后分别给出根据该邻接表从顶点v1出发进行深度优先搜索与广度优先搜索后的顶点序列。 【解答】 邻接表结构： 深度优先搜索序列为： v1，v2，v4，v5，v6，v7，v3 广度优先搜索序列为： v1，v2，v3，v4，v6，v5，v7 4. 用宽度优先搜索和深度优先搜索对如图所示的无向图G进行遍历(从顶点1出发)，给出遍历序列 【解答】搜索本题图的宽度优先搜索的序列为：12，，4，3，6，5，8，7，深度优先搜索的序列为：1，2，6，4，5，7，8，30 5. 指出下列算法的时间复杂度。 sum1(int n) { int p=1,sum=0,1; for(i=1;i<=n;i++) { p*=I; sum+=p; } return(sum); } 【解答】 sum1()的嵌套最深层语句： p*=I; sum+=p; 它的频度为n次，所以其时间复杂度是O(n)。 6. 对于一个栈，给出输入项A,B,C。如果输入项序列由A,B,C所组成，试给出全部可能的输出序列。 【解答】ABC，ACB，BAC，BCA，CBA 7. 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。 【解答】 n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。例如： 8. 请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求？ 【解答】 采用顺序查找法：文件中记录可以任意次序存放。 采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。 采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中的所有记录的关键字值必须小于后一块中所有记录的关键字值。 9. 试对右图所示的AOE网络: (1) 这个工程最早可能在什么时间结束。 (2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 (3) 确定哪些活动是关键活动。 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。 然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。 此工程最早完成时间为43。 关键路径为<1, 3><3, 2><2, 5><5, 6> 10. 何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？ 【解答】 数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是 指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。 11．分别写出如图所示各二叉树的前序、中序和后序序列 【解答】： （1）前序 （a）12357864 （b）124735689 （2）中序 (a ) 17583624 (b) 472153869 （3）后序 (a ) 78563421 (b) 742589631 12.画出下图所示的AOV网的所有拓扑有序序列。 【解答】ADBECF ADBEFC ADEBCF ADEBFC DABECF DABEFC DAEBCF DAEBFC 13. 何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？ 【解答】 数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系 14 . 已知序列(35，70，12，26，90，41，66，58)，请写出对该序列采用泡排序方法进行升 序排序时各趟的结果。 【解答】 原始序列：35，78，12，26，90，41，66，58 第—趟后：35，12，26，78，41，66，58，90 第二趟后：12，26，35，41，66，58，78，90 第三趟后：12，26，35，41，58，66，78，90 第四趟后：12，26，35，41，58，66，78，90 15. 何为数据的逻辑结构？何为数据的存储结构？一般情况下，两者之间有什么联系？这种联系是如何反映的？ 【解答】 数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。数据的存储结构是指数据在计算机存储器中的存储方式。在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。16．给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少? 【解答】 仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。 17. 已知序列(35，78，12，26，66，41，66，58)，请写出对该序列采用选择排序方法进行 升序排序时各趟的结果。 【解答】 原始序列：35，78，12，26，90，41，66，58 第—趟后：12，78，35，26，90，41，66，58 第二趟后：12，26，35，78，90，41，66，58 ， 第三趟后：12，26，35，78，90，41，66，58 第四趟后：12，26，35，41，90，78，66，58 第五趟后：12，26，35，41，58，78，66，90 第六趟后：12，26，35，41，58，66，78，90 第七趟后：12，26，35，41，58，66，78，90 18. 数据逻辑结构包括哪三种类型？树形结构和图形结构合称为什么？ 【解答】 包括线性结构、树形结构和图形结构。树形结构和图形结构合称为非线性结构 19 . 请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求？ 【解答】 采用顺序查找法：文件中记录可以任意次序存放。 采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。 采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中的所有记录的关键字值必须小于后一块中所有记录的关键字值。 20. 有向图的邻接表如下 试给出至少两个拓扑序列。 【解答】 V1 V2 V3 V4 V5 V6 V1 V3 V2 V4 V5 V6 五、算法题 1.已知非空双向循环链表最左边那个链结点的指针为list,请写一逆置该双向循环链表的算 法 【解答】 2.借助栈将输入任意一个非负的十进制数,打印输出与其等值的八进制。 【解答】 conversion( ) {InitStack(s); scanf("%d",n); while(n) {Push(S,n%8); n=n/8; } while(!StackEmpty(s)) {Pop(s,X); priintf("%d",X) } } 3.设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有 结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。 解答1】 template if ( first == NULL ) return; ListNode while ( p != NULL ) { first→link = pr; //逆转first指针 pr = first; first = p; p = p→link; //指针前移 } } 【解答2】 template ListNode while ( first != NULL ) { p = first; first = first→link; //摘下first链头结点 p→link = head→link; head→link = p; //插入head链前端 } first = head→link; delete head; //重置first } 4.有—个循环双链表，每个结点由两个指针(nght和left)以及关键字(key)构成，p指向其中 某一结点，编写一个函数从该循环双链表中删除p所指向的结点。 【解答】 本题的关键是找出p所指结点的前后结点，这可以循环指针找到。实现本题功能的函数如下： struct dlist { int key; struct dlist *left,*right; } void delnode(p) struct dlist *p; { struct dlist *q,*r; q=p; while(q->right!=p)q=q->right; r=p; while(r->left!=p)r=r->left; q->right=r; r->left=q;free(p); } while(r->left!=p)r=r->left; q->right=r; r->left=q;free(p); } 5.已知一个顺序表Ａ中的元素按值非递减有序，编写一个函数插入一个元素Ｘ后保持该顺 序表是有序的 【解答】 #define MAX 100 typedef int vector[MAX] void insert(vector A,int n,x) { int,j; if(x>=A[n])A[n+1]=x; else { i=1; while(x>=A[i])i++; for(j=n;j>=i;j--)A[j+1]=A[j]; A[i]=x; n++; } } 6.试写出后序遍历二叉树的递归算法。 【解答】 设t为指针，且其存储结构为二叉链表，则可将算法描述为：postorder(t) /* 后序遍历二叉树*/ bitree t; /设其类型为bitree*/ { if(t) /*二叉树t 非空*/ { postorder(t->lchild); /*后序遍历二叉树t的左子树*/ postorder(t->rchild); /*后序遍历二叉树t的右子树*/ printf("\t%c\n",t->data); /*访问结点*/ } }/postorder*/ 7. 第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数据的基本单位；___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为________。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成的二元组：DS=（D，R）。 3．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02， 06>，<03，07>，<03，08>，<03，09>}。则此数据结构属于_____________结构。4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为__________；成正比关系时，则表示为___________；成对数关系时，则表示为___________；成平方关系时，则表示为__________。 5．数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_____________；数据结构的存储结构主要包括____________和____________两种类型。 6．线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后继结点，其余每个结点有且仅有_______个后继结点。 7．树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后继结点，其余结点可以有_________个后继结点。 8．图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。 9．程序段for（i=1，s=0；s 数据结构试卷（一） 一、选择题（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、抽象数据类型的三要素是，，。 2、队列是。 3、线索二叉树是 。 4、数据的逻辑结构是。 5、在大根堆中，关键值最大的元素是。 6、在记录集{2、5、 7、10、14、15、1 8、20、22}中，进行二分查找，若要查找 元素18，共需要比较次关键字。 7、分层依次将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么树 的深度为。 8、在一个长度为 n 的顺序表中第 i 个位置插入新元素时，需向后移动元素个 数是。 9、在直接插入排序中使用监视哨的作用是。 10、在含n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为。 二、判断题（正确在题后括号内划“√”，错误划“×”） 1、在拓扑排序中，拓扑序列的第一个顶点必定是出度为零的顶点。（） 2、算法DFS应用于一个带权连通图时，所经过的边形成一棵最小生成树。（） 3、（101，88，46，70，34，39，45，58，66，10）是堆。（） 4、n个结点的树的各结点度数之和为n-1。（） 5、由二叉树的前序序列和中序序列能唯一确定一棵二叉树。（） 6、有向图中一个顶点i的出度等于其邻接矩阵中第i列的非0元素的个数。（） 7、哈夫曼树的带权路径长度WPL等于各叶子结点的带权路径长度之和（） 8、所谓冲突即是两个关键字的值不同的元素，其散列地址相同。（） 9、设一个9阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B 中，其中 B[1] 存储矩阵中第一个元素a[1,1], 则B[5] 中存放的元素是a[2,3]。（） 10、在串S ="structure" 中，以 t 为首字符的子串有 8个。（） 三、求解与简答题： 1、以数据集{2，6，13，17，20，30}为叶子结点的权值。（1）构造一棵哈夫曼 数据结构试题库 一、单项选择题 1．下列程序段所代表的算法的时间复杂度为（D ）。 x=n; y=0; while (x>=(y+1)*(y+1)) y++; (A)O(n) (B)O(n2) (C)O(log2n) (D)O(n) 2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2 3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为（C ）。 (A)HS->next=s;(B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next; 4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（A ）。 void AddQueue(struct linkqueue Q) { p=Q->front; while(p->next!=Q->front) p=p->next; } (A)p->next=s;s->next=Q->front; (B)Q->front->next=s;Q->front=s; (C)s->next=p;p->next=Q->front; (D)Q->front->next=s;s->next=p; 5．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B ）。 (A)2h-1(B)2h-1+1 (C)2h-1 (D)2h-1-3 习题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.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。 数据结构综合练习题 1填空题 1.数据结构包含三个方面的内容，分别是数据的逻辑结构、数据的存储结构和数据的运算。 2.实现数据结构的四种存储方法有顺序存储方法、链接存储方法、索引存储方法和散列存储方法。 3.数据结构的逻辑结构有线性结构和非线性结构两大类。 4.一种抽象数据类型包括抽象数据的组织和与之相关的操作两个部分。 5.算法的五个重要特性是输入、输出、确定性、可行性和有穷性。 6.栈顶的位置是随进栈和出栈操作而变化的。 7.在链队列只有一个元素的情况下，对其做删除操作时，应当把对头指针和队尾指针都置为null。 8.操作系统中先来先服务是数据结构中的队列应用的典型例子。 9.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输 出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个队列结构。 10.有一棵树如下图所示，回答下列问题。11.有一棵树如下图所示，回答下列问题。 （1）这棵树的根结点是K1；（1）结点k3的度是 2 ； （2）这棵树的叶子结点是K2，K4，K5，K7；（2）这棵树的度为 3 ； 12.有一棵树如下图所示，回答下列问题。 13有一棵树如下图所示，回答下列问题。 这棵树的深度为 4 ； （1）结点K3的子女是 K5 ，K6 ； （2）结点K3的双亲结点是 K1 。 14.在一棵二叉树中，度为零的结点个数为n0，度为2的结点的个数为n2，则有n0=n2+1。 15.n （n>0）个结点的二叉树高度最大是 n ，其深度最小是?log 2(n+1)?或??1log 2+n 。 16.n(n>0)个结点的满二叉树深度是)1(log 2+n ，叶子结点数是 (n+1)/2。阿 17.下面二叉树的中序序列是GDHABC 。 18.n （n>0）个结点的哈夫曼树中度为2的结点共 (n-1)/2 个，叶子结点共(n+1)/2个。 19.n 个顶点的有向图最多有 n*(n-1) 条边。 20.n （n>0）个顶点的连通无向图各顶点度之和最少是 2(n-1) 。 21.有6个顶点的无向图至少应有 5 条边才能确保是一个连通图。 22. n(n>0)个顶点的连通无向图至少有 n-1 条边。 23. 恰有 n(n-1) 条边的有向图称为有向完全图。 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式 B．数据的存储形式 C．数据的表示形式 D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项 B．数据类型 C．数据元素 D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大 B．小 C．相同 D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间 B．在顺序结构中查找元素的速度比在链接结构中查找要快 C．与链接结构相比，顺序结构便于安排数据元素 D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 第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)一个算法应该就是（)。 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 习题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、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?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.栈和队列的共同特点是（只允许在端点处插入和删除元素） 4.栈通常采用的两种存储结构是（线性存储结构和链表存储结构） 5.下列关于栈的叙述正确的是（D） A.栈是非线性结构 B.栈是一种树状结构 C.栈具有先进先出的特征 D.栈有后进先出的特征 6.链表不具有的特点是（B） A.不必事先估计存储空间 B.可随机访问任一元素 C.插入删除不需要移动元素 D.所需空间与线性表xxxx 7.用链表表示线性表的优点是（便于插入和删除操作） 8.在单链表中，增加头结点的目的是（方便运算的实现） 9.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表）1 0."线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D） A.每个元素都有一个直接前件和直接后件 B.线性表中至少要有一个元素 C.表中诸元素的排列顺序必须是由小到大或由大到小 D.除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 1 1."线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D） A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 12."线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构） 1 3."树是结点的集合，它的根结点数目是（有且只有1） 1 4."在深度为5的满二叉树中，叶子结点的个数为 （31） 1 5."具有3个结点的二叉树有（5种形态） 1 6."设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为 （13） 1 7."已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba） 1 8."已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（DGEBHFCA） 1 9."若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca） 2 0."数据库保护分为： 安全性控制、完整性控制、并发性控制和数据的恢复。 1.在计算机中，算法是指（解题方案的准确而完整的描述） 2.在下列选项中，哪个不是一个算法一般应该具有的基本特征（无穷性） 说明： 算法的四个基本特征是： 可行性、确定性、有穷性和拥有足够的情报。 3.算法一般都可以用哪几种控制结构组合而成（顺序、选择、循环） 4.算法的时间复杂度是指（算法执行过程中所需要的基本运算次数） 5.算法的空间复杂度是指（执行过程中所需要的存储空间） 6.算法分析的目的是（分析算法的效率以求改进） 7.下列叙述正确的是（C） A．算法的执行效率与数据的存储结构无关 一．是非题 （正确的打“√”，错误的打“×”。） 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章概论 1.数据、数据元素、数据结构、数据类型的含义分别是什么？ 数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。 数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。 数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？ 逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息： ①数据元素的信息； ②各数据元素之间的关系。 物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些？ 对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有： ●创建：建立一个数据结构； ●清除：清除一个数据结构； ●插入：在数据结构中增加新的结点； ●删除：把指定的结点从数据结构中删除； ●访问：对数据结构中的结点进行访问； ●更新：改变指定结点的值或改变指定的某些结点之间的关系； ●查找：在数据结构中查找满足一定条件的结点； ●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。 4.什么是抽象数据类型？如何定义抽象数据类型？ 抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。 对抽象数据类型的描述一般用（D,R,P)三元组表示，抽象数据类型的定义格式为： ADT<抽象数据类型名> { 数据对象D：<数据对象的定义> 数据关系R：<数据关系的定义> 基本操作P：<基本操作的定义> 数据结构试题（含答案） 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 。 数据结构练习题及参考答案 《数据结构》练习题 一、解答题（共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,下标上限为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之间的元素进行快速排序的分区。请填空，完善程序。 int Partition(int r[ ], int first, int end) { int i,j,t; i=first; j=end; //初始化 while ( ⑸) { while (i数据结构习题
数据结构试卷带答案
数据结构复习题
数据结构试题库
数据结构习题及参考答案
数据结构考试题库
数据结构-综合练习题-打印
数据结构习题库
数据结构考试题库含答案
数据结构练习试题和答案解析
数据结构试题库答案
数据结构习题及参考答案 .
数据结构试题及答案
数据结构面试题(含答案)
数据结构试题(含答案)
数据结构习题参考答案
数据结构试题(含答案)
数据结构练习题及
相关主题
文本预览