数 据 结 构 习 题 集

数 据 结 构 习 题 集

一、选择题

１.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动 B 个元素。

A. n-1 B. n-i+1 C. n-i-1 D. i ２.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为 C 。

A. top不变 Ｂ. top＝ -n C. top＝top-1 D. top=top+1 ３.向顺序栈中压入元素时，是 A 。

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

４.在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。

A. 前一个位置 B. 后一个位置 C. 队首元素位置 D. 队尾元素位置 ５.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4

６.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 C 。

A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0

７.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是 D 。

A. rear % n= =front B. (rear-1) % n= =front

C. (rear-1) % n= =rear D. (rear+1) % n= =front

８.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较 D 个结点。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2 ９.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 C 。

A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q;

10.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 C 。 A. hs->next=s; B. s->next=hs->next; hs->next=s; C. s->next=hs；hs=s; D. s->next=hs; hs=hs->next;

11.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行 B 。

A. front->next=s; front=s; B. rear->next=s; rear=s; C. front=front->next; D. front=rear->next;

12.线性表是 A 。

A. 一个有限序列，可以为空 B. 一个有限序列，不能为空

1

C. 一个无限序列，可以为空 D. 一个无限序列，不能为空

13.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的 C 个元素。

A. n+1 B. n-1 C. (n-1)/2 D. n 14.线性表采用链式存储时，其地址 D 。

A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以

15.设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 B 后修改p->link=f即可。 A. f->link=p; B. f->link=p->link;

C. p->link=f->link; D. f=nil;

16.在双向链表存储结构中，删除p所指的结点时需修改指针 B 。 A. ((p->rlink) ->rlink) ->link=p; p->rlink=(p->rlink) ->rlink; B. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;

C. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p; D. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;

17.在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针 A 。

A. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink; B. ((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink; C. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;

D. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p; 18.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和 B 。 A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表 19.在数据结构中，与所使用的计算机无关的数据叫 C 结构。 A. 存储 B. 物理 C. 逻辑 D. 物理和存储 20.二分法查找 A 存储结构。

A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式

21.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上 B 。 A. 一定相邻 B. 不一定相邻 C. 有时相邻 22.设字符串s1='abcdefg',s2='pqrst'，则运算

s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为 D 。 A. 'bcdef' B. 'bcdefg' C. 'bcpqrst' D. 'bcdefef'

23.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为 B 。 A. 15 B. 16 C. 17 D. 47 24.假定一棵二叉树的结点数为18个，则它的最小高度 B 。 A. 4 B. 5 C. 6 D. 18 25.在一棵二叉树中第五层上的结点数最多为 C 。

A. 8 B. 15 C. 16 D. 32 26.在一棵具有五层的满二叉树中，结点总数为 A 。

A. 31 B. 32 C. 33 D. 16

27.已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为 B 。

2

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

28.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 C 。 A. 23 B. 37 C. 44 D. 46 29.在树中除根结点外，其余结点分成m (m≥0)个 A 的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。 A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交 30.下面答案 D 是查找二叉树（又称二叉排序树）。

A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于１ B. 二叉树中的每个结点的两棵子树的高度差等于１ C. 二叉树中的每个结点的两棵子树是有序的

D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值， 且小于其右子树（如果存在）所有结点的关键字值。

31.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是 B 。

A. 3 B. 4 C. 5 D. 1

32.一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从１开始对全部结点编号，编号为n的有右兄弟的条件是 B 。

A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=0

33.在完全二叉树中，当i为奇数且不等于１时，结点i的左兄弟是结点 D ，否则没有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1 34.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,…,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 B 编号。 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 35.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4

36.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小 为 A 。 A. n B. n+1 C. n-1 D. n+e 37.具有n个顶点的无向完全图，边的总数为 D 条。

A. n-1 B. n C. n+1 D. n*(n-1)/2

38.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e>=n,故可推得深度优先搜索的时间复杂度为 A 。

A. O(e) B. O(n) C. O(ne) D. O(n+e) 39.最小代价生成树 D 。

A.是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原因的边的权数有关 40.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于 C 。 A. i+j B. i-j C. 1 D. 0

41.图的深度优先或广度优先遍历的空间复杂性均为 A 。(访问标志位数组空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e)

42.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为90的元素时， B 次比较后查找成功；当二分查找值为47的元素时， D 次比较后查找成功。 A. 1 B. 2 C. 3 D. 4

43.散列函数有一个共同性质，即函数值应当以 D 取其值域的每个值。

3

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 44.设散列地址空间为0～m－1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H(k)＝k % p。为了减少发生冲突的频率，一般取p为 D 。 A. 小于m的最大奇数 B. 小于m的最大偶数 C. m D. 小于m的最大素数

45.目前以比较为基础的内部排序时间复杂度T(n)的范围是 A ③ ；其比较次数与待 排序的记录的初始排列状态无关的是 B ② 。

A. ①O(log2 n)～O(n) ②O(lon2 n)～O(n2 )

③O(nlog2 n)～O(n2 ) ④O(n)～O(n2 ) ⑤O(n)～O(nlog2 n) B. ①插入排序 ②先用二分法查找，找到后插入排序

③快速排序 ④冒泡排序

46.设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是 A 。 A. 6 B. 7 C. 8 D. 20 47.在归并排序过程中，需归并的趟数为 C 。

A. n B. √n C. log2 n向上取整 D. log2 n向下取整

48.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为 B 。

A. (79、46、56、38、40、80) B. (84、79、56、38、40、46)

C. (84、79、56、46、40、38) D. (84、56、79、40、46、38)

49.一组记录的关键码为(46、79、56、38、40、84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。

A. (38、40、46、56、79、84) B. (40、38、46、79、56、84)

C. (40、38、46、56、79、84) D. (40、38、46、84、56、79)

50.在平均情况下快速排序的时间复杂性为 C ，空间复杂性为 B ；在最坏情况下（如初始记录已有序），快速排序的时间复杂性为 D ，空间复杂性为 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) 选择题参考答案：

１.B ２.C ３.A ４.A ５.C ６.C ７.D ８.D ９.C 10.C 11.B 12.A 13.C 14.D 15.B 16.B 17.A 18.B 19.C 20.A

21.B 31.B 41.A 46.A

22.D 23.B 24.B 25.C 26.A 27.B 28.C 29.A 30.D 32.B 33.D 34.B 35.B 36.A 37.D 38.A 39.D 40.C 42.B,D 43.D 44.D 45.A:③ B:②

采用选择排序对给定的关键字序列进行排序，只需６次。

47.C 48.B 49.C 50.C B D A 二、填空题

1.在线性结构中第一结点 [1] 无 前驱结点，其余每个结点有且只有 [2] 一 个前驱结点；最后一个结点 [3] 无 后继结点，其余每个结点有且只有 [4] 一 个后继结点。 2.在树型结构中，树根结点没有 [1] 前趋 结点，其余每个结点有且仅有 [2] 一 个前驱结点；树叶结点没有 [3] 后继 结点，其余每个结点的 [4] 后继 结点数不受限制。

3.一个数据结构用二元组表示时，它包括 [1] 数据元素 的集合K和K上 [2]二元

4