北航2000数据结构

北京航空航天大学程序设计与数据结构试题
(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(i<j)的位置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进制的各位数字。要求算法中用到的堆栈采用线性链表存储结构。(1<r<10)

五、(10’)
已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量)

六、(10’x2)
设有一集合，其成员为任意类型的数据元素，基本操作为插入、删除和成员测试。若为该集合设计一个集合类型，则
1.        该集合可以采用哪几种存储结构？就存储空间开销以及操作而言，分别说明每种存储结构的特点。
2.        分别写出上述三种操作在你所确定的一种存储结构上的具体体现(算法)。

好东西！！！

很好啊，好东西

好啊～～我想考北航～～！！！

顶顶顶顶顶顶顶顶

怎么没有答案啊

怎么没有答案啊

阿.没有答案啊...

没有答案啊

谢谢啦 嘿嘿