北京航天航空大学数据结构与程序设计2000年考研真题.doc

北京航天航空大学2000年硕士研究生入学考试程序设计与数据结构一、选择题(2’x10) 1. 在非空双向循环链表中q所指的结点前插入一个由p所指的链接点的过程依次为：rlink(p)←q；llink(p)←llink(q)；llink(q)←p；_________。 (A)rlink(q)←p (B)rlink(llink(q))←p (C)rlink(llink(p))←p (D)rlink(rlink(p))←p 2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B 中，则在B中确定aij(ij)的位置k的关系为_________。 (A) (B) (C) (D) 3. 某堆栈的输入序列为a，b，c，d，下面的四个序列中，_________不可能是它的输出序列。 (A)a，c，b，d (B)b，c，d，a (C)c，d，b，a (D)d，c，a，b 4. 深度为h的满m叉数的第k层有_________个结点。(1≤k≤h) (A)mk-1 (B)mk-1 (C)mh-1 (D)mh-1 5. 具有10个叶结点的二叉树中有_________个度为2的结点。 (A)8 (B)9 (C)10 (D)11 6. 要连通具有n个顶点的有向图，至少需要_________条边。 (A)n-1 (B)n (C)n+1 (D)2n 7. 已知有向图G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7}，E={v1，v2，v1，v3，v1，v4，v2，v5，v3，v5，v3，v6，v4，v6，v5，v7，v6，v7}，G的拓扑序列是_________。 (A)v1，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 8. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为_________ (A) (B) (C) (D)n 9. 下面关于B树和B+树的叙述中，不正确的是_________ (A)B树和B+树都是平衡的多分树。 (B)B树和B+树都可用于文件的索引结构。 (C)B树和B+树都能有效地支持随机检索。 (D)B树和B+树都能有效地支持顺序检索。 10. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是_________。 (A)选择排序法 (B)插入排序法 (C)快速排序法 (D)堆积排序法 二、(10’) 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。 三、(5’+10’+10’+5’) 为建立一个具有n份档案的档案库需要设计如下数据结构：所有档案存储在一个动态存储的双向循环链表中，每份档案占用一个地址连续的存储块成为该链表中的一个结点，整个链表为一个链接顺序文件，取名为dossier(档案)，同时分别建立两个索引，其中一个为稠密索引，取名为dense，另一个是表长为m的杂凑表索引，取名为bucket，该杂凑表采用链地址法处理冲突。上述两种索引中都分别存储在每一份档案的存储地址。 1. 请分别画出dossier、dense、bucket的结构示意图。 2. 分别设计出dossier、dense、bucket的数据结点的结构，即为了满足档案的插入、删除、查找的操作，每个结点必要的数据项的名称及其作用。 3. 针对上述结构，用简明的文字分别说明所有可能的查找方法(查找路径)。 4. 分别给出每一种查找方法在查找成功时的平均查找长度。 四、(10’) 已知num为无符号十进制整数，请写一非递归算法，该算法依次输出num对应的r进制的各位数字。要求算法中用到的堆栈采用线性链表存储结构。(1r10) 五、(10’) 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量) 六、(10’x2) 设有一集合，其成员为任意类型的数据元素，基本操作为插入、删除和成员测试。若为该集合设计一个集合类型，则 1. 该集合可以采用哪几种存储结构？就存储空间开销以及操作而言，分别说明每种存储结构的特点