数据结构复习
一、选择题
1、在有N个叶子结点的哈夫曼树中，其结点总数为（）。
A、不确定
B、2N
C、2N+1
D、2N-1
2、具有2000个结点的二叉树，其高度至少为（）。
A、9
B、10
C、11
D、12
3、对于任何一颗二叉树T，设N0、N1、N2分别是度为0、1、2的结点数，则N0=（）。
A、N0=N1+1
B、N0=N1+N2
C、N0=N2+1
D、N0=2N1+1
4、深度为K且为（）个结点的二叉树称为满二叉树（设根结点处于第1层）。
A、2K-1
B、2K
C、2K-1
D、2K-1
5、设一数列的顺序为1，2，3，4，5，6，通过队列操作可以得到（）的输出序列。
A、3，2，5，6，4，1
B、1，2，3，4，5，6
C、6，5，4，3，2，1
D、4，5，3，2，6，1
6、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（）。
A、3
B、4
C、5
D、1
7、下列哪一个程序片段是在链表中间插入一个结点。（假设新结点为NEW，欲插入在Pointer结点之后）
A、NEW->next=Pointer
B、 NEW->next=Pointer->next Pointer=NEW Pointer->next=NEW
C、Pointer->next=NEW->next
D、以上皆非
NEW->next=Pointer
8、线性表的链接实现有利于（）运算。
A、插入
B、读表元
C、查找
D、定位
9、线性表采用链式存储时，其地址（）。
A、必须是连续的
B、一定是不连续的
C、部分地址必须是连续的
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、抽象结构，逻辑结构
13、若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为11的元素的存储地址为（）。
A、140
B、143
C、144
D、136
14、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（）。
A、front=rear MOD n
B、rear=(front+1) MOD n
C、front=rear MOD n-1
D、front=(rear+1) MOD n
15、二叉树的中序序列与后序序列相同的所有二叉树为（）。
A、空树或只有根结点的二叉树
B、空树或缺左子树的单支树
C、空树或缺右子树的单支树
D、任意一棵树
16、线性结构的特点是（）。（在数据元素的非空有限集合中）
A、存在惟一的“第一个”数据元素和存在惟一的“最后一个”数据元素
B、除第一个数据元素之外，集合中的每一个数据元素都只有一个前驱
C、除最后一个数据元素之外，集合中的每一个数据元素都只有一个后继
D、以上都正确
17、在内部排序中，排序时不稳定的有（）。
A、直接插入排序
B、冒泡排序
C、简单选择排序
D、以上都不是
18、在一颗度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。
A、 4
B、 5
C、 6
D、 7
19、以二叉链表作为二叉树的存储结构，在有N个结点的二叉链表中，值为非空的链域的个数为（）。
A、 N-1
B、 2N-1
C、 N+1
D、 2N+1
20、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）二叉树。
A、空树或只有一个根结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
21、冒泡排序的时间复杂度为（）。
A、O(n2)
B、O(log2n)
C、O(nlog2n)
D、 O(n)
22、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。
A、单链表
B、双链表
C、单循环链表
D、顺序表
23、设p为栈，栈中的元素类型是char。下列程序段的运行结果为（）。
initstack(p);
x='c'; y='k';
push(p,x); push(p,'a'); push(p,y);
x=pop(p);
push(p,'t'); push(p,x);
x=pop(p);
push(p,'s');
while(!empty(p)) { y=pop(p); printf("%c",y); }
printf("%c",x);
A、sktac
B、stkac
C、stack
D、ksact
24、替换操作StrReplace("I AM A STUDENT","STUDENT","WORKER")的结果是（）。
A、"I AM A STUDENT"
B、"STUDENT"
C、"I AM A WORKER"
D、"WORKER"
25、完全二叉树的叶子结点只可能出现在（）。
A、最后一层上
B、第一层上
C、层次最大的两层上
D、第二层上
26、哈夫曼树是（）最小的二叉树。
A、路径长度
B、带权路径长度
C、度
D、权值
27、队列的逻辑结构与（）的逻辑结构不同。
A、线性表
B、栈
C、二叉树
D、串
28、线性链表不具有的特点是（）。
A、随机访问
B、不必事先估计所需存储空间大小
C、插入与删除时不必移动元素
D、所需空间与线性表长度成正比
29、对线性表进行折半查找时，要求线性表必须（）。
A、以顺序存储方式存储
B、以链式存储方式存储
C、以顺序存储方式存储，且数据元素有序
D、以链式存储方式存储，且数据元素有序
30、下列程序的时间复杂度为（）。
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) s++;
A、O(1)
B、O(n)
C、O(log2n)
D、 O(n2)
二、填空题
1、算法的特性包含有以下五个方面：________________、_________________、_________________、_________________、___________________。
2、链式存储结构中，结点分为两部分：、。
3、在堆栈中，通常将允许进行插入或删除的一端称为。
4、单链表表示法的基本思想是用____________表示结点间的逻辑关系。
5、在查找中，若关键字可以唯一标志一个记录，则称此关键字为。
三、判断题。正确的打“√”错误的打“×”。
1、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( )
2、数组是一组有固定个数的元素的集合。( )
3、顺序存储的线性表可以随机存取。（）
4、空串与由空格组成的串没有区别。( )
5、堆栈又叫做LIFO表。（）
6、深度为h的非空二叉树的第i层最多有2h-1 个结点。( )
7、完全二叉树就是满二叉树。( )
8、可以根据一棵二叉树的后序序列和中序序列唯一地构造出一棵二叉树。( )
9、非空二叉排序树的任意一棵子树也是二叉排序树。( )
10、有向图是一种非线性结构。( )
四、简答题
1、有8个带权结点A,B,C,D,E,F,G,H，其对应的权值分别为7，18，3，32，5，26，12，8，试以它们为叶子结点的结点值构造一颗哈夫曼树，写出该哈夫曼树中每个叶子结点的哈夫曼编码。
2、请将图1所示的二叉树转换成森林。
五、算法设计题
1、用递归算法求二叉树的深度，请将下面的算法补充完整。
已知二叉树的链式存储结构为：
typedef struct node
{ char data;
struct node *lchild, *rchild;
} BTCHINALR;
/*已知二叉树bt，求该二叉树的深度，并返回该二叉树的深度*/
Int treehigh ( BTCHINALR *bt )
{ int lh, rh, h; //lh、rh分别存放左、右子树的高度
if ______(1)_______
h = 0;
{ ______(2)_____________;
rh = treehigh ( bt->rchild );
h = ____(3)______________; //二叉树的深度为左、右子树的深度
//的最大值，再加1
}
_______(4)_______________
}
1.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) 。
A.n-i+1
B.n-i
C.i
D.i-1
2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。
A.顺序表
B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表
D.单链表
3.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( )。
A.4
B.5
C.6
D.7
4.为查找某一特定单词在文本中出现的位置，可应用的串运算是( )。
A.插入
B.删除
C.串联接
D.子串定位
5.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到( )。
A.P=″SCIENC″
B.P=″STUDY″
C.S=″SCIENCE″
D.S=″STUDY″
6.下列陈述中正确的是( )
A.二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点
D.二叉树中最多只有两棵子树，并且有左右之分
7、假定一个链队列的队首和队尾指针分别为front和rear，则判断队空的条件是( )
A、front==rear
B、front!=NULL
C、rear!=NULL
D、front==NULL
8、栈的插入与删除操作在( )进行。
A、栈顶
B、栈底
C、任意位置
D、指定位置
9、由权值分别为3,4,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
A、 24
B、 45
C、 72
D、 53
10、在一棵深度为6的完全二叉树中，至少含有( )个节点。
A、 24
B、 48
C、 72
D、 32
11、算法分析的目的是( )。
A、找出数据结构的合理性
B、研究算法中的输入/输出关系
C、分析算法的效率以求改进
D、分析算法的易读性
12、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。
A、单链表
B、双向链表
C、顺序表
D、循环链表
13、下面关于线性表的叙述中，错误的为( )。
A、顺序表使用一维数组实现的线性表
B、顺序表必须占用一片连续的存储单元
C、顺序表的空间利用率高于链表
D、在链表中，每个结点只有一个链域
14、带头结点的单链表head为空的判断条件是( )
A、head=NULL
B、head->next=NULL
C、head->next=head
D、head!=NULL
15、队列通常采用两种存储结构是( )
A、顺序存储结构和链表存储结构
B、散列方式和索引方式
C、链表存储结构和数组
D、线性存储结构和非线性存储结
构
16、按照二叉树的定义，具有3个结点的二叉树有( )种。
A、3
B、4
C、5
D、6
17、深度为5的二叉树至多有( )个结点。
A、16
B、32
C、31
D、10
18、对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )。
A、n
B、n+1
C、n-1
D、n+边数
19、在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。
A、n
B、n+1
C、n-1
D、n/2
20、在一个长度为n的顺序表的表尾插入一个新元素，其时间复杂度为( )。
A、O (n)
B、O (1)
C、O (n2 )
D、O (log2 n)
21、设单链表中结点的结构为（data , next）。已知指针q所指结点是指针p 所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？( )
A、s->next= p->next ; p->next=s
B、q->next=s ;s->next=p
C、p->next=s->next ;s->next=p
D、p->next=s ;s->next=q
22、若让元素1，2，3依次进栈，则出栈次序不可能出现第( )种情况。
A、3，2，1
B、2，1，3
C、3，1，2
D、1，3，2
23、在一棵用二叉链表表示的具有n个结点的二叉树中，所有结点的空链域共有( )个。
A、n
B、n-1
C、n+1
D、2*n
24、对长度为n的有序单链表，若搜索每个元素的概率相等，则利用顺序查找法搜索到表中任一元素的平均搜索长度为( )。
A、n/2
B、(n+1)/2
C、(n –1)/2
D、n/4
25、线性表采用链式存储时，结点的存储地址( )。
A、必须是不连续的
B、连续与否均可
C、必须是连续的
D、和头结点的存储地址相连续
26、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为( )。
A、O(1)
B、O(n)
C、O(m)
D、O(m+n)
27、以链表作为栈的存储结构，则出栈操作时（）。
A、必须判断栈是否满
B、判断栈元素的类型
C、必须判断本是否空
D、对栈不做任何判断
28、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear 为队尾指针，则执行出队操作后其头指针front值为( )。
A、front=front+1
B、front=(front+1)%(m-1)
C、front=(front-1)%m
D、front=(front+1)%m
29、如下陈述中正确的是（）。
A、串是一种特殊的线性表
B、串的长度必须大于零
C、串中元素只能是字母
D、空串就是空白串
30、在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为()。
A、4
B、5
C、6
D、7
31、在有N个叶子结点的哈夫曼树中，其结点总数为（）。
A、不确定
B、2N
C、2N+1
D、2N-1
32、具有2000个结点的二叉树，其高度至少为（）。
A、9
B、10
C、11
D、12
33、对于任何一颗二叉树T，设N0、N1、N2分别是度为0、1、2的结点数，则N0=（）。
A、N0=N1+1
B、N0=N1+N2
C、N0=N2+1
D、N0=2N1+1
34、深度为K且为（）个结点的二叉树称为满二叉树（设根结点处于第1层）。
A、2K-1
B、2K
C、2K-1
D、2K-1
35、设一数列的顺序为1，2，3，4，5，6，通过队列操作可以得到（）的输出序列。
A、3，2，5，6，4，1
B、1，2，3，4，5，6
C、6，5，4，3，2，1
D、4，5，3，2，6，1
36、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（）。
A、3
B、4
C、5
D、1
37、下列哪一个程序片段是在链表中间插入一个结点。（假设新结点为NEW，欲插入在Pointer结点之后）
A、NEW->next=Pointer
B、 NEW->next=Pointer->next Pointer=NEW Pointer->next=NEW
C、Pointer->next=NEW->next
D、以上皆非
NEW->next=Pointer
38、线性表的链接实现有利于（）运算。
A、插入
B、读表元
C、查找
D、定位
39、线性表采用链式存储时，其地址（）。
A、必须是连续的
B、一定是不连续的
C、部分地址必须是连续的
D、连续与否均可以
40、二叉树第I（I≥1）层上至多有（）结点。
A、 2I
B、 2I
C、 2I-1
D、 2I-1
41、线性表是（）。
A、一个有限序列，可以为空
B、一个有限序列，不可以为空
C、一个无限序列，可以为空
D、一个无限序列，不可以为空
42、数据结构是研究数据的（）以及它们之间的相互关系。
A、理想结构，物理结构
B、理想结构，抽象结构
C、物理结构，逻辑结构
D、抽象结构，逻辑结构
43、若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为11的元素的存储地址为（）。
A、140
B、143
C、144
D、136
44、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（）。
A、front=rear MOD n
B、rear=(front+1) MOD n
C、front=rear MOD n-1
D、front=(rear+1) MOD n
45、二叉树的中序序列与后序序列相同的所有二叉树为（）。
A、空树或只有根结点的二叉树
B、空树或缺左子树的单支树
C、空树或缺右子树的单支树
D、任意一棵树
46、线性结构的特点是（）。（在数据元素的非空有限集合中）
A、存在惟一的“第一个”数据元素和存在惟一的“最后一个”数据元素
B、除第一个数据元素之外，集合中的每一个数据元素都只有一个前驱
C、除最后一个数据元素之外，集合中的每一个数据元素都只有一个后继
D、以上都正确
47、在内部排序中，排序时不稳定的有（）。
A、直接插入排序
B、冒泡排序
C、简单选择排序
D、以上都不是
48、在一颗度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。
A、 4
B、 5
C、 6
D、 7
49、以二叉链表作为二叉树的存储结构，在有N个结点的二叉链表中，值为非空的链域的个数为（）。
A、 N-1
B、 2N-1
C、 N+1
D、 2N+1
50、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）二叉树。
A、空树或只有一个根结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
51、冒泡排序的时间复杂度为（）。
A、O(n2)
B、O(log2n)
C、O(nlog2n)
D、 O(n)
52、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。
A、单链表
B、双链表
C、单循环链表
D、顺序表
53、设p为栈，栈中的元素类型是char。下列程序段的运行结果为（）。
initstack(p);
x='c'; y='k';
push(p,x); push(p,'a'); push(p,y);
x=pop(p);
push(p,'t'); push(p,x);
x=pop(p);
push(p,'s');
while(!empty(p)) { y=pop(p); printf("%c",y); }
printf("%c",x);
A、sktac
B、stkac
C、stack
D、ksact
54、替换操作StrReplace("I AM A STUDENT","STUDENT","WORKER")的结果是（）。
A、"I AM A STUDENT"
B、"STUDENT"
C、"I AM A WORKER"
D、"WORKER"
55、完全二叉树的叶子结点只可能出现在（）。
A、最后一层上
B、第一层上
C、层次最大的两层上
D、第二层上
56、哈夫曼树是（）最小的二叉树。
A、路径长度
B、带权路径长度
C、度
D、权值
57、队列的逻辑结构与（）的逻辑结构不同。
A、线性表
B、栈
C、二叉树
D、串
58、线性链表不具有的特点是（）。
A、随机访问
B、不必事先估计所需存储空间大小
C、插入与删除时不必移动元素
D、所需空间与线性表长度成正比
59、对线性表进行折半查找时，要求线性表必须（）。
A、以顺序存储方式存储
B、以链式存储方式存储
C、以顺序存储方式存储，且数据元素有序
D、以链式存储方式存储，且数据元素有序
60、下列程序的时间复杂度为（）。
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) s++;
A、O(1)
B、O(n)
C、O(log2n)
D、 O(n2)
二、填空题
1、数据的逻辑结构是从逻辑关系上描述数据，它与数据的___________无关，是独立于计算机的。
2、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=______________。
3、已知一棵完全二叉树中共有400结点，则该树中共有_________个叶子结点。
4、在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__________。
5、二叉树的第i(i≥1)层上至多有_________个结点。
6. 关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为。
7. 直接插入排序算法的时间复杂度是。
8. 列的插入操作在________进行，删除操作在进行。
9. 一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为。
10. 一棵树中，结点没有前驱结点。
11. 设由字符串a=′data′、b=′structure′、c=′-′,则a与c连接然后与b连接的结果为：________。
12.有一段语句如下：
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;
在这段程序中，s++执行的次数是________，这段程序的时间复杂度是________。
13. 数据元素之间的关系称为数据的逻辑结构，它通常有四种基本结构，分别是：集合结构、_____________、______________、_______________。
14.已知一棵二叉树如图1所示，该二叉树的先序遍历序列是___________________、中序遍历序列是______________________、后序遍历序列是___________________。
图1 二叉树
15、算法的特性包含有以下五个方面：________________、_________________、_________________、_________________、___________________。
16、链式存储结构中，结点分为两部分：、。
17、在堆栈中，通常将允许进行插入或删除的一端称为。
18、单链表表示法的基本思想是用____________表示结点间的逻辑关系。
19、在查找中，若关键字可以唯一标志一个记录，则称此关键字为。
20、数组的顺序存储结构有两种：按行序存储和。
21、在二叉排序树中，左子树上所有的结点的值都它的根结点的值，而右子树上所有结点的值都__________它的根结点的值。
22、在排序的过程中，如果整个排序过程完全在内存中进行，称为___________。
23、从稳定性角度来说，归并排序是______________的排序方法。
24、在顺序表中插入和删除一个数据元素时，时间主要耗费在__________上，所以当表中的元素较多时，算法的效率较低。
25、在图状结构中，数据元素间存在着_______________的关系。
26、二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，D，H，其后序遍历序列为__________________。
27、输入一个序列{34，76，45，18，26，54，92，65}，将它们依次插入一棵二叉排序树，则该二叉排序树的深度是__________________。
28、从待排序序列中选择一个元素，该元素将待排序序列分成前后两个部分，前一部分中所有元素都小于等于所选元素。后一部分中所有元素都大于等于所选元素，这种排序方法称为_____________排序法。
三、判断题。正确的打“√”, 错误的打“×”。
1. 在线性结构中，每个结点都有一个直接前驱和一个直接后继。
( )
2. 简单选择排序是一种不稳定的排序方法。( )
3. 折半查找法只适用于有序表，包括有序的顺序表和有序的链表。( )
4. 选择排序过程中元素之间的比较次数与原始序列的状态无关。( )
5. 二维数组可以视为数组元素为一维数组的一维数组。（）
6.冒泡排序是稳定的。( )
7. 树是一种线性结构。
（）
8. 哈夫曼树又称为最优二叉树。( )
9. 根据二叉树的先序序列和中序序列，可以构造多种形态的二叉树。（）
10. 一棵深度为k且有2k-1个节点的二叉树称为满二叉树。（）
21、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( )
22、数组是一组有固定个数的元素的集合。( )
23、顺序存储的线性表可以随机存取。（）
24、空串与由空格组成的串没有区别。( )
25、堆栈又叫做LIFO表。（）
26、深度为h的非空二叉树的第i层最多有2h-1 个结点。( )
27、完全二叉树就是满二叉树。( )
28、可以根据一棵二叉树的后序序列和中序序列唯一地构造出一棵二叉树。
( )
29、非空二叉排序树的任意一棵子树也是二叉排序树。( )
30、有向图是一种非线性结构。( )
四、应用题
1、请将图2所示的森林转换成二叉树。
图2 森林
2、有7个带权结点A,B,C,D,E,F,G，其对应的权值分别为6，9，10，4，
7，18，32，试以它们为叶子结点的权值构造一颗哈夫曼树，写出该哈夫曼树中每个叶子结点的哈夫曼编码。
3、已知一棵二叉树的先序序列为ABDECFGH，中序序列为DBEAGHFC。根
据这两个序列构造一棵相应的二叉树。
4、以关键字序列{40，28，6，72，100，3，54}为例，手工执行直接插
入排序算法，写出每一趟排序结束时的关键字状态。
答案
一、选择题
二、填空题
1、存储（或存储结构）
2、p->next->next
3、200
4、２
5、2i-1
6、48 44 52 63 80 91
7、O(n2)
8、队尾、队头
9、3
10、根
11、"data-structure"
12、n*(n+1)/2 O(n2)
13、线性结构、树型结构、图状结构
14、ABDEHICFJG、DBHEIAFJCG、DHIEBJFGCA
15、有限性、确定性、可行性、输入、输出
16、数据域指针域
17、栈顶
18、指针
19、主关键字
20、按列存储
21、小于大于
22、内部排序
23、稳定的
24、移动元素
25、多对多
26、E，F，C，G，H，D，B，A
27、4
28、快速
三、判断题。正确的打“√”错误的打“×”。
四、应用题
1、对应的二叉树为
2、参考的哈夫曼树为：
哈夫曼编码如下：
A 0001
B 101
C 001
D 0000
E 100
F 11
G 01
3、
4、
初始状态： 40 28 6 72 100 3 54
第1趟：{40} 28 6 72 100 3 54
第2趟：{28 40} 6 72 100 3 54
第3趟：{6 28 40} 72 100 3 54
第4趟：{6 28 40 72} 100 3 54
第5趟：{6 28 40 72 100} 3 54
第6趟：{3 6 28 40 72 100} 54
第7趟：{3 6 28 40 54 72 100}
硬盘数据组织结构
EBR，叫做扩展MBR（Extended MBR），位于硬盘的某柱面0磁道1扇区 1.簇（cluster） 是DOS给文件系统分配磁盘空间的最小单位。由若干连续的逻辑扇区组成，不同的盘，簇的大小不同，簇是从2开始编号，见表6-1。 逻辑扇区号=（簇号-2）×扇区数/簇+数据区首扇区号 2.BOOT记录： 第一部分：0～2字节为跳转指令，转向启动码区。 第二部分：3～10字节为厂商标识字段，如MSDOS5.0。 第三部分：11～61字节为磁盘参数表（51字节）。 第四部分：62～509字节为启动程序（438字节）。 最后：55,AA字节。 51字节BPB表（BIOS Parameter Block） OB－OC：每扇区字节数(512) OD：扇区数/簇 0E－0F：保留扇区（指Boot区） 10：FAT个数 11－12：根目录最大登记项数 13－14：本分区扇区总数（小于32M的分区，大于32MB时,为0） 15：介质描述符 16－17：每个FAT扇区数 18－19：每道扇区数 1A－1B：磁头数 1C－1F：本分区前的扇区数（隐含扇区，即从0（X）柱0头1扇到0（X）柱1头1扇之间的扇区，由于不能为DOS访问，故称为隐含扇区）。 20－23：大容量盘总扇区数。 24：BIOS设备号（hex：HD=8x） 25：未使用 26：扩展引导标记（29H） 27-2A：卷序列号（随机） 2B-35：卷标，分区标识，如：WIN98 36-3D：文件系统格式（FAT16） 3.FAT（文件配置表） FAT有两个，当第一个损坏时，为人工修复提供方便，DOS不会自动用第二个去修复第一个FAT，而DOS实际上没有用尽2个FAT占用的扇区，因为可作为他用。FAT登记盘上簇的使用情况，登记项有12位、16位和32位之分，下面以16位为例说明FAT的格式。 16位FAT格式： 簇号（表项） 0000H 0001H 0002H … NNNNH 类型保留簇使用簇 含义介质标志记录文件簇号链
全国自学考试数据结构导论试题及答案(4套)
全国2011年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中，度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
数据结构实验报告
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 数据模型所描述的内容包括三个部分：数据结构、数据操作、数据约束。 1）数据结构:数据模型中的数据结构主要描述数据的类型、内容、性质以及数据间的联系等。数据结构是数据模型的基础，数据操作和约束都建立在数据结构上。不同的数据结构具有不同的操作和约束。 2）数据操作:数据模型中数据操作主要描述在相应的数据结构上的操作类型和操作方式。 3）数据约束：数据模型中的数据约束主要描述数据结构内数据间的语法、词义联系、他们之间的制约和依存关系，以及数据动态变化的规则，以保证数据的正确、有效和相容。 数据模型按不同的应用层次分成三种类型：分别是概念数据模型、逻辑数据模型、物理数据模型。 1、概念数据模型（Conceptual Data Model）：简称概念模型，主要用来描述世界的概念化结构，它使数据库的设计人员在设计的初始阶段，摆脱计算机系统及DBMS的具体技术问题，集中精力分析数据以及数据之间的联系等，与具体的数据管理系统（Database Management System，简称DBMS）无关。概念数据模型必须换成逻辑数据模型，才能在DBMS中实现。 概念数据模型是最终用户对数据存储的看法，反映了最终用户综合性的信息需求，它以数据类的方式描述企业级的数据需求，数据类代表了在业务环境中自然聚集成的几个主要类别数据。 概念数据模型的内容包括重要的实体及实体之间的关系。在概念数据模型中不包括实体的属性，也不用定义实体的主键。这是概念数据模型和逻辑数据模型的主要区别。 概念数据模型的目标是统一业务概念，作为业务人员和技术人员之间沟通的桥梁，确定不同实体之间的最高层次的关系。 在有些数据模型的设计过程中，概念数据模型是和逻辑数据模型合在一起进行设计的。 2、逻辑数据模型（Logical Data Model）:简称数据模型，这是用户从数据库所看到的模型，是具体的DBMS所支持的数据模型，如网状数据模型(Network Data Model)、层次 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为( A ) 邻接矩阵的实现 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. #include 2. #include 全国2010年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k； 17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 《数据结构》实验报告 班级：网络1311 学号：10 姓名：曾梦成绩： 实验1：指针和结构体程序设计 1．实验目的 （1）复习C（或C++）语言的基本描述方法。 （2）熟练掌握数组的用法。 （3）提高运用C（或C++）语言解决实际问题的能力。 2．实验内容 设一个班有10个学生，每个学生有学号，以及数学、物理、英语、语文、体育5门课的成绩信息。分别写3个函数以实现以下3个要求： （1）求数学的平均成绩。 （2）对于有两门以上课程不及格的学生，输出他们的学号、各门课成绩及平均成绩。 （3）输出成绩优良的学生（平均成绩在85分以上或全部成绩在80分以上）的学号、各门课成绩和平均成绩。 3．实验要求 （1）利用C（或C++）语言完成程序设计。 （2）上机调试通过实验程序。 （3）输出10个学生的学号和数学、物理、英语、语文、体育5门课的成绩，检验程序运行的正确性。 （4）总结整个程序的组成和设计思想。 （5）撰写实验报告（把输入数据及运行结果用抓图的形式粘贴到实验报告上）。 4．实验程序 #include printf("成绩输入按照数学物理英语语文体育的顺序"); for(i=0;i 第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next; 2012年10月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分。 1.下面几种算法时间复杂度阶数中，值最大的是 A.O(nlog2n) B.O(n2) C.O(n) D.O(2n) 2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为 A.正确性 B.易读性 C.健壮性 D.时空性 3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为 A.40 B.60 C.61 D.100 4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是 A. head->next==head B. head->next==NULL C. head!=NULL D. head==NULL 5.在链栈的运算中，不需要 ．．．判断栈是否为空的是 A.出栈 B.进栈 C.取栈顶元素 D.求链栈的元素个数 6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是 A.A，B，C，D B.B，C，D，A C.D，C，B，A D.C，D，B，A 7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是 A.100 B.108 C.114 D.116 8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为 A.4 B.5 C.6 D.无法确定 9.m个叶结点的哈夫曼树中，其结点总数为 A.m B.2m+1 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 天津科技大学 2015—2016学年第2学期数据结构实验任务书 课程名称：数据结构实验学时： 2 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的： 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 实验内容： 定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 实验提示： 学生信息的定义： typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int score; //成绩 }Student; 顺序表的定义 typedef struct { Student *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList； 链表的定义： typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 实验要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。 (5) 以班为单位实验周周五上传源程序和实验报告。顺序表的源程序保存为SqList.cpp，链表的源程序保存为LinkList.cpp，实验报告命名为：实验报告1.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如07081211薛力.rar。数据结构实验一 实验报告
自考数据结构导论复习资料
数据结构实验十一：图实验
数据模型所描述的内容包括三个部分
数据结构实验---图的储存与遍历
自考数据结构导论
数据结构实验报告图实验
数据结构实验1
2010年1月自考数据结构导论真题
数据结构实验
数据结构 _实验1
自考02142《数据结构导论》串讲笔记
数据结构实验一 实验报告
02142数据结构导论份真题及答案.doc
数据结构实验报告图实验
数据结构实验1