2004年下半年高等教育自学考试全国统一命题考试

数据结构试题

课程代码：2331

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

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

 1．下列各式中，按增长率由小至大的顺序正确排列的是(       )

 A．，n！，2ⁿ ，n^3/2      B．n^3/2，2ⁿ，n^logn，2¹⁰⁰

 C．2ⁿ，log n，n^logn，n^3/2  D．2¹⁰⁰，logn, 2ⁿ, nⁿ

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

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

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

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

A．各自的头结点

B．各自的尾结点

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

D．一个表的头结点，另一个表的尾结点

4．栈的两种常用存储结构分别为(       )

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

C．链式存储结构和索引存储结构　　D．链式存储结构和散列存储结构

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

A．5     B．6

C．16   D．17

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

typedef struct node {

char data[8];

struct node *next;

} LinkStrNode;

A．1/4    B．1/2

C．2/3    D．3/4

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

A．7      B．9

C．10    D．12

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

A．574B．576

C．578D．580

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

A．（c,d）B．(d)

C．b           D．(b)

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

A．ABCDEF   B．ABCEFD

C．ABFCDE   D．ABCDFE

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

A．O(n)      B．O(e)

C．O(n+e)  D．O(n²)

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

A．4，4，3      B．4，3，3

C．3，4，4     D．3，3，4

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

A．冒泡排序　B．直接选择排序

C．堆排序　　D．归并排序

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

A．1.0 B．2.9

C．3.4    D．5.5

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

A．顺序文件B．索引文件

C．散列文件D．多重表文件

自考相关信息与资料关注:重庆自考网