数据结构练习题2010
部分练习题
一、单项选择题（在每小题四个备选答案中选出一个正确答案，填在题末的括号中）
1、若某线性表中最常用的操作是取第i个元素和查找第i个元素的的前驱元素，则采用（）的存储方式最节省时间。
A．顺序表B．双链表
C．单链表D．单循环链表
2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A．存储结构B．存储实现
C．逻辑结构D．运算实现
3、用链表表示线性表的优点是（）。
A．便于随机存取 B.花费的存储空间较顺序存储少
C．便于插入和删除 D.数据元素的物理顺序与逻辑顺序相同
4、设单向循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单向循环链表的尾结点的指针。若想删除该链表的第一个结点，则应执行下列哪一个操作？（）
A．s=rear; rear=rear->link; free(s);
B．rear=rear->link; free(rear);
C．rear=rear->link ->link; free(rear);
D．s=rear->link->link; rear->link->link=s->link; free(s);
5、设双向循环链表中结点的结构为（data, l Link, r Link），且不带表头结点。若想在指针p所指结点之后（右链方向）插入指针s所指的结点，则应执行下列哪个操作？（）A．p-> r Link =s;s-> l Link=p;p->rLink->l Link=s;s->r Link=p->r Link
B．p-> r Link =s; p->rLink->lLink=s;s->l Link=p; s->r Link=p->r Link
C．s->l Link=p;s->r Link=p->r Link;p->r Link=s;p->r Link->l Link=s;
D．s->l Link=p;s->r Link=p->r Link;p->r Link->l Link=s;p->r Link=s;
6、在具有n个结点的有序单链表中插入一个新结点并使该链表仍然有序的时间复杂度是（）。
A．O(1) B．O(n)
C．O(nlogn) D．O(n2)
7、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（）。A．s =rear; rear=rear->link; delete s;
B．rear=rear->link; delete rear;
C ．rear=rear->link->link; delete rear;
D ．s=rear->link->link;rear->link->link=s->link; delete s;
8、将下图所示的s 所指结点加到p 所指结点之后，其语句为（ ）。
A ．s->next=p+1；p->next=s ；
B ．(*p).next=s ；(*s).next=(*p).next ；
C ．s->next=p->next ；p->next=s ；
D ．s->next=p->next ；p->next=s->next ； 9、队列和栈的主要区别是（ ）。 A ．逻辑结构不同
B ．存储结构不同
C ．所包含的运算个数不同
D ．限定插入和删除操作的位置不同
10、已知广义表的表头为a ，表尾为（b ，c ），则此广义表为（ ）。 A ．（a ，（b ，c ）） B ．（a ，b ，c ） C ．（（a ），b ，c ）
D ．（（a ，b ，c ））
11、对表长为n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（ ）。 A ．(n-1)/2 B ．n/2 C ．(n+1)/2
D ．n
12、如图所示的4棵树中，是满二叉树的为 （ ）。
(A) (B) (C) (D)
13、一个二叉树按顺序方式存储在一个维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A ．1
B 、2
C．3 D．4
14、n个顶点的强连通图中至少含有（）。
A．n-l条有向边B．n条有向边
C．n(n-1)／2条有向边D．n(n-1)条有向边
15、对有n个结点的顺序表进行快速排序，在最坏情况下其关键码比较次数为（）。A．O(n) B．O(log2n)
C．O(nlog2n) D．O(n2)
16、在下面各种链表结构中，能在O(1) 时间内完成在指定结点之前插入元素X的结构是（）。
A．单链表B．单向循环链表
C．带表头结点的单链表D．双向循环链表
17、若让元素1,2,3依次进栈，则出栈次序不可能出现（）。
A．3，1，2 B．2，1，3
C．3，2，1 D．1，3，2
18、如图所示的4棵树中，不是完全二叉树的为（）。
A．B．C．D．
19、设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（）。A．2k B．2k+1-1
C．2k+1 D．2k-1+1
20、某棵二叉树按顺序方式存储在一维数组中，如下图
则结点E在二叉树的第（）层。
A．1 B．2
C．3 D．4
21、含有n个结点的二叉链表中，空链域个数为（）。
A．n B．n+1
C．2n D．n2
22、广义表A（a），则表尾为（）。
A．a B．(())
C．空表D．（a）
23、向一个有127个元素的顺序表中插入一个新元素并保持元素原来的先后关系不变，在等
概率情况下平均要移动（）个元素。
A、8
B、63.5
C、63
D、7
24、设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪个操作？（）
A．s->link=p->link;p->link=s; B．q->link=s; s->link=p;
C．p->link=s->link;s->link=p; D．p->link=s; s->link=q;
25、设单向循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单向循环链表的尾结点的指针。若想删除该链表的第一个结点，则应执行下列哪一个操作？（）
A．s=rear; rear=rear->link; free(s);
B．rear=rear->link; free(rear);
C．rear=rear->link ->link; free(rear);
D．s=rear->link->link; rear->link->link=s->link; free(s);
26、根据二叉树的定义，二叉树有（）种形态。
A. 6
B. 5
C. 4
D. 3
27、一棵有100个结点的完全二叉树从根这一层开始，每一层中从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左子女编号为（）。
A. 98
B. 99
C. 50
D. 48
28、如图所示的4棵树中，不是完全二叉树的为（）。
A． B． C． D．
29、广义表A（a），则表尾为（）。
A．a B．(())
C．空表D．（a）
30、从顺序表{2，5，7，10，14，15，18，23，35，41，52}中用折半搜索法搜索出元素18需要做（）次比较。
A．3 B．4
C．5 D．7
31、n 个顶点的连通图至少有（）条弧。
A．n-1 B．n
C．n+1 D．0
32、顺序存储结构（）。
A．仅适合于静态查找表的存储
B．仅适合于动态查找表的存储
C．既适合静态又适合动态查找表的存储
D．既不适合静态又不适合动态查找表的存储
33、循环链表最大的优点是（）
A．已知某个结点的位置后，能够直接找到它的直接前驱
B．在进行插入、删除等运算时，能够很好地保证链表连续
C．不再需要头指针
D．从表中任一结点出发都能扫描到整个链表
34、判断头指针为head的带头结点的单链表为空的条件是（）。
A．head==NULL B．head->next==NULL
C．head->next=head D．head!=NULL
35、设双向循环链表中结点的结构为（data, l Link, r Link），且不带表头结点。若想在指针p所指结点之后（右链方向）插入指针s所指的结点，则应执行下列哪个操作？（）A．p-> r Link =s;s-> l Link=p;p->r Link->l Link=s;s->r Link=p->r Link
B．p-> r Link =s; p->r Link->l Link=s;s->l Link=p; s->r Link=p->r Link
C．s->l Link=p;s->r Link=p->r Link;p->r Link=s;p->r Link->l Link=s;
D．s->l Link=p;s->r Link=p->r Link;p->r Link->l Link=s;p->r Link=s;
36、若让元素1,2,3依次进栈，则出栈次序不可能出现（）。
A．3，2，1 B．3，1，2
C．2，1，3 D．1，3，2
37、如图所示的4棵树中，不是完全二叉树的为（）。
A． B． C． D．
38、将含有98个结点的完全二叉树从根这一层开始，每层从左至右依次对结点进行编号，根结点的编号为1。则编号为76的结点的双亲结点的编号为（）。
A．36 B．37
C．38 D．不确定
39、含有n个结点的二叉链表中，空指针个数为（）。
A．n B．n+1
C．2n D．n2
40、n 个顶点的连通图至少有（）条弧。
A．n-1 B．n
C．n+1 D．0
41、线性表采用链表存储时，其地址（）
A.必须是连续的
B.一定是不连续的
C.部分地址必须是连续的
D.连续与否均可以
42.链表不具备的特点是（）
A.可随机访问任一结点
B.插入删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与其长度成正比
43.与单链表相比，双链表的优点之一是（）
A.插入、删除操作更简单
B.可以进行随机访问
C.可以省略表头指针或表尾指针
D.访问前后相邻结点更灵活
44.在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r(指向尾结点)，执行（）操作与链表的长度有关。
A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素之前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
45.两个串相等必有串长度相等且（）
A.串的各位置上的字符任意
B.串中各位置上的字符均对应相等
C.两个串含有相同的字符
D.两个串所含字符任意
46、算法原则上都是能够有机器或人所完成的。整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（）
A、正确性
B、有穷性
C、确定性
D、可行性
47．线性表采用链式存储时，其地址（）。
(A) 必须是连续的； (B) 部分地址必须是连续的；
(C) 一定是不连续的； (D) 连续与否均可以。
48．下面关于线性表的叙述错误的是（）。
(A) 线性表采用顺序存储，必须占用一片地址连续的单元；
(B) 线性表采用顺序存储，不便于进行插入和删除操作；
(C) 线性表采用链式存储，不必占用一片地址连续的单元；
(D) 线性表采用链式存储，不便于进行插入和删除操作；
49.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
(A) 单链表 (B) 仅有头指针的单循环链表
(C) 双链表 (D) 仅有尾指针的单循环链表
50．假定一个链队的队首和队尾指针分别为front和rear,则判断队空的条件为（） (A) front==rear (B) front!=NULL
(C) rear!=NULL (D) front==NULL
51、在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，打印机则从该缓冲区取出数据打印。该缓冲区应该是一个（）结构。
A.堆栈
B. 队列
C.数组
D.线性表
52、用链表表示线性表的优点是（）。
(A)便于随机存取 (B)花费的存储空间较顺序存储少
(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同
53、当利用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
A.top++
B.top--
C.top
D.top=0
54、设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为（）
A.10
B.11
C.12
D.不确定
55、有8个顶点的无向连通图最少有（）条边。
A.5
B.6
C.7
D.8
56、一个算法必须在执行有穷步之后结束，这是算法的（）。
A、正确性
B、有穷性
C、确定性
D、可行性
57．线性表是（）。
(A)一个有限序列，可以为空；(B) 一个有限序列，不能为空
(C) 一个无限序列，可以为空 (D) 一个无序序列，不能为空。
58．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。
(A) n/2 (B) n+1/2 (C) n-1/2 (D) n
59.线性表采用链式存储时，其地址（）。
(A) 必须是连续的； (B) 部分地址必须是连续的；
(C) 一定是不连续的； (D) 连续与否均可以。
60．用链表表示线性表的优点是（）。
(A)便于随机存取 (B)花费的存储空间较顺序存储少
(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同
61、栈中元素的进出原则是（）
A.先进先出
B.后进先出
C.栈空则进
D.栈满则进
62、判定一个栈ST（最多元素为m0）为空的条件是（）
A.ST->top<>0
B. ST->top=-1
C. ST->top<>m0
D. ST->top=m0
63、当利用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
A.top++
B.top--
C.top
D.top=0
64、设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为（）
A.10
B.11
C.12
D.不确定
65、有8个顶点的无向图最多有（B）条边。
A.14
B.28
C.56
D.112
66、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（）。
A、正确性
B、有穷性
C、确定性
D、可行性
67．顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n
68．下面关于线性表的叙述错误的是（）。
(A) 线性表采用顺序存储，必须占用一片地址连续的单元；
(B) 线性表采用顺序存储，不便于进行插入和删除操作；
(C) 线性表采用链式存储，不必占用一片地址连续的单元；
(D) 线性表采用链式存储，不便于进行插入和删除操作；
69.线性表采用链式存储时，其地址（）。
(A) 必须是连续的； (B) 部分地址必须是连续的；
(C) 一定是不连续的； (D) 连续与否均可以。
70．判定一个队列QU（最多元素为m0）为满队列的条件是（）
A.QU->rear-QU->front==m0
B.QU->rear-QU->front-1==m0
C. QU->rear==QU->front
D. QU->front==QU->rear+1
71、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）
A.2h
B.2h+1
C.2h-1
D.h+1
72、深度为5的二叉树至多有（）个结点。
A.16
B.32
C.31
D.10
73、设一棵二叉树中，度为1的结点数为9，则该二叉树的叶子结点的数目为（）
A.10
B.11
C.12
D.不确定
74、在一个图中，所有顶点的度数之和等于图的边数的（）倍。
A.1/2
B.1
C.2
D.4
75、如图所示的4棵树中，是满二叉树的为（）。
A． B． C． D．
76、二维数组A按行优先顺序存储，其中每个元素占1个存储单位。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为（）。
A．470 B．471
C．472 D．473
77、设有两个均只有头指针的单链表，若要将长度为n的单链表链接到长度为m的单链表之后，则实现该功能的算法的时间复杂度为（）。
A．O(1) B．O(n)
C．O(m) D．O(m+n)
78、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（）A．s =rear; rear=rear->link; delete s;
B．rear=rear->link; delete rear;
C．rear=rear->link->link; delete rear;
D．s=rear->link->link;rear->link->link=s->link; delete s;
79、从堆中删除一个元素的时间复杂度为（）。
A．O(1) B．O(n)
C．O(log2n) D．O(nlog2n)
80、对于一棵具有n个结点的二叉树，在其二叉链表的存储结构中，所有结点的空指针数等于（）。
A．n B．n-1
C．n+1 D．2*n
81、如图所示的4棵二叉树中，不是完全二叉树的为（）。
(A) (B) (C) (D)
82、利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉搜索树以后，查找元素35要进行（）元素间的比较。
A．4次B．5次
C. 7次D．10次
83、在一个带权连通图G中，权值最小的边一定包含在G的（）中。
A．最小生成树B．生成树
C．广度优先生成树D．深度优先生成树
84、一个有n个顶点和n条边的无向图一定是（）。
A．连通的B．不连通的
C．无回路D．有回路
85、对n个关键字的序列进行快速排序，其平均情况下的空间复杂度为（）。A．O(1) B．O(logn)
C．O(n) D．O(nlogn)
二、填空题（在每小题括号中填写正确答案）
1.在线性表的顺序存储中，元素之间的逻辑关系是通过（）决定的。
2、一个顺序栈存储于一维数组a[m]中，当栈顶指针等于（）时，则为空栈。
3、有42个结点的二叉树的高度最小是（）。
4、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（）个。
5、在一个最小堆中，堆顶结点的值是所有结点中的（）。
6、对于一个具有n个顶点昨e条边的连通图，其生成树中的边数为（）。
7、从邻接矩阵A=????
??????010101010可以看出，若该图是有向图，则共有（ ）条边。 8、直接插入排序在最好情况下的时间复杂度为（ ）
9.在线性表的链式存储中，元素之间的逻辑关系是通过（ ）决定的。
10.在一个长度为n 的顺序表中的第i 个元素（1≤i ≤n ）之前插入一个元素时，需向后移动（ ）个元素。
11.在一个长度为n 的顺序表中删除第i 个元素（1≤i ≤n ）时，需要向前移动（ ）个元素。
12、数据的逻辑结构是从逻辑上描述数据，它与数据的（ ）无关，是独立于计算机的。
13、数据的逻辑结构是从逻辑上描述数据，它与数据的（ ）无关，是独立于计算机的。
14、在下面程序段中，设n 为常数，s=s+p ；语句的执行次数为（ ）。 int i=0, s=0; while(++i<=n) { int p=1;
for(int j=1;j<=i; j++) p*=j; s=s+p;
}
15、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（ ）。
16、在下面程序段中，设n 为常数，s=s+p ；语句的执行次数为（ ）。 int i=0, s=0; while(++i for(int j=1;j<=i; j++) p*=j; s=s+p; } 17、在带头结点的单链表中，要删除某一指定的结点，必须找到该结点的（）结点。 18、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，若保持数据元素的原有次序不变，需要向前移动（）个元素。 19、递归工作栈中的工作记录通常包括：（）、在本次过程调用时与形参结合的实参值和本层的局部变量值。 20、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（）个。 21、在用于表示有向图的邻接矩阵中，对第J列的元素进行累加, 可得到第J个顶点的（）度。 22、对于一个具有n个顶点和e条边的有向图，在其对应的邻接表中，所含边结点为（）个。 23、如图所示的有向无环图可以排出（）种不同的拓扑序列。 24、任何一棵树的结点个数减去边数等于（）。3、一个顺序栈存储于一维数组a[m]中，若栈顶指针指向栈顶元素，则当栈顶指针等于（）时，表示空栈。 25、有20个结点的二叉树的高度最大是（），设根结点所处层次为0。 26、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加, 可得到第i个顶点的（）度。 27、对于一个具有n个顶点和e条边的无向图，在其对应的邻接表中，所含边结点为（）个。 28、在一个带头结点的单循环链表中，结点结构为（数据域data，指针域next），p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为（）。 29、队列中队尾指针是随着（）操作而发生变化的。 30、以折半搜索方法搜索一个线性表时，此线性表必须是（）。 31、在平衡的二叉搜索树中，任意结点的平衡因子的绝对值均（）。 32、在线性表的链式存储中，元素之间的逻辑关系是通过（）决定的。 33、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，若保持元素间的先后关系不变，需要向前移动（）个元素。 34、在顺序表（）元素后面插入一个元素，不需要移动任何元素。 35、队列的操作特点是（）。 36、树中任意结点允许有零个或多个孩子结点，除根结点外，其余结点（）双亲结点。 37、对二叉排序树进行（）遍历，可以得到按关键字从小到大排列的结点序列。 38、以折半搜索方法搜索一个线性表时，此线性表必须是（）。 39、任何一棵树的结点个数减去边数等于（） 40、在平衡的二叉排序树中，任意结点的平衡因子的绝对值均（） 41.删除顺序表的（）元素，不需要移动任何元素。 42.删除顺序表的（）元素，需要移动的元素最多。 43.在顺序表（）元素后面插入一个元素，不需要移动任何元素。 44.在单链表中，要删除某一指定的结点，必须找到该结点的（）结点。 45.栈是一种具有（）操作特性的线性表。 46、在线性表的顺序存储中，元素之间的逻辑关系是通过（）决定的。 47、在线性表的链式存储中，元素之间的逻辑关系是通过（）决定的。 48、在用于表示有向图的邻接矩阵中, 对第J列的元素进行累加, 可得到第J个顶点的（）度。 49、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，若保持元素原来的先后关系不变，需要向前移动（）个元素。 50、在单链表中，要删除某一指定的结点，必须找到该结点的（）结点。 51、栈是一种具有（）操作特性的线性表。 52、循环队列的优点是（）。 53、有10个结点的二叉树的高度最大是（）。 54、不加限定时，遍历二叉树有（）种结点排列顺序 55、深度为K（K≥1）的满二叉树有（）个结点 56.在队列中，新插入的元素只能插入到（） 57.循环队列的优点是（）。 58、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚 地给出规定，这是算法的（）。 59、在线性表的顺序存储中，元素之间的逻辑关系是通过（）决定的。 60、在一个长度为n的顺序表中的第i个元素（1≤i≤n）之前插入一个元素时，若保持元素原来的先后关系不变，需向后移动（）个元素。 61、在单链表中，要删除某一指定的结点，必须找到该结点的（）结点。 62、循环队列的优点是（）。 63、在一棵二叉树中，层次从1开始，第5层上的结点数最多为（）。 64、有10个结点的二叉树的高度最大是（）。 65、在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有（）个。 66、在用于表示有向图的邻接矩阵中, 对第I行的元素进行累加, 可得到第I 个顶点的（）度。 三、判断题（在每个小题后面的括号内作标记，正确的打“√”，错误的打“×”） 1.线性表中每个元素都有一个直接前驱和一个直接后继。（） 2.线性表中所有元素的排列顺序必须由小到或由大到小。（） 3、向栈顺序地输入一个整数序列1,2,3,4,5,6，能得到输出序列3,2,5,6,4,1。（） 4、满二叉树的结点个数一定为奇数。（） 5、在只有度为0和度为k的结点的正则k叉树中，设度为0的结点有n0个，度为k的结点有n k个，则有n0=n k+1。（） 6、满二叉树的结点个数不一定为奇数。（） 7、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（） 8、链表插入排序方法是稳定的。（） 9、栈和队列的存储方式既可是顺序方式，也可是链接方式。（） 10、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（） 11、直接插入排序中的数据比较次数与数据的初始排列无关。（） 12、链表插入排序方法是稳定的。（）3.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。（） 13.在单链表中，可以从头结点开始查找任何一个结点。（） 14.在n个元素进栈后，它们的出栈顺序和进栈顺序必定正好相反。（） 15.对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。（） 16.空串就是由空格构成的串。（） 17、线性表的链式存储结构优于顺序存储结构。（） 18、一个算法的评价主要从时间复杂度和空间复杂度来考虑。（） 19、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（） 20、根据二叉树的先序和后序序列可以唯一地确定一棵二叉树。（） 21、无向图的连通分量可以有很多个。（） 22、线性表的逻辑顺序与存储顺序总是一致的。（） 23、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（） 24、线性表的顺序存储表示优于链式存储表示。（） 25、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（） 26、对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。（） 27、将一棵树转换为二叉树后，根结点没有右子树。（） 28、快速排序方法是不稳定的排序方法。（） 29、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（） 30、二叉树是一种特殊的树。（） 31、无向图的连通分量只有一个。（） 32、线性表的链式存储结构优于顺序存储结构。（） 33、一个算法的评价只从时间复杂度考虑。（） 34、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（） 35、根据二叉树的先序和中序序列可以唯一地确定一棵二叉树。（） 36、无向图的连通分量可以有很多个。（） 37、哈希冲突是指同一个关键字对应多个不同的哈希地址。（） 38、N个元素进队列的顺序和出队列的顺序是一致的。（） 39.空串就是由空格构成的串。（） 40、图G的最小生成树的代价一定小于其他生成树的代价。（） 41一个算法的评价主要从时间复杂度和空间复杂度来考虑。（） 42哈希冲突是指同一个关键字对应多个不同的哈希地址。（） 43在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键小。（） 44连通图的生成树包含了图中所有顶点。（ ） 45.哈夫曼树中不存在度为1的结点。（ ） 四、简答题 1、设表示式a+b*(c-d)-e/f 对应的语法树如图所示，请写出该语法树的前序、中序、后序、层次遍历的结果序列。 2、已知一棵二叉树如下，请写出按前序、中序、后序、层次遍历时得到的结点序列。 3、设输入元素为1，2，3，P 和A ，输入次序为123PA ，如下图所示，经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可作为高级语言的变量名？ 4、设有序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。 5、有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵霍夫曼树（要求左子女的权值小于右子女），并求出该树的带权路径长度。 6、设有一个输入数据的序列为{46，25，78，62，12，37，70，29}，试根据二叉排序树的插入过程画出逐个输入以上数据而生成的二叉排序树。（要求写出插入过程） 7、已知某系统在通讯时，只出现F ，T ，D ，S ，H 五种字符，它们出现的频率依次为5，10，4，2，1，试设计Huffman 编码。 8、用序列（46，88，45，39，70，58，101，10，66，34）建立一棵二叉排序树，画出该树，并求在等概率情况下查找成功的平均搜索长度。 9、设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需要记录的平均比较次数不超过2次。试问散列表需要设计多大？设a 是散列表的装载因子，则有ASLsucc=(1/2)*[1+1/(1-a)]。 10、分别根据Kruskal 、普里姆算法的基本思想，从顶点0开始，给出下图的最小生成树(要 求写出生成过程)。 11、若一个具有n 个顶点，k 条边的无向图是一个森林（n>k ），则该森林中必有多少棵树。 输入序列 12、假设通信电文使用的字符集为{a，b，c，d，e，f，g}，字符的霍夫曼编码依次为：0110，10，110，111，00，0111和010。 （1）请根据编码画出该霍夫曼树，并在叶子结点中标注相应字符； （2）若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该霍夫曼树 的带权路径长度WPL的值。 13、给定权值集合{15，03，14，02，06，09，16，17}。根据赫夫曼算法的内容来构造相应的赫夫曼树，并计算它的带权路径长度WPL。 14、设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行折半搜索时的判定树（或扩充的二叉搜索树），并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。（5分） 15、已知一个无向网G如图所示，根据克鲁斯卡尔算法给出G的一棵最小生成树（要求给出生成过程的步骤） 16、已知有向图G=（V，E），其中 V={a,b,c,d,e,f,g},E={ d>, 17、设散列表为HT[13]，散列函数为H(key)=key % 13，用闭散列法解决冲突，对于下列关键码序列12，23，45，57，20，03，78，31，15，36构造表。若采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 18、已知二叉树的先序和中序序列如下，试构造出相应的二叉树。 先序：ABCDEFGHIJ 中序：CDBFEAIHGJ 19.有5个元素，其进栈次序为A,B,C,D,E,在各种可能的出栈次序中，以元素C,D最先出栈（即C第一个且D第二个出栈）的序列有哪些？ 20、已知一个无向连通网络G，如下图所示，根据克鲁斯卡尔和普里姆算法画出一棵最小生成树（要求写出求解过程的步骤）。 21、已知12个初始归并段，其长度分别为30，44，8，6，3，20，60，18，9，61，68，85。现要做4路外归并排序，试画出表示归并过程的最佳归并树。 22、设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需要记录的平均比较次数不超过2次。试问散列表需要设计多大？设a是散列表的装载因子，则有ASLsucc=(1/2)*[1+1/(1-a)]。 23、假定一组记录的排序码为(46，79，56，38，40，84，50，42)，若需利用堆排序方法将其排序为递增有序，请问应建立最小堆还是最大堆？并给出建立的初始堆。（5分） 24、设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连接，每个页块可存放30个记录。若采用按桶散列，且要求搜索到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？ 五、编程题 说明：本大题均要求有实现过程的说明。 1、假定数组A[n]中有多个零元素，试写出一个函数，将A中所有的非零元素依次移到数组A的前端。 2、设有一个线性表（e0，e1，…，e n-2，e n-1）存放在一个一维数组A[n]中的数据元素，请编写一个函数将这个线性表原地逆置，即将数组的这n个原址内容置换为（e n-1，e n-2，…，e1，e0），设数据元素e i为整型。 3、针对带表头结点的单链表，设计一个算法，通过一趟遍历在单链表中确定值最大的结点。函数首部为：ListNode* Max() 4、设二叉树的结点结构为（left，data，right）其中指针left和right分别指向结点的左右子女，请根据下面的函数声明编写出求一棵二叉树深度的算法，该深度由函数返回，参数BT 指向一棵二叉树。 5、针对带表头结点的单链表，设计一个算法，通过一趟遍历在单链表中确定值最小的结点。 6、假定二叉树采用二叉链表存储结构，试设计一个算法计算所有度为1的结点个数。 7假设二叉树采用二叉链表存储结构存储，试设计一个算法，计算一棵给定二叉树的所有结点数。 8设计一个算法，在带头结点的单链表head中删除一个data域值最小的结点。（假定该结点是唯一的）。 9、设顺序表A[1……m+n]中前m个元素递增有序，后n个元素递增有序，且这（m+n）个元素中没有重复元素，试设计一个迭代算法使得整个顺序表有序，要求算法时间尽可能少且空间复杂度为O(1)。 10、设计一个算法以统计出二叉树中大于给定值x的结点个数，该统计值由函数返回。 11、已知一棵用二叉链表表示的二叉树，其根指针为root，试编写一个递归算法，以计算二叉树中指定结点*p所在层次。 数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74 中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 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.对线性表，在下列哪种情况下应当采用链表表示？( ) 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网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 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的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 数据结构习题集 一、选择题 1．数据结构中所定义的数据元素，是用于表示数据的。（ C ） A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 2．从逻辑上可以把数据结构分为（ C ） A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 3．当待排序序列中记录数较少或基本有序时，最适合的排序方法为(A) A.直接插入排序法 B.快速排序法 C.堆排序法 D.归并排序法 4．关于串的的叙述，不正确的是( B) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 5．带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（A ）A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL 6．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B ） A.n/2 B.n C.(n+1)/2 D.n+1 7．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（A） A.n B.2n-1 C.2n D.n2 8．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为(B ) A.236 B.239 C.242 D.245 9．一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是(A ) A.dceab B.decba C.edcba D.abcde 10．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top 作为栈顶指针，则出栈处理后，top的值应修改为(D ) A.top=top B.top=n-1 C.top=top-1 D.top=top+1 11．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（ B ） A.13 B.35 C.17 D.36 12．栈和队列(C) A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表 C.共同之处在于二者都只允许在顶端执行删除操作 《数据结构》期中试卷（2009级） 2010-2011学年第一学期姓名：学号：成绩： 一、选择题：（每小题2分，共20分） 1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2.在一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（） 个元素。 A．8 B. 62.5 C. 62 D. 7 3. 已知广义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原子项e的运算是：( ) A.head(tail(A)) B.head(tail(tail(A))) C.head(head(tail(tail(A)))) D.head(tail(head(tail(A)))) 4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则入队 时的操作为（）。 A. front=( front +1) mod (m+1) B. rear=(rear+1) mod (m+1) C. front=( front +1) mod m D. rear=(rear+1) mod m 5. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指 针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。A．p->llink=q； q->rlink=p；p->llink->rlink=q；q->llink=q； B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink； C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q; D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q； 6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．以上答案都不对 7. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果 为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 8. 利用二叉链表存储树时，则根结点的右指针是（）。 A．指向最左孩子B．指向最右孩子C．空D．非空 9.设有二维数组A[0..9, 0..19], 其中每个元素占两个字节，第一个元素的存储地址为100， 若按列优先顺序存储，则元素A[6,6]存储地址为( )。 A. 252 B. 132 C. 352 D.232 10. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构综合练习题 数据结构（一） 一、选择题 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的度数数为（ 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) 希尔排序 11、以下说法正确的是（ A ） A.连通图的生成树，是该连通图的一个极小连通子图。 B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C.任何一个有向图，其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 12、以下说法错误的是 ( D ) A.一般在哈夫曼树中，权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点 C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树 一、是非题 1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发，都能访问到所有结点........( F ) 7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中，队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是（ D ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址（B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A．O(n) B．O(1) C．O(n2) D．O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点 的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B ) A．s一>1ink=p一>1ink；p一>1ink＝s B．q一>1ink＝s；s一>link=p C．p一>link＝s一>1ink；s一>1ink＝p 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 数据结构试题? 一、?单选题（每题 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(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 2010年招收攻读硕士学位研究生入学考试试题（副题） ******************************************************************************************** 学科、专业名称：计算机技术、软件工程 研究方向：各专业 考试科目名称：830数据结构 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一.选择题(每题2分，共40分) 1.具有n个顶点的完全有向图的边数为( ). A n(n-1)/2 B n(n-1) C n2 D n2-1 2.队列操作的原则是（） A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除 3. 顺序栈S的Pop(S, e)操作弹出元素e，则下列( )是正确的操作。 A. e=*(s.top) B. e=*(s.top--) C. e=*(--s.top) D. e=--s.top 4. 对具有n个结点的有序表折半查找时，其时间复杂度是 ( ) 。 A. O(log2n） B. O(nlog2n） C. O(n） D. O(n2） 5. 若线性表最常用的操作是存取第i个元素及其前趋的值,则采用( )存储方式节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 6. 线性表的链接实现有利于( )运算 A.插入 B. 读表元素 C .查找 D.定位 7. 设连通图G的顶点数为n,则G的生成树的边数为( ) A. n B. n-1 C.2n D. 2n-1 8.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。 A.n-i B.n-i+1 C.n-i-1 D. i 9. 若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n,则第i个输出元素是（） A.n-i B.n-i-1 C.n-i+1 D.不确定 10. 二叉树第i(i≥1)层上至多有( )个结点。 A. 2i B.2i C.2i-1 D.2i-1 11.串是一种特殊的线性表, 其特殊性体现在( ) A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个 12. 稀疏矩阵一般的压缩存储方法有两种,即: ( ) A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 考试科目：数据结构共 4 页，第 1 页 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构练习题 第一部分绪论 一、单选题 1. 一个数组元素a[i]与________的表示等价。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。 A、参数类型 B、参数个数 C、函数类型 3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数 A、指针 B、引用 C、值 4. 下面程序段的时间复杂度为____________。 for(int i=0; i 计算机学院2010-2011学年第一学期 《数据结构》试卷（A 卷）（考试时间：100分钟） 专业： 计算机专业 班级： 序号： 姓名： 注意：所有答案都必须写在答题纸上！！！ 三．简答（每小题10分，共50分） 1．有如图所示的有向图，请给出该图的: 1) 邻接矩阵表示； 2) 逆邻接表表示。 2．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13 的哈希表，（利用线性探测）请画出存放状态； 2) 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 3．请写出对序列{21，25，49，28，16，22，25，38}的二叉排序树构造过程。 4．试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。 5．如果一个项目由10个主要任务构成，其计划图展示了任务之间关系与任务所需天数，则项目关键路径如何求解，请展示其过程。 四．算法（10分，共10分） 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。 要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回负1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。 计算机学院2010-2011学年第一学期 《数据结构》答题纸（A卷）一．填空（2*20=40分） 数据结构综合练习题 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) 条边的有向图称为有向完全图。 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main()数据结构树练习题
数据结构-数据结构历年考题及答案2
(完整版)数据结构实验报告全集
数据结构试题及答案(免费)
数据结构综合习题集(含答案)
2010年数据结构期中考试试卷及答案
数据结构实验报告图实验
数据结构综合练习题
2010级数据结构期末复习题(E)
数据结构图的遍历实验报告
数据结构试题及答案
数据结构2010
数据结构实验报告图实验
数据结构习题与答案
数据结构练习题及参考答案
中国矿业大学2010年数据结构试卷及答案
数据结构-综合练习题-打印
数据结构实验报告无向图