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