全国2004年1月自考（课程代码：02142）数据结构导论试题
全国2004年1月高等教育自学考试
数据结构导论试题
课程代码：02142
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列数据组织形式中，（ ）的各个结点可以任意邻接。
A．集合 B．树形结构
C．线性结构 D．图状结构
2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ ）
A．O（log2n） B．O(n)
C．O(nlog2n) D．O(n2)
3．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）
A．单链表 B．双链表
C．循环链表 D．顺序表
4．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为
q=NULL;
while (p!=NULL)
{
（ ）
}
p=q;
A．r=q; q=p; p=p -> next; q -> next=r;
B．q=p; r=q; p=p -> next; q -> next=r;
C．r=q; p=p -> next; q=p; q -> next=r;
D．q=p; p=p -> next; r=q; q -> next=r;
5．数组通常具有两种基本运算，即（ ）
A．创建和删除 B．索引和修改
C．读和写 D．排序和查找
6．除根结点外，树上每个结点（ ）
A．可有任意多个孩子、任意多个双亲
B．可有任意多个孩子、一个双亲
C．可有一个孩子、任意多个双亲
D．只有一个孩子、一个双亲
7．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。
A．50 B．99
C．100 D．101
8．邻接表是图的一种（ ）
A．顺序存储结构 B．链式存储结构
C．索引存储结构 D．散列存储结构
9．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ）
A．G肯定不是完全图 B．G一定不是连通图
C．G中一定有回路 D．G有2个连通分量
10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ）
A．n/2 B．n
C．(n+1)/2 D．n+1
11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（ ）
A．该中间位置 B．该中间位置－1
C．该中间位置＋1 D．该中间位置／2
12．散列文件不能（ ）
A．随机存取 B．索引存取
C．按关键字存取 D．直接存取
13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（ ）
A．n/2 B．n
C．n/4 D．log n
14．下列关键码序列中，属于堆的是（ ）
A．（15，30，22，93，52，71） B．（15，71，30，22，93，52）
C．（15，52，22，93，30，71） D．（93，30，52，22，15，71）
15．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（ ）
A．16，28，34，54，73，62，60，26，43，95
B．28，16，34，54，62，73，60，26，43，95
C．28，16，34，54，62，60，73，26，43，95
D．16，28，34，54，62，60，73，26，43，95
二、填空题（本大题共13小题，每小题2分，共26分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．下列程序段的时间复杂性量级是_____________。
for (i=1;i<n; i++)
for (j=1; j<i; j++)
t=t+1;
17．在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动_____________个元素。
18．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：
_____________；
sq -> data[sq -> top]=x；
19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。
20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m, T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为_____________。
21．在下列树中，结点H的祖先为_____________。
22．顶点数为n、边数为n(n-1)/2的无向图称为_____________。
23．动态查找表在开散列表上通常采用_____________来解决冲突问题。
24．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。
25．查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于______________。
26．文件的基本运算包括______________和修改两类。
27．在排序方法中，依次将每个记录插入到一个有序的子序列中去，即在第i(i≥1)遍整理时，r1,r2,…,ri-1已经是排好顺序的子序列，取出第i个元素ri，在已排好序的子序列里为ri找到一个合适的位置，并把它插到该位置上。这种排序方法被称为___________。
28．快速排序法在待排序数据_____________的情况下最不利于发挥其长处。
三、应用题（本大题共5小题，共30分）
29．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）
30．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）
31．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分）
32．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=k mod 6，采用线性探测法解决冲突，要求：（7分）
（1）构造散列表；
（2）求查找数34需要的比较次数。
33．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的每一趟的结果。（8分）
四、设计题（本大题共2小题，共14分）
34．设某头指针为head的单链表的结点结构说明如下：（6分）
typedef struct node1
{
int data;
struct node1*next
}node;
试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。
35．编写一个算法 void DisplayQueue ()，产生50个300～600之间的随机整数（调用一次MyRand()可产生一个符合条件的随机整数）。每产生一个数据，若是奇数，则入队列，若是偶数，则从队首取出一个数据。要求：（8分）
（1）队列用链表实现；
（2）每产生一个数显示一次相应操作后的队列当前状态；
（3）无需定义函数int MyRand()；
（4）显示队列可调用函数 void DisOne (QueptrTp lq)，也无需定义；
（5）设链队列定义为：
typedef struct linked_queue
{int data;
struct linked_queue*next;
}LqueueTp;
typedef struct queueptr
{ LqueueTp *front, *rear;
}QueptrTp;
QueptrTp lq;
试题word文档下载：
数据结构导论试题
课程代码：02142
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列数据组织形式中，（ ）的各个结点可以任意邻接。
A．集合 B．树形结构
C．线性结构 D．图状结构
2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ ）
A．O（log2n） B．O(n)
C．O(nlog2n) D．O(n2)
3．在线性表的下列存储结构中，读取元素花费时间最少的是（ ）
A．单链表 B．双链表
C．循环链表 D．顺序表
4．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为
q=NULL;
while (p!=NULL)
{
（ ）
}
p=q;
A．r=q; q=p; p=p -> next; q -> next=r;
B．q=p; r=q; p=p -> next; q -> next=r;
C．r=q; p=p -> next; q=p; q -> next=r;
D．q=p; p=p -> next; r=q; q -> next=r;
5．数组通常具有两种基本运算，即（ ）
A．创建和删除 B．索引和修改
C．读和写 D．排序和查找
6．除根结点外，树上每个结点（ ）
A．可有任意多个孩子、任意多个双亲
B．可有任意多个孩子、一个双亲
C．可有一个孩子、任意多个双亲
D．只有一个孩子、一个双亲
7．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。
A．50 B．99
C．100 D．101
8．邻接表是图的一种（ ）
A．顺序存储结构 B．链式存储结构
C．索引存储结构 D．散列存储结构
9．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ）
A．G肯定不是完全图 B．G一定不是连通图
C．G中一定有回路 D．G有2个连通分量
10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ）
A．n/2 B．n
C．(n+1)/2 D．n+1
11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（ ）
A．该中间位置 B．该中间位置－1
C．该中间位置＋1 D．该中间位置／2
12．散列文件不能（ ）
A．随机存取 B．索引存取
C．按关键字存取 D．直接存取
13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（ ）
A．n/2 B．n
C．n/4 D．log n
14．下列关键码序列中，属于堆的是（ ）
A．（15，30，22，93，52，71） B．（15，71，30，22，93，52）
C．（15，52，22，93，30，71） D．（93，30，52，22，15，71）
15．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（ ）
A．16，28，34，54，73，62，60，26，43，95
B．28，16，34，54，62，73，60，26，43，95
C．28，16，34，54，62，60，73，26，43，95
D．16，28，34，54，62，60，73，26，43，95
二、填空题（本大题共13小题，每小题2分，共26分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．下列程序段的时间复杂性量级是_____________。
for (i=1;i<n; i++)
for (j=1; j<i; j++)
t=t+1;
17．在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动_____________个元素。
18．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：
_____________；
sq -> data[sq -> top]=x；
19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。
20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m, T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为_____________。
21．在下列树中，结点H的祖先为_____________。
22．顶点数为n、边数为n(n-1)/2的无向图称为_____________。
23．动态查找表在开散列表上通常采用_____________来解决冲突问题。
24．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。
25．查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于______________。
26．文件的基本运算包括______________和修改两类。
27．在排序方法中，依次将每个记录插入到一个有序的子序列中去，即在第i(i≥1)遍整理时，r1,r2,…,ri-1已经是排好顺序的子序列，取出第i个元素ri，在已排好序的子序列里为ri找到一个合适的位置，并把它插到该位置上。这种排序方法被称为___________。
28．快速排序法在待排序数据_____________的情况下最不利于发挥其长处。
三、应用题（本大题共5小题，共30分）
29．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）
30．分别写出下列二叉树的先根、中根、后根遍历序列。（6分）
31．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分）
32．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=k mod 6，采用线性探测法解决冲突，要求：（7分）
（1）构造散列表；
（2）求查找数34需要的比较次数。
33．已知序列（503，87，512，61，908，170，897，275，653，462）请给出采用快速排序法作升序排序时的每一趟的结果。（8分）
四、设计题（本大题共2小题，共14分）
34．设某头指针为head的单链表的结点结构说明如下：（6分）
typedef struct node1
{
int data;
struct node1*next
}node;
试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。
35．编写一个算法 void DisplayQueue ()，产生50个300～600之间的随机整数（调用一次MyRand()可产生一个符合条件的随机整数）。每产生一个数据，若是奇数，则入队列，若是偶数，则从队首取出一个数据。要求：（8分）
（1）队列用链表实现；
（2）每产生一个数显示一次相应操作后的队列当前状态；
（3）无需定义函数int MyRand()；
（4）显示队列可调用函数 void DisOne (QueptrTp lq)，也无需定义；
（5）设链队列定义为：
typedef struct linked_queue
{int data;
struct linked_queue*next;
}LqueueTp;
typedef struct queueptr
{ LqueueTp *front, *rear;
}QueptrTp;
QueptrTp lq;
试题word文档下载：
 |
全国2004年1月自考（课程代码：02142）数据结构导论试题.doc |