首页 > 代码库 > 中国大学MOOC-陈越、何钦铭-数据结构-2016秋期中考试(附答案)

中国大学MOOC-陈越、何钦铭-数据结构-2016秋期中考试(附答案)

判断题:

1-1  

算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 (2分)

1-2  
N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找,那么查找的平均时间复杂度是O(logN)。 (3分)
 
1-3  
通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为:123。 (3分)
 
1-4  
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (2分)
 
1-5  
在一棵二叉搜索树上查找63,序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。 (3分)
 
1-6  
将1、2、3、4、5、6顺序插入初始为空的AVL树中,当完成这6个元素的插入后,该AVL树的先序遍历结果是:4、2、1、3、5、6。 (3分)
 
1-7  
一棵有124个结点的完全二叉树,其叶结点个数是确定的。 (3分)
 
1-8  
用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。 (3分)
 
1-9  
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G中一定有回路。 (3分)
 
1-10  
某二叉树的前序和中序遍历序列正好一样,则该二叉树中的任何结点一定都无右孩子。(3分)
 
 
选择题:
 
2-4 
设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是:(4分) 
A、h=t; t->next=h->next; 
B、t->next=h->next; h=t; 
C、h=t; t->next=h; 
D、t->next=h; h=t;
 
2-5
若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式,当读入f时,堆栈里的内容是什么(按堆栈自底向上顺序)? (4分) 
A、+(*+ 
B、+(+ 
C、++(+ 
D、abcde
 
2-6
若用大小为6的数组来实现循环队列,且当前front和rear的值分别为0和4。当从队列中删除两个元素,再加入两个元素后,front和rear的值分别为多少? (4分) 
A、2和0 
B、2和2 
C、2和4 
D、2和6
 
2-7
三叉树中,度为1的结点有5个,度为2的结点3个,度为3的结点2个,问该树含有几个叶结点? (4分) 
A、8 
B、10 
C、12 
D、13
 
2-8 
已知一棵二叉树的先序遍历结果是ABC,则以下哪个序列是不可能的中序遍历结果: (4分) 
A、ABC 
B、BAC 
C、CBA 
D、CAB
 
2-9 
在一个用数组表示的完全二叉树中,如果根结点下标为1,那么下标为17和19这两个结点的最近公共祖先结点在哪里(数组下标)? (注:两个结点的“公共祖先结点”是指同时都是这两个结点祖先的结点) (4分) 
A、8 
B、4 
C、2 
D、1
 
2-10 
将6、4、3、5、8、9顺序插入初始为空的最大堆(大根堆)中,那么插入完成后堆顶的元素为: (4分) 
A、3 
B、5 
C、6 
D、9
 
2-11 
设一段文本中包含字符{a, b, c, d, e},其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后,文本所占字节数为: (4分) 
A、40 
B、36 
C、25 
D、12
 
2-12 
在并查集问题中,已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }(注:-n?n表示树根且对应集合大小为nn),那么将元素6和8所在的集合合并(要求必须将小集合并到大集合)后,该集合对应的树根和父结点编号值分别是多少? (4分) 
A、1和-6 
B、4和-5 
C、8和-5 
D、8和-6
 
 
程序填空题:
 
3-1
下列代码的功能是从一个大顶堆H的某个指定位置p开始执行下滤。
 1 void PercolateDown( int p, PriorityQueue H )
 2 {
 3    int  child;
 4    ElementType  Tmp = H->Elements[p];
 5    for ( ; p * 2 <= H->Size; p = child ) {
 6       child = p * 2;
 7       if ( child!=H->Size && 
 8 
 9 (6分) )
10          child++;
11       if ( H->Elements[child] > Tmp )
12          
13 
14 (6分);
15       else  break;
16    }
17    H->Elements[p] = Tmp; 
18 }
 
3-2
下列代码的功能是返回带头结点的单链表L的逆转链表。
 1 List Reverse( List L )
 2 {
 3     Position Old_head, New_head, Temp;
 4     New_head = NULL;
 5     Old_head = L->Next;
 6 
 7     while ( Old_head )  {
 8         Temp = Old_head->Next;
 9         
10 (6分);  
11         New_head = Old_head;  
12         Old_head = Temp; 
13     }
14     
15 (6分);
16     return L;
17 }
 
 
参考答案:
 
判断题:TFFFF  TTFFF
 
选择题:CACDB  AADBD  CB
 
程序填空题:
H->Elements[child+1] > H->Elements[child]  H->Elements[p] = H->Elements[child]  
Old_head->Next = New_head  L->Next = New_head

中国大学MOOC-陈越、何钦铭-数据结构-2016秋期中考试(附答案)