2015-2016数据结构习题课

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.顺序表 C.链队列

B.链表 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 C.50 B.37 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构造散

列表,用拉链法解决冲突,散列地址为1的链中记录个数为( ) A.1 C.3

B.2

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 C.5,1,6,3,4,2

B.1,5,6,2,3,4 D.5,1,2,6,4,3

二.填空题

1. 深度为k的完全二叉树至少有_______个结点,至多有_______个结点。

2.下面程序段中带下划线的语句的执行次数的数量级是:。 i=1;while( i

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开始的广度优先和深度优先搜索序列。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4