北京航空航天大学程序设计与数据结构专业考研真题
(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={<v编程递归函数1，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.分别写出上述三种操作在你所确定的一种存储结构上的具体体现(算法)。
北京航空航天大学程序设计与数据结构试题
(2001年)
一 、问答题(10’)
一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理与特点。
二、（10’)
已知AOE网为G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7，v8，v9，v10}，E={a1，a2，a3，a4，a5，a6，a7，a8，a9，a10，a11，a12，a13，a14}，其中：
a1:(v1，v2)5    a2:(v1，v3)6    a3:(v2，v5)3    a4:(v3，v4)3
a5:(v3，v5)6    a6:(v4，v5)3    a7:(v4，v7)1    a8:(v4，v8)4
a9:(v5，v6)4    a10:(v5，v7)2    a11(v6，v10)4    a12:(v7，v9)5
a13:(v8，v9)2    a14:(v9，v10)2
注：顶点偶对右下角的数字表示边上的权值。
请按下述过程指出所有关键路径：
ee[1:10]:
le[1:10]:
e[1:14]:
l[1:14]:
其中，ee[i]与le[i]分别表示事件vi的最早发生时间与最晚发生时间；e[i]与l[i]分别表示活动ai的最早开始时间与最晚开始时间。
三、(10’)
欲建立一文献库，其正文(文献本身)存放在一个双向循环链表的各个链接点中。
1.为便于链接点的插入、删除操作，以及按题目、发表日期、发表者名称、主题词(假设每文最多给出三个主题词)进行检索，请设计该链表的链接点结构(给出链接点每个域的名称，并说明该域内存放什么信息。注：以下各小题设计链结点结构也这样要求)。画出整个链表结构的示意图。
2.设计一个三级索引结构，其中第三级索引称为题目索引，示按文献题目构造的稠密索引，通过该级索引并根据给定题目可得到每个文献的存放地址；该级索引按文献学科类分类存放。第二级索引称为中类索引，是题目索引的索引，指出同一中类的文献题目索引的存放位置(例如农林类、气象类……，古代史类，近代史类……)。第一级索引称为大类索引，指出同一大类(如：自然科学类、历史类……)的文献的中类索引的存放位置。请设计每一级索引的结点结构，并画出该索引的整体示意图。
3.在设计一种三级索引结构，其中第三级索引仍是题目索引(与2题所述相同)，第二级索引把具有相同主题词的文献题目索引地址组织在一个单链表中。第一级索引称为主题词索引，用文献给出的主题词做关键字组成杂凑表，即该级索引为一个杂凑表，能够指出具有同一主题词的文献题目索引的索引链表的第一个链结点的存储位置。该杂凑表采用链地址法处理冲突。请设计每一级索引的结点结构，并画出该索引的整体示意图。
四、(10’)
已知非空线性链表由list指出，链结点的构造为，请写一算法，将链表中数据域值最小的那个链结点移至链表的最前面。要求：不得额外申请新的链接点。
五、(5’+10’)
已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：
第一步：若n等于零，则返回m；
第二步：若m小于n，则m与n相互交换；
否则保存m，然后将n送m，将保存的m除以n的余数送n。
1.将上述过程用递归函数表达出来(设求x除以y的余数可以用x MOD y形式表示)。
2.写出求解该递归函数的非递归算法。
六、(10’)
函数void insert(char *s, char *t, int pos)将字符串t插入到字符串s中，插入位置为pos。请用C语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。(说明：不得使用任何库函数。)
七、(15’)
命令sgrep用来在文件中查给定字符串，并输出串所在行及行号。
命令格式为：sgrep [-i] filename searchstring
其中：-i：表示查时大小写无关，省略时表示大小写相关。
filename：给定文件名。
searchstring：所要查的串。
用C语言实现该程序，该程序应具有一定的错误处理能力。(提示：使用命令行参数)
注意：除文件及输入/出操作可使用库函数外，其它不允许使用库函数。
北京航空航天大学程序设计与数据结构试题
(2002年)
一、简答题
1. “数据结构”课程是计算机专业的基础课还是专业课，或者专业基础课？(2’)
2. 学习“数据结构”课程需要哪些课程作为它的基础(举例两门课程)？若没有这些知识，对学习“数据结构”课程可能会产生哪些影响？请举例说明(不超过100字)。(4’)
3. “数据结构”课程将为那些课程学习奠定必要的基础？请举例说明哪些课程(举例两门课程)
用到了“数据结构”课程的哪些知识(不超过100字)。(4’)
二、(5’)
请推导出结论：具有n0个叶结点的哈夫曼树(Huffman)的分支总数为2(n0-1)。
三、单项选择题(2’x15)
1. 线性链表中各链接点之间的地址__________。
A)必须连续    B)部分地址必须连续
C)不一定连续    D)连续与否无所谓
2. 在非空线性链表中由p所指的链接点后面插入一个由q所致的链接点的过程是依次执行动作__________。
A) link(q) p; link(p) q;    B) link(q) link(p); link(p) q;
C) link(q) link(p); p q;    D) link(p) q; link(q) p;
3. 在非空双向循环链表中由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
4. 在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是__________。
A) c    B) d    C) b    D) e
5. 若某堆栈的输入序列为1，2，3，……，n，输出序列的第1个元素为n，则第i个输出元素为__________。
A) i    B) n-i    C) n-i+1    D)哪个元素无所谓
6. 求字符串T在字符串S中首次出现的位置的操作称为__________。
A)求串的长度    B)求子串    C)串的模式匹配    D)串的连接

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。