一、单项选择题：
1、树形结构不具备这样的特点：（）
A.每个节点可能有多个后继（子节点）
B.每个节点可能有多个前驱（父节点）
C.可能有多个内节点（非终端结点）
D.可能有多个叶子节点（终端节点）
2、二叉树与度数为2的树相同之处包括（）。
A.每个节点都有1个或2个子节点
B.至少有一个根节点
C.至少有一个度数为2的节点
D.每个节点至多只有一个父节点
3、一棵完全二叉树有999个结点，它的深度为（）。
A．9B．10C．11D．12
4、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）
A.s->next=p;p->next=s;
B.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-4
C.树的高度至多是n
D.树的高度至多是n-5
6、在顺序队列中，元素的排列顺序（）。
A.由元素插入队列的先后顺序决定
B.与元素值的大小有关
C.与队首指针和队尾指针的取值有关
D.与数组大小有关
7、串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储B．数据元素是一个字符
C．可以链式存储D．数据元素可以是多个字符若
8、顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3
和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（）。
A．5和1B．2和4C．1和5D．4和2
9、一棵完全二叉树上有1001个结点，其中叶子结点的个数为（）。
A．250B．500C．254D．501
10、已知一个有向图如下图所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序
列为（）。
A．adbefc B．adcefb C．adcebf D．adefbc
11、在一个带权连通图G中，权值最小的边一定包含在G的（）。
A．最小生成树中B．深度优先生成树中
C．广度优先生成树中D．深度优先生成森林中
12、适用于折半查的表的存储方式及元素排列要求为（）。
A．链式方式存储，元素无序B．链式方式存储，元素有序
C．顺序方式存储，元素无序D．顺序方式存储，元素有序
13、含有27个关键字节点的平衡二叉树（AVL树）（）
A.有13个度数为2的节点
B.最大高度为6
C.最低高度是6
D.有14个度数为0的节点
14、任何一个无向连通图的最小生成树（）。
A.有一棵或多棵
B.只有一棵
C.一定有多棵
D.可能不存在
15、下述几种排序方法中，要求内存量最大的是（）。
A．插入排序B．选择排序C．快速排序D．归并排序
16、以下属于逻辑结构的是（）
A.顺序表
B.哈希表
C.有序表
D.单链表
17、一个有n个顶点的无向图最多有（）条边。
A.n
B.n(n-1)
c语言的冒泡排序算法C.n(n-1)/2
D.2n
18、下面（）算法适合构造一个稠密图G的最小生成树。
A．Prim算法B．Kruskal算法C．Floyd算法D．Dijkstra算法
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）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
21、如下图所示带权无向图的最小生成树的权为（）。
A．14B．15C．17D．18
22、以下排序方法中，不稳定的排序方法是（）。
A．直接选择排序B．二分法插入排序
C．归并排序D．基数排序
23、下列哪一个选项不是下图所示有向图的拓扑排序结果（）。
A．AFBCDE B．FABCDE C．FACBDE D．FADBCE
24、参加排序的记录可以具有相同的关键码。当一个排序方法在排序过程中不改变这种相同
关键码记录的原始输入顺序时，称之为稳定的；反之称为不稳定的。下面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．二叉树的度为2B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2D．二叉树中任一个结点的度均为2
28、一棵具有5层的满二叉树所包含的结点个数为（）。
A．15B．31C．63D．32
29、在关键字序列（12，23，34，45，56，67，78，89，91）中二分查关键字为45、
89和12的结点时，所需进行的比较次数分别为（）。
A．4，4，3B．4，3，3C．3，4，4D．3，3，4
30、一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）
方法。
A．快速排序B．堆排序C．插入排序D．二路归并排序
31．若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上（）A．操作的有限集合B．映象的有限集合
C．类型的有限集合D．关系的有限集合
32．在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head，则（）
A．p指向头结点B．p指向尾结点
C．*P的直接后继是尾结点D．*p的直接后继是头结点
33．在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（）A．O(1)B
．O(n)C．O(nlogn)D．O(n2)
34．队列和栈的主要区别是（）
A．逻辑结构不同B．存储结构不同
C．所包含的运算个数不同D．限定插入和删除的位置不同
35．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（）A．4B．5C．6D．7
36．一棵含18个结点的二叉树的高度至少为()
A．3B．4C．5D．6
37．在一个带权连通图G中，权值最小的边一定包含在G的（）
A．最小生成树中B．深度优先生成树中
C．广度优先生成树中D．深度优先生成森林中
二、填空题：
1、树最适合用来表示具有（）性和（）性的数据。
2、设有一批数据元素，为了最快的存储某元素，数据结构宜用（）结构，为了方便
插入一个元素，数据结构宜用（）结构。
3、在顺序表的（）后面插入一个元素，不需要移动任何元素。
4、设循环队列的容量为40（），队头指针为front，队尾指针为rear；现经过
一系列的入队和出队运算后，队头与队尾指针分别指向front=11，rear=19，则可求出循环队列中有（）个元素。
5、哈夫曼树是带权路径长度（）的二叉树，又称最优二叉树。
6、前序遍历和中序遍历结果相同的二叉树为（）；前序遍历和后序遍历结
果相同的二叉树为（）。
7、在一个长度为n的顺序表中删除第i个元素（）时，需向前移动（）个元素。
8、线性的数据结构包括：（）、（）、（）和数组、串。
9、访问单向链表的节点，必须顺着（）依次进行。
10、设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
11、数据结构涉及三个方面的内容，即()、()和()。
12、具有4个顶点的无向完全图有()条边。
三、判断对错题：
1、二维数组是其数据元素为线性表的线性表。（）
2、栈和链表是两种相同的数据结构。（）
3、在中序线索二叉树中，每一非空的线索均指向其祖先结点。（）
4、必须把一般树转换成二叉树后才能进行存储。（）
5、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）
6、循环链表不是线性表。（）
7、一棵哈夫曼树中不存在度为1的结点。（）
8、线性表的逻辑顺序与存储顺序总是一致的。（）
9、若有向图中存在拓扑序列，则该图不存在回路。（）
10、有序表与数据的存储结构无关（）
11、单链表的存储密度小于1。（）
12、执行广度优先遍历图时，需要使用队列作为辅助存储空间。（）
13、把一棵树转换为二叉树后，这棵二叉树的形态是唯一的。（）
14、在完全二叉树中，叶子结点的双亲的左兄弟（如果存在）一定不是叶子结点。（）
15、数据的机内表示称为数据的存储结构。（）
16、深度优先遍历类似于二叉树的先序遍历。（）
17、某算法的时间复杂度为O（n2），表明该算法的问题规模是n2。（）
18、一个顺序表所占用的存储空间大小与元素的类型无关。（）
19、消除递归一定要使用栈。（）
20、一个有n个顶点和n条边的无向图一定是有环的。（）
21、调用一次深度优先遍历可以访问到图中的所有顶点。（）
22、二叉树是一般树的特殊情形。()
23、数据的逻辑结构是指数据在计算机内的实际存储形式。()
24、归并排序要求内存量比较大。()
25、数据的物理结构是指数据在计算机内的实际存储形式。()
26、对任何数据结构链式存储结构一定优于顺序存储结构。()
27、拓扑排序是一种内部排序的算法。（）
28、栈和队列的存储方式只能是链接方式。（）
29、栈是实现过程和函数等子程序所必需的结构。()
30、线性表在物理存储空间中也不一定是连续的。()
四、综合应用题：（共40分）
1、两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？
2、已知一棵二叉树如右图所示，试求：
（1）该二叉树前序、中序和后序遍历的结果；
（2）该二叉树是否满二叉树？是否完全二叉树？
（3）将它转换成对应的树或森林；
（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(a[i]<x)x=a[i];
（2）for(i=1;i<=n-1;i++)
{k=i;
for(j=i+1;j<=n;j++)
if(a[j]>a[j+1])k=j;
t=a[k];a[k]=a[i];a[i]=t;
}
6、分析下列语句的执行次数，并给出它们的时间复杂度T(n)。
（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=a[i][s]*b[s][j];
c[i][j]=c[i][j]+t;
}
7、如右图所示的连通图，用Prim算法构造其最小生成树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。