|
|
西安电子科技大学网络教育
2015期末模拟试题4课程名称：__ 数据结构 考试形式： 闭 卷 学习中心：_________ 考试时间： 90分钟 姓 名：_____________ 学 号： 一 填空题（每空1分，合计20分）
在二叉树中，指针p所指结点为叶子结点的条件是______。
求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。
分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。
循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。
在单链表L中，指针p所指结点有后继结点的条件是：__ 。
快速排序在_____的情况下最易发挥其长处。
在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
下面程序段的时间复杂度为________。(n>1)
sum=1；
for (i=0;sum<n;i++) sum+=1;
当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。
循环队列的引入，目的是为了克服_______。
两个字符串相等的充分必要条件是_______。
已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为_______。
上三角矩阵压缩的下标对应关系为：_______。
对于一个具有n个结点的二叉树，当它为一棵_ _时具有最小高度，当它为一棵_ _时，具有最大高度。二 选 择（每题2分，合计30分）
1．对于循环队列，下列说法错误的是（ ）
A.可用顺序存储结构 B.会产生下溢
C.不会产生上溢 D.不会产生假溢2. 若完全无向图有n 个顶点，则边的数目为（ ）
A. n B. n-1
C. n(n-1)/2 D. n(n-1)3. 如右图中有向图的深度优先搜索遍历得到的结点序列是（ ）
A.1 2 4 6 3 5 B.1 3 2 4 5 6
C.1 2 3 4 5 6 D.1 3 2 6 4 54. 下列说法中符合队列性质的是（ ）
A.先进後出
B.只能在一边插入和删除
C.只能为顺序结构
D.只能在一边插入和另一边删除
5．如图BST树成功的平均查找长度为（ ）
A.21/7
B.18/7
C.15/6
D.21/6
6．在下面的程序段中，对x的赋值语句的频度为（ ）
FOR（i=1；i<=n ;i++）
FOR (j=1;j<= n;j++ )
x=x+1;
A． O(2n) B．O(n) C．O(n2) D．O(log2n)
7. 以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈8. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
9. 在单链表指针为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;
10. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
11. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
12. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175 B. 1180 C. 1200 D. 1210
13. 对稀疏矩阵进行压缩存储目的是（ ）。
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度
14. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3
15. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A．9 B．11 C．15 D．不确定三 应用题（每题6分 合计36分）
数据结构是一门研究什么内容的学科？
设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。用序列(46,88,45,39,70,58,101,10,66,34)建立一个BST树，画出该树，并求在等概率情况下查找成功的平均查找长度。已知一棵二叉树的先序和后序序列如下：
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C
给出这棵二叉树：
转换为对应的森林：
如图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树。有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
四 编程题（每题7分 合计14分）
编写在递增有序的线性链表La中插入元素 x的算法(插入后仍然有序)。
写出求二叉树T中叶子个数的算法。
|
|
