数据结构复习题 有答案的打印版

一、选择题

1．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

3. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A．不确定 B．2n C．2n+1 D．2n-1 4．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（A ）。

A．n-1 B．?n/m?-1 C．?(n-1)/(m-1)? D． ?n/(m-1)?-1 E．?(n+1)/(m+1)?-1 5. 有关二叉树下列说法正确的是（ B ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2

2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 4. 静态链表中指针表示的是（ C ）. A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址

5. 链表不具有的特点是（ B ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比

1. 对于栈操作数据的原则是（ B ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ A ）

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

3. 设栈的输入序列是1，2，3，4,则（ D ）不可能是其出栈序列。

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

D. 4，3，1，2， E. 3，2，1，4，

1. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，求A[6，8]的地址。1340

2. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，求A[5，9]的地址。1196

1．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）

A．9 B．11 C．15 D．不确定 2．具有10个叶结点的二叉树中有（ B ）个度为2的结点， A．8 B．9 C．10 D．ll

C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2

1．图中有关路径的定义是（ A ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C

．

由

不

同

边

所

形

成

的

序

列 D．上述定义都不是

2．设无向图的顶点个数为n，则该图最多有（ B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2

3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A ．n-1 B．n C．n+1 D．nlogn；

4．要连通具有n个顶点的有向图，至少需要（ B ）条边。 A．n-l B．n C．n+l D．2n

5．n个结点的完全有向图含有边的数目（ D ）。【中山大学 1998 二、9 （2分）】

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）

6．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。

A．0 B．1 C．n-1 D．n

7．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。

A．1/2 B．2 C．1 D．4

8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A )。 A．5 B．6 C．8 D．9

9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。

A．逆拓扑有序 B．拓扑有序 C．无序的

10．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )

A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3. 下面关于二分查找的叙述正确的是 ( D )

A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找

构造的结果不同的是( C )

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）

C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)

ASL为(C )。【北京航空航天大学 2000 一、8 （2分）】 13 ．分别以下列序列构造二叉排序树，与用其它三个序列所

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 1．某内排序方法的稳定性是指( D )。

B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储

4. 对线性表进行二分查找时，要求线性表必须（ B ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序

C.以链接方式存储 D.以链接方式存储,且数据元素有序

5．适用于折半查找的表的存储方式及元素排列要求为( D ) A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

6. 用二分（对半）查找表的元素的速度比用顺序法( D ) A. 必然快 B. 必然慢 C. 相等 D. 不能确定

7．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减

8. 具有12个关键字的有序表，折半查找的平均查找长度（ A ）

A. 3.1 B. 4 C. 2.5 D. 5

9. 折半查找的时间复杂性为（ D ）

A. O（n2

） B. O（n） C. O（nlogn

） D. O（logn

） 10．当采用分快查找时，数据的组织方式为 ( B ) A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

11．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性

12. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C )

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( D )排序法是不稳定性排序法。

A. 插入 B. 冒泡 C. 二路归并 D. 堆积

3．下列排序算法中，其中（ D ）是稳定的。 【福州大学 1998 一、3 (2分)】

A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序

4．稳定的排序方法是（ B ）

A．直接插入排序和快速排序 B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序 D．树形选择排序和shell排序

5 ．下列排序方法中，哪一个是稳定的排序方法？（ B ） A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序

6．若要求尽可能快地对序列进行稳定的排序，则应选 B （A．快速排序 B．归并排序 C．冒泡排序）。

7．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ A ）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数 8．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序

9．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( A )

A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法

10．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( D )。

A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序

11．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D ）。

A． 直接插入排序 B. 气泡排序 C. 快速排序

D. 直接选择排序

12．比较次数与排序的初始状态无关的排序方法是( D )。

D．以上均不正确

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序

13．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C )的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序 D.堆排序

14．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。

6．一个具有1026个结点的二叉树的高h为（ ）。

A．11 B．12 C．11至1026之间 A. 快速排序 B. 冒泡排序 C. 选择排序 D ． 10 至1024之间

D. 插入排序

15．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为

A. 84 47 25 15 21 B. 15 47 25 84 21 C. 15 21 25 84 47 D. 15 21 25 47 84

则采用的排序是 ( A )。 A. 选择 B. 冒泡 C. 快速 D. 插入

16．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ C ）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡

1．一个堆栈的入栈序列为A、B、C、D、E，则可能的出栈序列是（ ）。 A. DCEAB B. DECBA C. EDCBA D. ABCDE

2. （ ）属于不稳定的排序算法。

A. 希尔排序 B. 堆排序 C.

快速排序 D. 基数排序

3. 向单链表中指针hs指向的结点后插入一个新节点s，应执行（ ）。 A

．

hs->next=s; B．s->next=hs; hs=s; C．s->next=hs->next; hs->next=s; D．s->next=hs; hs=hs->next;

4. 一个n个顶点的连通有向图，其边的数量至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn；

5. 设图如下所示，在下面的5个序列中，不符合深度优先遍历的序列有（ ）种。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．2 B．3 C．4

7．某二叉树中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则其先序序列不是（ ）。

A．EACBDGF B．EFGACBD C．EAGCFBD D．EGFACDB

8 ．不适用于折半查找的表的存储方式及元素排 列要求为

（ ）。

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存 储，元素有序

9. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ ）。 A. n 在 m右方 B. n在m左方 C. n是m的祖先 D. n是m的子孙

10．用户依次输入如下一组查询关键字：70、50、30、60、66、56、80。请问最后建立的平衡二叉树树根是（ ）。 A. 50 B. 56 C. 60 D. 70

二、填空题

1 ．当线性表的元素总数基本稳定，且很少进行插入和删除

操作，但要求以最快的速度存取线性表中的元素时，应采用__顺序 _____存储结构。

2．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__（n-1）/2 ______。【北方交通大学 2001 二、9】 3 ．设单链表的结点结构为 (data,next)，next为指针域，已知

指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______；py->next=px->next; px->next=py ______; 4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_ n-i+1_______个元素。 5．对于一个具有n个结点的单链表，在已知的结点*p后插

入一个新结点的时间复杂度为 _ O(1)， _______,在给定值为

x的结点后插入一个新结点的时间复杂度为__ O(n)______ 6．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。

7． 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、f->next=p->next; f->prior=p; p->next->prior=f; p->next=f; _______、_______、________。

8. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句： s^ .next:=p； s^ .prior:= _ p^.prior

_______；p^ .prior:=s；__ s^.prior^.next______:=s； 9．链接存储的特点是利用__指针 ______来表示数据元素之间的逻辑关系。

10.顺序存储结构是通过__物理上相邻 _____表示元素之间的关系的;链式存储结构是通过__指针_______表示元素之间的关系的。

11. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 __4__个，单链表为____2___个。

12. 循环单链表的最大优点是：_从任一结点出发都可访问到链表中每一个元素。_______。13. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_ u=p->next; p->next=u->next; free(u); _______

14. 带头结点的双循环链表L中只有一个元素结点的条件是：__ L->next->next==L ______

15. 在单链表L中，指针p所指结点有后继结点的条件是：_ p->next!=null_

16.带头结点的双循环链表L为空表的条件是：____ L->next==L && L->prior==L ____。

17. 在单链表p结点之后插入s结点的操作是：_ s->next=p->next;p->next=s;______。

1．栈是_操作受限（或限定仅在表尾进行插入和删除操作） ______的线性表，其运算遵循__后进先出 _____的原则。 2．___栈____是限定仅在表尾进行插入或删除操作的线性表。

3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3 1 2 ______。

4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为

1

，2

，3，4

，5，

经过

PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。

5. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为__0 ，栈2空时 ，top[2]为___ n+1 ____，栈满时为__ top[1]+1=top[2]_____。

6．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式

是：M：= M= _(M+1)% N；_______。 7．___队列_____又称作先进先出表。 8. 队列的特点是__先进先出 _____。

9．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是__先进先出 _____。

1. 数组的存储结构采用___顺序存储结构 ____存储方式。 2. 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）9572_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为__（2）1228_。

3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为（_1）9174_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）8788 _。

4. 将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：__1100_____。

5. 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为__232_____。

6. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为__ 1340 _____。

7. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：___1196____。

8. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_1_行，第_3_列的元素。

1．二叉树由_(1)根结点(2)左子树(3)右子树(1)__，__(2)_，_(3)__三个基本单元组成。

2．在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==null && p->rchlid==null _____。

3．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的__平衡因子__。

4．具有256个结点的完全二叉树的深度为__9 ____。 5．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。 6．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是__ n ____。

7．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =__ N2+1____ 8．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为__ ?N/2? ____。

9．高度为K的完全二叉树至少有__2k-2

____个叶子结点。 10．高度为8的完全二叉树至少有___64___个叶子结点。 11．已知二叉树有50个叶子结点，则该二叉树的总结点数

至少是_ 99 _____。

12．一个有2001个结点的完全二叉树的高度为__11 ____。 13．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为__69____。

14．具有N个结点的二叉树，采用二叉链表存储，共有__ N+1____个空链域。

15．二叉树的先序序列和中序序列相同的条件是_任何结点至多只有右子女的二叉树。 _____。

16．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是__ DGEBFCA __。

17．一个无序序列可以通过构造一棵___二叉排序树___树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

18．利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树____。

19．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的___前序 ___序列中的最后一个结点。

20．哈夫曼树是_带权路径长度最小的二叉树，又称最优二叉树 _____。

21．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__69____。

22．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_6 __，带权路径长度WPL为_261 __。 23. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__5, ________，带权路径长度WPL的值为___96_______。

1.判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图_____。

2．有向图G的强连通分量是指__有向图的极大强连通子图____。

3．一个连通图的__生成树____是一个极小连通子图。 4．具有10个顶点的无向图，边的总数最多为__45 ____。 5．若用n表示图中顶点数目，则有__ n(n-1)/2 _____条边的无向图成为完全图。

6．G是一个非连通无向图，共有28条边，则该图至少有__9 ____个顶点。

7. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_ n _____条弧。

8．在有n个顶点的有向图中，每个顶点的度最大可达__2(n-1) ____。

9．设G为具有N个顶点的无向连通图，则G中至少有_ N-1_____条边。

10．n个顶点的连通无向图，其边的条数至少为__ n-1____。 11．如果含n个顶点的图形形成一个环，则它有__ n ____棵生成树。

12．N个顶点的连通图的生成树含有__ N-1 ____条边。

13．构造n个结点的强连通图，至少有__ n ____条弧。

14．有N个顶点的有向图，至少需要量__ N ____条弧 才能保证是连通的。

15．右图中的强连通分量的个数为（ 3 ）个。

16．N个顶点的连通图用邻接矩阵表示时,该矩阵 至少有___ 2（N-1）____个非零元素。

17．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度 ____；对于有向图来说等于该顶点的_出度_____。

18. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_第I列非零元素个数 _____。

19．构造连通网最小生成树的两个典型算法是__普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法____。 20．求图的最小生成树有两种算法，__克鲁斯卡尔____算法适合于求稀疏图的最小生成树。

21. Prim（普里姆）算法适用于求__边稠密 ___的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_边稀疏______的网的最小生成树。

22. 有向图G可拓扑排序的判别条件是__不存在环____。 23．求最短路径的Dijkstra算法的时间复杂度为__ O(n2

）____。 24. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为__ 75 ____。

25．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为__.O(n+e）____。

26．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为__关键路径 ____。

1．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__6,9,11,12 ________。 2. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5 ________

3. 在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4

的元素的下标从小到大依次是

__1,3,6,8,11,13,16,19________

4. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需___2,

_______次查找成功，47时_____4,____成功，查100时，需___3_______次才能确定不成功。

5. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把

结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。 5. 平衡二叉树又称__________，其定义是__________。 6. 在哈希函数H（key）=key%p中，p值最好取__________。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构复习题 有答案的打印版在线全文阅读。