手机APP下载

您现在的位置: 首页 > 考研频道 > 考研专业课 > 北京航天航空大学 > 正文

北京航天航空大学2000年程序设计与数据结构专业课考研真题试卷(回忆版)

来源:可可英语 编辑:max   可可英语APP下载 |  可可官方微信:ikekenet

一、选择题(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

(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={
},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

五、(10’)

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

六、(10’x2)

设有一集合,其成员为任意类型的数据元素,基本操作为插入、删除和成员测试。若为该集合设计一个集合类型,则

1. 该集合可以采用哪几种存储结构?就存储空间开销以及操作而言,分别说明每种存储结构的特点


发布评论我来说2句

    最新文章

    可可英语官方微信(微信号:ikekenet)

    每天向大家推送短小精悍的英语学习资料.

    添加方式1.扫描上方可可官方微信二维码。
    添加方式2.搜索微信号ikekenet添加即可。