|
软件基础试题 共4页,第1页
电子科技大学
2004 年秋季软件工程硕士生入学试题
科目名称：软件基础
第一部分 数据结构
一、 单项选择题（请选出正确的编号填入括号中，每小题 2 分，共 20 分）
1. 若已知一个栈的入栈序列是 1,2,3,… ,n,其出栈序列为 p1,p2,p3,… ,pn, 若 p1=n, 则 pi
为( )
①i ②n-i ③n-i+1 ④不确定
2. 广义表((a),a)的表头是( )
①a ②b ③(a) ④((a))
3．一个数组第一个元素的存储地址是 100, 每个元素的长度为 2,则第 4 个元素的地址是
（ ）
①110 ②106 ③108 ④120
4．有向图的邻接表中，顶点 Vi 的出度是（ ）
①依附于 Vi 的弧数 ②Vi 出边表中的表结点数
③Vi 在所有出边表中出现的次数 ④Vi 度的一半
5．在下列排序算法中，不稳定的算法是（ ）
①直接插入排序 ②归并排序 ③冒泡排序 ④直接选择排序
6. 设深度为 h 的二叉树上只有度为 0 和度为 2 的结点,则该二叉树中包含的结点数至少为
( )
①2h ②2h-1 ③2h+1 ④h+1
7．由 n（n≥1）个结点构成的完全二叉树，其深度是（ ）
①log2n+1 ②log2n-1 ③ log2n +1 ④ log2n -1
8．若对有 18 个元素的非递减有序表作折半查找，则查找第 3 个元素的比较序列为（ ）。
①1，2，3 ②9，5，2，3 ③10，5，3 ④9，4，2，3
9. 顺序查找适合于存储结构为( )的线性表
①散列存储 ②顺序存储 ③压缩存储 ④索引存储
10．设 H 为带头结点单循环链表的头指针，P 为沿链表移动指针，则表空条件为（ ）
①H=NIL ②P=H ③H↑.next= H ④H↑.next=NIL
二、简答题（每小题 5 分，共 20 分）
1．已知一棵二叉树的中序和先序序列分别是 CDBGFEAHJIK 和 ABCDEFGHIJK，构造该二叉树。
2. 设 HASH 函数为 H(k)=k MOD 7, HASH 地址空间为 0..8, 采用线性探测再散列方法处理冲突,
对关键字序列 100,20,21,35,3,78,99,45 构造 HASH 表。
3. 列举出栈的五个基本运算。
4．将下图的树转换成二叉树。
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
