计算机应用基础数据结构部分试题及答案202
读万卷书，行万里路——刘彝
计算机应用基础数据结构部分试题及答案
1．选择题：
1.下面程序段的时间复杂度的量级为（）
for(i=1;i<=n;i++)
for (j=1;j<=i;j++)
for (k=1;k<=j;k++)
x=x+1;
A. O(1) B.O(n) C. O(n2) D.O(n3)
2.在数据结构中，从逻辑上可以把数据结构分成（）
A. 动态结构和静态结构 B.紧凑结构和非紧凑结构
C. 线性结构和非线性结构 D.内部结构和外部结构
3．数据结构的（）包括集合、线性、树形和图形结构四种基本类型
A. 存储结构 B.逻辑结构 C. 基本运算 D.算法描述
4．数据的（）包括查找、插入、删除、更新和排序等
A. 存储结构 B.逻辑结构 C. 基本运算 D.算法描述
5．数据的存储结构包括顺序、链接、散列和（）四种基本类型
A. 线性 B.数组 C. 集合 D.索引
6．下面（）的时间复杂性最好，即执行时间最短
A. O(n) B.O(logn) C. O(nlogn) D.O(n2)
7.下面程序段的时间复杂性的量级为（）
for(int i=0;i
A. O(m2) B.O(n2) C. O(m*n) D.O(m+n)
8．（ ）不是算法的基本特征
A. 正确性 B. 长度有限 C.在规定时间内完成 D. 确定性
9．一个栈的输入序列是1，2，3，4，5，则下列序列中（）是栈的输出序列
A. 31245 B.41325 C.23415 D.14253
10．在有n个结点的二叉链表中，值为空的链域个数为（）
A. n-1 B. 2n-1 C. n+1 D. 2n+1
1-5 D C B C D 6-11 B C C C C
11．已知完全二叉树有30个结点，则整个二叉树有（）个度为1的结点
A. 0 B. 1 C. 2 D. 不确定
12．深度为k的完全二叉树至少有（）个结点
A. 2k-1 B. 2k-2 C. 2k-1 D. 2k-2
13．深度为k的完全二叉树至多有（）个结点
A. 2k-1 B. 2k-2 C. 2k-1 D. 2k-2
14．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次
A. 1 B. 2 C. 3 D. 4
15．折半查找有序表（6，15，30，37，65，68，70，72，89，99），若查找元素37，需依次与表中元素（）进行比较
A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，37
16．一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后面向前依次后移（ ）个元素
A. n-i B. n-i+1 C. n-i-1 D. I
17．如图所示的4棵二叉树中，（ ）不是完全二叉树
（A） (B) (C) (D)
18．对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的查找长度为（ ）
A. 3 B. 4
C.5 D.6
19．设有10000个无序元素，希望用最快的速度挑选出其中前10个最大元素，最好选用（ ）排序法
A. 堆排序 B. 快速排序 C. 起泡排序 D. 插入排序
20．计算机算法指的是（ ）
A. 计算方法 B. 排序方法 C.解决问题的有序序列 D. 调度方法
11-15 B C A C D 16-20 B A B A C
21．一个栈的入栈序列1，2，3，4，则它的不可能的输出序列是（ ）
A. 1，2，3，4 B. 4，3，2，1 C. 1，3，4，2 D. 4，1，2，3
22．对于任何一棵二叉树，如果其终端结点数为N0，度为2的结点数为N2，则N0=（ ）
A. N2-1 B. N2+1 C. N2 D. N2-2
23．线性表是（）
A. 一个有限序列，可以为空 B. 一个有限序列，不能为空
C. 一个无限序列，可以为空 D. 一个无限序列，不能为空
24．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）
A. （n+1）/2 B.n/2 C. n D.n+1
25．在一个顺序表的表尾插入一个元素的时间复杂度的量级为（）
A. O(n) B.O(1) C. O(n2) D.O(logn)
26．设单链表中指针p指向结点ai,若要删除ai之后的结点（若存在），则需修改指针的操作为（）
A. p->next= p->next->next B. p=p->next C. p=p->next->next D. next=p
27．设单链表中指针p指向结点ai,指针f指向将要插入的新结点 x，则当x插在链表中两个数据元素ai和ai+1之间时，只要先修改（ ）后修改（）即可
A. p->next= f B. p->next= p->next->next
C. p->next=f->next D. f->next= p->next
E. f->next=null F. f->next=p
28．设单链表中指针p指向结点ai,指针f指向将要插入的新结点 x，则在链表中最后一个结点an之后插入时，只要先修改（）后修改（）即可
A. f->next= p B. f->next= p->next
C. p->next=f D. p->next= f->next
E. f =null
29．在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值
A. 1 B. 2 C. 3 D.4
30．在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂性的量级为（）
A. O(n) B.O(n/2) C. O(1) D.O(n1/2)
21-25 D B A C B 26-30 A (D.A) (B.C) B A
31．不带头结点的单链表L为空的判定条件是（）
A. L= = NULL B. L->next = = NULL
C. L->next = = L D. L! = NULL
32．带头结点的单链表L为空的判定条件是（）
A. L= = NULL B. L->next = = NULL
C. L->next = = L D. L! = NULL
33．在一个带有头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值
A. 2 B. 3 C. 4 D.6
34．在一个带有头结点的双向循环链
表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（）
A. p->prior B. p->next
C. p->next->next D. p->prior ->prior
35．对一个具有n个元素的线性表，建立其单链表的时间复杂度为（）
A. O(n) B.O(1) C. O(n2) D.O(logn)
36．线性表采用链式存储时，其地址（）
A. 必须是连续的
B. 一定是不连续的
C. 部分地址必须是连续的
D. 连续与否均可以
37．假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top= =-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）
A. a[--top]=x B. a[top--]=x C. a[++top]=x D .a[top++]=x
38．若已知一个栈的入栈序列是1，2，3，.....n，其输出序列为p1, p2, p3,..... pn，若p1=n，则pi为（）
A. i B.n-i C. n-i+1 D.不确定
39．判定一个栈S（最多元素为m0）为空的条件是（）
A. S. top!=0 B. S. top= =0 C. S. top!=m0 D .S. top= =m0
40．判定一个栈S（最多元素为m0）为满的条件是（）
A .S. top!=0 B. S. top= =0 C. S. top!=m0-1 D .S. top= =m0-1
31-35 A B C B A 36-40 D C C B D
41．一个队列的入队序列是1，2，3，4，则队列的输出序列是（）
A.4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D .3，2，4，1
42．从一个顺序循环队列中删除元素时，首先需要（）
A. 前移队首指针 B. 后移队首指针
C. 取出队首指针所指位置上的元素 D . 取出队尾指针所指位置上的元素
43．假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判断队列空的条件为（）
A.front+1= =rear B.rear+1= =front C. front= =0 D . front= =rear
44．假定一个顺序循环队列存储于数组a[N]中，其队首和队尾指针分别用front和rear表示，则判断队列满的条件为（）
A. （rear-1）%N= =front B. （rear+1）%N= =front
C. （front-1）%N= =rear D . （front+1）%N= =rear
45．树中所有结点的度等于所有结点数加（）
A.0 B.1 C.-1 D.2
46．在一棵树中，每个结点最多有（）个前驱结点
A.0 B.1 C.2 D.任意多个
47．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点点数为2个，则度为0的结点数为（）个
A.3 B.4 C.5 D.6
48．在一棵二叉树上第5层的结点数最多为（）
A.16 B.15 C.8 D.32
49．在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点
A.2i B. 2i+1 C. 2i-1 D. 2n
50．一颗具有35个结点的完全二叉树的深度为（）
A.6 B.7 C.5 D.8
41-45 B B D B C 46-50 B D A C A
51．在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点的编号为（）
A.2i B.2i-1 C.2i+1 D.2i+2
52．设高度为h的二叉树上只有度为0和度为2的结点，
则此类二叉树中所包含的结点数至少为（）
A.2h B.2h-1 C.2h+1 D.h+1
53．按照二叉树的定义，具有3个结点的二叉树有（）种状态
A.5 B.4 C.3 D.30
54．若查找每个元素的概率相等，则在长度为n的顺序表上查找任意元素的平均查找长度为（）
A.n B.n+1 C.（n-1）/2 D.（n+1）/2
55．顺序查找法适合于存储结构为（）的线性表
A.散列存储 B.顺序存储或链接存储
C.压缩存储 D.索引存储
56．对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用折半查找，则查找元素26的查找长度（）
A.2 B.3 C.4 D.5
57．对线性表进行折半查找时，要求线性表必须（）
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
58．采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）
A. O(n2) B. O(nlogn) C. O(n) D. O(logn)
59．在对n个元素进行直接插入排序的过程中，共需要进行（）趟
A .n B.n+1 C.n-1 D.2n
60．对n个元素进行直接插入排序时间复杂度为（）
A. O(1) B. O(n2) C. O(n) D. O(nlog2n)
51-55 C B A D B 56-60 C C D C B
61．在对n个元素进行快速排序的过程中，最好情况下需要进行（）趟
A. n B. n/2 C. logn D. 2n
62．在对n个元素进行冒泡排序的过程中，至少需要（）趟完成
A. 1 B. n C. n-1 D. n/2
63．在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（）
A. O(1) B. O(logn) C. O(n2) D. O(nlogn)
64．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）
A. 插入排序 B. 起泡排序 C. 希尔排序 D. 选择排序
65．用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
（1）25，84，21，47，15，27，68，35，20
（2）20，15，21，25，47，27，68，35，84
（3）15，20，21，25，35，27，47，68，84
（4）15，20，21，25，27，35，47，68，84
则采用的排序方法是（）
A. 选择排序 B. 希尔排序 C. 插入排序 D. 快速排序
66．对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）
A. 1，3，5，7，9 B. 5，7，9，1，3
C. 5，3，1，7，9 D. 9，7，5，3，1
67．若对n个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（）
A. O(1) B. O(logn) C. O(n) D. O(n2)
68．若对n个
元素进行堆排序，则在由初始堆进行每趟排序的过程中，共需要进行（）次筛运算
A. n+1 B. n/2 C. n D. n-1
69．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一段的方法，称为（）
A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
70．一组记录的关键字为（45，80，55，40，42，85），则利用堆排序的方法建立的初始堆为（）
A. （80，45，55，40，42，85） B. （85，80，55，40，42，45）
C. （85，80，55，45，42，40） D. （85，55，80，42，45，40）
61-65 C A D A D 66-70 B C D D B
71．若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为（）
A. 1 B.i-1 C.i D. i+1
72．在对n个元素进行冒泡排序的过程中，第一趟至多需要进行（）次相邻元素之间的比较
A. n+1 B. n/2 C. n D. n-1
73．若一个元素序列基本有序，则选用（）排序较快
A. 堆排序 B. 快速排序 C. 直接插入排序 D. 直接选择排序
74．快速排序方法在（）情况下最不利于发挥其长处
A.要排序的数据量太大 B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数
75．排序方法中，将整个无序序列分割成若干个小的子序列并分别进行插入排序的方法，称为（）
A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序
76．用直接插入排序方法对下列4个表由小到大进行排序，比较次数最少的是（）
A. （94，32，40，90，80，46，21，69）
B. （21，32，46，40，80，69，90，94）
C. （32，40，21，46，69，94，90，80）
D. （90，69，80，46，21，32，94，40）
77．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序方法，以第一个纪录为基准得到的一次划分结果为（）
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）
78．如果对元素序列（7，2，5，8，1，11）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）
A.（1，2，5，7，8，11）
B.（1，2，5，8，7，11）
C.（1，5，2，7，8，11）
D.（1，5，2，8，11，7）
79．如图所示，该二叉树的前序遍历序列是（）
A. EGFACDB
B. EAGCFBD
C. EACBDGF
D. EGACDFB
80．已知某二叉树的后序遍历序列是DACBE，中序序列是DEBAC，则它的前序遍历序列是（）
A. ACBED
B. DEABC
C. DECAB
D. EDBAC
71-75 C D C C A 76-80 B C B C D
81．已知某二叉树的前序遍历序列是ABDEFGC，中序序列是DEBGFAC，则对应的二叉
树为（）
81-85 B
2．填空题
1． 数据结构及数据的逻辑结构包括_____,______,______,________四种类型
2． 数据的存储结构及物理结构包括_____,______,______,________四种基本类型
3． 数据结构是研究数据的_____，_____以及它们之间的相互关系，并对这种结构定义相应的_____，设计出相应的_____，而确保经过这些运算后所得到的新结构是_____结构类型
4． 一个算法应具有_____，_____，_____，_____，_____这五个特征
5． 一个算法的时间复杂度是该算法包含的_____的多少，它是一个算法运行时间的相对度量，一个算法的空间复杂性是指该算法在运行过程中临时占用的_____的大小
6． 一个算法的时间复杂性通常用它的_____形式表示，当一个算法的时间复杂度与问题的规模n大小无关时，则表示为_____；成正比时，则表示为_____；成对数关系时，则表示为_____；成平方时，则表示为_____
7． _____是描述客观事物的数、字符以及所有能输入到计算机且被计算机程序加工处理的符号集合
_____是数据的基本单位，有时这个单位由若干个_____组成，在这种情况下，又称它为记录，_____是数据的最小单位，而由记录组成的线性表为_____
8． 一种数据结构的元素集合K和他的二元关系R为：
K={a,b,c,d,e,f,g,h}
R={
该数据结构具有_____结构
9．一种数据结构的元素集合K和他的二元关系R为：
K={a,b,c,d,e,f,g,h}
R={
该数据结构具有_____结构
10．一种数据结构的元素集合K和他的二元关系R为：
K={1,2,3,4,5,6}
R={(1,2), (2,3) ,(2,4), (3,4), (3,5), (3,6), (4,5), (4,6)}
该数据结构具有_____结构
1． 集合、线性结构、树型结构、图形结构（网状结构）
2． 顺序存储、链式存储、散列、索引
3． 物理结构、逻辑结构（二者顺序可颠倒）、运算、算法、原来的
4． 有穷性、确定性、可行性、输入性、输出性
5． 语句执行次数、存储空间
6． 数量级、O(1)、O(n)、O(logn)、O(n2)
7． 数据、数据元素、数据项、数据项、文件
8． 线性结构
9． 树型结构
10．图形结构（网状结构）
11．若经常需要对线性表进行插入和删除运算，则最好采用_____存储结构，若经常需要对线性表进行查找运算，则最好采用_____存储结构
12． 访问一个线性表中具有给定值元素的时间复杂性的量级为_____
13． 对于一个长度为n的顺序表，在表头插入元素的时间复杂性为_____，在表尾插入元素的时间复杂性为_____
14． 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把_____的值赋给q->next，然后把_____的值赋给p->next
15． 在一个
单链表中的p所指向结点之前插入一个指针s所指向的结点时，可执行如下操作：
（1）s->next=_____;
(2) p->next= s；
(3) t= p->data；
(4) p->data=_____；
(5) s->data=_____；
16．假定指向单链表中第一个结点的表头指针为head，则向该单链表的表头插入指针p所指向的新结点时，首先执行_____赋值操作，然后执行_____赋值操作
17．在一个单链表中删除指针p所指向结点的后继结点时，需要把_____的值赋给p->next指针域
18．在一个单链表中删除指针p所指向结点时，应执行一下操作：
q=p->next;
p->data= p->next->data;
p->next=_____；
free(q);
19．在_____链表中，既可以通过设定一个头指针也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表中的每个结点
20．在一个带有头结点的双向循环链表中的p所指向的结点之前插入一个指针s所指向结点时,可执行如下操作：
（1）s->data= element;
(2) s ->prior=_____；
(3) p->prior->next=s;
(4) s->next=_____;
(5) p->prior=_____;
11．链式、顺序
12．O(n)
13．O(n)、O(1)
14．p->next、q
15．p->next、s->data、t
16．p->next= head、head=p
17．p->next->next
18．p->next->next
19．循环
20．p->prior、p、s
21．在一个双向链表中指针p所指向结点之前插入一个新结点时，其时间复杂性的量级为_______
22． 线性表的长度是指_______
23．在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的，在线性表的链式存储中，元素之间的逻辑关系是通过_______决定的
24．根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_______和_______
25．线性表、栈和队列都是_______结构，对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素，在______删除元素
26．设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push ,pop, push ,push后，对应的输出序列是_______
27．设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为push(S,1),push(S,2), ______，pop(S)，push(S,4)，pop(S)，______，______,pop(S)，pop(S)
28．在一个具有n个存储单元的循环队列中，当队列满时共有______个元素
29．有一棵树如图所示，回答下列问题：
（1）这棵树的根结点是（）；
（2）这棵树的叶子结点是（）
（3）结点C的度是（），这棵树的度是（）
（4）结点C的子女是（）
（5）结点C的父结点是（）
30．对于一个具有n个结点的二叉树，它可能具有的最小深度为______，具有的最大深度为______
21．O(1)
22．线性表中包含数据元素的个数
23．物理存储地址、指针的值
24．单链表、双链表
25．线性、栈
顶、队尾、队头
26．2，3
27．push(S,3)、pop(S)、push(S,5)
28．n-1
29．(1) A (2) B,E,G,D (3) 2,3 (4) E,F (5) A
30．[log2n]+1、n
31．一棵深度为k的满二叉树的结点总数为______，一棵深度为k的完全二叉树的结点总数的最小值为______，最大值______
32． 由a,b,c三个结点构成的二叉树，共有______种不同的结构
33． 对于一棵具有n个结点的树，该树中所有结点的度数之和为______
34． 在一棵二叉树中，假定度为2的结点数为5个，度为1的结点数为6个，则叶子结点数为______个
35． 假定一棵二叉树顺序存储在一维数组a中，但让编号为1的结点存入a[0]元素中，让编号为2的结点存入a[1]元素中，其余类推，则编号为i结点的左孩子结点对应的数组下标为______，右孩子对应下标为______
36． 一棵n个结点的完全二叉树从根结点这一层开始，每一层上的结点按从左到右的顺序存储于数组A[1....n]中，设某个结点在数组中的位置为i（1≤i≤n），则其父结点的位置是_______
37．设二叉树的深度为h，且只有度为0和2的结点，则此二叉树中所含结点数最多为_______
38．假定一组记录为（46,79,56,38,40,84），在冒泡排序的过程中进行第一趟排序后的结果为_______
39．假定一组记录为（46,79,56,38,40,80），对其进行快速排序的过程中，共需要______趟排序
40．假定一组记录为（46,79,56,38,40,80），对其进行快速排序，则第一次划分后的结果为______
31．2k-1、2k-1、2k-1
32．5
33．n-1
34．6
35．2i-1、2i
36．[i/2](取整数部分)
37．2h-1
38．46,56,38,40,79,84
39．3
40．[40,38],46,[56,79,80]
41．对n个记录的有序表进行折半查找时，最大的比较次数是______
42．折半查找法的存储结构仅限于______，且是有序的
43．在单链表中，要删除某一指定的结点，必须找到该结点的______
44．线性表的最基本的四种操作分别是插入、删除、查找和______操作
45．循环单链表与非循环单链表的主要不同是循环单链表的尾结点指针______，而非循环单链表的尾结点指针______
46．访问单链表中的结点，必须沿着______依次进行
47．在双向链表中，每个结点有两个指针域，一个指向______，另一个指向______
48．在一个双向链表中删除指针p所指向的结点时，需要对p->next->prior指针域赋值为______
49．设head为单循环链表L的头结点，则L为空表的条件是______
50．栈又称为______表，队列又称为______表
41．log2n
42．顺序存储结构
43．前驱结点
44．排序
45．指向链表头结点，指向空
46．指针域或next域
47．前驱结点，后继结点
48．p->prior
49．head->next=head
50．后进先出，先进先出
51．假设以S和X分别表示进栈和退栈操作，则对输
入序列a, b, c ,d, e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是______
52．在一个用一维数组a[n]表示的顺序栈中，该栈所含元素的个数最少为______个，最多为______
53．在一个长度为n的顺序表中的删除第i个元素（0≤i≤n-1），需要向前移动______个元素
54．一个数据结构在计算机中的表示（映象）称为______
55．在线性结构和树型结构中，前驱结点和后继结点之间分别存在着______和______的联系
51．b, c ,e, d, a
52．0，n-1
53．n-i
54．数据的存储结构
55．一对一，一对多
56．每次从无序子表中取出一个元素，然后插入到有序子表中的适当位置，此中排序方法叫做_______排序；每次从无序表中挑选出一个最大或者最小元素，把它交换到有序表的一端，此种方法叫做________排序
57．如图所示，该二叉树的中序遍历序列是____________
56．插入，选择
57．A B C D E G F
读万卷书，行万里路——刘彝