运用证据认定案件事实问题研究

《运用证据认定案件事实问题研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》部分一、简答题（10分，每题5分）1、数据元素之间的关系在计算机中的存储有几种表示方法？各有什么特点？（P6）解：数据元素之间的关系在计算机中有四种不同的表示方法： (1)顺序存储方法。数据元素顺序存放，每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。 (2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。 (

2、3)索引存储方法。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。  (4)哈希(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存储，也不能折半存取。2、对于堆排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？（P28

3、9）答：若只从存储空间考虑，则应首先选取堆排序 方法，其次选取 快速排序 方法，最后选取 归并排序 方法； 若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。二、应用题（55分）1、证明：同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同）。（8分）（例如先序abc，后序bca，中序bac。）(P128)答：【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机

4、不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。2、设有正文AADBAACACCDACACAAD，字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。（10分）(P144;P148)3、对于下图完成下列指定操作。（12分）(1)从顶点A出发，求它的深度优先生成树。(P167;)(2)从顶点E出发，求它的广度优先生成树。(P169;)(3)根据普利姆(Prim)算法，求它的最小生成树。(P173)4.设哈希(Hash)表的地址范围为0～17，哈希函数为：H(K)=KMOD16,K为关键字，用线性探测再散列法处理冲突，输入关键字序列

5、:(10,24,32,17,31,30,46,47,40,63,49)构造哈希表，试回答下列问题：（15分）（P257）(1)画出哈希表示意图。(2)若查找关键字63，需要依次与哪些关键字比较?(3)若查找关键字60，需要依次与哪些关键字比较?(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。答：（1）画表如下（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标

6、记），所以应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，ASL=1/11（6＋2＋3×3）＝17/11≈1.555．奇偶交换排序如下所述：对于初始序列A[1]，A[2],…,A[n],第一趟对所有奇数i（1<=iA[i+1]，则将两者交换；第二趟对所有偶数i（2<=iA[i+1]，则将两者交换；第三趟对所有奇数i（1<

7、=i