《数据结构》-1自考试卷及答案
- 格式：doc
- 大小：64.49 KB
- 文档页数：9
《数据结构》-1
一、判断题 (每小题1分，共10分)
1、线性表的逻辑顺序与物理顺序总是一致的。( )
2、线性表只能采用顺序存储结构或者链式存储结构。( )
3、线性表的顺序存储表示优于链式存储表示。( )
4、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。( )
5、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( )
6、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( )
7、一般树和二叉树的结点数目都可以为0。( )
8、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。( )
9、每种数据结构都应具备三种基本运算：插入、删除和搜索。( )
10、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。( )
二、单项选择题 (每小题2分，共20分)
1、算法分析的目的是( )
A.研究算法的输入与输出之间的关系
B.找出数据结构的合理性
C.分析算法的效率以求改进算法
D.分析算法的可读性与可移植性
2、已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作( )
A. s->link = p； p->link = s；
B. s->link = p->link； p->link = s；
C. s->link = p->link； p = s；
D. p->link = s； s->link = p； 3、 图的深度优先搜索类似于树的（ ）次序遍历。
A.先根 B.中根 C.后根 D.层次
4、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（ ）
A. 1，3，2，4 B. 2，3，4，1
C. 4，3，1，2 D. 3，4，2，1
5、若深度为5的完全二叉树的第5层有3个叶结点，则该二叉树一共有( )个结点。
A.15 B.16 C.17 D.18
6、下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关（ ）
A. 直接插入排序 B. 起泡排序
C. 快速排序 D. 直接选择排序
7、对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，38 ,50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是( )
A.插入排序法 B.选择排序法
C.冒泡排序法 D.堆积排序法
8、对于循环队列，存储空间大小为n，头指针为F，尾指针为R。则队列中元素的个数为( )
A.R-F B.n+R-F C.(R-F+1)mod n D.(n+R-F）mod n
9、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ）
A. 9 B. 11 C. 12 D. 不确定
10、对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=( )
A.n1+1 B.n1+n2 C.n2+1 D.2n1+1
三、填空题 (每空2分，共8分)
1、从逻辑结构看，栈是 ，图是 。
2、具有2000个结点的二叉树，其深度至少为_________。
3、在序列(2，5，8，11，15，16，22，24，27，35，40)中采用折半查找(二分查找)方法查找元素24，需要进行_________次元素之间的比较。 四、简答画图题：（第1小题12分，其余每小题9分，共48分）
1、请简述以下概念：
物理结构、二叉树、连通图
2、设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出每趟排序后的结果。
3、请将图1所示的树结构转化为二叉树结构。
图1
4、请给出图2所示二叉树的先序遍历序列和后序遍历序列。
B C
D E F
J G A
H B C D
E F G
H I J A
图2
5、从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。
五、给出冒泡排序算法的C语言描述（14分）
I
《数据结构》-1参考答案
一、判断题 (每小题1分，共10分)
F T F F T T T T T T
评分标准：每题答案判断正确给1分，否则不给分。
二、单项选择题 (每小题2分，共20分)
CBACD DCDBC
评分标准：每题答案选择正确给2分，否则不给分。
三、填空题 (每空2分，共8分)
1.线性结构，非线性结构
2、11__
3、___4____
评分标准：每小题填写正确给2分，否则不给分。
四、简答画图题：（第1小题12分，其余每小题9分，共48分）
1、请简述以下概念：
物理结构、二叉树、连通图
物理结构是相互之间存在一种或多种特定关系的数据集合在内存中如何存储，也叫存储结构。
二叉树是每个节点最多有两个子树的树结构。
如果图中任意两点都是连通的，那么图被称作连通图。
2、设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出每趟排序后的结果。
170 275 154 503 512 765 612 897 677 908 E 154 170 275 503 512 677 612 765 897 908
154 170 275 503 512 612 677 765 897 908
3、请将图1所示的树结构转化为二叉树结构。
图1
C
D
G
H
I
J B C D
E F G
H I J A
A
B
F
4、请给出图2所示二叉树的先序遍历序列和后序遍历序列。
图2
先序遍历：ABDHECFIJG
后序遍历：HDEBIJFGCA
5、从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。
B C
D E F
I J G A
H
13 31
7 15
20 37 25
评分标准：每小题回答正确给9分，否则酌情给分，或者不给分。
五、冒泡排序算法（14分）
void Bubblesort(ElenType R[],int n )
{
int flag=1;
int i,j;
for(i=1;i { flag=0; for(j=n-1;j>=i;j--____ ) if(R[j] { ElemType t=R[j]; R[j]=R[j-1]; R[j-1]=t; flag=1; } if(flag==0___) return; } } 评分标准：回答正确给14分，否则酌情给分，或者不给分。
