21秋西电网院数据结构模拟试题2资料
西安电子科技大学网络教育2010学年上学期期末模拟试题2课程名称：__数据结构 考试形式： 闭 卷 学习中心：_________ 考试时间：90分钟姓 名：_____________ 学 号： 一 填空题（每空1分，合计20分）
1. 是数据的基本单位，通常由若干个 组成， 是数据的最小单位。
2. 数据的存储结构常用的存储方法有 、 、 和散列存储方法四种。
3. 计算机执行下面的语句时，语句s的执行次数为 _______ 。
for(i=l；i<n-l；i++)
for(j=n;j>=i;j--)
s;
4. 在一个长度为n的顺序表中删除第i（0≤i≤n-1）个元素，需向前移动 个元素。
5. 带头结点的双循环链表L中只有一个元素结点的条件是 __。
6. 是限定仅在表尾进行插入或删除操作的线性表。
7. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。（进栈时栈顶指针增加）
8. 设循环队列存放在向量sq.data中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。
9. 若一稀疏矩阵有8个非零元素，矩阵元素为整型， 现用三元组表方式对其进行压缩存储，假设整型元素占2个存储单元，请问该三元组表至少占 个存储单元。
10. 深度为h 的完全二叉树至少有_ __个结点；至多有_ __个结点；h和结点总数n之间的关系是 __。
11．一个8个顶点的完全无向图边数为 。
12. 每次直接或通过间接比较两个元素，若出现逆序排列时就交换它们的位置，此种方法叫做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。二 选择（每题2分，合计30分）
1. 算法必须具备（） 这三个特性。
A.可执行性、可移植性、可扩充性
B. 可执行性、确定性、有穷性
C.确定性、有穷性、稳定性
D.易读性、稳定性、安全性
2. 在数据结构中，从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构
B．顺序结构、链式结构
C．线性结构、非线性结构
D．初等结构、构造型结构
3．如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。
A.单链表
B.双链表
C.单循环链表
D.顺序表
4. 在一个以 h 为头指针的单循环链中，p 指针指向链尾的条件是（ ）。
A. p->next=h
B. p->next=NULL
C. p->next->next=h
D. p->data=-1
5. 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换其中某两个元素的值
6. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A．p->next=s;s->next=p->next;
B．s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next;
D．p->next=s->next;p->next=s;
7. 下列程序段的时间复杂度为（ ）。
x=0;
while(x<10000)
x++;
A. O(0)
B. O(1)
C. O(1000)
D. O(n)
8. 若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1,p2,p3，…，pn，若p1=3，则p2为（ ）。
A.可能是2
B.不一定是2
C.可能是1
D。一定是1
9. 有六个元素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
10. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。
A. A
B. A
C. A
D. A
11. 对稀疏矩阵进行压缩存储目的是（ ）。
A．便于进行矩阵运算
B．便于输入和输出
C．节省存储空间
D．降低运算的时间复杂度
12. 如图所示二叉树的中序遍历序列是（ ）。
A.abdefgc
B.dbgfeac
C.dbfgeac
D.dgfebac
13. 用于编码的是（ ）。
A.完全二叉树
B.二叉排序树
C.哈夫曼树
D.空树
14. 一个图中包含k个连通分量，如按深度有限搜索方法访问所有顶点，则必须调用（ ）次深度优先遍历算法。
A．k
B．1
C．k-1
D．k+1
15. 对记录关键字为{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：（50 26 38 80 70 90 8 30 40 20）（50 8 30 40 20 92 26 38 80 70）（26 8 30 40 20 80 50 38 90 70）（8 20 26 30 38 40 50 70 80 90），其使用的排序方法是（ ）。
A.冒泡排序
B.快速排序
C.希尔排序
D.交换排序
三 应用题（每题6分 合计36分）
1. 如图，用Prim算法从顶点0开始球最小生成树，按次序产生的边为 ，共 条边；用Kruskal算法产生的边次序为 ，共 条边。（注：边用（i,j）形式表示。）
2. 简述数据结构的定义？3. 对于一个栈，按顺序输入A，B，C。如果不限制出栈时机（即栈中元素不必等所有输入元素都进栈再输出），试给出全部可能的输出序列。4. 设矩阵A=
a. 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素aij (0<=i,j<4)；
b.若将A视为稀疏矩阵，画出A的三元组表结构。5. 假设二叉树采用顺序存储结构，如图所示。
画出此二叉树树形；
写出此二叉树的先序、中序和后序遍历序列；
将此二叉树转换为森林。6. 已知序列{25，18，60，40，7，21，32，73，68}，请给出采用直接选择排序方法对该序列作升序排列时的每一趟结果。四 编程题（每题7分 合计14分）
1. 编写算法，将元素x插入非递增有序的线性表A中，插入后A表仍然保持非递增有序。要求用顺序存储结构实现。2. 假设二叉树采用链式存储结构，设计一个算法求二叉树中指定结点的层数。
页:
[1]