2024年4月30日发(作者：)

一、单选题（每题1 分，共15分）

1、设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，

09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，

08>，<03，09>}，则数据结构A是（ ）。

A． 线性结构 B. 树型结构 C. 物理结构 D. 图型结构

2、栈的插入和删除操作在( )进行。

A.栈顶 B栈底 C.任意位置 D．指定位置

3、下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++）

{ t=1；

for(j=1；j<=i；j++)

t=t*j；

s=s+t；}

234

A. O(n) B).O(n) C.O(n) D. O(n)

4、栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素 B.都是先进后出

C.都是先进先出 D.没有共同点

5、设链式栈中结点的结构为(data，link)，且top是指向栈顶的指针。若想在链式栈的栈

顶插入一个由指针s所指的结点，则应执行( )操作。

A．top->link=s B．s->link

C．Slink=top；top=s D．S-->link=top; top=top->link

6、二叉树的第k层的结点数最多为( ).

k-1 K+1Kk

A．2 B.2 C.2-1 D. 2+1

7、设有两个串t和p，求p在t中首次出现的位置的运算叫做( )。

A.求子串 B．模式匹配 C.串替换 D.串连接

8、数据的最小单位是（ ）。

A.数据项 B.数据类型 C .数据元素 D.数据变量

9、设单链表中结点的结构为(data，link)，已知指针p所指结点不是尾结点，若在*p之后

插入结点s，则应执行的操作是( )。

A．S->link=p；p->link=s B．p->link=s；S->link=p

C.S->link=p->link；p=s D．s->link=p->link；p->link=s

10、函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。

A.“STRUCTURE” B.“DATA” C. “ASTRUCTUR” D.“DATASTRUCTURE”

11、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A．5 B．6 C．7 D.8

12、以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

13、设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。

2

A.O(1) B. O(log

2

n) C.O(n ) D.O(n)

14．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别

为（ ）。

A. n，e B. e，n C. 2n，e D. n，2e

15、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二

分查找，则查找A［3］的比较序列的下标依次为( )

A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3

16、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）

=K %9作为散列函数，则散列地址为1的元素有（ ）个，

A．1 B．2 C．3 D．4

17、一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储

空间的大小，即记录长度为( ) 。

A．所有域长度之和 B．最大域所占字节长度

C．任意一个域长度 D．sizeof(r)的值

18、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关

键字，则用下列（ ）方法可以达到此目的。

(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序

19、下列四种排序中（ ）的空间复杂度最大。

(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

20、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准

记录的一趟快速排序结束后的结果为( )。

(A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21

(C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21

21、带头结点的单链表first为空的判定条件是( )。

A．first==NULL B．first->link==NULL

C．first->link==first D．first!=NULL

14、在一个长度为n的顺序表中删除第i个元素(0<=i<=n-1)时，需要从前向后依次

前移( )个元素。

A．n-i B．n-i+l C．n-i-1 D．i

22、设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一

趟希尔排序结束后前4条记录关键字为（ ）。

A.40，50，20，95 B. 15，40，60，20

C.15，20，40，45 D.45，40，15，20

23、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序

列为（ ）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)；

B.q=p->next；q->data=p->data；p->next=q->next；free(q)；

C. q=p->next；p->next=q->next；free(q)；

D.q=p->next；p->data=q->data；free(q)；

24、用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

25、设输入序列是1、2、3、„„、n，经过栈的作用后输出序列的第一个元素是n，则输出

序列中第i个输出元素是（ ）。

A. n-i B. n-1-i C. n+1-i D. 不能确定

二、填空题（ ）