欢迎访问深圳自考网!网站为考生提供深圳自考信息服务,供学习交流使用,非政府官方网站,官方信息以广东省教育考试院为准。

报名热线:177-2280-6683

招生老师微信|深圳自考微信公众号

首页
自考服务: |报名报考 |报考须知 |考办联系方式 |考试时间安排表 |免考办理 |学历证明办理 |合并准考证办理 |转出、转入办理 |考籍信息更正办理
通知公告:

全国2007年10月高等教育自学考试数据结构试题

编辑整理:深圳自考网    发布时间:2018-05-24 06:23:24    浏览热度:   [添加招生老师微信]
立即购买

《自考视频课程》名师讲解,轻松易懂,助您轻松上岸!低至199元/科!

全国200710月高等教育自学考试
数据结构试题
课程代码:02331

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.下面程序段的时间复杂度为( )
s=0;
for(i=1;ifor(j=1;js+=i*j;
A.O(1)
B.O(logn)
C.O(n)
D.O(n2)

2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点.假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为( )
A.q->next=s->next;s->next=p;
B.s->next=p;q->next=s->next;
C.p->next=s->next;s->next=q;
D.s->next=q;p->next=s->next;

3.在计算机内实现递归算法时所需的辅助数据结构是( )
A.栈
B.队列
C.树
D.图

4.假设以数组A[m]存放循环队列的元素.已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位置为( )
A.(rear-length+m+1)%m
B.(rear-length+m)%m
C.(rear-length+m-1)%m
D.(rear-length)%m

5.通常将链串的结点大小设置为大于1是为了( )
A.提高串匹配效率
B.提高存储密度
C.便于插入操作
D.便于删除操作

6.带行表的三元组表是稀疏矩阵的一种( )
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构

7.表头和表尾均为空表的广义表是( )
A.()
B.(())
C.((()))
D.((),())

8.用二叉链表表示具有n个结点的二叉树时,值为空的指针域的个数为( )
A.n-1
B.n
C.n+l
D.2n

9.为便于判别有向图中是否存在回路,可借助于( )
A.广度优先搜索算法
B.最小生成树算法
C.最短路径算法
D.拓扑排序算法

10.连通网的最小生成树是其所有生成树中( )
A.顶点集最小的生成树
B.边集最小的生成树
C.顶点权值之和最小的生成树
D.边的权值之和最小的生成树

11.按排序过程中依据的原则分类,快速排序属于( )
A.插入类的排序方法
B.选择类的排序方法
C.交换类的排序方法
D.归并类的排序方法

12.下列关键字序列中,构成小根堆的是( )
A.{84,46,62,41,28,58,15,37}
B.{84,62,58,46,41,37,28,15}
C.{15,28,46,37,84,41,58,62}
D.{15,28,46,37,84,58,62,41}

13.在长度为32的有序表中进行二分查找时,所需进行的关键字比较次数最多为( )
A.4
B.5
C.6
D.7

14.假设在构建散列表时,采用线性探测解决冲突.若连续插入的n个关键字都是同义
词,则查找其中最后插入的关键字时,所需进行的比较次数为( )
A.n-1
B.n
C.n+l
D.n+2

15.散列文件也称为( )
A.顺序文件
B.索引文件
C.直接存取文件
D.间接存取文件


二、填空题(本大题共10小题,每小题2分,共20)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.数据的逻辑结构描述数据元素之间的_________________,与存储方式无关.
17.在一个长度为100的顺序表中删除第10个元素时,需移动___________________个元素.
18.队列的队尾位置通常是随着______________操作而变化的.
19.两个空串联接得到的串的长度为___________________.
20.设对称矩阵A压缩存储在一维数组B中,其中矩阵的第一个元素a11存储在B[0],元素a52存储在B[11],则矩阵元素a36存储在B[______________]中.
21.已知一棵哈夫曼树含有60个叶子结点,则该树中共有________________个非叶子结点.
22.如图所示的有向图中含有_______________个强连通分量.
全国2007年10月高等教育自学考试数据结构试题(图1)
23.已知一组关键字为{15,36,28,97,24,78,47,52,13,86},其中每相邻两个关键字构成一个有序子序列.对这些子序列进行一趟两两归并的结果是______________.
24.从空树起,依次插入关键字1l,27,35,48,52,66和73构造所得的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度为____________________.
25.控制区间和控制区域是________________文件的逻辑存储单位.

三、解答题(本大题共4小题,每小题5分,共20)
26.利用广义表的head和tail操作,可从广义表L=((a,b),(c,d))中分解得到原子c,其操作表达式为head(head(tail(L)));
分别写出从下列广义表中分解得到b的操作表达式.
(1)L1=(a.,b,c,d);
(2)L2=(((a),(b),(c),(d))).
(1)__________________________________________
(2)__________________________________________
27.画出与如图所示森林对应的二叉树. 
全国2007年10月高等教育自学考试数据结构试题(图2) 
28.已知有向图G的定义如下:
G=(V,E)
V={a,b,c,d,e}
E={, ,,,,,}
(1)画出G的图形;
(2)写出G的全部拓扑序列.
(1)__________________________________________
(2)__________________________________________
29.已知3阶B-树如图所示.
(1)画出将关键字88插入之后的B-树;
(2)画出将关键字47和66依次插入之后的B-树.
全国2007年10月高等教育自学考试数据结构试题(图3)
(1)__________________________________________
(2)__________________________________________


四、算法阅读题(本大题共4小题,每小题5分,共20)
30.假设某个不设头指针的无头结点单向循环链表的长度大于1,s为指向链表中某个结点的指针.算法f 30的功能是,删除并返回链表中指针s所指结点的前驱.请在空缺处填入合适的内容,使其成为完整的算法.
typedef struct node {
DataType data;
struct node *next;
}*LinkList;
DataType f 30(LinkList s) {
LinkList pre,p;
DataType e;
pre=s; ’
p=s->next;
while( (1) ){
pre=p;
____________(2) ;
}
pre ->next= (3) ;
e=p->data;
free(p);
return e;
}
(1)__________________________________________
(2)__________________________________________
(3)__________________________________________
31.算法f31的功能是清空带头结点的链队列Q.请在空缺处填入合适的内容,使其成为一个完整的算法.
typedef struct node{
DataType data;
struct node *next;
}QueueNode;
typedef struct {
QueueNode *front;//队头指针
QueueNode *rear;//队尾指针
}LinkQueue;
void f 31(LinkQueue*Q) {
QueueNode*p,*s;
p= (1)
while(p!=NULL) {
s=p;
p=p->next;
free (s);
________(2) =NULL;
Q->rear=_______(3)_______;
}
(1)__________________________________________
(2)__________________________________________
(3)__________________________________________
32.假设采用动态存储分配的顺序串HString作为串的存储结构.该类型实现的串操作函数原型说明如下:
void strinit(HString s);//置s为空串
int strlen(HString s);//求串s的长度
void strcpy(HString to,HString from);//将串from复制到串to
void strcat(HString to,HString from);//将串from联接到串to的末尾
int strcmp(HString sl,HString s2);
//比较串sl和s2的大小,当s1s2时,
//返回值小于0,等于0或大于0
HString substr(HString s,int i,int m);
//返回串s中从第i(0≤I≤strlen(s)-m)个字符起长度为m的子串
阅读下列算法f 32,并回答问题:
(1)设串S=″abcdabcd″,T=″bcd″,V=″bcda″,写出执行f 32(S,T,V)之后的S;
(2)简述算法f 32的功能.
void f 32 (HString S, HString T, HString V) {
int m, n, pos, i;
HString news;
strinit (news) ;
n=strlen(S);
m=strlen(T);
pos=i=0;
while (i<=n-m) {
if( stremp(substr(S,i,m),T)! =0)i++;
else{
strcat(news,substr(S, pos, i-pos)) ;
strcat(news, V) ;
pos=i=i+m;
}
}
strcat(news,substr(S,pos,n-pos)) ;
strcpy(S,news)
}
(1)
(2)
33.假设以二叉链表作为二叉树的存储结构,其类型定义如下:
typedef struct node {
char data;
struct node *lchild, *rchild; //左右孩子指针
} BinTNode,*BinTree;
阅读下列算法f 33,并回答问题:
(1)已知如图所示的二叉树以T为指向根结点的指针,画出执行f 33(T)后的二叉树;
(2)简述算法f 33的功能.
void f33(BinTree T) {
if (T) {
f 33 (T - > lchild) ;
f 33(T - > rchild) ;
if ( ( !T - > lchild) && T->rchild) {
T - > lchild=T->rchild;
T - > rchild=NULL;
}
}
}
全国2007年10月高等教育自学考试数据结构试题(图4)
(1)__________________________________________
(2)__________________________________________

五、算法设计题(本大题10)
34.假设以带头结点的单链表表示有序表,单链表的类型定义如下:
typedef struct node {
int data;
struct node*next;
} LinkNode,*LinkList;
编写算法,输入n个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一个).算法的函数原型给定为
LinkList f 34(int n);


《深圳自考网》免责声明:

1、由于考试政策等各方面情况的调整与变化,本网提供的考试信息仅供参考,最终考试信息请以省考试院及院校官方发布的信息为准。

2、本站内容部分信息均来源网络收集整理或来源出处标注为其它媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com