18春北大 03081015-数据结构*作业资料

admin

03081015-数据结构*
分数：100  题数：25
总体情况
姓名        开始时间        结束时间        用时(分钟)        得分        得分率        是否通过        考试状态               
陈国伟        2018-04-10 17:25:19        2018-04-29 11:11:10        10.02        ***        ***        ***        考试中               
一、单选题(共15题，每题2分，共30分)
1.        以下哪个算法的时间复杂度表示是最慢的？（数据量很大时）_______（视频02）
         A.
O(1)
B.
O(log2n)
C.
O(n)

D.
O(n2)


       
        试题编号：01.03
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
2.        以下哪个序列是时间复杂度由大到小排列的？_______（视频02）


         A. (1)(2)(3)(4)(5)

B. (2)(1)(3)(4)(5)

C. (5)(4)(2)(1)(3)

D. (5)(3)(4)(2)(1)


       
        试题编号：01.05
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
3.        在什么情况下使用链表要比顺序表更优？（视频03、04）
         A. 保存大量不可更改的数据

B. 要求数据的存储空间越小越好

C.  频繁的插入、删除操作

D. 频繁的查找操作


       
        试题编号：02.11
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
4.        不带头结点的单链表head为空的判定条件是？（视频04）
         A. head->next == NULL

B. head->next == head

C. head == NULL

D. head!=NULL


       
        试题编号：02.14
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
5.        栈的插入和删除操作都在哪里进行？（视频06）
         A. 任意位置

B. 栈底

C. 栈顶

D. 随机位置


       
        试题编号：03.21
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
6.        依次读入数据元素序列{a，b，c，d，e，f，g} 进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列不可能是以下哪个序列？（视频07）
         A. {c，d，b，e，f，a，g}

B. {e，f，d，g，b，c，a}

C. {a，c，e，f，g，d，b}

D. {a，b，c，d，e，f，g}


       
        试题编号：03.24
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
7.        栈和队列都是______。（视频08）
         A. 限制存取位置的线性结构

B. 顺序存储的线性结构

C. 链式存储的线性结构

D. 限制存取位置的非线性结构


       
        试题编号：03.25
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
8.        下面的树中，G结点的度数是（视频09）


         A. 0

B. 1

C. 2

D. 3


       
        试题编号：06.31
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
9.         (a,b),(a,c),(a,d), __(c,d)

       
       
        试题编号：07.44
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
10.        设有100个有序元素，用二分查找法进行查找时，最大比较次数是：（视频16、17）
         A. 7

B. 10

C. 25

D. 50


       
        试题编号：09.51
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
11.        折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败（视频16）
         A. 20，70，30，50

B. 30，88，70，50

C. 20，50

D. 30，88，50


       
        试题编号：09.53
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
12.        在各种查找方法中，平均查找长度与结点个数n无关的查找方法是（ ）（视频16，17，18）
         A. 散列查找

B. 顺序查找

C. 二分查找

D. 没有这样的查找方法使得平均查找长度和n无关


       
        试题编号：09.55
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
13.        已知一组元素为{25, 48, 36, 72, 79, 82, 23, 40, 16, 35}，其中每相邻两个为有序子序列，对这些子序列进行一趟两两归并的结果是：（视频22）
         A. {25, 36, 48, 72, 23, 40, 79, 82, 16, 35}

B. {25, 36, 48, 72, 16, 23, 40, 79, 82, 35}

C. {25, 36, 48, 72, 16, 23, 35, 40, 79, 82}

D. {16, 23, 25, 35, 36, 40, 48, 72, 79, 82}


       
        试题编号：10.59
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
14.        直接插入排序、快速排序、冒泡排序、归并排序、Shell排序，当元素数量很大时，时间复杂度最小的是（视频20、21）
         A. 直接插入排序

B. 快速排序

C. 冒泡排序

D. 直接选择排序


       
        试题编号：10.60
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
15.        在冒泡排序、快速排序、堆排序、归并排序中，_________排序是稳定的。（视频20）
         A. 冒泡、快速

B. 快速、归并

C. 堆、归并

D. 冒泡、归并


       
        试题编号：10.61
        试题类型：单选题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
二、谋学网（www.mouxue.com）(共5题，每题4分，共20分)
16.        算法5要素包括：动态有穷性、 、 、 和可行性。（视频02）
       
       
        试题编号：01.06
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
17.        一个算法的平均时间复杂度为(n+10)log2(n+1)-20n用数量级表示是 。（视频02）大O标识发，如logn，底数默认为2

       
       
        试题编号：01.08
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
18.        一个直接调用自己或通过一系列调用语句间接地调用自己的函数，称做 （视频07）
       
       
        试题编号：03.26
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
19.        请写出下面这棵二叉树的后序遍历 （视频11）（无逗号，结果如ABCDEF）


       
       
        试题编号：06.34
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
20.        无向图G=(V, E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}，对该图进行深度优先遍历（优先访问编号小的结点），得到的顶点序列为 ？(结果无逗号分隔符，如abcdef)

       
       
        试题编号：07.45
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
三、问答题(共5题，每题10分，共50分)
21.        请指出下面算法实现的功能和时间复杂度（用大O表示）。仅对时间复杂度来讲，有没有可以提高算法效率的方法？请给出代码并写出时间复杂度。（视频02）  


int isPrime(int n){
  int i=1;
  while (++i <= n) {
    if (n%i==0){
      break;
    }
  }
  if(i>n){
    return 1;
  }else{
    return 0;
  }
}

         

       
        试题编号：01.10
        试题类型：问答题
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
22.        利用顺序栈的基本运算（push(stack, element), pop(stack)），试设计一个算法，判断一个输入字符串是否具有中心对称（也就是所谓的“回文”，正读和反读均相同的字符序列），例如acbababca，abcddcba都是中心对称的字符串。（视频07）
         

       
        试题编号：03.30
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
23.        实现二叉树的先序、中序、后序遍历函数（视频11）
         

       
        试题编号：06.40
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
24.        假定一个待散列存储的数据集合为{32,75,29,63,48,94,25,46,18,70}，散列地址空间为H[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。（视频18、19）
         

       
        试题编号：09.57
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***
25.        实现快速排序算法（视频22,书10.3）
         

       
        试题编号：10.63
        试题类型：谋学网（www.mouxue.com）
        标准资料：***
        试题难度：一般
        试题解析：***
        考生资料：
        考生得分：***
        是否评分：未评分
        评价描述：***