2001-2002学年度第二学期“开放本科”期末考试
数据结构试题
一、单选题（每小题2分，共20分）
1、向顺序栈中压入新元素时，应当（ A ）。
A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行
2、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ B ）。
A．O（nlog2e） B．O（n+e） C．O(ne) D．O(n2)
3、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 4、线性链表不具有的特点是（ A ）。
A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 5、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ A ）位置。
A．32 B．33 C．41 D．65 6、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ A ）个。
A．n-1 B．n C．n+1 D．n+2 7、具有65个结点的完全二叉树的高度为（ D ）。（根的层次号为0）
A．8 B．7 C．6 D．5 8、若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ A ）方法比较次数最少。
A．直接插入排序 B．快速排序 C．归并排序 D．直接选择排序 9、在一个无向图中，所有顶点的度数之和等于所有边数的（ B ）倍。 A．3 B．2 C．1 D．1/2 10、对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，