学时数据结构期末试题答案

班 学号 山东工2014～2015班 学号 《数据结构》试题（B卷（考试时间：120：100 —二三四五六 一、选择题（120分1、从逻辑上可以把数据结构分为（ 2、线性表若采用链式结构时，要求内存中可用单元的地址(D (B)一定是不连续(C)部分地址必须是连续 (D)连续或不连续都可3、在一个单链表中，若在结点p之后s所指结点，则执行（A(A)s->next=p->next;p- (B)s->next=p;p-(C)s->next=p->next; (D)p->next=s;s-O(1) (A)单链 (B)单循环链(C)带尾指针的单循环链 (D)结点的双循环链5、栈和队列的共同特点是（ (A)都是先进后 (B)都是先进先(C)只允许在同一端点处和删除(D)以上都不6、设一维数组中有n个数组元素， 第i个数组元素的平均时间复杂度为（C

(A) (B) (C) (D)7、矩阵A[1..5,1..6]每个元素占5个单元，将其按行优先次序在起始地址为1000的连续A[5,5]的地址为（D(A) (B) (C) (D)8、0N01Nl2N2，则下列等式成立的是（C。(A) (B) (C) (D)一结点的左右孩子中，其左孩子的小于其右孩子的，可采用(C)遍历实现。(A)先 (B)中 (C)后 (D)从根开始层10、n（A(A)n(n- (B)n(n+ (C) (D)列是（C(A)拓扑有 (B)无序 (C)逆拓扑有 (D)以上都不12、n（C）(A) (B) (C)n- (D)13、下面关于图的的叙述中，哪一个是正确的（C14、下面关于哈希查找的说法正确的是（C15、设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD131（D）个记录。(A)1(B)2(C)3(D)16、某顺序的表格中有90000个元素，已按关键字值升序排列，假定对每个元素进行查找约为（D(A)15000(B)25000(C)35000(D)17、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。选择好的（C）(A)(B)处理(C)散列函数和处理(D)18、一个对象序列的关键字为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的对象为基准）而得到的第一次划分结果为（D(A) (B)(C) (D)19、O(nlog2n）的是（C(A)冒泡排 (B)直接选择排(C)堆排 (D)快速排20、对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序（A (A) (B)(C) (D)二、填空题（110分

10、在散列中，装填因子α的值越大，则存取元素时发生的可能性就越 α值越小，则存取元素发生的可能性就越 三、论述题（每题10分共70分1（510分解答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序或链表；栈和队列是两种特殊的线性表，即受限的线性表，只是对、删除运算加以限制。队列是只允许在一端进行、另一端进行删除运算，因而是先进先出表。1、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表

O（n）

2、对于一个长度为n的单链的线性表，在表头元素的时间复杂度为 元素的时间复杂度为 3、在单链表中,除了表头结点外,任意结点的位置由其 4、队列是具 先进先 5、对于一棵具有n个结点的二叉树，用二叉链表时，其指针总数 个，其中 6、n个顶点的有向完全图的弧 结 9、从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向右子树

对结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表2（510分StatusPush(SqStack&S,SElemTypee)if(S.top-S.base>=S.stacksize){//栈满，追 S.base=(SElemType*(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base) ;//分配失败 } //元素e栈顶，修改栈顶指return

3（510分5个元素，其入栈次序为：A，B，C，D，E最先出栈（CD第二个出栈）的次序有哪几个？ijv12313121132ijv12313121132233143-

1010 0000

0 0 0 0intPush(SqStack*S,ElemTypee);//入栈intPop(SqStack*S,ElemType*e);//voidconversion(){

} }答案（1）Push(S,N%8)

4（10分ABCABC 解：(1) AABGCHDIEJ 5（10分设一段文本中包含字符{a,b,c,d,e}，其出现频率相应为{3,2,5,1,1}。

6（10分v2v1,v3v2,v4v2,v6v4,v5v4,v7v5,v6)}，请分别给出根据该邻接表画出此图，并先后。深度优先搜索序列：v1,v2