21秋西电网院数据结构模拟试题3百分
西安电子科技大学网络教育2010学年上学期期末模拟试题2课程名称：__数据结构 考试形式： 闭 卷 学习中心：_________ 考试时间：90分钟姓 名：_____________ 学 号： 一 填空题（每空1分，合计20分）
1. 对于给定的n个元素,可以构造出的逻辑结构有 ， ， ，__ _四种。
2. 在单链表中，要删除某一指定的结点，必须找到该结点的 结点。
3. 将一个单链表中的*p结点删除，可执行如下操作：
q=p->next;
p->data=p->next->data;
p->next= ;
free(q);
4. 若用不带头结点的单链表来表示链栈s，则创建一个空栈所要执行的操作是 。
5. 当两个栈共享一存储区时，栈利用一维数组stack(0,n-1)表示，两栈顶指针为top与top，则当栈1空时，top为_______，栈2空时 ，top为_______，栈满时为_______。
6. 所谓稀疏矩阵指的是___ ____。
7. 若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度为 。
8. 二叉树由_ __，__ _，_ __三个基本单元组成。
9. 已知一有向图的邻接链表存储结构如图所示，以顶点0为出发点的深度优先搜索遍历序列为 ；广度优先搜索遍历序列为 。
10. 在n个顶点的有向图中，每个顶点的度最大为 。
11．已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。二 选择（每题2分，合计30分）
1. 链表是一种采用 存储结构存储的线性表。
A. 顺序
B. 网状
C. 星式
D. 链式
2. 下面关于线性表的叙述中，错误的是（ ）。
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．与单链表相比，双链表的优点之一是（ ）。
A.插入、删除操作更简单
B.可以进行随机访问
C.可以省略头指针或表尾指针
D.访问相邻结点更灵活
4. 数据结构用集合的观点可以表示为一个二元组DS=(D,R) 。其中，D是( ）的有穷集合。
A.算法
B.数据元素
C.数据操作
D.逻辑结构5. 以下那一个术语与数据的存储结构无关？（ ）
A．栈
B. 哈希表
C. 顺序表
D.双向链表
6. 在存储数据时，通常不仅需要存储各数据元素的值，而且还需要存储（ ）。
A.数据元素的类型
B.数据的存储方法
C.数据的处理方法
D.数据元素之间的关系
7. 若一个栈的输入序列为1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。
A．n-i
B.n-i-1
C.i
D.n-i+18. 向一个栈顶指针为top的链栈中插入一个s所指的结点时，操作语句序列为（ ）。
A.top->next=top;
B.s->next=top->next;top_>next=s;
C.s->next=top;top=s;
D.s->next=top;top=top->next;
9. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A. (rear+1)%n==front
B. rear==front
C．rear+1==front
D. (rear-l)%n==front
10. 假设以行序为主序存储二维数组A ，设每个数据元素占2个存储单元，基地址为10，则LOC(A)=（ ）。
A. 418
B. 818
C. 1010
D. 102011. 树最适合用来表示（ ）。
A．有序数据元素
B. 无序数据元素
C．元素之间具有分支层次关系的数据
D. 元素之间无联系的数据12. 如图所示二叉树是由森林转换过来的，那么此森林中有（ ）个叶子结点。
A.4
B.5
C.6
D.7
13. 已知一棵二叉树的先序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
A．CBEFDA
B．FEDCBA
C．CBEDFA
D．不定
14. 在待排元素序列基本有序的前提下，效率最高的排序方法是（ ）。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
15. 适用于折半查找的表的存储方式及元素排列要求为( ) 。
A．链接方式存储，元素无序
B．链接方式存储，元素有序
C．顺序方式存储，元素无序
D．顺序方式存储，元素有序三 应用题（每题6分 合计36分）
1. 已知带权连通图G=(V,E)的邻接链表如图11.15所示。请画出该图，并分别以深度优先搜索和广度优先搜索遍历该图，写出从顶点0出发的遍历顶点序列，并画出该图的一个最小生成树。图中链表结点的三个域依次为顶点序号、边的权和指针。
2. 有向网络G如图所示，试求从顶点0到其余顶点的最短路径，要求给出求最短路径过程中的动态变化情况。
3. 设给定字符集合{a,b,c,d,e,f}的权值集合w={2,3,4,7,8,9};试构造关于w的一颗哈夫曼树，并求其带权路径长度及各字符的哈夫曼编码。
4. 证明具有n个顶点和n-1条边的无向连通图G是树。
5. 已知序列{25，18，60，40，7，21，32，73，68}，请给出采用冒泡排序方法对该序列作升序排列时的每一趟结果。
6. 画出长度为10的折半查找判定树，并求其等概率时查找成功的平均查找长度。
四 编程题（每题7分 合计14分）
1. 仔细阅读下面程序，并回答有关问题。
void test(int a,int n)
{
int i,j,x,flag;
flag=1;
i=1;
while(i<n && flag)
{
flag=0;
for(j=1;j< ;j++)
if( )
{
x=a;
a=a;
a=x;
;
}
i++;
}
}
（1）在 中填上正确语句，使该过程能完成预期的排序功能。
（2）该过程使用的是什么排序方法？
（3）当数组a的元素初始时已按值递增排列，在该过程执行中会进行多少次比较？打少次交换？
（4）当数组a的元素初始时已按值递减排列，在该过程执行中会进行多少次比较？打少次交换？
2. 编写一个算法计算头指针为head的单链表中数据域值为x的结点个数。
页:
[1]