北京航天航空大学2002年程序设计与数据结构专业课考研真题试卷(回忆版)
日期:2014-05-02 15:48
(单词翻译:单击)
一、简答题
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)串的连接
7. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有__________个叶结点。
A) 35 B) 28 C) 77 D) 78
8. 若一棵二叉树有1001个结点，且无度为1的结点，则叶结点的个数为__________。
A)498 B)499 C)500 D)501
9. 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为A、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为__________。
A)HDEBFGCA B)HEDBFGCA C)HDEBAFGC D)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)19 B)20 C)21 D)22
11.顺序查找法适合于存储结构为__________的线性表。
A)顺序存储结构或链式存储结构 B)散列存储结构
C)索引存储结构 D)压缩存储结构
12.当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是__________。
A)(n+1)/2 B)n/2 C)log2(n+1)-1 D)log2(n+1)
13.下述命题中，不成立的应是__________。
A)m阶B树中的每一个分支结点的子树的个数都小于或等于m
B)m阶B树中的每一个分支结点的子树的个数都大于或等于ém/2ù
C)m阶B树中的任何一个结点的子树的高度都相等
D)m阶B树中有k个子树的分支结点包含k-1个关键字
14.已知散列范围为[0..9]，散列函数(哈希函数)为H(key)=key MOD 9，处理冲突的方法为线性探测再散列法，依次插入关键字序列8，18，25，44，34，21，19，23后的哈希表为__________。
0 1 2 3 4 5 6 7 8 9
A) 18 44 19 21 23 25 8 34 0
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)串的连接
7. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有__________个叶结点。
A) 35 B) 28 C) 77 D) 78
8. 若一棵二叉树有1001个结点，且无度为1的结点，则叶结点的个数为__________。
A)498 B)499 C)500 D)501
9. 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为A、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为__________。
A)HDEBFGCA B)HEDBFGCA C)HDEBAFGC D)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)19 B)20 C)21 D)22
11.顺序查找法适合于存储结构为__________的线性表。
A)顺序存储结构或链式存储结构 B)散列存储结构
C)索引存储结构 D)压缩存储结构
12.当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是__________。
A)(n+1)/2 B)n/2 C)log2(n+1)-1 D)log2(n+1)
13.下述命题中，不成立的应是__________。
A)m阶B树中的每一个分支结点的子树的个数都小于或等于m
B)m阶B树中的每一个分支结点的子树的个数都大于或等于ém/2ù
C)m阶B树中的任何一个结点的子树的高度都相等
D)m阶B树中有k个子树的分支结点包含k-1个关键字
14.已知散列范围为[0..9]，散列函数(哈希函数)为H(key)=key MOD 9，处理冲突的方法为线性探测再散列法，依次插入关键字序列8，18，25，44，34，21，19，23后的哈希表为__________。
0 1 2 3 4 5 6 7 8 9
A) 18 44 19 21 23 25 8 34 0
