数据结构与算法考试试卷

《数据结构与算法考试试卷》由会员分享，可在线阅读，更多相关《数据结构与算法考试试卷（10页珍藏版）》请在装配图网上搜索。

1、江西财经大学第 学期期末考试试卷试卷代码：03266A授课课时：112课程名称： 数据结构与算法适用对象：本科一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸 相应位置处。答案错选或未选者，该题不得分。每小题 2分，共 24 分。)1数据结构被形式地定义为(K,R),其中K是数据元素的有限集，R是K上的_有限集。A. 操作B. 映像 C. 存储 D. 关系2线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。A.必须连续的B.部分地址必须连续的C一定是不续的D.连续不连续都可以3. 个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是。A.edcba

2、B.decbaC.dceab D.abcde4. 一个队列的入队序列是1、 2、 3、 4，则队列输出序列是。A.4、 3、 2、 1B.1、 2、 3、 4C.1、 4、 3、 2D.3、 2、 4、 15. 栈和队列的共同点是。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入、删除元素D. 没有共同点6在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s 结点，则执行。A. s-next = p-next; p-next=s;B. p-next = s-next; s-next = p;C. q-next = s; s-next = p;D. p-next

3、 = s; s-next = q;7. 设串s1= ABCDEFG，s2= PQRST，函数con (x, y)返回x与y串的连接串，函数subs (s, i, j)返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串 s 的长度，则 con (subs (s1, 2, len (s2), subs (s1, len (s2), 2) 的结果串是。A. BCDEF B. BCDEFG C. BCPQRSTD. BCDEFEF8. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为。A. 2hB. 2h-1C. 2h +1D. h

4、 +19. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是。A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca10. 具有6个顶点的无向图至少应有条边才能确保是一个连通图。A. 5B. 6C. 7D. 811. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为-。A. n B. n/2 C. (n+1)/2 D. (n-1)/212. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为 空)的一端的方法，称为。A. 希尔排序 B. 归并排序 C.

5、插入排序 D. 选择排序二、填空题(请在每小题的横线上填入正确内容，每空 1 分，共 7 分。) 1在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点。2. 对n个元素的序列进行起泡排序时，最少的比较次数是。3空串是，其长度等于0。4. 一棵有n个结点的满二叉树共有个叶子结点。5在散列函数H(key)二key % p中，p应取。6. 已知模式串t二abcaabbabc其用KMP法求得的每个字符对应的next函数值 为。三、简答题(本大题共3小题，每小题5分，共15分)1. 在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述 在什么情况下使用顺序表比链表好？2

6、. 简述什么是稳定的排序，什么是不稳定的排序。3. 下列中缀表达式对应的后缀形式是什么？(1) (A + B) * D + E / (F + A * D) + C(2) A & B| ! (E F) 注：按 C 的优先级 )四、判断题(本大题共10小题，命题正确的在题后括号内写“T”，错误的在题后括号内 写“F”，每小题1分，共10分)1. 数据元素不是数据的最小单位( )。2. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。 ( )3. AOE 网是一种带权的无环连通图。 ( )4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索 树都是相同的( )

7、。5. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。 ( )6. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 ( )7. 折半插入排序是稳定的。 ( )8. 在散列法中，使用双散列函数可保证绝对不产生冲突。 ( )9. 消除递归不一定需要使用栈( )10. 堆排序是交换排序的一种。 ( )五、分析应用题(本题共 26 分， 1、4 小题各6 分， 2、3 小题各7 分) 1阅读后分析下面程序段的功能是什么? (6分)SeqStack S1, S2, tmp;DataType x;/设栈tmp和S2已做过初始化while ( ! StackEmpty (S1) x

8、=Pop(S1) ; Push(tmp,x);while ( ! StackEmpty (tmp) ) x=Pop（tmp）;Push（ S2, x）;2. 某子系统在通信联络中只可能出现 8种字符，其出现的概率分别为 0.05，0.29，0.07， 0.08，0.14，0.23，0.03，0.11 试设计赫夫曼编码。（7 分）3设散列表为HT13,散列函数为H （key） = key %13。用线性探测再散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。画出相应的散 列表, 并计算等概率下搜索成功的平均搜索长度。 （7分）

9、4设待排序的排序码序列为12, 2, 16, 30, 2& 10, 16*, 20, 6, 18,试写出使用希 尔排序（增量为5,2,1）方法每趟排序后的结果。（6分）六、算法设计题（本题共 18 分，第 1 小题 10分，第 2小题 8 分）1编写一个算法frequency，统计在一个输入字符串中所含各个不同字符出现的频度。 用适当的测试数据来验证这个算法。 （10分）2在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，并统计树中具有度为1的结点数目的算法。要求给出二叉链表的类型定义。 （8分）江西财经大学授课课时： 112 适用对象：本科第 学期期末考试试卷试卷代码：03

10、266B课程名称： 数据结构与算法一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题 2分，共 24 分。)1数据结构被形式地定义为(K, R),其中K是_的有限集，R是K上的关系有限集。A. 算法B. 数据元素 C. 数据操作 D. 逻辑结构2在数据结构中，从逻辑上可以把数据结构分成_。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构3. 以下的叙述中，正确的是。A. 线性表的存储结构优于链式存储结构B. 二维数组是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D.

11、 队列的操作方式是先进后出4若一个栈的入栈序列是1、2、3、n其输出序列为pl、p2、p3、pn，若p1=n，贝U pi 为。A. iB. n = iC. n - i +1D.不确定5判断一个循环队列QU (最多元素为m)为空的条件是_。A. QU-front = QU-rearB. QU-front != QU-rearC. QU-front = (QU-rear+1)%mD. QU-front != (QU-rear+1)%m6. 在某单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s-next = p; p-next=s;B. s-next = p-next

12、; p-next = s;C. s-next = p-next; p = s;D. p-next = s; s-next = p;7. 串是一种特殊的线性表，其特殊性体现在。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符8. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,前序遍历序列是。A. acbedB. decabC. deabcD. cedba9对于一个满二叉树，m个树叶，n个结点，深度为h，则。A. n = h + mB. h + m = 2nC. m = h-1D. n = 2h -110. 一个有n个顶点的无向图最多有条边。A.

13、 nB. n(n-1)C. n(n-1)/2D. 2n11. 顺序查找法适合于存储结构为的线性表。A. 散列存储B. 顺序存储或链接存储C. 压缩存储 D. 索引存储12. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是。A.插入排序B.选择排序 C.快速排序 D.归并排序二、填空题(请在每小题的横线上填入正确内容，每空 1 分，共 7 分。)1. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点。2在无权图G的邻接矩阵中，若Aij等于1，则等于Aji =_。3. 根据二叉树的定义，具有三个结点的二叉树有种不同的形态。4. 空格串是扌旨，其长度等于。5在散列存储中，

14、装填因子a的值越大，则存储元素时发生冲突的可能性就。6.已知模式串t二abacabaaad,其用KMP法求得的每个字符对应的next函数值 为。三、简答题(本大题共3小题，每小题5分，共15分)1. 比较静态查找与动态查找的主要区别，它们的基本运算有哪些不同？2. 逻辑结构分哪几种，存储结构有哪几种？3在具有n(n 1)个结点的各棵不同形态树中，其中深度最小的那棵树的深度是多少？它 共有多少叶子和非叶子结点？四、判断题(本大题共10小题，命题正确的在题后括号内写“T”，错误的在题后括号内 写“F”，每小题1分，共10分)1. 每种数据结构都应具备三种基本运算：插入、删除、搜索( )。2. 满二

15、叉树不一定是完全二叉树。 ( )3. 带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。 ( )4. 任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均 搜索时间。 ( )5. 线性链表中所有结点的类型必须相同。 ( )6. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与 图中顶点个数有关，而与图的边数无关( )。7. 在散列法中解决冲突时，其装载因子的取值一定在(0， 1)之间。 ( )8. 任何一个关键活动延迟，那么整个工程将会延迟。 ( )9. 平衡二叉树的左右子树深度之差的绝对值不超过 1。 ( )10. n个结点的有

16、向图，若它有n(n 1)条边，则它一定是强连通的。()五、分析应用题(本题共 26 分， 1、4 小题各6 分， 2、3 小题各7 分)1. 下述算法的功能是什么? (6 分)LinkList Demo(LinkList L) / L 是无头结点单链表ListNode *Q,*P;if(L&L-next)Q=L;L=L-next;P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL; return L;2. 将给定的图简化为最小的生成树，要求从顶点 1出发。(7分)3. 设散列表为 HT13, 散列函数为 H (key) = key %13。用双散

17、列法解决冲突, 对下列 关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个地址的公式为 H = (H + RH (key) % 13, H = Hi i-1 1(key)。画出相应的散列表，并计算等概率下搜索成功的平均搜索长度。(7分)4. 设待排序的排序码序列为12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 写出使用快速 排序法每趟排序后的结果。 (6分)六、算法设计题(本题共 18 分，第 1 小题 10分，第 2小题 8 分)1.

18、试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink, 存放字符数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在 链表上进行一次Locate(L, x)操作时，令元素值为x的结点的访问频度freq加1， 并将该结点前移,链接到与它的访问频度相等的结点后面,使得链表中所有结点保持 按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 (10分)2. 设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子 树相互交换。要求给出二叉链

19、表的类型定义。 (8分)江西财经大学授课课时： 112 适用对象：本科第 学期期末考试试卷试卷代码：03266C课程名称： 数据结构与算法一、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸 相应位置处。答案错选或未选者，该题不得分。每小题 2分，共 24 分。）1. 算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是。A. 空间复杂度和时间复杂度B. 正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性2. 向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是。A.110B.108C.100D.1203. 栈结构通常

20、采用的两种存储结构是。A. 线性存储结构和链表存储结构B.散列方式和索引方式C. 链表存储结构和数组D.线性存储结构和非线性存储结构4. 一个队列的入队序列是 1、2、3、4，则队列输出序列是。A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、15. 判断一个循环队列 QU （最多元素为 m） 为满队列的条件是。A. QU-front = QU-rearB. QU-front != QU-rearC. QU-front = （QU-rear+1）%mD. QU-front != （QU-rear+1）%m6在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p-ne

21、xt = p-next-next;B. p = p-next; p-next=p-next-next;C. p-next 二 p-next;D. p 二p-next -next;7. 设两个字符串p和q,求q在p中首次出现的位置的运算称作_。A. 连接 B. 模式匹配 C. 求子串 D. 求串长8. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf,则其后序遍历结点访问顺序是。A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca9. 深度为 5 的二叉树至多有个结点。A. 16B. 32C. 31D. 1010. 具有

22、 4 个顶点的无向完全图有条边。A. 6B. 12C. 16D. 2011. 对线性表进行二分查找时，要求线性表必须。A. 以顺序方式存储B. 以顺序方式存储，且结点按关键字有序排列C. 以链接方式存储D. 以链接方式存储，且结点按关键字有序排列12. 排序方法中，从未排序序列中依次取出元素与已排序序列（注：初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序二、填空题(请在每小题的横线上填入正确内容，每空 1 分，共 7 分。)1. 在图形结构中，每个结点的前驱结点个数和后续结点个数可以。2. 两个串相等的充

23、分必要条件是。3在双链表中，每个结点有两个指针域，一个指向，另一个指向。4在一棵二叉树中，度为零的结点的个数为nO,度为2的结点的个数为n2,则有n0 二 。5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。6. 已知模式串t二abcabaa,其用KMP法求得的每个字符对应的next函数值为。三、简答题(本大题共3小题，每小题5分，共15分)1. 简述栈的特点以及栈与一般线性表的区别。2. 简述什么是内部排序，什么是外部排序。3. 什么是满二叉树？什么是完全二叉树？满二叉树和完全二叉树有何关系？四、判断题(本大题共10小题，命题正确的在题后括号内写“T”，错误的在题后括号内 写

24、“F”，每小题1分，共10分)1. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的( )。2. 线性表的逻辑顺序与物理顺序总是一致的( )。3. 深度为h的非空二叉树的第h层最多有2h-1个结点()4. 线性表的顺序存储结构特点是逻辑关系上相邻的两个元素在物理位置上也相邻。 ( )5. 最优二叉搜索树一定是平衡的二叉搜索树。 ( )6. 任何无环的有向图，其结点都可以排在一个拓扑序列里。 ( )7. 关键活动不按期完成就会影响整个工程的完成时间。 ( )8. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是 该子树的前序遍历结果序列的最后一个结点。

25、 ( )9. 快速排序是对起泡排序的一种改进。 ( )10. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。()五、分析应用题(本题共 26 分， 1、4 小题各6 分， 2、3 小题各7 分)1设有对堆栈Stack操作的算法：StackEmpty (判断栈空)、Push (压栈)、Pop (出栈), 请仔细阅读下面算法，指出其功能。( 6 分)SF2(Stack) int j, n=0, a100;while(!StackEmpty(Stack)n+;Pop(Stack, an);for(j=1;j=n;j+)Push(Stack,aj);2. 将下面的森林变换成二叉树

26、(7 分)。3. 设记录的关键字集合K=52,41,95,21,14,2& 82,29，请“除留余数法”设计一合适 的哈希函数，在012的散列地址空间填入各关键字，解决冲突的方法为“二次探测再 散列”，画出散列表，并计算等概率情况下的ASL。（7分）4. 设待排序的排序码序列为12, 2, 16, 30, 28, 10, 16*, 20, 6, 18,画出用堆排序 排序方法得到的初始堆及前两次输出堆顶元素后，每次堆的调整变化结果。（6分）六、算法设计题（本题共 18 分，第 1 小题 10分，第 2小题 8 分）1设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所 有结点的链接方向逆转示。要求逆转结果链表的表头指针h指向原链表的最后一个结 点。 （10 分）2. 设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。要求给出二叉链 表的类型定义。 （8分）