黄河科技学院期末考试
《数据结构》课程试题(B卷)
一、单选题(每小题1分,共20分)
1.一个栈的输入序列是abcde,则栈的不可能的输出序列是__C_ __。
A.edcba
B. abcde
C. adebc D .bacde
2.子串是____C_ _。
A. 串中若干个连续字母构成的序列
B. 串中一些字符构成的序列
C. 串中任意个连续字符组成的序列
D. 串中一个以上连续字符组成的序列
3.下列排序算法中,算法不稳定的是___D____。
A.直接插入排序
B.折半插入排序
C.冒泡排序
D.快速排序
4.关键路径是指事件结点网络中的____A____。
A.从开始结点到完成结点的最长路径
B.从开始结点到完成结点的最短路径
C.最长的回路且按拓扑排序
D. 最短的回路
5.二叉树采用二叉链表存储方式进行存储,具有n个结点的二叉树中共个非空的指针。 C
A. 2n
B. 2n+1
C. n-1
D. n+1
6.深度为h的满二叉树的共有个结点。 B
A. 2h-1-1 B.2h-1 C.2h-1 D.2h
7.对于后序遍历与中序遍历结果相同的二叉树为。C
A.一般二叉树
B.根结点无左孩子的二叉树
C.所有结点只有左子数的二叉树
D.所有结点只有右子树的二叉树
8.适用于折半查找的表的存储方式及元素排列要求为 ;B
A.链接方式存储,元素无序 B.顺序方式存储,元素有序
C.顺序方式存储,元素无序 D.链接方式存储,元素有序
9. 散列表的地址区间为0-9, 散列函数为H (x)=x mod 10。采用线性探测法处
理冲突,并将关键字序列26,25,71,32,2,12,51依次存储到散列表中。
元素56存放在散列表中的地址是。A
A.8
B.5
C.6
D.7
10.下列四个序列中,哪一个是大根堆。 C
A.75,65,30,15,25,45,20,10
B. 75,65,45,10,30,25,20,15
C.75,45,65,30,15,25,20,10
D. 75,45,65,10,25,30,20,15
11具有n个顶点的无向完全图的边数为。C
A. n*(n-1)
B. n*n
C. n*(n-1)/2
D. (n*n)-1
12.线性表采用链式存储时,其存储地址。D
A.必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D.连续与否均可以
13.若给定的关键字集合为{20,15,14,18,21, 6,40,1},一趟快速排序结束时,键值的排列为。C
A.20,15,14,18,21,1,40,6
B、15,14,18,20,6, 40,1,21
C、15,14,18,20,6,21,1,40
D、15,14,40,20,6,21,1,18
14.队列操作的原则是。B
A. 先进后出
B.先进先出
C.只能进行插入
D.只能进行删除
15.任一带权连通图的最小生成树。B
A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.可能不存在
16.给定权的集合{1,3,4,2,6,5,7},所构造出的哈夫曼树的带权外部路径长度为_____B______。
A .47
B . 74 C. 89 D.98
17.假设h(key),h1(key)是不同的散列函数,散列表冲突的条件是。C
A. h(key
i )=h(key
j
)
B.key
i ≠key
j
,h(key
i
)=h1(key
j
)
C. key
i ≠key
j
,h(key
i
)=h(key
j
)
D.h1(key
i )=h(key
j
)
18.具有n个顶点的连通图的生成树有边。A
A. n-1
B. n
C.n+1
D.2n
19. 将一棵有110个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为29的结点的左孩子的编号为。D A.78 B.99 C.50 D.58
20.对于键值序列(12,3,11, 8,50,5,7,18,15,100),用筛选法建堆,必须从键值为的结点开始。B
A.12
B.50
C.11
D.15
二、判断题(每小题1分,共10分)
1.连通图一定是无向图。(X )
2.由二叉树的中序序列和前序序列不可以导出二叉树的后序。( X)
3.在Huffman树中,权值较大的叶子结点离根较远。(X )
4.在拓扑序列中,如果结点Vi排在结点Vj的前面,从Vi到Vj必存在路径。 ( X) 5.按中序遍历一棵二叉排序树所得到的中序遍历序列是一个非减序列。 (V ) 6.在AOE网中,关键路径是唯一的。 (X )
7.对于连通图,从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。 (V )
8.有向图的邻接矩阵不一定是对称的。 ( V)
9. 将一棵树转换成二叉树,则该二叉树的根结点一定没有。(V)
10.顺序存储方式只适用于线性结构。(X )
三、综合分析题(每小题10分,共60分)
1.已知一表为{13,15,24,12,37,8,14},按表中顺序依次插入初始为空的二叉排序树,构建一棵二叉排序树,写出具体步骤。
2.设二叉树的顺序存储结构如下:
(2)写出先序遍历该二叉树所得的结点序列。
3.应用冒泡排序算法,对键值序列:30,18,66,88,16, 9,17,3从小到大进行排列,试写出每趟排列的结果。
4.假设某电文仅由6个字母组成,字母在电文中出现的频率分别为:0.07,0.2,0.06,0.3,0.17,0.1,试构建一棵哈夫曼树,写出具体过程,并求出此哈夫曼树的带权外部路径长度WPL。
5.选取散列函数h(k)=kMOD10, 用线性探查法解决冲突,且试在0-9的散列地址空间中,对关键序列{13,31,23,11,25,33,1,18}构造散列表,并求出
。
等概率情况下成功的平均查找长度ASL
succ
6.已知某图的邻接表为
(1).写出此邻接表对应的邻接矩阵;
(2).写出由v1开始的深度优先遍历的序列;
(3).写出由v1开始的广度优先遍历的序列;
四、程序题(每小题10分,共10分)
下面的算法描述片段用于在双链表中指针变量p所指结点后插入一个新结点q ,请补充完整相关语句:
结点结构定义为:
typedef struct node
{ struct node * Llink;
int data;
struct node * rlink;}
q=( struct node *)(malloc( ((struct node)));
q->Llink= ;
q->rlink= ;
p->rlink->Llink = ;
p->rlink= ;
黄河科技学院期末考试
《数据结构》课程试题答案及评分标准(B卷)一、单选题(每小题1分,共20分)
1-5. CCDAC 6-10.BCBAC
11-15.CDCBB 16-20.BCADB
二、判断题(每小题1分,共10分)
1-5.XXXXV 6-10.XVVVX
三、综合分析题(每小题10分,共60分) 1.
1) Ф 1分 2)
1分
3)
4)
1分
5)
1分
6)
1分
7)
1分
8)
2分
2.
1) 5分
2)
EADCBFHGI 5分 3.
1)18,30,66,16,9, 17,3,|88 3分 2)18,30,16,9,17, 3,|66,88 1分 3)18,16,9,17,3, |30,66,88 1分 4)16,9,17,3,|18, 30,66,88 1分 5)9,16,3,|17,18, 30,66,88 1分 6)9,3,|16,17,18, 30,66,88 1分 7)3,|9,16,17,18, 30,66,88 2分 4.
1
2分
2 2
分
3) 1分
4)
1分
1分
6)
1
分
Wpl=(0.06+0.07)*4+0.1*3+(0.3+0.2+0.17)*2=2.16 2分 5.
h(13)=13MOD10=3
h(31)=31MOD10=1 h(23)=23MOD10=3 h(11)=11MOD10=1
h(25)=25MOD10=5 h(33)=33MOD10=3 h(1)=1MOD10=1
h(18)=18MOD10=8 3分 地址 0 1 2 3 4 5 6 7 8 9
成功查
找次数1 2 1 2 1 4 7 1 4分
ASL succ=(1+2+1+2+1+4+7+1)/8=19/8 3分
6.已知某图的邻接表为
(1).写出此邻接表对应的邻接矩阵;
有邻接表可知,此图为有向图
其邻接矩阵为
0 1 1 1 0 0
1 0 0 0 1 0
1 0 0 0 1 0
A= 1 0 0 0 0 1
0 1 1 0 0 0
0 0 0 1 0 0
4分
(2).写出由v1开始的深度优先遍历的序列;3分V1,V2,V5,V3,V4,V6
(3).写出由v1开始的广度优先遍历的序列;3分V1,V2,V3,V4,V5,V6
四、程序题(每小题10分,共10分)
q=( struct node *)(malloc( sizeof((struct node))); 2分
q->llink= p ; 2分
q->rlink= p->rlink- ; 2分
p->rlink->llink = q ; 2分
p->rlink= q ; 2分
数据结构试卷(一) 一、选择题(20分) 1.组成数据的基本单位是( 1.C )。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A是( C )。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3.数组的逻辑结构不同于下列(D)的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4.二叉树中第i(i≥1)层上的结点数最多有(C)个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为(.A )。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是(.C )。 (A) 6 (B) 4 (C) 3 (D) 2 7.将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为(C )。 (A) 100 (B) 40 (C) 55 (D) 80 8.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为(8.B (A) 3 (B) 4 (C) 5 (D) 1 9.根据二叉树的定义可知二叉树共有(B)种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法,则(B )的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0:m-1]的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元 素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;。 2.设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________, 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指 针域,__________个空指针域。 4.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编 号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种()。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度()。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为()参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的()。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为()。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为_________,在表尾插入元素的时间复杂度为____________。 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时, for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S; (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树,其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树,其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个,则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中,元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2. 物理结构是数据结构在计算机中的表示,又称为(存储结构)。 3. 数据元素的逻辑结构包括(线性)、(树)和图状结构3 种类型,树形结构和图状结构合称为(非线性结构)。 4. (数据元素)是数据的基本单位,(数据项)是数据不可分割的最小单位。 5. 线性结构中元素之间存在(一个对一个)关系,树形结构中元素之间存在(一个对多个)关系,图状结构中元素之间存在(多个对多个)关系。 ? 6.数据结构是一门研究非数值计算的程序设计问题中:计算机的(数据元素)以及它们之间的(关 系)和(运筹)等的学科。 7. 算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1. 数据的不可分割的基本单位是(D)。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的,这种说法(B)。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种(D)。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中,从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D)。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答:有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素(1< i产时,需向前移动(n-i)个元素。 2. 从循环队列中删除一个元素时,其操作是(先移动队首指针,后取出元素)。 3?在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为(p-> next)。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时,首先把(p->next)的值赋给q->next,然后(q->date)的值赋给p->next。 5. 从一个栈删除元素时,首先取出(栈顶元素),然后再使(栈顶指针)减1。 6. 子串的定位操作通常称做串的(模式匹配)。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第(六)次匹配成功。。 8. 顺序栈S 中,出栈操作时要执行的语句序列中有S->top(--);进栈操作时要执行的语句序列中有S->top(++)。 数据结构试题? 一、?单选题(每题 2 分,共20分) 1.1.???? 对一个算法的评价,不包括如下( B )方面的内容。 A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度 2.2.???? 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点, 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种( D )。 A.有向图 B.无向图 C.无向无环图D.有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时,其平均查找长度( B )。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7.7.???? 若需要利用形参直接访问实参时,应将形参变量说明为( D )参数。 A.值 B.函数 C.指针 D.引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有 相同的( A )。 A.行号B.列号 C.元素值 D.非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为( D )。 A.O(log 2n) B.O(nlog 2 n) C.O(n) D.O(n2) 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N(M: N)的联系时,称这种结构为图(或图结构)。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为 2011-2012学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题1分,共10分) 1.长度为n的线性表采用顺序存储结构,一个在其第i个位置插入新元素的算法时间复杂度为(D) A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6,5,4,3,2,1的顺序入栈,下列哪一个是合法的出栈序列?(D) A.543612 B.453126 C.346512 D.234156 3.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为(B ) A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点,B的右子树结点个数为n,森林F中第一棵树的结点个数是( B ) A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。(A) A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有(B )个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是(B) 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) 9.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下:(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47(4)15 21 25 47 84则采用的排序方法是(B ) A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时,要求线性表必须(D) A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的(A ) A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是(D ) A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录,其中数据结构考了90分,那 么下面关于数据对象、数据元素、数据项描述正确的是(C ) A、某班级的学生成绩表是数据元素,90分是数据项 B、某班级的学生成绩表是数据对象,90分是数据元素 C、某班级的学生成绩表是数据对象,90分是数据项 D、某班级的学生成绩表是数据元素,90分是数据元素 4.*数据结构是指(A )。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时,物理地址与逻辑地址不相同,称之为(C )。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是(C ) A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法(A )。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是(B ) A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储 比顺序存储要(B )。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于( C ) A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构,又研究物理结构,这种观点(B )。 A、正确 B、错误 C、前半句对,后半句错 D、前半句错,后半句对 12.在数据结构中,从逻辑上可以把数据结构分成( C ) A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种( A ) 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是(A ) for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题(每题 2 分,共 20 分) 1. 栈和队列的共同特点是 ( )。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列,在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构? ( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(io ), A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中,第一个元素放A[1]中, 现进行二分查找,则查找 A [3]的比较序列的下标依次为( A. 1 , 2, 3 B. 9, 5, 2, 3 C. 9, 5, 3 D. 9, 4, 2, 3 8. 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O (1) B. O (n ) C. O ( 1 og 2n ) D. O (n2) 9. 对于线性表( 7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选 用 H (K )=K %9 作为散列函数,则散列地址为 1 的元素有( )个, 位置在 676(10),每个元素占一个空间, 表示用 10 进制表示。 问 A[3][3] (10)存放在什么位置?脚注 (10) 5. A .688 B .678 C . 692 D . 696 树最适合用来表示 ( )。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 ( ). A .2-1 B.2K+1 C.2K-1 D. 2k-1 7. 第一章概论 一、选择题 1、研究数据结构就是研究(D)。 A. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D.数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中,计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是(A)。 A.空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D.数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。(线性结构就是:在非空有限集合中,存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素,集合中每一个元素均只有一个前驱,除了最后一个元素有唯一后继)(链表、栈、队列、数组、串) A. 图B. 树??C.广义表(线性表的推广) D.栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A.可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 for(i=0;i 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head!=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表:表中各结点都没有直接前趋和直接后继。 在顺序表中,只要知道(),就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中,使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中,向第i个元素之前插入一个新元素时,需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234,则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 数据结构试题(含答案) 1.数据逻辑结构包括线性结构、树形结构和图状结构三种类型,树形结构和图状结构合称非线性结构 2.数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有 1 个后续结点。 4.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。 5.在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;叶子结点没. 6.数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点,其余每个结点的后续结点可以任意多个。 7.衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8.评估一个算法的优劣,通常从时间复杂度和空间复杂度两个方面考察。 9.算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 11.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 12.在双链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。13.在顺序表中插入或删除一个数据元素,需要平均移动 n 个数据元素,移动数据元素的个数与位置有关 14.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表的元素是,应采用顺序存储结构 15.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成单链表和双链表。 16.顺序存储结构是通过下标表示元素之间的关系的;链式存储结构是通过指针表示元素之间的关系的 17.带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18.栈是限定仅在表尾进行插入或删除操作的线性表,其运算遵循后进先出的原则。19.空串是零个字符的串,其长度等于零。空白串是由一个或多个空格字符组成的串,其长度等于其包含的空格个数。 20.组成串的数据元素只能是单个字符。 21.一个子串”str”在主串”datastructure”中的位置是 5 。 22.字符串中任意个连续字符构成的部分称为该串的子串。 23.二维数组M的每个元素是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要 540个字节;M的第8列和第5行共占108个字节24.稀疏矩阵一般的压缩存储方法有两种,即三元组表和十字链表。 25.广义表((a),((b),c),(((d))))的长度是 3 ,深度是 4 。 26.在一棵二叉树中,度为零的结点的个数为n0,度为2 的结点的个数为n2,则有n0= n2+1 。 27.在有n个结点的二叉链表中,空链域的个数为__n+1__。 28.一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29.深度为5的二叉树至多有 31 个结点。 30.若某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点个数为69 。 一、单选题(每题2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种( D )。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度(B)。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为(D )参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的(A)。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为(D )。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为____O(1)_____,在表尾插入元素的时间复杂度为____O n________。 《数据结构》试题(A卷) (考试时间: 90分钟) 一、单项选择题(本大题共15小题,每小题2分,共30分) (每题只有一个选项是正确的,将答案填写在括号内,错选、多选不得分) 1.()是组成数据的基本单位,是一个数据整体中相对独立的单元。 A.数据 B.数据元素 C.数据对象 D.数据结构 2.算法计算量的大小称为算法的()。 A.效率????? B.复杂度 C.数据元素之间的关系??? ? D.数据的存储方法 3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算,则采用以下()方式最节省时间。 A.链式存储 B. 索引存储 C.顺序存储 D.散列存储 4.下述哪一条是顺序存储结构的优点?() A.存储密度大? B.插入运算方便? C.删除运算方便? D.可方便地用于各种逻辑结构的存储表示 5.在一个单链表中,若删除p所指结点的后续结点,则执行()。 >next=p->next->next >next=p->next =p->next;p->next=p->next->next =p->next->next 6.带头结点的单链表head为空的判定条件是()。 ==NULL >next==NULL >next==head !==NULL 7.非空的循环单链表head的尾结点(由p所指向)满足()。 >head==NULL ==NULL >next==head ==head 8.下面关于线性表的叙述中,错误的是哪一个?() A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链式存储,不必占用一片连续的存储单元。 D.线性表采用链式存储,便于插入和删除操作。 9.队列操作的原则是()。 A.后进先出 B.先进先出 C.只能进行插入 D.只能进行删除 10.栈中允许进行插入和删除的一端称为()。 A.栈首 B.栈尾 C.栈顶 D.栈底 11.假设以数组A[n]存放循环队列的元素,其首尾指针分别为front和rear,则当前队列中的元素个数为()。 A.(rear-front+n)%n B. rear-front+1 C. (front-rear+n)%n D.(rear-front)%n 12.最大容量为n的循环队列,队尾指针是rear,队首指针是front,则队空的判断条件是( )。 A.(rear+1)%n==front ==front +1==front D.(rear-1)%n==front 13.将一个十进制的数转换成二进制的数,可以使用以下一种称为()的数据结构。 A. 图 B. 树 C. 广义表 D. 栈 14. 把一棵树转换为二叉树后,这棵二叉树的形态是()。 A. 有2种 B. 有3种 C. 有4种 D. 唯一的 15.一棵左右子树均不空的二叉树在先序线索化后,其中空链域的个数是()。 A. 3 B. 2 C. 0 D. 不确定 二、填空题(本大题共10个空,每空2分,共计20分) 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 (一) (二) (三) (四) (五) (六) (七 )(八 ) (九 ) (十 ) 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 (一) (二) (三 ) (四 ) (五 ) (六) (七) (八) (九) (十 ) 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列,在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分,共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n],假设 个空间,问 676(10),每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置?脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ) 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中,第一个元素放 A[1]中,现进行二 分查找,则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选用 H (K ) =K %9作为散列函数,则散列地址为 1的元素有(D )个, A . 1 B . 2 C . 3 10. 设有6个结点的无向图,该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分,共26分) 1.通常从四个方面评价算法的质量: _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个,树的深度为 ____________ ,树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性 数据结构试题及答案 Document number【SA80SAB-SAA9SYT-SAATC-SA6UT-SA18】 数据结构试题 一、单选题(每题 2 分,共20分) 1.1. 对一个算法的评价,不包括如下( B )方面的内容。 A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度 2.2. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点, 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3. 对线性表,在下列哪种情况下应当采用链表表示( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5. AOV网是一种( D )。 A.有向图 B.无向图 C.无向无环图D.有向无环图 6.6. 采用开放定址法处理散列表的冲突时,其平均查找长度( B )。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7.7. 若需要利用形参直接访问实参时,应将形参变量说明为( D )参数。 A.值 B.函数 C.指针 D.引用 8.8. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有 相同的( A )。 A.行号B.列号 C.元素值 D.非零元素个数 9.9. 快速排序在最坏情况下的时间复杂度为( D )。 A.O(log 2n) B.O(nlog 2 n) C.O(n) D.O(n2) 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N (M:N)的联系时,称这种结构为图(或图结构)。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的_对头_进 行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈 满的条件是_top==0__。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为 _O(1)_,在表尾插入元素的时间复杂度为__O(n)_。 5. 5.设W为一个二维数组,其每个数据元素占用4个字节,行下标i从0到7 , 列下标j从0到3 ,则二维数组W的数据元素共占用_128_个字节。W中第6 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为()。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为()。 for(i=n-1;i>=0;i--) for(j=0;jnext; Q.front->next=p->next; (C)、p=Q.rear->next; p->next= Q.rear->next; (D)、p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于() (A)、除根结点之外的所有结点权值之和(B)、所有结点权值之和 (C)、各叶子结点的带权路径长度之和(D)、根结点的值 10.线索二叉链表是利用()域存储后继结点的地址。数据结构试题及答案(免费)
数据结构期末考试试题及答案
数据结构考试题库
数据结构试题及答案
《数据结构》期末考试题及答案
数据结构考试题库含答案
2017数据结构期末考试试题及答案
数据结构试题及答案
数据结构期末考试试题及答案
数据结构试题(含答案)
数据结构试题及答案
数据结构期末考试试题和标准答案及评分标准
十套数据结构试题与答案
数据结构试题及答案
数据结构期末考试试题及答案资料