北京航空航天大学程序设计与数据结构试题.pdfVIP

北京航空航天⼤学程序设计与数据结构试题

北京航空航天⼤学程序设计与数据结构试题

(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)←pB)rlink(llink(q))←p

C)rlink(llink(p))←pD)rlink(rlink(p))←p

4.在初始为空的堆栈中依次插⼊元素f，e，d，c，b，a以后，连续进⾏了

三次删除操作，此时栈顶元素是__________。

A)cB)dC)bD)e

5.若某堆栈的输⼊序列为1，2，3，……，n，输出序列的第1个元素为n，

则第i个输出元素为__________。

A)iB)n-iC)n-i+1D)哪个元素⽆所谓

6.求字符串T在字符串S中⾸次出现的位置的操作称为__________。

A)求串的长度B)求⼦串C)串的模式匹配D)串的连接

7.若⼀棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个

度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树⼀共有__________个

叶结点。

A)35B)28C)77D)78

8.若⼀棵⼆叉树有1001个结点，且⽆度为1的结点，则叶结点的个数为

__________。

A)498B)499C)500D)501

9.已知某完全⼆叉树采⽤顺序存储结构，结点数据信息的存放顺序依次为

A、B、C、D、E、F、G、H，该完全⼆叉树的后序遍历序列为__________。

A)HDEBFGCAB)HEDBFGCAC)HDEBAFGCD)HDEFGBCA

10.若某带权图为G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7，v8，v9，

v10}，E={(v1，v2)5，(v1，v3)6，(v2，v5)3，(v3，v5)6，(v3，v4)3，(v4，v5)3，(v4，v7)1，(v4，v8)4，(v5，v6)4，

(v5，v7)2，(v6，v10)4，(v7，v9)5，(v8，v9)2，(v9，v10)2}(注：顶点偶对右下⾓的数据表⽰边上的权值)，则G的关键路径

的长度为__________。

A)19B)20C)21D)22

11.顺序查找法适合于存储结构为__________的线性表。

A)顺序存储结构或链式存储结构B)散列存储结构

C)索引存储结构D)压缩存储结构

12.当n⾜够⼤时，在按值有序的顺序表中进⾏折半查找，当查找概率相等

的情况下，其查找成功的平均查找长度是__________。

A)(n+1)/2B)n/2C)log2(n+1)-1D)log2(n+1)

13.下述命题中，不成⽴的应是__________。

A)m阶B树中的每⼀个分⽀结点的⼦树的个数都⼩于或等于m

B)m阶B树中的每⼀个分⽀结点的⼦树的个数都⼤于或等于?m/2?

C)m阶B树中的任何⼀个结点的⼦树的⾼度都相等

D)m阶B树中有k个⼦树的分⽀结点包含k-1个