数据结构习题

数 据 结 构 习 题

一、基本概念

1. 为了描述n个人之间的同学关系，可用 结构表示。 C A.线性表 B.树 C.图 D.队列 2.数据结构主要研究数据的______。 D

A.逻辑结构 B.存储结构

C.逻辑结构和存储结构 D.逻辑结构和存储结构及起运算的实现 二、线性表

1.链表不具备的特点是 。 A

A．可随机访问任何一个元素 B．插入、删除操作不需要移动元素 C．无需事先估计存储空间大小 D．所需存储空间与线性表长度成正比 2. 若线性表采用链式存储结构，则适用的查找方法为____。 D

A. 随机查找 B. 散列查找 C. 二分查找 D. 顺序查找

3.已知 N 个数已存入数组 A[1..M]的前 N 个元素中（N

4．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（ ）。 D

A． p->next=p

B． p=p->next

D． p->next=p->next->next

C．p=p->next->next

5．线性表采用链式存储结构时，要求存储单元的地址（ ）。 D

A． 必须是连续的

B．部分地址必须是连续的

C． 一定是不连续的 D．连续不连续都可以

6．设head为单链表的头指针，则不带头结点的单链表为空的判定条件是（ ）。 A A． head==NULL

B． head->next==NULL

C． head->next==head D． head!=NULL

7．设指针p指向单链表中结点A，指针q指向单链表中结点A的前驱结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作为（ ）。 B A． s->next=p->next； p->next=s； B． q->next=s； s->next=p； C． p->next=s->next； s->next=p； D． p->next=s； s->next=q； 三、栈和队列

1. PUSH和POP命令常用于______操作。 C

A.队列 B.数组 C.栈 D.记录

2.若push 、pop 分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过 操作序列push、push、pop、pop 、push、pop 之后，得到的出栈序列为____ 。 B A．321 B．213 C．231 D．123

3.可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符\就将其入栈，遇到\就执行出栈操作。对算术表达式

\检查时，__11__ ；对算术表达式\检查时，_ 12__ 。这两种情况都表明所检查的算术表达式括号不匹配。 A C (11)A. 栈为空却要进行出栈操作 B.栈已满却要进行入栈操作

C.表达式处理已结束，栈中仍留下有字符\ D.表达式处理已结束，栈中仍留下有字符\ (12)A. 栈为空却要进行出栈操作 B．栈已满却要进行入栈操作

C．表达式处理已结束，栈中仍留下有字符\ D．表达式处理已结束，栈中仍留下有字符\

4. 判断一个表达式中左右括号是否匹配，采用_ _实现较为方便。 D A.线性表的顺序存储 B.队列 C.线性表的链式存储 D.栈

5.某循环队列的容量为 M，队头指针指向队头元素，队尾指针指向队尾元素之后，则队列中的元素数目为 （MOD 表示整除取余运算）。 ((Q.Rear-Q.Front+M) MOD M 6.判断“链式队列为空”的条件是____（front为头指针，rear为尾指针）。 C A．front==NULL B．rear==NULL C．front==rear D．front!=rear

7.若一个栈以向量V[1..n]存储，且空栈的栈顶指针top为n+1，则将元素x入栈的正确操作是 （ ） 。 C

A. top = top+1; V[top] = x;

C. top = top-1; V[top] = x;

B. V[top] = x; top = top+1; D. V[top] = x; top = top-1;

8.设初始栈为空，s表示入栈操作，x 表示出栈操作，则 是合法的操作序列。 C A. sxxsssxxx B. xxssxxss C. sxsxssxx D. xssssxxx

四、串和数组

1.字符串\中长度为3的子串有__ _ 个。 C

A．4 B．5 C．6 D．7 2. 以下关于字符串的判定语句中正确的是__(7)__。 A

A．字符串是一种特殊的线性表 B．串的长度必须大于零

C．字符串不属于线性表的一种 D．空格字符组成的串就是空串

3.对矩阵压缩存储的主要目的是____。 B

A．方便运算 B．节省存储空间 C．降低计算复杂度 D．提高运算速度

4.数组是一种数据结构，对数组通常进行的两种基本操作是___(40)___。 C

（40）A. 插入和删除 B. 插入和赋值 C. 查找和修改 D. 查找和删除

6. 数组A[-5..5, 0..8]按列存储。若第一个元素的首地址为100，且每个元素占用4个存储单元，则元素A[2,3]的存储地址为 。 B 100+(3*11+7)*4=260

A. 244 B. 260 C. 364 D. 300

7. 采用一维数组S存储一个n阶对称矩阵A的下三角部分（按行存放，包括主对角线），设元素A[i][j]存放在S[k] 中（i、j、k均从1开始取值），且S[1]=A[1][1]，则k与i、j的对应关系是 。例如，元素A[3][2]存在S[5]中。 D

A.

k?i(i?1)?j?12

B.

k?i(i?1)?j2

C.

k?i(i?1)i(i?1)?j?1k??j22 D.

8.若二维数组P[1..5, 0..8]的首地址为base，数组元素按行存储，且每个元素占用1个存储单

元，则元素P[3, 3]在该数组空间的地址为 。 A

A. base+13 B. base+16 C. base+18 D. base+21

五、树

1. 在具有100个结点的树中，其边的数目为____。 C

A．101 B．100 C．99 D．98

2.满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为 h(h>1)的满二叉树，其结点总数为 。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、2、3、?依次编号，则对于树中编号为 i 的非叶子结点，其右子树的编号为 。 2^n-1 2i-1

3. 树最适合用来表示 的情况。 C

A. 数据元素有序 B. 数据元素之间具有多对多关系 C. 数据元素无序 D. 数据元素之间具有一对多关系

4.在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多_ _个。 D A.-1 B.0 C.1 D.2

5. 如果要根的层次为1，具有61个结点的完全二叉树的高度为 _。 A

A. 5 B. 6 C. 7 D. 8 6.若某二叉树的先序遍历序列和中序遍历序列分别为 PBECD、BEPCD，则该二叉树的后序遍历序列为 。 C

A. PBCDE B. DECBP C. EBDCP D. EBPDC

7.对下图所示的二叉树进行后序遍历（左子树、右子树、根结点）的结果是 C A. 5 2 3 4 6 1 B. 5 2 3 4 1 6 C. 2 6 4 1 3 5 D. 2 5 6 4 3 1

2 3 5 六、图

1. 具有n(n>0) 个顶点的无向图最多含有______条边。 C

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

2.无向图的邻接矩阵一定是 。 D

A. 对角矩阵 B. 稀疏矩阵 C. 三角矩阵 D. 对称矩阵

填空题

1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_____数据元素____是数据的基本单位；_____数据项______是数据的最小单位。

2．已知某数据结构的二元组形式表示为：B=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={，，，，，，}。则此数据结构属于_______树形_____结构。

3.数据结构的逻辑结构包括_____线性结构________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为______非线性结构_______；数据结构的存储结构主要包括______顺序存储______和______链式存储______两种类型。

6 4 1 4.线性结构的特点是：第一个结点___无____前驱结点，其余结点有且仅有____1___个前驱结点；最后一个结点____无___后继结点，其余每个结点有且仅有___1____个后继结点。

5.树型结构的特点是：根结点没有___前驱_____结点，其余每个结点有且仅有___1_____个前驱结点；叶子结点____无_____后继结点，其余结点可以有_____任意____个后继结点。

6. 图型结构的特点是：每个结点可以有_____任意____个前驱结点和后继结点。

7. 在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要____向后____移动一个

位置。

8. 在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要_____向前_____移动一个

位置。

9. 设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平

均需要移动___n/2____个元素，删除一个元素时平均需要移动___(n-1)/2___个元素。

10. 单链表表示法的基本思想是用_____指针___表示结点间的逻辑关系。

11．线性表的顺序存储结构中逻辑上相邻的元素，物理位置____一定______相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置______不一定______相邻。

12. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_____先进后出_____表；队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做______队头____，进行删除的一端叫做____队尾_______，先进队的元素必定先出队，所以又把队列称为_____先进先出_______表。

13．在具有n个单元的循环队列中，队满时共有_____n-1______个元素。

14 ．设有一个空栈，现有输入序列1、2、3、4、5，经过push、pop、push、pop、push、pop、push、push、pop、pop后，输出序列为__________________。

15 ．当且仅当两个串的___长度___相等并且各个对应位置上的字符都___相等___时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的__子____串，该串称为它所有子串的____主__串。

16．二维数组A有m行n列，每个数组元素占L个字节的存储单元，按行的顺序存放在m*n个连续的存储单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为__________________________。

17．一棵树的二元组形式表示为T=（D，R），其中D={A，B，C，D，E，F，G}，R={(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，则该树的度数为____3____，树的深度为___3_____，叶子结点的个数为____4_____，分支结点的个数为____3_____，C结点的双亲结点为_____A_____，C结点的孩子结点为____F、G______。 18．设无向图G中有e条边且所有顶点的度数之和为m，则m与e之间的关系为____m=2e_______。

本文来源：https://www.bwwdw.com/article/ooyw.html