数据结构习题集

数据结构习题

第一章 绪论

数据结构是一门研究非数值计算的程序设计问题中计算机的___①__ 以及它们之间的__②_ 和运算等的学科。

①A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 ②A.结构 B.关系 C.运算 D.算法

算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。 ① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系

C.分析算法的效率 以求该进 D.分析算法的易懂性和文档性 ② A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性

计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。 ① A.计算方法 B.排序方法

C.解决问题的有限运算序列 D.调度方法

② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性

C.确定性、有穷性和可行性 D.易读性、稳定性 和安全性 数据元素是数据处理的 基本单位；数据项是数据处理的_最小单位。

数据结构是研究数据的 逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、 树形结构和 图形结构 三种类型,其中树形结构和图状结构合称为__非线性结构__。

线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。

数据结构 在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。

顺序存储方法是把逻辑上相邻的元素 存储在物理位置 相邻的内存单元中 ；链式存储方法中元素间的关系是由__指针来表示_的。

第二章 线性表

链表不具备的特点是 ____ 。

A.可随机访问任一结点 B.插入删除不需移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 不带头结点的单链表head 为空的判定条件是____。

A. head==null B. head->next==null C. head->next==head D. head !=null 带头结点的单链表head 为空的判定条件是____。

A. head==null B. head->next==null C. head->next==head D. head!=null

非空的循环单链表head 的尾结点（由p所指向）满足____。

A. p->next==null B. p==null C. p->next==head D. p==head

在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。

2

A. O(1) B. O(n) C. O(n) D. O(nlog2n) 线性链表中各个结点之间的地址 不一定 连续。

线性表中数据元素之间具有__一对一__，除第一个和最后一个元素外，其他数据元素有且只有_一个后继

和前趋。

若频繁地对线性表进行插入和删除操作，该线性表采用 链式 存储结构比较合适。

在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_p->next_和p->next=_s_的操作。

已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=__ LOC(a1)+（i-1）*k_。

若线性表采用顺序存储结构，每个数据元素占用3个存储单元，第11个数据元素的存储地址为130，则第1个数据元素的存储地址是 100 。

若线性表采用顺序存储结构，线性表的最大长度为1000，每个数据元素占3个存储单元，则要分配给该线性表_3000__存储单元，若第一个数据元素的存储地址是2000，则第11个元素的存储地址是__2030__。 以head为头结点循环双链表为空时，应满足head->llink= head ，head->rlink= head 。 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 。

=p->next; >next=p->next->next; >next=p; =p->next->next;

在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行________。

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

C. p->next=s->next;s->next=p >next=s;s->next=q 用链表表示线性表的优点是（）

A．便于随机存储 B.便于进行插入和删除操作

C. 占用的存储空间较顺序表少 D.元素的物理顺序与逻辑顺序相同 下面关于线性表的叙述中，错误的是（）

A. 线性表采用顺序存储必须占用一片连续的存储单元 B. 线性表采用顺序存储便于进行插入和删除操作 C. 线性表采用链式存储不必占用一片连续的存储单元 D. 线性表采用链式存储便于进行插入和删除操作 线性表是具有n个（）的有限序列

A. 数据项 B. 数据元素 C. 表元素 D. 字符

长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为（）

2

A. O（1） （n） C. O（n） （log2n）

在长度为n的顺序表删除第i（1≤i≤n）个元素，则需要向前移动元素的次数为（） A. i B. n-i C. n-i+1

在长度为n的顺序表中第i（1≤i≤n）个位置上插入一个元素时，为留出插入位置所需要移动元素的次数为（）

A. n-i B. i C. n-i-1 D. n-i+1 以下对单链表的叙述错误的是（）

A. 单链表中的每一个结点都由存放结点值的数据域和存放直接后继结点地址信息的指针域两部分组成

B.从单链表的第i 个结点出发，可以访问到链表中的任何一个结点 C.在单链表结构中加入头结点可以简化结点的插入和删除操作 D.单链表尾结点的指针域应置为空指针

以下记叙中正确的是 （）

A. 线性表的链式存储结构优先于顺序存储结构 B. 线性表的存储结构不影响其各种运算的实现

C. 选择线性表的存储结构就是要保证存储其各个元素的值 D.顺序存储属于静态结构，链式存储属于动态结构

第三章 栈与队列

一、选择题

栈的特点是___B_ ，队列的特点是___A_ 。

A.先进先出 B.先进后出 栈和队列的共同点时____。

A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点

一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是____ 。

A. edcba B. decba C. dceab D. abcde

判定一个栈ST（最多元素MaxSize）为空的条件是____ 。

>top!=-1 B. ST->top==-1

>top!= MaxSize D. ST->top==MaxSize-1

判定一个栈ST（最多元素MaxSize）为栈满的条件是____ 。

>top!=-1 B. ST->top==-1

>top!= MaxSize D. ST->top==MaxSize-1

循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和 rear,则 当前队列中的元素个数是____。

A.（rear-front+m）%m B. rear-front+1 C. rear-front-1 D. rear-front

在一个链队中，假设f和r 分别是队头和队尾指针，则插入一个s结点的运算时____。 A. f->next=s; f=s; B. r->next=s; r=s;

C. s->next=r; r=s; D. s->next=f; f=s;

在一个链队中，假设f和r 分别是队头和队尾指针，则删除一个结点的运算时____。 A. r=f->next; B. r=r->next; C. f=f->next; D. f=r->next;

若进栈序列为a，b，c，进栈过程中允许出栈，则以下_____是不可能得到的出栈序列。

A. a,b,c B. b,a,c C. c,a,b D. c,b,a

一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列为满的条件是__________

A. +1)%m= = B. = =

C. +1= = D. +1)%m= =

一个最多能容纳m个元素的顺序存储的循环队列Q，其头尾指针分别为front和rear，则判定该队列为空的条件是__________

A. +1)%m= = B. = = C. +1= = D. +1)%m= = 若进栈序列为 1，2，3，4，，进栈过程中可以出栈，则以下不可能的出栈序列是（）

A. 1，4，3，2 ，3，4，1 C. 3，1，4，2 ，4，2，1

一个队列的入队序列是1，2，3，4，则队列的输出序列是_____。

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

若用一个可容纳6个元素的数组来实现循环队列，且当前rear和front的值分别是0和4，当执行2次出队和1次入队操作后 ，rear和front 的值分别为（）

和0 和2 C.2和5 和5

第四章 串和数组

串是一种特殊的线形表，其特殊性体现在____

A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 串的两种最基本的存储方式是_顺序和链式___。

两个串相等的充分必要条件是: 长度相等_且_对应位置上的字符相等__。 如下陈述中正确的是______。

A．串是一种特殊的线性表? ? B．串的长度必须大于零 ?? C．串中元素只能是字母??? D．空串就是空白串 不含任何字符的串称为__空串_,其长度为_长度等于零__。 设有字符串S=“ABC123XYZ”，问该串的长度为（）

.10 C

已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A[0][0]），则A[i][j]的地址是__loc(a[0][0])+(n*i+j)*k。

二维数组有两种存储方式，第一种是以_行 为主序的存储方式，第二种是以_列_为主序的存储方式。设有二维数组A[10][20]，其中每个元素占2个字节，数组按行优先顺序存储，第一个元素的存储地址为100，那么元素A[8][12]的存储地址为__100+（20*8+12）*2

对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素的值、 行、 列 。这些信息可用一个三元组 数组表示，也称此为 三元组顺序表 。

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，a0,0为第一个元素，其存储地址为1，每个元素占1个字节，则a8,5的地址为__________。

A. 13 B. 33 C. 18 D. 42

第五章 树与二叉树

采用二叉链表存储结构,具有n 个结点的二叉树中,一共有_2n_个指针域,其中有__n-1_个指针域指向孩子结点，有_n+1_个指针域为空.

i-1

一棵非空二叉树,其第i层上最多有_2__结点。

k

满二叉树是一棵深度为k且恰有_2-1___结点的二叉树. 一棵哈夫曼树有个m叶子结点,则其结点总数为_2m-1__. 三个结点的二叉树，最多有_5__种形状。

将一棵完全二叉树按层次编号,对任一编号为i的结点有:如有左孩子,则其编号为__2i_; 如有右孩子,则其编号为_2i+1.

ki-1

深度为k的非空二叉树最多有 2-1个结点，最少有 k 个结点，其第i层最多有_2 个结点。 树最适合用来表示____。

A. 有序数据元素 B.无序数据元素

C. 数据之间具有分支层次关系的数据 D. 元素之间无联系的数据 在下列存储形式中，不是树的存储形式的是____。

A．双亲表示法 B.孩子表示法 C.孩子双亲表示法 D.孩子兄弟表示法