数据结构与算法考试试卷.doc

江西财经大学 第 学期期末考试试卷 试卷代码：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 B.decba C.dceab D.abcde4.一个队列的入队序列是1、2、3、4，则队列输出序列是_。 A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.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 = 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. BCPQRST D. BCDEFEF8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_。A. 2h B. 2h-1 C. 2h +1 D. h +19.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是_。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca10.具有6个顶点的无向图至少应有_条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 811.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为。A. n B. n/2 C. (n+1)/2 D. (n-1)/212.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为_。A. 希尔排序 B. 归并排序 C. 插入排序 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.简述什么是稳定的排序，什么是不稳定的排序。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.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的( )。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=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分）4.设待排序的排序码序列为12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 试写出使用希尔排序(增量为5,2,1)方法每趟排序后的结果。（6分） 六、算法设计题（本题共18分，第1小题10分，第2小题8分）1.编写一个算法frequency，统计在一个输入字符串中所含各个不同字符出现的频度。用适当的测试数据来验证这个算法。(10分)2.在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，并统计树中具有度为1的结点数目的算法。要求给出二叉链表的类型定义。(8分)江西财经大学 第 学期期末考试试卷 试卷代码：03266B 授课课时：112课程名称：数据结构与算法 适用对象：本科 一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)1.数据结构被形式地定义为 (K, R)，其中K是_的有限集，R是K上的关系有限集。 A.算法 B.数据元素 C.数据操作 D.逻辑结构2.在数据结构中，从逻辑上可以把数据结构分成_。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构3.以下的叙述中，正确的是_。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出4.若一个栈的入栈序列是1、2、3、 、n，其输出序列为p1、p2、p3、 、pn，若p1=n，则pi为_。 A. i B. n = i C. n - i +1 D.不确定5.判断一个循环队列QU (最多元素为m) 为空的条件是_。A. QU-front = QU-rear B. QU-front != QU-rear C. QU-front = (QU-rear+1)%m D. QU-front != (QU-rear+1)%m6.在某单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s-next = p; p-next=s; B. s-next = p-next; 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. acbed B. decab C. deabc D. cedba9.对于一个满二叉树，m个树叶，n个结点，深度为h，则_。A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -110.一个有n个顶点的无向图最多有_条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n11.顺序查找法适合于存储结构为_的线性表。A. 散列存储 B. 顺序存储或链接存储C. 压缩存储 D. 索引存储12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是_。A. 插入排序 B.选择排序 C.快速排序 D. 归并排序二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)1.在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点。2.在无权图G的邻接矩阵中，若Aij等于1，则等于Aji = 。3.根据二叉树的定义，具有三个结点的二叉树有 种不同的形态。4.空格串是指 ，其长度等于 。5.在散列存储中，装填因子的值越大，则存储元素时发生冲突的可能性就 。6.已知模式串t= abacabaaad， 其用KMP法求得的每个字符对应的next函数值为 。三、简答题(本大题共3小题，每小题5分，共15分)1.比较静态查找与动态查找的主要区别，它们的基本运算有哪些不同？2.逻辑结构分哪几种，存储结构有哪几种？3.在具有n(n1)个结点的各棵不同形态树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)1.每种数据结构都应具备三种基本运算：插入、删除、搜索( )。2.满二叉树不一定是完全二叉树。( )3.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( )4.任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。( )5.线性链表中所有结点的类型必须相同。( )6.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关( )。7.在散列法中解决冲突时，其装载因子的取值一定在(0，1)之间。( )8.任何一个关键活动延迟，那么整个工程将会延迟。( )9.平衡二叉树的左右子树深度之差的绝对值不超过1。( )10.n个结点的有向图，若它有n(n1)条边，则它一定是强连通的。( )五、分析应用题（本题共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分）132547685153101227963.设散列表为HT13, 散列函数为 H (key) = key %13。用双散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个地址的公式为 Hi = (Hi-1 + RH (key) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）4.设待排序的排序码序列为12, 2, 16, 30, 28, 10, 16*, 20, 6, 18,写出使用快速排序法每趟排序后的结果。（6分）六、算法设计题（本题共18分，第1小题10分，第2小题8分）1.试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。(10分)2.设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。要求给出二叉链表的类型定义。(8分)江西财经大学 第 学期期末考试试卷 试卷代码：03266C 授课课时：112课程名称：数据结构与算法 适用对象：本科 一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)1.算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是_。 A.空间复杂度和时间复杂度 B.正确性和简单性 C.可读性和文档性 D.数据复杂性和程序复杂性2.向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_。 A.110 B.108 C.100 D.1203.栈结构通常采用的两种存储结构是_。 A.线性存储结构和链表存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构4.一个队列的入队序列是1、2、3、4，则队列输出序列是_。 A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、15.判断一个循环队列QU (最多元素为m) 为满队列的条件是_。A. QU-front = QU-rear B. QU-front != QU-rear C. QU-front = (QU-rear+1)%m D. QU-front != (QU-rear+1)%m6.在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p-next = 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. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca9.深度为5的二叉树至多有_个结点。A. 16 B. 32 C. 31 D. 1010.具有4个顶点的无向完全图有_条边。A. 6 B. 12 C. 16 D. 2011.对线性表进行二分查找时，要求线性表必须_。A. 以顺序方式存储 B. 以顺序方式存储，且结点按关键字有序排列C. 以链接方式存储 D. 以链接方式存储，且结点按关键字有序排列12.排序方法中，从未排序序列中依次取出元素与已排序序列(注：初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)1.在图形结构中，每个结点的前驱结点个数和后续结点个数可以 。2.两个串相等的充分必要条件是 。3.在双链表中，每个结点有两个指针域，一个指向 ，另一个指向 。4.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0 = 。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。6.已知模式串t =abcabaa, 其用KMP法求得的每个字符对应的next函数值为 。三、简答题(本大题共3小题，每小题5分，共15分)1.简述栈的特点以及栈与一般线性表的区别。2.简述什么是内部排序，什么是外部排序。3.什么是满二叉树？什么是完全二叉树？满二叉树和完全二叉树有何关系？四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)1.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的( )。2.线性表的逻辑顺序与物理顺序总是一致的( )。3.深度为h的非空二叉树的第h层最多有2h-1个结点( )4.线性表的顺序存储结构特点是逻辑关系上相邻的两个元素在物理位置上也相邻。( )5.最优二叉搜索树一定是平衡的二叉搜索树。( )6.任何无环的有向图，其结点都可以排在一个拓扑序