数据结构考题剖析.doc

选择题（1*25=25分） 下面关于算法说法错误的是 。B A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 在下面的程序段中，对x的赋值语句的频度为 C FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A．O(2n) B．O(n) C．O(n2) D．O(log2n)1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 适用于折半查找的表的存储方式及元素排列要求为 。D A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 当采用分快查找时，数据的组织方式为 。B A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？ 。D A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 下列四个序列中，哪一个是堆 。C A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 填空题（2*10=20分） 在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动 个元素。n-i+1 一个栈的输入序列是：1，2，3则不可能的栈输出序列是 。3 1 2 设有一个顺序栈s，元素1，2，3，4，5，6依次进栈，如果6个元素的出栈顺序为2，3，4，6，5，1，则顺序栈的容量至少应为 。3 知U=‘xyxyxyxxyxy’；t=‘xxy’； ASSIGN（S，U）； ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））； ASSIGN（m，‘ww’） 求REPLACE（S，V，m）= 。’xyxyxywwy’ 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为 。232 若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。69 用一维数组存放的一棵完全二叉树如下图所示： A B C D E F G H I J K L 写出后序遍历该二叉树时访问结点的顺序。HIDJKEBLFGCA 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是 。第I列非零元素个数 G是一个非连通无向图，共有28条边，则该图至少有个顶点。在各种查找方法中，平查找长度与结点个数n无关的查找方法是。散列查找 树和二叉树之间有什么样的区别与联系？(8分) 考虑右图： (1)从顶点A出发，求它的深度优先生成树(2分) (2)从顶点E出发，求它的广度优先生成树(2分) （3）根据普利姆(Prim) 算法，(6分) 求它的最小生成树(12分) 算法实现题（2 * 10 = 20分） 1．将两个非递减有序的有序表归并为非递增的有序表（利用原表结点）。请将下面的程序补充完整。 void union( LinkList Lc, LinkList La,LinkList Lb) { Lc = new LNode; Lc-next = NULL; pa = La-next; pb = Lb-next; // 初始化 // 归并 delete La; delete Lb; // 释放La 和 Lb的头结点 } // union 2．试写出直接插入排序的算法。 20 ~ 20学年第 学期 数据结构 课程试卷 标准答案及评分标准