全国2012年1月自考《数据结构导论》试题_第2页

11.具有n个顶点的无向图的边数最多为(      )
A.n+1                                                              B.n(n+1) 
C.n(n-1)/2                                                       D.2n(n+1)
12.三个顶点v1,v2,v3的图的邻接矩阵为 ，该图中顶点v3的入度为(      )
A. 0                                                                B. 1 
C. 2                                                                D. 3
13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为(      )
A.20000                                                          B.30000 
C.40000                                                          D.60000
14.外存储器的主要特点是(      )
A.容量小和存取速度低                                    B.容量大和存取速度低
C.容量大和存取速度高                                    D.容量小和存取速度高
15.在待排数据基本有序的前提下，效率最高的排序算法是(      )
A.直接插入排序                                              B.直接选择排序 
C.快速排序                                                     D.归并排序
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.数据的不可分割的最小标识单位是______，它通常不具有完整确定的实际意义，或不被当作一个整体对待。
17.运算分为加工型运算和引用型运算，读取操作是______ 运算。
18.带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是 ______。
19.在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句 ______。
20.元素s1，s2，s3，s4，s5，s6依次进入顺序栈S，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 ______。
21. 稀疏矩阵一般采用的压缩存储方法是______ 。
22. 在一棵树中，______ 结点没有双亲。
23.一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为 ______。
24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是______。
25.边稀疏的无向图采用 ______存储较省空间。
26.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为 ______。
27.二分查找算法的时间复杂度是 ______。
28.要将序列{51，18，23，68，94，70，73}建成堆，则只需把18与 ______相互交换。