全国2013年1月自考试卷数据结构试题02331
全国2013年1月高等教育自学考试
数据结构试题
课程代码：02331
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题
纸”的相应代码涂黑。错涂、多涂或未涂均无分。
1．数据的逻辑结构可以分为
A．动态结构和静态结构 B.顺序结构和链式结构
C．线性结构和非线性结构 D.简单结构和构造结构
2．线性表是一个有限序列，组成线性表的基本单位是
A．数据项 B.数据元素
C．数据域 D.字符
3．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可
能的出栈序列是
A．dcba B.cbda
C．cadb D.cdba
4．稀疏矩阵的三元组表是
A．顺序存储结构 B.链式存储结构
C．索引存储结构 D.散列表存储结构
5．已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是
A．5 B.6
C．7 D.8
6．下列编码集合中，属于前缀编码的一组是
A.{11,10,001,101,0001} B.{00,010,0110,1000}
C.{11,01,001,0101,0001} D.{0,10,110,1011}
7.如题7图所示二叉树的中序序列为
A．ACDB
B．DCBA
C．CDBA
D．ABCD
题7图
8．有向图中所有顶点入度之和与所有顶点出度之和的比是
A．1/2 B.1
C．2 D.4
9．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是
A.e B.2e
C.n2-2e D.n2-e
10.n个顶点的无向连通图，其生成树的边数为
A.n-l B.n
C.n+l D.nlogn
11．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为
A．2 B.3
C．4 D.5
12．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是
A.(13,44,55,26,8,29) B.(13,26,55,44,8,29)
C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)
13．采用分块查找时，要求数据
A．块内有序 B.分块有序
C．分块无序 D.每块中数据个数必须相同
14.下列关于散列函数的说法正确的是
A．散列函数越复杂越好
B.散列函数越简单越好
C．用除余法构造的散列函数是最好的
D.在冲突尽可能少的情况下，散列函数越简单越好
15.下列关于m阶B树的叙述中，错误的是
A．每个结点至多有m棵子树
B.每个结点至多有m-1个关键字
C．所有的叶结点均在同一层上
D.根结点至少有棵子树
二、填空题（本大题共10小题，每小题2分，共20分）
16．算法的时间复杂度与实现时采用的程序设计语言____________。
17．在长度为n的顺序表的第i(1≤i≤n)个元素之后插入一个元素时，需向后移动___________个元素。
18．设循环队列存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为___________。
19．树的前序遍历序列等同于该树对应二叉树的____遍历序列。
20．一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是___________。
21．当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是____。
22．采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数
为___________。
23．对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的
算法是___________。
24．在16个记录的有序顺序表中进行二分查找，最大比较次数是___________。
25．在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是___________的。
三、解答题（本大题共4小题，每小题5分，共20分）
26．在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么？
27．画出题27图所示树的孩子链表。
题27图
28．已知一个无向图G如题28图所示，以顶点①为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。
题28图
29．判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。
①(1,5,7,20,18,8,10,40)
②(18,9,5,8,4,17,21,6)
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30．单链表类型定义如下：
typedef struct node {
DataType data;
struct node *next;
}ListNode;
typedef ListNode *LinkList;
阅读下列算法，并回答问题：
void f30 (LinklList head, DataType x)
{ ∥head是带头结点的非空单链表的头指针
ListNode *p， *q;
p=head;
while（p->next->next）
p=p->next;
q=(ListNode*) malloc (sizeof(ListNode));
q->data=x；
q->next=p->next;
p->next=q；
}
(1)该算法的功能是什么？
(2)若单链表的长度为n，算法的时间复杂度是多少？该时间复杂度和链表的初始状态有关吗？
31．阅读下列算法（假设栈的操作函数都已定义），并回答问题：
void f31 ( )
{ SeqStack S；
char x， y；
x=′c′；
y=′k′；
Push (＆S，x)；
Push (＆S，′a′)；
Push (＆S，y)；
x=Pop(&S)；
Push(＆S，′t′)；
Push(＆S，x)；
x=Pop(＆S);
Push(&S，′s′)；
while ( !StackEmpty(&S))
{ y=Pop (＆S);
putchar (y)；
}
putchar (x)；
}
(1)自底向上写出执行while语句之前栈S中的元素序列。
(2)写出该函数的最后输出结果。
32．下列算法的功能是在中序线索树中查找结点*p的前趋，填上适当内容使算法完整。
typedef enum { Link,Thread } PointerTag;
∥ 枚举值Link和Thread分别为0和1
typedef struct node {
DataType data;
PointerTag ltag, rtag;
Struct node *lchild, *rchild;
}BinThrNode;
BinThrNode*f32 (BinThrNode *p)
{ ∥ 在中序线索树中找结点*p的中序前趋，设p非空
BinThrNode *q；
if(p->ltag==Thread) (1) ;
else
{
q=p->lchild；
while(q->rtag=Link) (2) ；
return q；
}
}
33．分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。
void f33( int a[ ],int n )
{ int i，j，k，t；
for (i=0；i<n；i++) ∥语句1
{ j=i；
for （k=j+1；k<=n；k++）
if (a[k]<a[j]) j=k； ∥语句2
t=a[i]; a[i]=a[j];a[j]=t;
}
}
五、算法设计题（本题10分）
34．二叉排序树的类型定义如下：
typedef struct node {
int data;
struct node *lchild,*rchild;
}*BSTree；
编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。
函数原型为void f34（BSTree T， int m， int n）
自考试题下载：
数据结构试题
课程代码：02331
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题
纸”的相应代码涂黑。错涂、多涂或未涂均无分。
1．数据的逻辑结构可以分为
A．动态结构和静态结构 B.顺序结构和链式结构
C．线性结构和非线性结构 D.简单结构和构造结构
2．线性表是一个有限序列，组成线性表的基本单位是
A．数据项 B.数据元素
C．数据域 D.字符
3．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可
能的出栈序列是
A．dcba B.cbda
C．cadb D.cdba
4．稀疏矩阵的三元组表是
A．顺序存储结构 B.链式存储结构
C．索引存储结构 D.散列表存储结构
5．已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是
A．5 B.6
C．7 D.8
6．下列编码集合中，属于前缀编码的一组是
A.{11,10,001,101,0001} B.{00,010,0110,1000}
C.{11,01,001,0101,0001} D.{0,10,110,1011}
7.如题7图所示二叉树的中序序列为
A．ACDB
B．DCBA
C．CDBA
D．ABCD
题7图
8．有向图中所有顶点入度之和与所有顶点出度之和的比是
A．1/2 B.1
C．2 D.4
9．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是
A.e B.2e
C.n2-2e D.n2-e
10.n个顶点的无向连通图，其生成树的边数为
A.n-l B.n
C.n+l D.nlogn
11．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为
A．2 B.3
C．4 D.5
12．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是
A.(13,44,55,26,8,29) B.(13,26,55,44,8,29)
C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)
13．采用分块查找时，要求数据
A．块内有序 B.分块有序
C．分块无序 D.每块中数据个数必须相同
14.下列关于散列函数的说法正确的是
A．散列函数越复杂越好
B.散列函数越简单越好
C．用除余法构造的散列函数是最好的
D.在冲突尽可能少的情况下，散列函数越简单越好
15.下列关于m阶B树的叙述中，错误的是
A．每个结点至多有m棵子树
B.每个结点至多有m-1个关键字
C．所有的叶结点均在同一层上
D.根结点至少有棵子树
二、填空题（本大题共10小题，每小题2分，共20分）
16．算法的时间复杂度与实现时采用的程序设计语言____________。
17．在长度为n的顺序表的第i(1≤i≤n)个元素之后插入一个元素时，需向后移动___________个元素。
18．设循环队列存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为___________。
19．树的前序遍历序列等同于该树对应二叉树的____遍历序列。
20．一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是___________。
21．当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是____。
22．采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数
为___________。
23．对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的
算法是___________。
24．在16个记录的有序顺序表中进行二分查找，最大比较次数是___________。
25．在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是___________的。
三、解答题（本大题共4小题，每小题5分，共20分）
26．在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么？
27．画出题27图所示树的孩子链表。
题27图
28．已知一个无向图G如题28图所示，以顶点①为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。
题28图
29．判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。
①(1,5,7,20,18,8,10,40)
②(18,9,5,8,4,17,21,6)
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30．单链表类型定义如下：
typedef struct node {
DataType data;
struct node *next;
}ListNode;
typedef ListNode *LinkList;
阅读下列算法，并回答问题：
void f30 (LinklList head, DataType x)
{ ∥head是带头结点的非空单链表的头指针
ListNode *p， *q;
p=head;
while（p->next->next）
p=p->next;
q=(ListNode*) malloc (sizeof(ListNode));
q->data=x；
q->next=p->next;
p->next=q；
}
(1)该算法的功能是什么？
(2)若单链表的长度为n，算法的时间复杂度是多少？该时间复杂度和链表的初始状态有关吗？
31．阅读下列算法（假设栈的操作函数都已定义），并回答问题：
void f31 ( )
{ SeqStack S；
char x， y；
x=′c′；
y=′k′；
Push (＆S，x)；
Push (＆S，′a′)；
Push (＆S，y)；
x=Pop(&S)；
Push(＆S，′t′)；
Push(＆S，x)；
x=Pop(＆S);
Push(&S，′s′)；
while ( !StackEmpty(&S))
{ y=Pop (＆S);
putchar (y)；
}
putchar (x)；
}
(1)自底向上写出执行while语句之前栈S中的元素序列。
(2)写出该函数的最后输出结果。
32．下列算法的功能是在中序线索树中查找结点*p的前趋，填上适当内容使算法完整。
typedef enum { Link,Thread } PointerTag;
∥ 枚举值Link和Thread分别为0和1
typedef struct node {
DataType data;
PointerTag ltag, rtag;
Struct node *lchild, *rchild;
}BinThrNode;
BinThrNode*f32 (BinThrNode *p)
{ ∥ 在中序线索树中找结点*p的中序前趋，设p非空
BinThrNode *q；
if(p->ltag==Thread) (1) ;
else
{
q=p->lchild；
while(q->rtag=Link) (2) ；
return q；
}
}
33．分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。
void f33( int a[ ],int n )
{ int i，j，k，t；
for (i=0；i<n；i++) ∥语句1
{ j=i；
for （k=j+1；k<=n；k++）
if (a[k]<a[j]) j=k； ∥语句2
t=a[i]; a[i]=a[j];a[j]=t;
}
}
五、算法设计题（本题10分）
34．二叉排序树的类型定义如下：
typedef struct node {
int data;
struct node *lchild,*rchild;
}*BSTree；
编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。
函数原型为void f34（BSTree T， int m， int n）
自考试题下载：
 |
全国2013年1月自考试卷数据结构试题02331.doc |