2015-2016数据结构习题课
- 格式:docx
- 大小:25.58 KB
- 文档页数:4
2015-2016学年第1学期数据结构习题课
一.选择题
1. 算法的时间复杂度取决于()。
A.问题的规模 B. 待处理数据的初态
C. A和B
2. 从逻辑上可以把数据结构分为()两大类。
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
3. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之
间插入一个s所指的结点,则执行()。
A s→link=p→link; p→link=s;
B p→link=s; s→
link=q;
C p→link=s→link; s→link=p;
D q →link=s; s→link
=p;
4. 设有三个元素X,Y,Z顺序进栈(进的过程中允许出栈),下列得不到的
出栈排列是( )。
A.XYZ B. YZX C. ZXY D. ZYX
5. 设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( )
最节省时间。
A. 单链表
B.单循环链表
C. 带尾指针的单循环链表
D.带头结点
的双循环链表
6. 数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起
始地址为1000的内存单元中,则元素A[5,5]的地址是( )。
A. 1175
B. 1180
C. 1205
D. 1210
7. 某内排序方法的稳定性是指( )。
A.该排序算法不允许有相同的关键字记录 B.该排序算法允许有相同的关键字记录
C.平均时间为0(n log n)的排序方法 D.以上都不对
8.下列选项中与数据存储结构无关的术语是()
A.顺序表
B.链表
C.链队列
D.栈
9.若带头结点的单链表的头指针为head,则判断链表是否为空的条件是( )
A.head=NULL
B.head->next=NULL
C.head!=NULL
D.head->next!=head
10. 假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元
素,则队列的尾指针值为()
A.3 B.37
C.50 D.97
11.设有两个串p和q,其中q是p的子串,则求q在p中首次出现位置的算法称为()
A.求子串
B.串联接
C.串匹配
D.求串长
12. 下列排序算法中不稳定的是()
A.快速排序B.归并排序
C.冒泡排序D.直接插入排序
13.设有一组关键字(19,14,23,1,6,20,4,27,5,11,10,9),用散列函数H(key)=key%13构造散列表,用拉链法解决冲突,散列地址为1的链中记录个数为( )
A.1
B.2
C.3
D.4
14.一个有序表为(1,3,9,12,32,41,45,62,75,77,82,95,100),当采用折半查
找方法查找值32时,查找成功需要的比较次数是()
A.2 B.3
C.4 D.8
15.对下面有向图给出了四种可能的拓扑序列,其中错误
..的是()
A.1,5,2,6,3,4 B.1,5,6,2,3,4
C.5,1,6,3,4,2 D.5,1,2,6,4,3
二.填空题
1. 深度为k的完全二叉树至少有_______个结点,至多有_______个结点。
2.下面程序段中带下划线的语句的执行次数的数量级是:。
i=1;while( i<n ) i=i*2;
3. 对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。
4.带头结点的双循环链表L为空表的条件是:________。
5. 直接插入排序用监视哨的作用是_______。
6. 实现字符串拷贝的函数 strcpy为:
void strcpy(char *s , char *t) /*copy t to s*/
{ while (________);
}
7. 二叉树的先序序列和中序序列相同的条件是______。
8.有N个顶点的有向图,至少需要量______条弧才能保证是连通的。
9.设一个连通图G中有n个顶点e条边,则其最小生成树上有________条边。
10.平衡二叉树又称__________,其定义是__________。
11.在单链表中某结点后插入一个新结点,需要修改_______________个结点指针域的值。
12.设栈S的初始状态为空,若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、
d、c、f、
e、a,则栈S的容量至少是________________。
13.长度为n的线性表采用单链表结构存储时,在等概率情况下查找第i个元素的时间复杂度是_______。
14.广义表G=(a,b,(c,d,(e,f)),G)的长度为________________。
15.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为___,整个堆排序过程的时间复杂度为___。
三.判断题
1. 栈是实现过程和函数等子程序所必需的结构。
()
2. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。
( )
3. 顺序存储结构的主要缺点是不利于插入或删除操作。
( )
4. 完全二叉树中,若一个结点没有左孩子,则它必是叶子节点。
()
5. 二维以上的数组其实是一种特殊的广义表。
()
6. 不同的求最小生成树的方法最后得到的生成树是相同的。
()
7. 折半查找法的查找速度一定比顺序查找法快。
()
8. 连通分量指的是有向图中的极大连通子图。
()。
()
9. 最小代价生成树是唯一的。
()
10. 直接选择排序算法在最好情况下的时间复杂度为O(N)。
()
四.解答题
1.已知一棵二叉排序树(结点值大小按字母顺序)的前序遍历序列为EBACDFHG,请画出这个二叉排序树
2. 已知无向图如下所示,给出从V1开始的广度优先和深度优先搜索序列。
3.对给定关键字序列(28,07,39,10,65,14,61,17,50,21)选择第一个元素28进行划分,写出其快速排序第一遍的排序过程。
4.写出折半查找算法
5. 已知二叉树的定义如下:
typedef struct node{
int data;
struct node *lchild, *rchild;
}*Bitptr;
编写递归算法求二叉树的高度。