数据结构(C语言版)复习题

1、一、单项选择题： 1、树形结构不具备这样的特点：（ ）A. 每个节点可能有多个后继（子节点）B. 每个节点可能有多个前驱（父节点）C. 可能有多个内节点（非终端结点）D. 可能有多个叶子节点（终端节点）2、二叉树与度数为2的树相同之处包括（ ）。A. 每个节点都有1个或2个子节点 B. 至少有一个根节点C. 至少有一个度数为2的节点 D. 每个节点至多只有一个父节点3、一棵完全二叉树有999 个结点，它的深度为（ ）。 A9 B10 C11 D12 4、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ ） A. s->next=p;p->next=s; B

2、. s->next=p->next;p->next=s; C. s->next=p->next;p=s; D. p->next=s;s->next=p;5、对于一棵具有n个结点、度为5的树来说，（ ）A. 树的高度至多是n-3 B. 树的高度至多是n-4C. 树的高度至多是n D. 树的高度至多是n-56、在顺序队列中，元素的排列顺序（ ）。A. 由元素插入队列的先后顺序决定B. 与元素值的大小有关C. 与队首指针和队尾指针的取值有关D. 与数组大小有关7、串是一种特殊的线性表，其特殊性体现在（ ）。 A可以顺序存储 B数据元素是一个字符 C可以链式存

3、储 D数据元素可以是多个字符若 8、顺序循环队列中（数组的大小为 6），队头指示 front 和队尾指示 rear 的值分别为 3和 0，当从队列中删除1个元素，再插入2 个元素后，front和 rear的值分别为（ ）。 A5 和1 B2和4 C1和5 D4 和29、一棵完全二叉树上有1001 个结点，其中叶子结点的个数为（ ）。 A250 B500 C254 D501 10、已知一个有向图如下图所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为（ ）。 Aadbefc Badcefb Cadcebf Dadefbc11、在一个带权连通图G 中，权值最小的边一定包含在G 的（ ）

4、。 A最小生成树中 B深度优先生成树中 C广度优先生成树中 D深度优先生成森林中 12、适用于折半查找的表的存储方式及元素排列要求为（ ）。 A链式方式存储，元素无序 B链式方式存储，元素有序 C顺序方式存储，元素无序 D顺序方式存储，元素有序 13、含有27个关键字节点的平衡二叉树（AVL树）（ ）A. 有13个度数为2的节点 B. 最大高度为6C. 最低高度是6 D. 有14个度数为0的节点14、任何一个无向连通图的最小生成树（ ）。A. 有一棵或多棵 B. 只有一棵 C. 一定有多棵 D. 可能不存在15、下述几种排序方法中,要求内存量最大的是（ ）。A插入排序 B选择排序 C快速排序

5、D归并排序16、以下属于逻辑结构的是（ ）A. 顺序表 B. 哈希表 C. 有序表 D. 单链表 17、一个有n个顶点的无向图最多有（ ）条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n18、下面（ ）算法适合构造一个稠密图G的最小生成树。A Prim算法 BKruskal算法 CFloyd算法 DDijkstra算法19、下面哪个术语与数据的存储结构无关（ ）。 A顺序表 B链表 C散列表 D队列20、无向图G=（V，E）， 其 中 ：V=a,b,c,d,e,f，E=（a,b），（a,e），（a,c），（b,e） ，（c,f），（f,d），（e,d），对该图进行深度优先

6、遍历，得到的顶点序列正确的是（ ）。 Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 21、如下图所示带权无向图的最小生成树的权为（ ）。 A14 B15 C17 D1822、以下排序方法中，不稳定的排序方法是（ ）。 A直接选择排序 B二分法插入排序 C归并排序 D基数排序 23、下列哪一个选项不是下图所示有向图的拓扑排序结果（ ）。 AAFBCDE BFABCDE CFACBDE DFADBCE24、参加排序的记录可以具有相同的关键码。当一个排序方法在排序过程中不改变这种相同关键码记录的原始输入顺序时，称之为稳定的；反之称为不稳定的。

7、下面4种排序方法中，属于不稳定的排序方法是（ ）。A. 快速排序 B. 冒泡排序 C. 简单选择排序 D. 折半插入排序25、链式存储设计时，结点内的存储单元地址（ ）A. 一定连续 B. 一定不连续C. 不一定连续 D. 部分连续，部分不连续26、若一个栈的进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=n,则pi的值是（ ）。 A. i B. n-i C. n-i+1 D. 不确定27、以下有关二叉树的说法正确的是（ ）。 A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任一个结点的度均为2 28、一棵具有5 层的满二叉树所包含的结

8、点个数为（ ）。 A15 B31 C63 D32 29、在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45、89 和 12的结点时，所需进行的比较次数分别为（ ）。 A4，4，3 B4，3，3 C3，4，4 D3，3，4 30、一个序列中有 10000 个元素，若只想得到其中前 10 个最小元素，最好采用（ ）方法。 A快速排序 B堆排序 C插入排序 D二路归并排序31若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上（ ）A操作的有限集合 B映象的有限集合C类型的有限集合 D关系的有限集合32在头指针为head且表长大于1的

9、单循环链表中，指针p指向表中某个结点，若p->next->next=head，则（ ）Ap指向头结点 Bp指向尾结点C*P的直接后继是尾结点 D *p的直接后继是头结点33在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ）AO(1) BO(n)CO(nlogn) DO(n2)34队列和栈的主要区别是（ ）A逻辑结构不同 B存储结构不同C所包含的运算个数不同 D限定插入和删除的位置不同35若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（ ） A4 B5 C6 D736一棵含18个结点的二叉树的高度至少为( )A3 B4 C5

10、D637在一个带权连通图G中，权值最小的边一定包含在G的（）A最小生成树中B深度优先生成树中C广度优先生成树中D深度优先生成森林中二、填空题： 1、 树最适合用来表示具有（ ）性和（ ）性的数据。 2、设有一批数据元素,为了最快的存储某元素,数据结构宜用（ ）结构,为了方便插入一个元素,数据结构宜用（ ）结构。3、在顺序表的（ ）后面插入一个元素，不需要移动任何元素。4、设循环队列的容量为40（ ），队头指针为front，队尾指针为rear；现经过一系列的入队和出队运算后，队头与队尾指针分别指向front=11，rear=19，则可求出循环队列中有（ ）个元素。5、哈夫曼树是带权路径长度（ ）

11、的二叉树，又称最优二叉树。6、前序遍历和中序遍历结果相同的二叉树为（ ）；前序遍历和后序遍历结果相同的二叉树为（ ）。 7、在一个长度为n的顺序表中删除第i个元素（ ）时，需向前移动（ ）个元素。8、线性的数据结构包括：（ ）、（ ）、（ ）和数组、串。9、访问单向链表的节点，必须顺着（ ）依次进行。10、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。11、数据结构涉及三个方面的内容，即( )、( )和( )。12、具有4个顶点的无向完全图有( )条边。三、判断对错题： 1、二维数组是其数据元素为线性表的线性表。 （ ）2、栈和链表是两种相同的数据结构。（ ） 3、

12、在中序线索二叉树中，每一非空的线索均指向其祖先结点。（ ）4、必须把一般树转换成二叉树后才能进行存储。（ ）5、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）6、循环链表不是线性表。（ ）7、一棵哈夫曼树中不存在度为1的结点。（ ）8、线性表的逻辑顺序与存储顺序总是一致的。 （ ）9、若有向图中存在拓扑序列，则该图不存在回路。（ ）10、有序表与数据的存储结构无关（ ）11、单链表的存储密度小于1。（ ）12、执行广度优先遍历图时，需要使用队列作为辅助存储空间。（ ）13、把一棵树转换为二叉树后，这棵二叉树的形态是唯一的。（ ）14、在完全二叉树中，叶子结点的双亲的左兄弟（如果存在

13、）一定不是叶子结点。（ ）15、数据的机内表示称为数据的存储结构。（ ） 16、深度优先遍历类似于二叉树的先序遍历。（ ）17、某算法的时间复杂度为O（n2）,表明该算法的问题规模是n2。（ ）18、一个顺序表所占用的存储空间大小与元素的类型无关。（ ）19、消除递归一定要使用栈。（ ）20、一个有n个顶点和n条边的无向图一定是有环的。（ ）21、调用一次深度优先遍历可以访问到图中的所有顶点。（ ）22、二叉树是一般树的特殊情形。( )23、数据的逻辑结构是指数据在计算机内的实际存储形式。( ) 24、归并排序要求内存量比较大。( )25、数据的物理结构是指数据在计算机内的实际存储形式。( )

14、26、对任何数据结构链式存储结构一定优于顺序存储结构。( )27、拓扑排序是一种内部排序的算法。 （ ） 28、栈和队列的存储方式只能是链接方式。（ ）29、栈是实现过程和函数等子程序所必需的结构。( )30、线性表在物理存储空间中也不一定是连续的。( )四、综合应用题：（共40分）1、两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？ 2、 已知一棵二叉树如右图所示，试求：6第 页 共 9 页（1）该二叉树前序、中序和后序遍历的结果； （2）该二叉树是否满二叉树？是否完全二叉树？ （3）将它转换成对应的树或森林； （

15、4）这棵二叉树的深度为多少？ （5）试对该二叉树进行前（中、后）序线索化； 3、 如右图所示的是个无向图的邻接表，试： （1）画出此图； （2）从顶点A 开始的DFS 遍历结果； （3）从顶点A 开始的BFS 遍历结果。 4、分析下列语句执行次数，并给出它们的时间复杂度T(n)。 （1） i+; （2）for(i=0;i<n;i+) for(j=0;j<n;j+) printf(“%d”,i+j); 5、分析下列语句的执行次数，并给出它们的时间复杂度T(n)。 （1） for(i=0;i<n;i+) if (ai<x) x=ai; （2）for (i=1;i<=n

16、-1;i+) k=i; for(j=i+1;j<=n;j+) if(aj>aj+1) k=j; t=ak; ak=ai; ai=t; 6、分析下列语句的执行次数，并给出它们的时间复杂度T(n)。 7第 页 共 9 页（1）for(i=0;i<n;i+) for(j=0;j<n;j+) +x;s=s+x; （2）、for(i=0;i<=2;i+) for(j=0;j<=2;j+) for(s=0;s<=2;s+) t=ais*bsj;cij=cij+t; 7、如右图所示的连通图，用Prim算法构造其最小生成树。 8、 分别画出具有3个结点的树和具有3个结

17、点的二叉树的所有不同形态。 8第 页 共 9 页9、对于如下图所示的无向图，试给出：（1）图中每个顶点的度； （2）该图的邻接矩阵； （3）该图的邻接表； 10、 如右图所示的连通图，用Kruskal，算法构造其最小生成树。 11、试写出如右图所示的AOV 网的 4个不同的拓扑序列。12、 算法有哪些特点？它和程序的主要区别是什么？13、 若一棵二叉树的左、右子树均有3个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试画出该二叉树。 14、 试述树和二叉树的主要区别。 15、 已知一棵二叉树的中序遍历的结果为 ABCEFGHD，后序遍历的结果为ABFHGEDC，试画出

18、此二叉树。 16、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。 17、试回答下列关于图的一些问题。 （1）有 n个顶点的有向强连通图最多有多少条边？最少有多少条边？ （2）表示一个有500 个顶点，500 条边的有向图的邻接矩阵有多少个非零元素？ （3）G是一个非连通的无向图，共有28条边，则该图至少有多少个顶点？18、请画出初始序列（212，26，172，126，8，56，23，2，6）的初始堆形，判断其是否是堆，如果不是请将其调整成堆（写出调整的过程）。19、假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。20、 给出初始待排序码27，46，5，18，16，51，32，26使用下面各种排序算法的状态变化示意图：（1）直接插入排序；（2）直接选择排序；（3）冒泡排序；（4）快速排序；（5）堆（大小）排序； 9第 页 共 9 页五、算法设计题：1、设计一个算法，求顺序表中值为x的结点的个数。2