新疆开放大学《数据结构（本）》课程复习题--课程ID-02272试卷号-11252.docx

新疆开放大学《数据结构（本）》课程复习题

课程ID：02272试卷号：11252

一、填空题

1.下列说法中，不正确的是(D)。

A.数据元素是数据的基本单位

B.数据项是数据中不可分割的最小可标识单位

C.数据可有若干个数据元素构成

D.数据项可由若干个数据元素构成‘

2.每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是(B)存储方式。

A.顺序 B.链接

C.索引 D.散列

3.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行(D)。

A.p-next=s;s-next=p-next

B.p-next=s-next

C.p=s-next

D.s-next=p-next,p-next=s

4.向顺序栈中压入新元素时，应当(A)。

A.先移动栈顶指针，再存入元素 B.先存入元素，再移动栈顶指针

C.先后次序无关紧要 D.同时进行

5.一般情况下，将递归算法转换成等价的非递归算法应该设置(A)。

A.栈 B.队列

C.堆栈或队列 D.数组

6.判断一个循环队列Q(最多元素为m)为满的条件是(C)。

A.Q-front==Q-rear

B.Q-front!=Q-rear

C.Q-front==(Q-rear+l)%m

D.Q-front!=(Q-rear+l)%m

7.空串与空格串(B)。

A.相同 B.不相同

C.可能相同 D.无法确定

8.广义表(f，h，(a，b，d，c)，d，e，((i，j)，k))的长度是(A)。

A.6 B.10

C.8 D.4

9.二叉树第k层上最多有(B)个结点。

A.2k B.2k-l

C.2k-l D.2k-l

10.对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为(B)。

A.n B.n2

C.n-l D.(n-l)2

11.采用折半查找方法查找长度为n的线性表时，其算法的时间复杂度为(D)。

A.O(n2) B.O(nlog2n)

C.O(n) D.0(1og2n)

12.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放人已排序序列的正确的位置上，此方法称为(A)。

A.插入排序 B.交换排序

C.选择排序 D.归并排序

13.设主串为“DBcCDABcdEFdBc”，以下模式串能与主串成功匹配的是（A）。

A.dBc B.BCd

C.DBC D.Abc

14.顺序表所具备的特点之一是（A）。

A.可以随机访问任一结点 B.不用占用连续的存储空间

C.插入删除操作不需要移动元素 D.必须要有头指针

15.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个已生成的结点，现要为该结点的数据域赋值e，并使结点入队的运算为p-data=e;p-next一NULL;和（B）。

A.f-next=p;f=p B.r-next=p;r=p

C.p-next=r;r=p D.p-next=f;f=p

16.在一个头指针为head的带头结点的单向循环链表中，p指向尾结点，要使该链表成为不带头结点的单向链表，可执行（D）。

A.head=head-next;p=NULL

B.head—head-next;P-next=head

C.head-next=p-next

D.head-head-next;p-next=NULL

17.元素212，214，216，218按顺序依次进栈，则该栈的不可能输出序列是（D）（进栈出栈可以交替进行）。

A.212,214,216,218 B.216,214,212,218

C.214,212,218,216 D.218,216,212,214

18.设有一个25阶的对称矩阵A(第一个元素为ai，，，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a4，s在一维数组B中的下标是（B）。

A.10 B.9

C.7 D.8

19.在一棵二叉树中，编号为19的结点的双亲结点的顺序编号为（A）。

A.9 B.8

C.34 D.35

20.线性表以（D）方式存储，能进行折半查找。

A.关键字有序的 B.顺序

C.链接 D.关键字有序的顺序

21.如图1所示的一个图，若从顶点a出发，按深度优先有哪些信誉好的足球投注网站法进行遍历，则可能得到的一种顶点序列为（D）。

A.abecdfg B.aecbdfg

C.aebcfdg D.aedfcbg

22.设