21秋西电网院数据结构模拟试题1题目
西安电子科技大学网络教育2010学年上学期期末模拟试题1课程名称：__数据结构 考试形式： 闭 卷 学习中心：_________ 考试时间：90分钟姓 名：_____________ 学 号： 一 填空题（每空1分，合计20分）
数据结构主要研究包括 、 和这些结构上定义的运算三个方面的内容。
非线性结构的逻辑特征是一个结点有 个直接前驱和直接后继。
已知如下程序段
for( i= n; i>0; i--) {语句1}
{
x=x+1； {语句2}
for(j=n;j>i; j--) {语句3}
y=y+1; {语句4}
}
语句1执行的频度为 ；语句2执行的频度为 ；语句3执行的频度为 ；语句4执行的频度为 。
在单链表中结点*p后插入结点*s的指令序列为 ； 。
用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。
设二维数组A[-20..30,-30..19]，每个元素占有4 个存储单元, 存储起始地址为200。如按行优先顺序存储，则元素 A的存储地址为__ _；如按列优先顺序存储，则元素A[-18][-25]的存储地址为__ _。
结点数最少的二叉树为 。
在二叉树中，指针p所指结点为叶子结点的条件是____ __。
如果树的孩子兄弟表示中结点A有 3个兄弟，而且B是A的双亲，则B的度是______。
若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。
有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_ __，带权路径长度WPL为_ __。
对n个顶点的连通图来说，它的生成树一定有 条边。
设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为 。二 选择（每题2分，合计30分）
1. 在数据结构中，与所使用计算机无关的数据叫 结构。
A.存储
B.物理
C.逻辑
D.物理和逻辑
2. 在链表中进行 操作的效率比在顺序表中进行该操作效率高。
A.二分法查找
B.快速查找
C.顺序查找
D.插入
3．带头结点的单链表head为空的判定条件是( )。
A.head==NULL
B.head->next==NULL
C.head->next==head
D.head!=NULL
4. 在双向链表的*p结点前插入新结点*s的操作为( )。
A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;
B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;
C.s->next=p;s->prior=p->prior;p->prior=s;p->prior->next=s;
D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;
5. 在长度为n的（ ）上，删除第一个元素，其算法复杂度为O(n)。
A.只有表头指针的不带头结点的循环单链表
B.只有尾指针的不带表头结点的循环单链表
C.只有表尾指针的带头结点的循环单链表
D.只有尾指针的带表头结点的循环单链表
6. 对于顺序存储的线性表，访问结点和删除结点的时间复杂度为（ ）。
A．O(n)O(n)
B. O(n)O(1)
C. O(1)O(n)
D. O(1) O(1)
7. 与单链表相比，双链表的优点之一是（ ）。
A.插入、删除操作更简单
B.可以进行随机访问
C.可以省略头指针或表尾指针
D.访问相邻结点更灵活
8. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A. 5 4 3 6 1 2
B. 4 5 3 2 6 1
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
9. 栈在（ ）中应用。
A. 递归调用
B. 子程序调用
C. 表达式求值
D. A，Ｂ，Ｃ
10. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5
B. 2和4
C. 4和2
D. 5和1
11. 下列操作中，（ ）是数组的基本运算。
A.插入
B.删除
C.修改
D.排序
12. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［0..(n(n+1))/2-1］中，则在B中确定aij（i<j）的位置k的关系为( )。
A. i*(i-1)/2+j
B. j*(j-1)/2+i
C. i*(i+1)/2+j
D. j*(j+1)/2+i
13. 如图所示二叉树中，（ ）不是完全二叉树。
14. 按照二叉树的定义，具有3个结点的二叉树有（ ）种不同的树形。
A.3
B.4
C.5
D.6
15. 已知一有向图的邻接链表存储结构如下图所示，以顶点0为出发点的深度优先搜索遍历序列为（ ）。
A.0 1 2 4 3
B.0 1 2 3 4
C.0 2 3 4 1
D.0 3 2 4 1三 应用题（每题6分 合计36分）
1. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试填补空格处的内容。
先序序列： B F ICEH G
中序序列：D KFIA EJC
后序序列： K FBHJ G A
2. 简述顺序存储和链式存储的特点。
3. 已知图G的邻接矩阵如下所示，请由邻接矩阵画出相应的图G。
（1）图中所有顶点是否都在它的拓扑序列中？
（2）如果要使此图成为完全图，还需增加几条边？
4. 将数据{1，9，25，11，12，35，17，29}散列到散列表中。采用除留余数法构造散列函数，线性探测再散列法处理冲突，要求新插入数据的平均查找长度不多于2.5次，试确定散列表的表长m及相应得散列函数H(key)；分别计算所构造散列表查找成功和不成功时的平均查找长度。
5. 已知序列{25，18，60，40，7，21，32，73，68}，请给出采用冒泡排序方法对该序列作升序排列时的每一趟结果。
6. 有一份电文中共使用了5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树（按左子树根结点的权小于等于右子树根结点的权的次序构造），并对每个字符进行编码。四 编程题（每题7分 合计14分）
1. 二叉树采用链式存储结构，设计一个算法计算一棵给定二叉树度为1的结点数。
2. 已知线性表元素递增有序，试写一高效算法，删除表中所有值大于x且小于y(x<y)的元素。要求以顺序表实现，并分析所写算法的时间复杂度。
页:
[1]