数构资料.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.abcde 4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。 A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1 5.栈和队列的共同点是____。 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. BCDEFEF 8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。 A. 2h B. 2h-1 C. 2h +1 D. h +1 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是____。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 11.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 12.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为____。 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.在对线性表的处理中一般使用两种存储结构，顺