2004年10月自考数据结构试题真题

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

全国2004年10月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题干的括号内。错选、多选或未选均无分。

1．下列各式中，按增长率由小至大的顺序正确排列的是( ) A．n，n！，2，n C．2n，log n，nlogn，n3/2

n

3/2

B．n，2，n

3/2nlogn

，2

100

D．2100，logn, 2n, nn

2．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( ) A．s->next=p->next; p->next=s; C．p->next=s->next; s->next=p;

B．p->next=s; s->next=p->next; D．s->next=p; p->next=s->next;

3．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向( ) A．各自的头结点 B．各自的尾结点

C．各自的第一个元素结点

D．一个表的头结点，另一个表的尾结点 4．栈的两种常用存储结构分别为( ) A．顺序存储结构和链式存储结构 C．链式存储结构和索引存储结构

B．顺序存储结构和散列存储结构 D．链式存储结构和散列存储结构

5．已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( ) A．5 C．16

B．6 D．17

6．已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为

typedef struct node {

char data[8]; struct node *next;

} LinkStrNode;

浙02331# 数据结构试卷 第 1 页 共 7 页

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

A．1/4 C．2/3

B．1/2 D．3/4

7．应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为( ) A．7 C．10

B．9 D．12

8．二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为( ) A．574 C．578

B．576 D．580

9．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是( ) A．（c,d） C．b

B．(d) D．(b)

10.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为( ) A．ABCDEF C．ABFCDE

B．ABCEFD D．ABCDFE

11．一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为( ) A．O(n) C．O(n+e)

B．O(e) D．O(n2)

12．在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( ) A．4，4，3 C．3，4，4

B．4，3，3 D．3，3，4

13．下列排序方法中，最好与最坏时间复杂度不相同的排序方法是( ) A．冒泡排序 C．堆排序

B．直接选择排序 D．归并排序

14．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( ) A．1.0 C．3.4

B．2.9 D．5.5

浙02331# 数据结构试卷 第 2 页 共 7 页

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

15．在下列各种文件中，不能进行顺序查找的文件是( ) A．顺序文件 C．散列文件

B．索引文件 D．多重表文件

二、填空题(本大题共10小题，每小题2分，共20分)

16．抽象数据类型是指数据逻辑结构及与之相关的___________。

17．已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的___________结点。

q=p;

while(q->next!=p)q=q->next;

的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。

18．假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”

19．在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的___________运算。

20．假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为___________。

21．在含100个结点的完全二叉树中，叶子结点的个数为___________。

22．在无向图中，若从顶点a到顶点b存在___________，则称a与b之间是连通的。 23．如果排序过程不改变___________之间的相对次序，则称该排序方法是稳定的。 24．索引顺序查找适宜对___________的顺序表进行查找。

25．文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及___________。

三、解答题(本大题共4小题，每小题5分，共20分) 26．画出下图所示二叉树的中序线索链表的存储表示。

27．已知图G=（V，E），其中：

V={a,b,c,d,e},

E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。

浙02331# 数据结构试卷 第 3 页 共 7 页

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

（1）画出图G；

（2）画出图G的邻接表。 （1） （2）

28．已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。

void MergeSorDC(SeqList R, int low, int high) {// 用分治法对R[low..high]进行二路归并排序} int mid; if (low

//区间长度大于1 //分解

//递归地对R[low..mid]排序 //递归地对R[mid+1..high]排序

//组合，将两个有序区归并为一个有序区

mid=(low+high)/2;

MergeSortDC(R, low, mid); MergeSortDC(R,mid+1,high); Merge(R, low, mid, high); }

} //MergeSortDC

29．由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。 四、算法阅读题(本大题共4小题，每小题5分，共20分)

30．L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的

所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) {

LinkList Lc,p,pre; pre=L;

p= (1) ;

Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L)

if(p->data>c)

浙02331# 数据结构试卷 第 4 页 共 7 页

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

{

pre->next=p->next; (2) ; Lc->next=p; p=pre->next; } else { pre=p; (3) ; } return Lc; } (1) (2) (3)

31．设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。 （1）写出调用f31(&S)后的S；

（2）简述函数f31中第1个循环语句的功能。 void f31 (Stack *S) {

Queue Q; Stack T; int i=0; InitQueue(&Q); InitStack(&T); while(!StackEmpty(S))

if ((i=!t)!=0) Push(&T,Pop(S)); else EnQueue(&Q, Pop(S)); while(!StackEmpty(&T))

Push(S,PoP(&T)); while(!QieueEmpty(&Q))

浙02331# 数据结构试卷 第 5 页 共 7 页

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

Push(S,DeQueue(&Q)); } (1) (2)

32．图的邻接矩阵表示描述如下： #define MaxNum 20 typedef struct { char vexs[MaxNum];

//字符类型的顶点表 //邻接矩阵

//图的顶点数和边数

int edges[MaxNum][MaxNum]; int n, e; } MGraph;

//图的最大顶点数

//图的邻接矩阵结构描述

阅读下列算法，并回答问题：

（1）对于下列图G的邻接矩阵，写出函数调用f32(&G,3)的返回值；

?0?0??0??1?0?1001011001101011??0?0? ?0?0??

（2）简述函数f32的功能； （3）写出函数f32的时间复杂度。 int f32(MGraph *G, int i) {

int d=0,j;

for(j=0;jn;j++) {

if (G->edges[i][j]) d++; if (G->edges[j][i]) d++; } return d; } (1) (2)

浙02331# 数据结构试卷 第 6 页 共 7 页

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

(3)

33．阅读下列算法并回答问题：

（1）设数组L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f33(L,8)

之后的L[1..8]中的元素值； （2）简述函数f33的功能。 void f33(int R[], int n) {

int x=R[1]; int low=1, high=n; while(low

while(low=0) high --; if (low>high) {

R[low++]=R[high];

while (low

五、算法设计题(本大题10分)

34．假设以二叉链表作为二叉树的存储结构，其结点结构为： lchild data rchild 依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中，参数level为函数执行过程中T当前所指结点的层次，其初值为1；*lmin与*lmax分别为叶子结点的最小层次与最大层次，它们的初值均为０。 void f34(BinTree T, int level, int * lmin, int * lmax);

浙02331# 数据结构试卷 第 7 页 共 7 页

本文来源：https://www.bwwdw.com/article/pulx.html