当前位置：文档库 › 中国地质大学2011数据结构试卷及其答案 (1)

中国地质大学2011数据结构试卷及其答案 (1)

课程名称：数据结构A 学时： 56 考核方式：笔试闭卷

班级： 191091-4、192091-3、193091-2

任课教师：

一、单项选择题：1－20小题，每小题2分，共40分。在每小题给出的四个选项中，请选出一项最符合题目要求的选项。

1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ D ）。

for(int i=1;i

i=2*i;

A.O(n2)

B.O(n)

C.O(nlog2n)

D.O(log2n)

2.若某线性表最常用的操作是存取任意指定序号的元素和在表尾进行插入和删

除运算，则利用（ A ）存储方式最节省时间。

A.顺序表

B.双链表

C.带头结点的双循环链表

D.单循环链表

3.某线性表中最常用的操作是在表尾插入一个元素和删除第一个元素，则采用

（ D ）存储方式最节省运算时间。

A.单链表

B.仅有头指针的单循环链表

C.双链表

D.仅有尾指针的单循环链表

4.若进栈序列为123456，且进栈和出栈可以交替进行，则不可能出现的出栈序

列为（ D ）。

A.125436

B.325641

C.342165

D.546231

5.若用数组A[60]存放循环队列的元素，已知头指针值为35，当前队列中有40

个元素，则队列的尾指针值为( C )。约定头指针指向队头元素的前一个位置。

解答：(35+40)%60=15

A.75

B.20

C.15

D.5

6.深度为6的完全二叉树（根结点的深度为0）至少有（B ）个结点。

A.32

B.64

C.127

D.128

解答：第0-5层全满，第6层1个，1+2+4+8+16+32+1=64个。

7.将一棵森林F转换为孩子兄弟链表表示的二叉树T，则F的后根遍历是T 的

（ B ）。

A.前序遍历

B.中序遍历

C.后序遍历

D.层序遍历

8.假设使用图的深度优先搜索DFS算法从根开始遍历一棵二叉树，先访问左子

树再访问右子树，则访问结点的顺序相当于二叉树的（ A ）序列。

A.前序遍历

B.中序遍历

C.后序遍历

D.层次遍历

9.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是

（ C ）。

A. B.

C. D.

10. 下列关于图的叙述中，正确的是（ D ）

I ．无向连通图中所有顶点的度之和为偶数

II ．存储稀疏图，用邻接矩阵比邻接表更省空间

III ．若有向图中存在拓扑序列，则该图不存在回路

A.只有II

B.只有I 和II

C.只有III

D.只有I 和III

11. 若无向图 G =（V ，E ）中含 7 个顶点，则保证图 G 在任何情况下都是连通

的，则需要的边数最少是（ A ）。

A. 6

B. 15

C. 16

D. 21

12. 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（B ）

A. 5

B. 4

C. 3

D. 2

13. 已知一个长度为 8 的有序顺序表，若采用折半查找法查找一个不存在的元

素，则比较次数最多的是（ B ）

A. 3

B. 4

C. 5

D. 6

14. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是

（ A ）。

A. 85, 12, 81, 14, 84, 61

B. 82, 10, 81, 24, 78, 25

C. 11, 79, 67, 19, 26, 28

D. 2, 15, 61, 58, 23, 24

15. 下列二叉树中，不满足平衡二叉树定义的是（ A ）。

a c

b d NULL NULL a

c b

d NULL a c

b d NULL a

c b

d a e

d c b

A. B. C. D.

16.下列叙述中，不符合m阶B-树定义要求的是（ D ）。

A．根结点至多有m-1个关键字 B.所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列 D.每个结点至少有两棵非空子树17.为提高散列（Hash）表的查找效率，可以采取的正确措施是（ D ）。

I．增大装载因子

II．设计冲突少的散列函数

III．处理冲突时尽量减少产生聚集（堆积）现象

A.只有I

B.只有II

C.只有I和II

D.只有II和III

18.若数据元素序列20，27，31，5，7，11，42，2，4是采用下列排序方法之

一得到的第二趟排序后的结果，则该排序算法只能是（ B ）。

A.冒泡排序

B.插入排序

C.选择排序

D.二路归并排序

19.为实现快速排序算法，待排序序列宜采用的存储方式是（ A ）。

A.顺序存储

B.散列存储

C.链式存储

D.索引存储

20.设有5000个无序记录，希望得到前10个最小元素，用（ C ）方法最快。

A.冒泡排序

B.快速排序

C.堆排序

D.简单选择排序

二、简答题。21－23小题。共35分。

21.（8分）假定用于通讯的电文仅由7个字母C1, C2, …, C7组成，各个字母在

电文中出现的次数分别为1, 3, 5, 6, 7，10, 12，试为这7个字母设计哈夫曼树，要求画出哈夫曼树，写出各个字符的哈夫曼编码略

答：哈夫曼树（略）构造成功5分，编码正确3分

22.（18分）已知6个顶点（顶点编号0~5）的有向带权图G，其邻接矩阵A为

上三角矩阵，按“行”为主序（行优先）保存在如下的一维数组中。

3 5 ∞∞∞

4 ∞

5 ∞ 3 2 ∞∞ 2 4

（1）写出图G的邻接矩阵A。（4分）

（2）画出有向带权图G。（2分）

（3）求图G的关键路径，并计算该关键路径的长度。（7分）

（4）采用Dijkstra算法求编号为0的顶点到其余各顶点的最短路径。（5分）

（3）关键路径为0—>1→2→4→5，长度为3+4+2+4=13.

（4）0→1:<0,1>,3

0→2:<0,2>,5

0→4:<0,2,4>,7

0→3:<0,2,3>,8

0→5:<0,2,3,5>,10

23.（9分）将关键字序列(SUN, MON, TUE, WED, THU, FRI, SAT)散列存储到一

个下标从0开始的一维数组中，散列函数为：H(key) = 关键字key中第一个字母在字母表中的序号% 7，处理冲突采用二次探测再散列法（地址增量序列为1,-1,4,-4,9,-9,……），要求装载因子为0.7。

（1）请画出所构造的散列表。（7分）

（2）计算等概率情况下，查找成功的平均查找长度。（2分）

答：（1）

关键字Mon Tue Wed Thu Fri Sat Sun

20 23 20 6 19 19 散列地址 6

6 2 6 6 5 5 探查次数 1 2 1 3 4 3 4

构造的散列表如下：（7分）

下标 0 1 2 3 4 5 6 7 8 9

关键字 FRI WED SAT THU MON TUE SUN

【评分说明】所画的散列表长度正确（长度为10，下标从0到9），给1分。填写关键字正确，每个给1分。考生可以不写出计算过程。若解答部分正确，酌情给分。

（2）查找成功的平均查找长度：（2分）

因为查找长度为1的关键字有4个，查找长度为2的关键字有1个，查找长度为3的关键字有2个，所以查找成功的平均查找长度：

ASL 成功=（1次×2+2次×1+3次×2+4*1）/7=2（2分）

各位置对应的探查次数如下表所示：

下标 0 1 2 3 4 5 6

探查次数 1 2 1 5 4 3 2

【评分说明】若分别采用公式（α为装填因子）：

11(1)21α

+-和211(1)2(1)α+- 计算查找成功，且计算正确，可共给2分。若解答部分正确，酌情给分。

三、算法设计题。24－25小题。共25分。每题要求：

24. （12分）给定有m 个整数的递增有序数组a[m]和有n 个整数的递减有序数组b[n]，试写出算法，将数组a 和b 归并为递增有序数组c[m+n] （要求算法的时间复杂度为O(m+n)）。

答：（1）描述算法的基本设计思想（3分）

把b[n]逆置，然后两个递增有序数组归并成c 数组。

（2）描述算法的详细实现步骤（4分）略

（3）根据设计思想和实现步骤，采用C 语言描述算法，关键处请给出注释（5分）略

25. （13分）设含有n 个元素的线性表A=(a 1, a 2, a 3,…, a n-1, a n )，用带头结点的单链表表示。试编写一个算法，对A 进行调整，使得所有偶数项排在奇数项之前，即：当n 为偶数时，A=(a 2,a 4,…,a n ,a 1,a 3,…,a n-1)；当n 为奇数时，A=(a 2,a 4,…,a n-1,a 1,a 3,…,a n )，并分析算法的时间复杂度。

答：

（1）描述算法的基本设计思想（3分）

设置遍历指针p 和计数器j ，以及指向偶数项表尾的指针。将偶数项从原表中删除，插在偶数项表尾。

（2）描述算法的详细实现步骤（4分）略

（3）根据设计思想和实现步骤，采用C语言描述算法，关键处请给出注释（5分）略

（4）算法时间复杂度：O(n).（1分）

数据结构标准答案

全国2011年1月高等教育自学考试数据结构试题课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（）？？？？ A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）p55 A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（）p66 A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（）p73 A.4 B.5 C.7 D.8 9.下列叙述中错误的是（）108 A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次107 B.图的遍历可以采用深度优先遍历和广度优先遍历108 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程108 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={，，，，

数据结构试题及答案10套

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p；Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ）Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）

数据结构试题(附有答案)

数据结构（本科）试卷7 一、选择题（每小题1分，共10分） 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是： A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。 A. 较慢 B.较快 C. 相同二、填空题（每小题1分，共10分） 1.二维数组是一种非线性结构，其中的每一个数组元素最多有____2___个直接前驱（或直接后继）。 2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中， A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_

数据结构c语言版试题大全含答案

1 绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室 2011-5-8

数据结构试卷带答案

数据结构试卷（一）一、选择题（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

数据结构试题库答案

数据结构试题及答案一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s

数据结构试题(含答案)

数据结构试题（含答案） 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 。

数据结构习题及答案-第11章文件

第十一章文件一、选择题 1. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。【哈尔滨工业大学 2001二、5 （2分）】 A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理 2. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用（）的方法可降低所需的代价。【北京邮电大学 2000 二、 8 （20/8分）】 A. 附加文件 B. 按关键字大小排序 C. 按记录输入先后排序 D. 连续排序 3. 用ISAM组织文件适合于（）。【中科院软件所 1998】 A．磁带 B．磁盘 4．下述文件中适合于磁带存储的是（）。【中科院计算所 2000 一、7（2分）】 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 5. 用ISAM和VSAM组织文件属于（）。 A. 顺序文件 B. 索引文件 C. 散列文件【中国科技大学 1998 二、5（2分）中科院计算所 1998 二、5（2分）】 6. ISAM文件和VASM文件属于（）。【山东大学 2001 二、5 (1分)】 A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 7. B+树应用在（）文件系统中。【北京邮电大学 2001 一、1（2分）】 A. ISAM B. VSAM 二、判断题 1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。【长沙铁道学院 1998 一、5 (1分)】 2. 倒排文件是对次关键字建立索引。【南京航空航天大学 1997 一、10（1分）】 3. 倒排序文件的优点是维护简单。【南京航空航天大学 1995 五、10（1分）】 4. 倒排文件与多重表文件的次关键字索引结构是不同的。【西安交通大学 1996 二、6 (3分)】 5. Hash表与Hash文件的唯一区别是Hash文件引入了‘桶’的概念。【南京航空航天大学1996六10(1分）】 6. 文件系统采用索引结构是为了节省存储空间。【北京邮电大学 2000 一、10 （1分）】 7. 对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。【东南大学 2001 一、1-10 （1分）】 8. 对磁带机而言，ISAM是一种方便的稳健组织方法。【中科院软件所 1997 一、10（1分）】 9. 直接访问文件也能顺序访问，只是一般效率不高。【北京邮电大学 2002 一、10（1分）】 10. 存放在磁盘，磁带上的文件，即可以是顺序文件，也可以是索引结构或其他结构类型的文件。【山东大学 2001 一、7 (1分)】 11. 检索出文件中的关键码值落在某个连续的范围内的全部记录，这种操作称为范围检索。对经常需要做范围检索的文件进行组织，采用散列法优于顺序检索法。【中山大学 1994 一、

数据结构试卷带答案

数据结构试卷带答案问题说明部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法（12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。

（13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作（15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数（16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错（18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材（19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟

数据结构试题及答案

一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）

数据结构试题及答案

第一章概论一、选择题 1、研究数据结构就是研究（Ｄ）。Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i

数据结构试题(含答案)

一．是非题（正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

数据结构试题及答案

数据结构试卷（十一）一、选择题(30分) 1．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 3．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（）。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 4．（）二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历 5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。 7．设带有头结点的单向循环链表的头指针变23 (A) O(n) (B) O(nlogn) (C) O(n) (D) O(n/2)2 量为head，则其判空条件是（）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 (A) 20 (B) 256 (C) 512 (D) 1024 9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 (A) 1 (B) 2 (C) 3 (D) 4 10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 二、判断题(20分) 1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（） 3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(logn)。（）24．完全二叉树中的叶子结点只可能在最后两层中出现。（） 5．哈夫曼树中没有度数为1的结点。（） 6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（） 7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）

数据结构试卷B卷(含答案)

《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

数据结构试题及答案

数据结构试题一、单选题（每题 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表示栈空，

北航2011年硕士研究生入学考试数据结构与C语言试题与答案

2011 年硕士研究生入学考试 “数据结构与C语言程序设计”(科目代码:991)试题与答案一、单项选择题(本题共20分，每小题各2分) 1．下列关于线性表的存储结构的叙述中，错误的是。 A．线性表的顺序存储结构中隐式地存储了数据元素之间的逻辑关系 B．线性表的顺序存储结构一定需要占用一片地址连续的存储空间 C．线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系 D．线性表的链式存储结构占用的存储空间一定不连续 2．若front 和rear 分别表示链接队列的队头指针与队尾指针，则向队列中插入一个由p 指的新元素的过程是依次执行。 A．rear=p; front=p; B．front=p; rear=p; C．rear->link=p; rear=p; D．front->link=p; rear=p; 3．下列关于二叉树的叙述中，正确的是。 A．二叉树的度可以小于2 B．二叉树的度等于2 C．二叉树中至少有一个结点的度为2 D．二叉树中每一个结点的度都为2 4．若某二叉树有40个叶结点，则该二叉树的结点总数最少是。 A．78 B．79 C．80 D．81 5．若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为0，则该有向图的拓扑序列。 A．存在且惟一B．存在但可能不惟一 C．不存在D．无法确定 6．下面关于AOE 网的叙述中，正确的是。 A．AOE 网是一个带权的连通图 B．AOE 网是一个带权的强连通图 C．AOE 网是一个带权的无回路的连通图 D．AOE 网是一个带权且无回路的有向图 7．下列关于线性表查找方法的叙述中，错误的是。 A．顺序查找法适合于采用顺序存储结构和链式存储结构的线性表的查找 B．对于相同元素，顺序查找法一定能够查找到表中首次出现的元素 C．对于相同元素，折半查找法一定能够查找到表中首次出现的元素 D．对于相同元素，折半查找法不一定能够查找到表中首次出现的元素 8．在二叉排序树中进行查找的平均时间效率主要与下列因素之一有关，该因素是。A．二叉排序树的深度B．二叉排序树中结点的个数的多少 C．被查找结点的度D．二叉排序树的存储结构 9．下列4 种排序方法中，每一趟排序结束时不一定能够确定一个元素排序最终位置的是。 A．插入排序B．快速排序 C．堆积(Heap)排序D．二路归并排序 2 10．下列4 种排序方法中，当待排序的序列中元素初始时已经按值有序，排序所花费的

软件学院2011级数据结构试题(A)

软件学院2011级《数据结构》课程试题（A卷） 1．任何一个算法的设计都取决于选定的（）． A. 数据逻辑结构 B. 数据的物理结构 C. 数据存储结构 D. 数据的数据类型 2. 非空单循环链表head的尾结点*P满足（）。 A. p->next=null B. p=NULL C. p->next=head D.p=head 3.表长为n的顺序存储的线性表，当在任何位置插入一个元素概率相等时，插入一个元素所需移动元素的平均个数为（）． A.n B. (n-1) / 2 C.n/2 D.O(n) 4. 设有顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序是 s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（）。 A. 2 B. 3 C. 5 D. 6 5. 循环队列的队满条件为（）。 A.（sq.rear+1）%maxsize==(sq.front+1)%maxsize B. (sq.rear+1)%maxsize==sq.front+1; C. (sq.rear+1)%maxsize==sq.front D. Sq.rear==sq.front 6. 稀疏矩阵的压缩存储方法通常有两种,即（）。 A.二元数组和三元组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 7. 二维数组A[10..20,5..10]采用行序为主的方式存储,每个数据元素占4个存储单元,且 A[10,5]的存储地址是1000,则A[18,9]的存储地址是（）。

A. 1208 B. 1212 C. 1368 D.1364 8. 串使用（）存储结构在进行串连接操作的时候可能会产出截尾现象。 A. 串的堆分配 B. 串的定长 C. 串的块链 D.串的二叉链表 9. 深度为6的二叉树最多有（）个结点 A．64 Ｂ. 63 C.32 D.31 10. 设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有（）个结点。 A．n1-1 B. n1 C. n1+n2+n3 D. n2+n3+n4 11. 设有一棵22个结点的完全二叉树，那么整棵二叉树有（）个度为0的结点。 A. 6 B. 7 C. 8 D. 11 12. 在一个图中，所以顶点的度数之和等于所有边数的（）倍。 A. 1/2 B. 1 C. 2 D. 4 13.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。 A. 1 B. n/2 C. n-1 D. n 14. 长度为10的按关键字有序的查找表按顺序组织方式。若采用折半查找方法，则在等概率的情况下，查找失败的ＡＳＬ值是（）。 A．24／10B．24／11C．39／10D．39／11 15．在采用链地址法处理冲突所构成的开散列表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值（）。 A．一定都是同义词B．不一定都是同义词 C．都相同D．一定都不是同义词 16. 下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A．选择B．冒泡C．归并D．堆 17. 最好和最坏情况下时间复杂度均为O(nlog2n)且稳定的排序是（） A．快速排序B．堆排序C．归并排序D．希尔排序 18. 设广义表L=(( ),( ))，则L的表尾是（）。 A.（） B. （（）） C. （（（））） D.NULL 19. 具有6个顶点的无向图中至少应有（）条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 20. 设有一棵22个结点的完全二叉树，那么整棵二叉树有（）个度为0的结点。 A. 6 B. 7 C. 8 D. 11

中国地质大学2011数据结构试卷及其答案 (1)

数据结构标准答案

数据结构试题及答案10套

数据结构试题(附有答案)

数据结构c语言版试题大全含答案

数据结构试卷带答案

数据结构试题库答案

数据结构试题(含答案)

数据结构习题及答案-第11章 文件

数据结构试卷带答案

数据结构试题及答案

数据结构试题及答案

数据结构试题(含答案)

数据结构试题及答案

数据结构试卷B卷(含答案)

数据结构试题及答案

北航2011年硕士研究生入学考试数据结构与C语言试题与答案

软件学院2011级数据结构试题(A)

数据结构习题及答案-第11章文件