下载文档原格式
数据结构试卷带答案数据结构试卷（一）一、选择题（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-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B 需要的操作为（.A ）。
(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈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) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。
(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（B）种不同的形态。
(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（B ）的空间复杂度最大。
(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。
6.一棵二叉树的第7层上最多含有的结点数为A.14B.64C.127D.128正确答案：B（2分）7.下列选项为完全二叉树的是正确答案：A（2分）8.用邻接表表示n个顶点e条边的无向图，其边表结点的总数是A. n×eB. eC. 2eD. n+e正确答案：C（2分）9.无向图中所有顶点的度数之和与所有边数之比是A.1/2B.1C.2D.4正确答案：C（2分）10.采用邻接矩阵存储图时，广度优先搜索遍历算法的时间复杂度为A. O（n）B. O（n+e）C. O（n2）D. O（n3）正确答案：C（2分）11.对序列（15，9，7，8，20，-1，4）进行排序，若一趟排序后的结果为（-1，15，9，7，8，20，4），则采用的排序方法是A.归并排序B.快速排序C.直接选择排序D.冒泡排序正确答案：D（2分）12.比较次数与待排序列初始状态无关的排序方法是A.快速排序B.冒泡排序C.直接插入排序D.直接选择排序正确答案：D（2分）13.查找较快，且插入和删除操作也比较方便的查找方法是A.分块查找B.二分查找C.顺序查找D.折半查找正确答案：A（2分）14.下列关于m阶B树的叙述中，错误．．的是A.根结点至多有m棵子树B.所有叶子都在同一层次上C.每个非根内部结点至少有棵子树D.结点内部的关键字可以是无序的正确答案：D（2分）15.在散列查找中处理冲突时，可以采用开放定址法。
下列不是开放定址法的是A.线性探查法B.二次探查法C.双重散列法D.拉链法正确答案：D（2分）非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
二、填空题（本大题共10小题，每小题2分，共20分）16.数据结构研究的内容包括数据的逻辑结构、________和数据的运算。
正确答案：存储结构（2分）17.头指针为L的带头结点的双循环链表，结点的前趋指针域为prior，后继指针域为next，判断该链表为空的条件是________。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流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. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。
2. 二叉树的节点最多有______个子节点。
3. 堆是一种特殊的______。
4. 散列表的查找效率取决于______。
5. 图的遍历算法包括______和______。
6. 快速排序算法的平均时间复杂度为______。
7. 哈希表中的冲突解决方法有______和______。
8. 最小树算法包括______和______。
9. 最短路径算法包括______和______。
10. 并查集算法用于解决______问题。
第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。
2. 请简述二叉搜索树的特点。
3. 请简述哈希表的原理。
4. 请简述图的深度优先搜索算法。
5. 请简述最小树算法的原理。
第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。
试卷代号:1252中央广播电视大学2013-2014学年度第一学期“开放学科”期末考试数据结构（本）试题2014年1月一、单项选择题（每小题2分，共30分）1. 在数据结构和算法中，与所使用的计算机有关的是（B）。
A．数据元数间的抽象关系 B．数据的存储结构C．算法的时间复杂度 D．数据的逻辑结构2.对顺序表,以下叙述中正确的是 ( A )。
A．用一组地址连续的存储单元依次存放线性表的数据元素B．各个数据元素的首地址是连续的C．数据元素不能随机访问D．插入操作不需要移动元素3．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为（C）。
A．9 B．10 C．15 D．164. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( A)。
A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p ;5．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（A）。
（进栈出栈可以交替进行）。
A．7，5，3，1 B．7，3，1,5C．7，5，1，3 D．5,1，3，76．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（C）。
A．p=top->next; top=top next; B．p->next=top;C．p->next=top;top=p; D．top=p;7．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（D）。
(矩阵中的第1个元素是a1,1）A．a7,6 B．a10,8C．a9,2 D．a8,58．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,6在一维数组B中的下标是（C）。
2014年武汉科技⼤学考研试题_856数据结构（C语⾔版）（A卷）和标准答案⼆O ⼀四年招收硕⼠研究⽣⼊学考试试题考试科⽬代码及科⽬名称： 856 数据结构(C 语⾔版)答题内容写在答题纸上，写在试卷或草稿纸上⼀律⽆效考完后试题随答题纸交回。
考试时间3⼩时，总分值 150 分。
姓名：报考专业：准考证号码：密封线内不要写题⼀、选择题（10⼩题，每题2分，共20分）1. 算法分析的主要内容是（）。
A ）正确性B ）可读性和稳定性C ）简单性D ）空间复杂性和时间复杂性 2. 线性表若采⽤链式存储结构时，要求内存中可⽤存储单元的地址（）。
A ）必须是连续的B ）部分地址必须是连续的C ）⼀定是不连续的D ）连续或不连续都可以3. 设有6个元素按1、2、3、4、5、6的顺序进栈，下列不合法的出栈序列是（）。
A ）234165B ）324651C ）431256D ）5463214. 设有⼆维数组A[1..12,1..10]，其每个元素占4个字节，数据按⾏优先顺序存储，第⼀个元素的存储地址为100，那么元素A[5,5]的存储地址为（）。
A ）76 B ）176 C ）276 D ）3765. 已知⼀棵⼆叉树的先序序列为ABDGCFK ，中序序列为DGBAFCK ，则后序序列为（）。
A ）ACFKDBGB ）GDBFKCAC ）KCFAGDBD ）ABCDFKG6. 在⼆叉树结点的先序，中序和后序序列中，所有叶⼦结点的先后顺序（）。
A ）都不相同B ）完全相同C ）先序和中序相同，⽽与后序不同D ）中序和后序相同，⽽与先序不同 7. 图的深度优先遍历类似于⼆叉树的（）。
A ）先序遍历B ）中序遍历C ）后序遍历D ）层次遍历 8. 下⾯（）算法适合构造⼀个稠密图G 的最⼩⽣成树。
A ） Prim 算法B ）Kruskal 算法C ）Floyd 算法D ）Dijkstra 算法 9. 对关键码{46,79,56,38,40,84}采⽤堆排序,则初始化堆(⼩堆)后最后⼀个元素是（）。
《数据结构》试卷（C卷）一、单项选择题1. 空串与空格字符组成的串的区别在于（B ）。
A.没有区别B.两串的长度不相等C.两串的长度相等D.两串包含的字符不相同2. 一个子串在包含它的主串中的位置是指（ D ）。
A.子串的最后那个字符在主串中的位置B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置D.子串的第一个字符在主串中首次出现的位置3. 下面的说法中，只有（ C ）是正确的。
A.字符串的长度是指串中包含的字母的个数B.字符串的长度是指串中包含的不同字符的个数C.若T包含在S中，则T一定是S的一个子串D.一个字符串不能说是其自身的一个子串4. 两个字符串相等的条件是（ D ）。
A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ B ）。
A. “ijing”B. “jing＆”C. “ingNa”D. “ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ C ）。
A.2B.3C.4D.57. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ D ）。
A. “Nanjing＆Shanghai”B. “Nanjing＆Nanjing”C. “ShanghaiNanjing”D. “Shanghai＆Nanjing”8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ C ）。
A.i＞0B. i≤nC.1≤i≤nD.1≤i≤n+19. 字符串采用结点大小为1的链表作为其存储结构，是指（D ）。
A.链表的长度为1B.链表中只存放1个字符C.链表的每个链结点的数据域中不仅只存放了一个字符D.链表的每个链结点的数据域中只存放了一个字符10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（C ）个。
A. 4B. 5C. 6D. 711. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ B ）个。
A. 15B. 16C. 17D. 4712. 假定一棵三叉树的结点数为50，则它的最小高度为（ C ）。
A. 3B. 4C. 5D. 613. 在一棵二叉树上第4层的结点数最多为（ D ）。
A. 2B. 4C. 6D. 814. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（B ）。
A. R[2i+1]B. R[2i]C. R[i/2]D. R[2i-1]15. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）。
A. 24B. 48C. 72D. 5316. 线索二叉树是一种（ C ）结构。
A. 逻辑B. 逻辑和存储C. 物理D. 线性17. 线索二叉树中，结点p没有左子树的充要条件是（ B ）。
A. p->lc=NULLB. p->ltag=1C. p->ltag=1 且p->lc=NULLD. 以上都不对18. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ B ）。
A. n在m右方B. n在m 左方C. n是m的祖先D. n是m的子孙19. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ B ）。
A. 中序B. 前序C. 后序D. 层次序20. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（ A ）存储结构。
A. 三叉链表B. 广义表C. 二叉链表D. 顺序21. 下面叙述正确的是（ D ）。
A. 二叉树是特殊的树B. 二叉树等价于度为2的树C. 完全二叉树必为满二叉树D. 二叉树的左右子树有次序之分22. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ A ）。
A. 不发生改变B. 发生改变C. 不能确定D. 以上都不对二、填空题1. 计算机软件系统中，有两种处理字符串长度的方法：一种是__固定长度__，第二种是___设置长度指针___。
2. 两个字符串相等的充要条件是___两个串的长度相等___和_____对应位置的字符相等__。
3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为__“BCDEDE”__。
4. 串是指___含n个字符的有限序列（n≥0）___。
5. 空串是指__不含任何字符的串__，空格串是指__仅含空格字符的字符串___。
6. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为__3___，树的深度为__4___，终端结点的个数为___6___，单分支结点的个数为__1____，双分支结点的个数为__1____，三分支结点的个数为__2_____，C结点的双亲结点为__A__，其孩子结点为_F____和___G_结点。
7. 设F 是一个森林，B 是由F 转换得到的二叉树，F 中有n 个非终端结点，则B 中右指针域为空的结点有__n+1_____个。
8. 对于一个有n 个结点的二叉树，当它为一棵__完全__二叉树时具有最小高度，即为_2log (1)n +⎡⎤⎢⎥___，当它为一棵单支树具有_最大____高度，即为____n___。
9. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_55__。
10. 在一棵二叉排序树上按__中序_____遍历得到的结点序列是一个有序序列。
11. 对于一棵具有n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为__2n_____个，其中__n-1_____个用于链接孩子结点，__n+1_____个空闲着。
12. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=__ n 2+1____。
13. 一棵深度为k 的满二叉树的结点总数为__2k -1_____，一棵深度为k 的完全二叉树的结点总数的最小值为__2k-1___，最大值为__2k -1____。
14. 由三个结点构成的二叉树，共有__5__种不同的形态。
15. 设高度为h 的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_2h -1___。
16. 一棵含有n 个结点的k 叉树，_单支树_____形态达到最大深度，_完全二叉树___形态达到最小深度。
三、算法设计题1. 设有一个长度为s 的字符串，其字符顺序存放在一个一维数组的第1至第s 个单元中（每个单元存放一个字符）。
现要求从此串的第m 个字符以后删除长度为t 的子串，m<s ，t<(s-m)，并将删除后的结果复制在该数组的第s 单元以后的单元中，试设计此删除算法。
1．算法描述为：int delete(r,s,t,m) //从串的第m 个字符以后删除长度为t 的子串char r[ ];int s,t,m;{ int i,j;for(i=1;i<=m;i++)r[s+i]=r[i];for(j=m+t-i;j<=s;j++)r[s-t+j]=r[j];return (1);} //delete2. 设s 和t 是表示成单链表的两个串，试编写一个找出s 中第1个不在t 中出现的字符（假定每个结点只存放1个字符）的算法。
2．算法思想为：（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较；（3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。
设单链表类型为LinkList；注意，此时类型LinkList中的data成分为字符类型。
LinkString find(s,t)LinkString *s, *t;{ LinkString *ps, *pt;ps=s;while(ps!=NULL){ pt=t;while((pt!=NULL)&&(ps->data!=pt->data))pt=pt->next;if(pt= =NULL)ps=NULL;else{ ps=ps->next;s=ps;}}return s;} //find。
