西安科技大学研究生2012数据结构试卷.doc

西安科技大学
2012年硕士研究生入学考试试题
─────────────────────────────────
科目编号：824 科目名称： 数据结构与算法设计
考生须知：
答案必须写在答题纸上，写在试题或草稿纸上不给分。
答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。
答题必须写清题号，字迹要清楚，卷面要保持整洁。
试题要随答题纸一起交回。
一、选择题（每题2分，共20分）
1. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。
（A）edcba （B）deacb （C）cbade （D）abcde
2. 判断一个循环队列Q(元素最多为n)为满的条件是( )。
（A）Q->rear==Q->front （B）Q->rear!=Q->front
（C）Q->front==(Q->rear+1)%n （D）Q->front!=(Q->front+1)%n
（ ）
（A）迷宫问题 (B) 表达式求值 (C) 作业调度 (D) 程序递归
4. 对于一个非空的广义表来说，( )。
（A）可能不含任何原子元素
（B）至少含一个原子元素
（C）其长度不小于其中任何一个子表的长度
（D）至少含一个非空的子表元素
5. 串的逻辑结构与( )的逻辑结构不同。
（A）线性表 （B）栈 （C）队列 （D）树
6. 高度为h的二叉树上只有度为0和2的结点，则此类二叉树中所包含的结点数至少为( )。
（A）2h （B）2h-1 （C）2h+1 （D）h+1
7. 在散列函数H(n)=n MOD p中，p应取( )。
（A）奇数 （B）偶数 （C）质数 （D）正数
8. 对任何一棵二叉树T，设n0，n1，n2分别是度数为0，1，2的结点数，则n0=( )。
（A）n1+1 （B）n2+1 （C）n1+n2 （D）2n1+1
9. 采用分块查找时，若线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。
（A）16 （B）64 （C）128 （D）256
10. 下列排序方法中，( )是从未排序序列中依次挑选元素，并将其放入已排序序列（初始为空）的一端。
（A）希尔排序 （B）归并排序 （C）选择排序 （D）插入排序
二、填空题（每空3分，共30分）
1．在长度为n的顺序表中插入一个元素，平均需要移动 元素，删除一个元素平均需要移动 个元素。
2．一个有n个顶点的无向图，其生成树有 条边。
3． 在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在