1．链表结点类和链表类定义：
template
struct Node
{ T data;
Node
};
template
class LinkList
{ public:
LinkList( ); //建立只有头结点的空链表
LinkList(T a[ ], int n); //建立有n个元素的单链表
~LinkList(); //析构函数
void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点 T Delete(int i); //在单链表中删除第i个结点
void PrintList( ); //遍历单链表，按序号依次输出各元素private: Node
};
2．二叉树类基本定义:
template
struct BiNode //二叉树的结点结构
{ T data;
BiNode
};
template
class BiTree
{public:
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间BiNode
void PreOrder(BiNode
void InOrder(BiNode
void PostOrder(BiNode
void LeverOrder(BiNode
private:
BiNode
BiNode
void Release(BiNode
};
3．图的邻接表类定义：
const int MaxSize=12;
struct ArcNode //定义边表结点
{ int adjvex; //邻接点域
ArcNode *next; //指向下一个边结点的指针
};
template
struct VertexNode //定义顶点表结点
{ T vertex; //顶点的名称
ArcNode *firstedge; //边表的头指针
};
template
class ALGraph
{public:
ALGraph(T a[ ],int n,int e);//构造函数，初始化一个有n个顶点e条边的图
~ALGraph(); //析构函数，释放邻接表中各边表结点的存储空间
T GetVex(int i); //取图中第i个顶点数据信息
void DFSTraverse(int v); //深度优先遍历图
void BFSTraverse(int v); //广度优先遍历图
private:
VertexNode
int vertexNum, arcNum; //图的顶点数和边数
};
练习题：
一、填空题
1、______是数据的最小单位，_________是讨论数据结构时涉及的最小数据单位。
2、设一棵完全二叉树具有50个结点，则此完全二叉树有个度为2的结点。
3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的______
度。
4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该
树中有____________ 个叶子的结点。
5、有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找
长度为3。
6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共______个。
删除一个结点需要修改的指针共__________个。
7、已知广义表LS=(a,(b,c,d),e)，它的深度是__________，长度是__________。
8、循环队列的引入是为了克服__________。
9、表达式a*(b+c)-d/f的后缀表达式是________________。
10、数据结构中评价算法的两个重要指标是。
11、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的
三条语句是___________；r=s; r->next=null;。
12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为a，b，c，d，e，经过
PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。
13、模式串P=‘abaabcac’的next函数值序列为________。
14、任意连通图的连通分量只有一个，即是。
15、栈的特性是。
16、串的长度是。
17、如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。
18、在具有n个叶子结点的哈夫曼树中，分支结点总数为。
19、在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于________。
20、排序的主要目的是为了以后对已排序的数据元素进行。
21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。
22、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
23、两个栈共享空间时栈满的条件_______。
24、深度为H 的完全二叉树至少有_ __个结点；至多有_ __个结点；H和结点总数N 之间的关系是 __。
25、在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________。
26、数据结构被形式地定义为（D,R），其中D和R 的含义是（）。数据的逻辑结构包
括哪四种类型（）。从存储结构的概念上讲，顺序表是线性表的（），链表是（）。
27、算法的五个重要特性有哪些。（）。抽象数据类型是指一个（）以及定义在该
模型上的（）。
28、在含有n个结点的顺序存储的线性表中，在任意一个结点前插入一个结点所需要移动结
点的平均次数为（）。在含有n个结点的顺序存储的线性表中，任意删除一个结点所需要移动结点的平均次数为（）。对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度量级均为（）。
29、线性结构中的一个结点代表一个（）。若线性表中最常用的操作是取第i个元素和
查找该元素的前驱，则采用的存储方式最能节省时间的是（）。若最常用的操作是插入和删除第i个元素，则采用的存储方式最能节省时间的是（）。
30、在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除操作过程不
同，需要修改（）。在单链表中设置头结点的作用是（），无论链表是否为空，使（）均不为空。
31、如果以链栈为存储结构，则出栈操作时( )，与顺序栈相比，链栈有一个明显
的优势是( )。
32、循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾
指针。为区分队列的满和空，约定：队中能够存放的元素个数最大为n-l，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（）；
入队时，可用语句（）求出新元素在数组data中的下标。
33、已知栈的输入序列为1，2，3…．，n，输出序列为a1，a2，…，an，a2=n的输出序列
共有（）种输出序列。
34、稀疏矩阵一般的压缩存储方法有两种，它们是用（ )。对矩阵压缩存储是为了( )。
35、将下三角矩阵A[l..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址为（）。
二、选择题
1、从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间
复杂度为（）(1<=i<=n+1)。
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
3、若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则
p i是( )。
A. i
B. n-i
C. n-i+1
D. 不确定
4、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。
A. head（tail（tail（L）））
B. tail（head（head（tail（L））））
C. head（tail（head（tail（L））））
D. head（tail(head（tail（tail（L）））)）
5、下列陈述中正确的是（）。
A.二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点
D.二叉树中最多只有两棵子树，并且有左右之分
6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F
中第一棵树的结点个数是（）。
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
7、．算术表达式a+b*（c+d/e）转为后缀表达式后为（）。
A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++
8、关键路径是事件结点网络中（）。
A．从源点到终点的最长路径 B．从源点到终点的最短路径
C．最长回路 D．最短回路
9、具有12个关键字的有序表，二分查找的平均查找长度（）。
A. 2.5
B. 4
C. 3.1
D. 5
10、A VL树是一种平衡的二叉排序树，树中任一结点的（）
A.左、右子树的高度均相同
B.左、右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度
D.左子树的高度均小于右子树的高度
11、线性表采用链接存储时，其地址（）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续与否均可以
12、栈和队列是两种特殊的线性表，只能在它们的（）处添加或删除结点。
Ａ．中间点Ｂ．端点Ｃ．随机存取点Ｄ．结点
13、输入序列为ABC，可以变为BAC时，经过的栈操作为（）。
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
14、下面（）不是算法所具有的特性。
Ａ．有穷性Ｂ．确切性Ｃ．高效性Ｄ．可行性
15、下面关于串的的叙述中，（）是不正确的？
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储
16、数组A[6][7]的每个元素占五个字节，将其按行优先次序存储在起始地址为2000的内
存单元中，则元素A[3][5]的地址是( )。
A. 2130
B. 2180
C. 2205
D. 2210
17、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。
A．n B．(n-1)2 C．n-1 D．n2
18、若广义表A满足Head(A)=Tail(A)，则A为（）。
A．（） B．（（）） C．（（），（）） D．（（），（），（））
19、堆的形状是一棵 ( )。
A.二叉排序树
B.满二叉树
C.完全二叉树
D.判定树
20、若要在单链表中的结点*p 之后插入一个结点*s ，则应执行的语句是( )
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；
21、链表不具有的特点是（）。
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
22、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
23、递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表
24、设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 。
A．不确定 B．2n C．2n+1 D．2n-1
25、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序
方法是（）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
26、某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是（）。
A. 空或只有一个结点
B.高度等于其结点数
C. 任一结点无左孩子
D.任一结点无右孩子
27、下列说法正确的是（）。
(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索
(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前
(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值
A．(1)(2)(3) B．(1)(2) C．(1)(3) D．前面的可选答案都不对
28、下面的说法中正确的是（）。
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错
29、树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是（）。 A．树的后根遍历与其对应的二叉树的后根遍历相同
B．树的后根遍历与其对应的二叉树的中根遍历相同
C．树的先根遍历与其对应的二叉树的中根遍历相同
D．以上都不对
30、.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是
（）。
A. V1V2V3V4V5
B. V1V2V3V5V4
C. V1V4V3V5V2
D.V1V3V4V5V2
31、以下说法不正确的是（）。
A．无向图中的极大连通子图称为连通分量
B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D．有向图的遍历不可采用广度优先搜索
32、设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，
84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。
A．8 B．3 C．5 D．9
33、对散列文件，以下说法错误的是（）。
A．散列文件插入、删除方便，不需要索引区且节省存储空间
B．散列文件只能按关键字随机存取且存取速度快
C．经过多次插入、删除后，可能出现溢出桶满的情况
D．散列文件顺序存取方便
34、二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，
2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是（）。
A．A[8，5] B．A[3，10] C．A[5，8] D．A[0，9]
35、.在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。
A. O(n)
B. O(log2n)
C. O(nlog2n)
D. O(n2)
三、判断题
1．如果两个串含有相同的字符，则这两个串相等。（）
2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。（）3．二叉树是度为2的树。（）
4．在顺序表中取出第i个元素所花费的时间与i成正比。（）
5．在栈满情况下不能作进栈运算，否则产生“上溢”。( ）
6．图G的生成树是该图的一个极小连通子图。（）
7．所谓数据的逻辑结构指的是数据之间的逻辑关系。（）
8．二叉排序树的查找和折半查找的时间性能相同。（）
9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）
10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（）
11、双向链表中至多只有一个结点的后继指针为空。（）
12、在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（）
13、对链表进行插入和删除操作时，不必移动结点。（）
14、栈可以作为实现程序设计语言过程调用时的一种数据结构。（）
15、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧
16、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，
则该图一定是完全图。( )
17、“顺序查找法”是指在顺序表上进行查找的方法。（）
18、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）
19、二分查找要求序列顺序存储且关键字序列有序。（）
20、二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）
21、调用一次深度优先遍历可以访问到图中的所有顶点。（）
22、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）
23、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）
24、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）
25、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）
26、层次遍历初始堆可以得到一个有序的序列。（）
27、设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）
28、线性表的顺序存储结构比链式存储结构更好。（）
29、中序遍历二叉排序树可以得到一个有序的序列。（）
30、快速排序是排序算法中平均性能最好的一种排序。（）
31、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）
32、当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）
33、设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（）
34、完全二叉树中的叶子结点只可能在最后两层中出现。（）
35、哈夫曼树中没有度数为1的结点。（）
36、对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）
37、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）
38、由树转化成二叉树，该二叉树的右子树不一定为空。（）
39、线性表中的所有元素都有一个前驱元素和后继元素。（）
40、带权无向图的最小生成树是唯一的。（）
四、应用题
1、已知一棵二叉树的先根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出
这棵二叉树，并给出其后序序列。
2
类似例题：画出与下列二叉树对应的森林。
3、已知无向图如下所示：
（1）．给出从V1开始的广度优先搜索序列；（2）．画出它的邻接表；
（3）．画出从V1开始深度优先搜索生成树。
4、假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，请先构建一棵哈夫曼树，计算其WPL 值，并为这8个字母设计相应的哈夫曼编码。
5、已知一表为（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec ）,按表中顺序依次插入初始为空的二叉排序树，要求：
(1)画出建立的二叉排序树（值的大小以字母顺序为准）。
(2)对该二叉排序树作中序遍历，试写出遍历序列。
(3)求出在等概率情况下查找成功的平均查找长度。
6、已知一个图的顶点集V 和边集G 分别为：
V={0,1,2,3,4,5,6,7};
E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,
(4,6)4,(5,7)20};
按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
________, ________, ________, ________, ________, ________, ________。
7、已知散列函数为H(K)=K mod 11,健值序列为{57，14，29，11，16，82，42，16，3}哈希表长为11，采用线性探测法处理冲突，试构造闭散列表，并计算查找成功的平均查找长度。
8、已知待排序的序列为（503，87，542，41，900，170，827，275，603，422），试完成下列各题。
(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。
(2) 输出最小值后，如何得到次小值。（并画出相应结果图）。
9、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出一个方案。
v 2 v 1 v 3 v 6 16 21 11 14 33
6
19 6
10、已知图G=（V, E），其中V={v1,v2,v3,v4,v5}, E={
11、设有关键码序列{20，35，40，15，30，25，38}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。
12、已知散列函数为H(K)=K mod 13,健值序列为11，31，15，44，06，78，12，25，38，84，19，49，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。
13、对于下列一组关键字47，56，15，45，80，19，9，61，试写出快速排序每一趟的排序结果。
14、对下面的关键字集（30，15，21，40，25，26，36，37），若查找表的装填因子为0.8，采用线性探测再散列解决冲突：（1）设计哈希函数；（2）画出哈希表；（3）求查找成功的平均查找长度。
15、按顺序输入下列顶点对: (V1, V2)、(V1, V6)、(V2, V6)、(V1, V4)、(V6, V4)、(V1,
V3)、(V3, V4)、(V6, V5)、(V4, V5)、(V1, V5)、(V3, V5)。（顶点序列为：V1，V2，V3，V4，V5，V6）
（1）画出相应的邻接表。
（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列和DFS生成树。
五、算法与程序设计
1、阅读算法完成题目要求：
（1）说出下列算法的功能。
template
struct Binnode
{ T data;
Binnode
bool Unknown (Binnode
{ Binnode
p=first->next; q=first->prior;
while(p!=q && p->prior!=q)
if(p->data==q->data)
{
p=p->next; q=q->prior;
}
else return 0;
return 1;
}
（2）根据下列算法和输入的数据画出生成的链表形式。
template
LinkList
{ first=new Node
Node
first->next=NULL;;
for (int i=0; i { cin>>x; s=new Node s->next=first->next; first->next=s; } } 输入数据为：10 9 8 7 6 5 （3）说出下列算法的功能，它是采用什么结构实现的。 template void BiTree { const int MaxSize = 100; int front = 0; int rear = 0; BiNode if (root==NULL) return; else{ Q[rear++] = root; while (front != rear) { q = Q[front++]; cout< if (q->lchild != NULL) Q[rear++] = q->lchild; if (q->rchild != NULL) Q[rear++] = q->rchild; } } } （4）阅读下列算法求出调用该算法后输出结果。 void AE(Stack& S) { InitStack(S); Push(S,10); Push(S,20); Push(S,30); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[4]={7,9,15,18}; for(i=0;i<4;i++) Push(S,a[i]); while(!StackEmpty(S)) cout< } 输出结果为： （5）阅读下列算法：（设L是带头结点的单链表的头指针，并为已知的LinkList类型）void DeleteX(LinkList &L){ p=L－>next; while(p&& p－>next－>data!=x){ q=p;p=p－>next; } if(p){ q－>next=p－>next; free(p); } } 算法的功能： （6）设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能。 void F1(Linklist &L){ p=L→next; pre=p; while(p){ if(p→data pre=p; p=p→next; } printf(pre→data); if(pre→next && pre→data%2==0) { p=pre→next, pre→next=p→next;free(p); } } 算法功能： 2、程序设计 (1)设有一单链表L，结点结构为L中的元素是否 成等差关系，即：设各元素值次为a1,a2,a3,…,a n，判断a i+1-a i=a i-a i-1是否成立。若是 返回1，否则返回0。 函数说明为：int dengcha(Node (2)写出二分查找的非递归算法。(要求统计查找过程中元素的比较次数) 函数说明为：int binsearch(int r[ ], int n,int k)； (3)设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。 函数说明为：Void Linklist::purge(Node (4)写出图在邻接表存储结构下广度优先的遍历算法。函数说明为： template 函数说明为：void ALGraph ::BFSTraverse(int v)； （5）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 （6）设计一算法判断一个单链表中的元素是否对称。 （7）设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 数据结构试题及答案 一、单项选择题 (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.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 一．是非题 （正确的打“√”，错误的打“×”。） 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’) 的结果是 ( d ) 。 a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’ 图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构期末考试题及答案 、选择题 1.在数据结构中, 从逻辑上能够把数据结构分为 A. 动态结构和静态结构 B ．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2. 数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3. 在数据结构中, 与所使用的计算机无关的是数据的 结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4. 在存储数据时, 一般不但要存储各数据元素的值, 而且还 要存储C A. 数据的处理方法 B. 数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时般不考虑A 。 A. 各结点的值如何 B. 结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据能够有相同的逻辑结构7．算法分析的目的是C , 算法分析的两个主要方面是A 。 (1) A.找出数据结构的合理性 和输出的关系 C. 分析算法的效率以求改进 档性 ( 2) A .空间复杂度和时间复杂度 C. 可读性和文档性 性 8. 下面程序段的时间复杂度是 s = 0; for( I = 0; i v n; i + + ) for( j = 0; j v n; j ++ ) s +二B[i][j]; sum = s ; 9. 下面程序段的时间复杂度是 for( i = 0; i v n; i + + ) for( j = 0; j v m; j ++ ) B .研究算法中的输入 C .分析算法的易读性和文 B .正确性和简明性D .数据复杂性和程序复杂 O( n2) 。 O( n*m) 。 数据结构期末复习题 一、选择题 1.以下说法中不正确的是（D）。 A.数据元素是数据的基本单位 B.数据项是不可分割的最小可标识单位 C.数据可由若干个数据元素构成 D.数据项可由若干个数据元素构成 2.计算机所处理的数据一般具备某种内在联系，这是指（B）。 A.数据和数据之间存在某种关系 B.元素和元素之间存在某种关系 C.元素内部具有某种结构 D.数据项和数据项之间存在某种关系 3.在数据结构中，与所使用的计算机无关的是数据的（A）结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4.数据的逻辑结构可以分为（C）两类。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.数据的逻辑结构是指（A）关系的整体。 A.数据元素之间逻辑 B.数据项之间逻辑 C.数据类型之间 D.存储结构之间 6.以下数据结构中（D）属非线性结构。 A.栈 B.串 C.队列 D.平衡二叉树 7.以下属于逻辑结构的是（C）。 A.顺序表 B.哈希表 C.有序表 D.单链表 8.以下不属于存储结构的是（A）。 A.栈 B.线索二叉树 C.哈希表 D.双链表 9.在计算机中存储数据时，通常不仅要存储个数据元素的值，而且还要存储（C）。 A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 10.数据结构在计算机内存中的表示是指（A）。 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 11.在数据的存储结构中，一个结点通常存储一个（B）。 A.数据项 B.数据元素 C.数据结构 D.数据类型 12.在决定选择何种类型的存储结构时，一般不多考虑（A）。 一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 1.以下与数据的存储结构无关的术语是（c ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（ A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（ A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ） D、 8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（ B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示 第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 页，共 11 页 任课教师签名： 命题教师签名： 系主任签名： 主管院长签名： 湛江师范学院2007年－2008学年度第1学期 期末考试试题A 卷 (考试时间:120分钟) 考试科目： 数据结构 请将所有答案填写在答题卡上，交卷时请将所有试卷上交 一、单选题(每小题2分，共40分) 1．下列算法的时间复杂度是（ B ）。 for ( i=0; i 6．栈的特点是（B ）。 A 先进先出 B 后进先出 C 后进 后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的 最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i 1.以下与数据的存储结构无关的术语是（ c ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ C ） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（ A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（ A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ） D、 8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（ B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（ D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（ A ）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的_ _尾______进行，删除操作是在队列的____ 首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。数据结构-第六章-图-练习题及答案详细解析(精华版)
数据结构试题库答案
数据结构 期末考试复习题及答案
数据结构复习题附答案
《数据结构》题库及答案
2017年数据结构期末考试题及答案A
数据结构学生期末复习卷习题答案
数据结构 第六章 图 练习题及答案详细解析
数据结构试题及答案(10套最新)
数据结构期末考试题及答案
(完整word版)数据结构期末复习题
数据结构复习题及答案(12级).
算法与数据结构题库与答案
数据结构(c语言版)期末考试复习试题
数据结构期末复习题答案
数据结构练习试题和答案解析
数据结构期末考试试题A卷(完成,不知对不对)
数据结构期末复习题答案
数据结构试题及答案(10套最新)
相关主题
文本预览