第二套 数据结构自测题
一、单项选择题（本大题共15小题，每小题2分，共30分）
（在每小题列出的四个选项中只有一个选项符合题目要求，请将正确选项前的字母填在题后的括号内。）
1. 程序段 i=n;x=0;
do{x=x+5*i; i--;} while (i>0);
的时间复杂度为 （ ）
A. 0(1) B. 0(n) C. 0(n ) D. 0(n )㎡㎡㎡
2. 在表长为n的顺序表上做删除运算，其平均时间复杂度为 （ ） A. 0(1) B. 0(n) C. 0(nlgn) D. 0( )
3. 在已知尾指针的但循环链表中，要在其开始结点前插入一新结点，其算法所需的时间复杂度为 （ ） A. 0(1) B. 0(lgn) C. 0(nlgn) D. 0( ) 4. 在链栈中执行栈操作时， （ ） Ａ.需要别栈是否满 B.需判别栈是否空
C.不必考虑上溢 Ｄ.限制在链表尾部进行 5. 串的“模式匹配”是指 （ ）
Ａ.判两个串是否相等 B.对两个串进行大小比较 C.找某字符在串中第一次出现的位置 D.找某子串在主串中第一次出现的位置
6. 稀疏矩阵是指 （ ） A.元素少的矩阵 B.有少量零元素的矩阵 C.有少量非零元素的矩阵 D.行数，列数很少的矩阵 7. 深度为K的二叉树，结点数最多有 （ ） A. 2K B.2K-1 C.2K-1㎡ D.2K-1-1
8. 判断线索二叉树中某结点P有左孩子的条件是 （ ） A.p! = null B.p ->lchild! = null C.p ->itag = 0 D.p ->itag = 1 9. N个结点的有向完全图的边数是 （ ） A.n㎡ B.2 C.n（n-1） D.2n(n+1)
10. 深度优先遍历类似于二叉树的 （ ） A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历
11. 归并排序的时间复杂度是 （ ） A.O（n2） B.O(nlog2n) C.O（n） D.O（log2n）
12. 折半查找排序的时间复杂度是 （ ） A.O（n2） B.O（nlog2n） C. O（n） D. O（log2n）
2
n
2
3
13. M阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于
（ ） A.[M/2] B.[M/2]-1 C.[M/2]+2 D.M
14.某顺序存储的表格中有90 000个元素.已按关键字值额升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不同。用顺序查找法查找时，平均比较次数约为 （ ）
A.25 000 B.30 000 C.45 000 D.90 000
15.散列文件是一种 （ ）
A.顺序文件 B.索引文件 C.链接文件 D.计算寻址文件
二.填空题（本大题共10小题，每小题2分，共20分）
16.线性表按存储方式的不同，可分为__________、___________和散列表等三种。 17.在栈结构中,允许插入的一端为__________;在队结构中,允许插入的一端称为____________.
18.在串的运算中,ctrcmp( )是一个_____函数;stremp( ‘key’,’key’)的值_____. 19.广义表LS=(a1,a2,a3,??an),则表头为________, 表尾为________ 20.深度为K的二叉树至多有_________个结点,最少有_________个结点.
21.在有N个结点的二叉树表中，空指针域有_________个，利用这些空指针域，存放指向结点在中序次序下的前趋或后继的指针，这种附加的指针称为_______________.
22.由一棵二叉树的前序序列和_____________序列可以确定这棵二叉树。设某二叉树的后序遍历为ABKCBPM，则可知该二叉树的根为______________.
23.n 个顶点 e条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为_______;n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为________。 24.快速排序最好和平均的时间复杂度为______,最坏时间复杂度为______。
25.在含有n个结点的二叉排序树上查找某结点时，其平均查找长度ASL的范围是从______至_______。
三．简答题（本大题共5小题，每小题4分，共20分）
26.简述在链表中设置头结点带来的好处。
27.设二维数组A的每个元素占6个字节，且LOC（a00）=100，问A共占多少个字节？ 28.已知权值:4,2,5,7,5。请画出相应的哈夫曼树并计算其带权路径长度WPL。 29.图G=（V,E），V={0,1,2,3,4,5},E={<0,1>,<0,2>,<1,4>,<2,5>,<5,4>,<4,3>,
<5,4>,<4,3>,<5,3>}。用邻接矩阵存储，算法中用栈存放无前趋顶点。根据算法，写出图G
中的拓扑排序序列。 30.设记录的关键字集合key={51,28,86,70,90,7,30,40,25},试写出对key 进行“希尔排列”（d=5,3,1）和“快速排序”时，各趟排序结果后的结果。
四、读程序填空题（本大题共4小题，每小题5分，共20分）
31.下列为在单链表中删除一个结点的算法。
Void Demo2(LinkList head,ListNode*p)
{ //head是带头结点的单链表，删除 p 指向的结点
ListNode*q=head;
While (q&&__(1)___) q=q->next; if q error(“*p not in head”); __(2)__; __(3)__;
}
32.下列函数是按从小到大的次序输出二叉排序树的各特点。 Void order(BinTree T) { if (___(1)___) {___(2)___;
printf(“%d”,T->data); ____(3)____; } }
33.完成下列深度优先遍历算法。 Void DFS(ALGraph*G int i ) { EdgeNode*P;
printf(“DFS vext ex %c\\n”,G->adjlist[i] .vextex); visited[i]=TURE; ____(1)____; while(p)
{if (___(2)___)DFS(G,p->adjvex); ____(3)____; }
34.下列函数完成的功能是将整数组A的元素按值递增的次序重新排列。在空格处填入适
当的句子，使该过程能完成预期的功能；该过程使用的是什么排序方法？ Void sort (int A[500],int n)
{ int i,j,x; boolean b;
b=ture; i=1;
while ((i {b=false; for( j=0;j<__(1)___;j++) if (___(2)____) { x=A[j];A[j]=A[j+1];A[j+1]=x; ____(3)___; } i++; } }