西  安  科  技  大  学2009—2010 学  年  第 1  学  期  期  末  考  试  试  题（卷）
          院系：              班级：              姓名：              学号：
装  订  线      装 订 线 以 内 不 准 作 任 何 标 记      装  订  线
科目
数据结构与算法
考试性质
考试
命题
张小艳
审批
张小艳
10.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用(      )存储方式节省时间。
A）顺序表    B）单链表      C）单循环链表          D）双链表
二、简答题（每题5分，共20分）
1. 什么是数据结构？有关数据结构的的讨论涉及那几个方面的问题？
2. 递归算法比非递归算法花费更多的时间，对吗？为什么？
3. 试述线性表的顺序存储与链式存储的优缺点。
4．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少?
四、算法设计（任选2题  每题15分  共30分）
1．设顺序表va中的数据元素递增有序，试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
2． 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
3. 以多叉链表为存储结构，设计算法对树进行层次遍历。　
4. 写出图的深度优先遍历算法。
五、综合应用题（任选3题  每题10分  共30分）
1．设无向图G=(V, E),  V={1, 2, 3, 4, 5, 6，7，8},  E={（1,2）,（1,3）, (2,4), (2,5), (3,6), (3,7),  (4,8), (5,8), (6,7)}。请画出图G的邻接表并在此基础上求出深度优先和广度优先遍历的序列及其相应生成树。
2.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.06，0.2，0.01，0.07，0.31，0.04，0.2，0.11。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。
试卷类型
A
考试地点
临潼
学生班级
软工、网工10级
成绩
一、单项选择题（每小题2分 共20分）
1. 链表不具备的特点是(    )。
（A）可随机访问任一个结点          （B）插入删除不须要移动元素
（C）不必事先估计存储空间          （D）所需空间与其长度成正比
2. 顺序查法适合于存储结构为(    )的线性表。
（A）散列存储                  （B）压缩存储
（C）顺序存储或链式存储        （D）索引存储
3. 下列4个广义表中，长度为1，深度为4的广义表是(    )。
（A）((), ((a)))                    （B）((((a), b)),c)
（C）(((a, b),(c)))                  （D）(((a, (b), c)))
数据结构与算法题库4. 具有4个顶点的无向完全图有(    )条边。
（A）6        （B）12        （C）16        （D）20
5. 二叉树的顺序存储结构适合于（      ）。   
  （A）单枝二叉树  （B）完全二叉树  （C）平衡二叉树  （D）二叉排序树
6. 深度为6（根层次为1）的二叉树至多有(    )个结点。
  A)  63      B) 64    C) 31    D) 32
7. 有一记录序列共有90000个数据元素, 采用如下哪种排序方法能以最快的速度选出前8个记录。（        ）   
直接插入排序    归并排序    快速排序    堆排序
8. 一个具有n个顶点的无向图中，要连通全部顶点至少需要(    )条边。
（A）n        （B）n+1        （C）n/2        （D）n-1
9.具有线性结构的数据结构是(    )。
  A) 图        B) 树          C) 队列          D) 广义表
西  安  科  技  大  学2009—2010 学  年  第 1  学  期  期  末  考  试  试  题（卷）
          院系：              班级：              姓名：              学号：
装  订  线      装 订 线 以 内 不 准 作 任 何 标 记      装  订  线
科目
数据结构与算法
试卷类型
A
考试班级
3． 给定二叉树的两种遍历序列，分别是：
前序遍历序列：D，A，C，E，B，H，F，G，I； 
中序遍历序列：D，C，B，E，H，A，G，I，F，
试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
4．假定对有序表：（3，5，8，17，24，30，42，54，63，72，87，95）进行折半查，试回答下列问题：
画出描述折半查过程的判定树；
若查元素54，需依次与哪些元素比较？
若查元素90，需依次与哪些元素比较？
假定每个元素的查概率相等，求查成功时的平均查长度。