北京大学16秋《数据结构》课程作业资料

admin

一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空 1 分，共 30 分）

1.数据的逻辑结构被形式地定义为 B=(K,R),其中 K 是 ______的有限集合，R 是 K 上

的______的有限集合。（第一章）

a 存储        b 数据操作        c 数据元素        d 操作
e 逻辑结构        f 映象        g 算法        h 关系

2.以下关于算法的说法不正确的是______________。（第一章）

a        一个算法应包含有限个步骤

b        算法越简单越好

c        算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之

d        算法中的每个步骤都能在有限时间内完成

3．设某数据结构的二元组形式表示为 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 是_______B_______。（第一章）

a 线性结构        b 树型结构        c 物理结构        d 图型结构

4.下面程序段的时间复杂度为______（第一章）

int sum=0;

for(i=0; i<m;i++)

for(j=i;j<n;j++)

s++;

a. O(m+n)        b. O(n*n)        c. O(m*n)        d. O(m*logn)

5. 下列有关线性表的叙述中，正确的是________。（第二章）

a 一个线性表是 n 个数据元素的有限序列

b        线性表中任何一个元素有且仅有一个直接前驱

c        线性表中任何一个元素有且仅有一个直接后继

d        以上说法都不正确

6.在含有 n 个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的

平均次数为______（第二章）

a．n        b．(n-1)/2        c．n/2        d．(n+1)/2

第１页 共 10 页

7.链表不具备的特点是____________。（第二章）

a 不必事先估计存储空间        b 插入删除不需要移动元素

c 可顺序访问任一结点        d 所需空间与其长度无关

8.带附加头结点的双循环链表 L 为空表的条件是____________。（第二章）

a        L==NULL        b        L->next==NULL
c        L->prior==L        d        L->prior==NULL

9.设广义表 L=（（（a,b）,c）,d）,则 L 的长度与深度分别为_________。（第三章）

a 1 和 1        b 1 和 3        c 2 和 3        d 1 和 2

10. 若栈采用链式存储结构,则下面的说法中正确的是_______（第四章） a.不需要判断栈满但需要判断栈是否为空 b.需要判断栈是否栈空与栈满

c.需要判断栈满但不需要判断栈空 d.栈满栈空都不需要判断