数据结构考试题(求几道数据结构选择题答案)

1．C

2．D

3．C

4．C

5．B）O(log2n) （D）O(log2n)

6．B

7．C

8．D

9．有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（）

（A）35/12 （B）37/12 （C）39/12 （D）43/12

10.D

11．A

12．堆的 C) 完全二叉树 D) 平衡二叉树

13．C

14．若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为：

A) 79，46，56，38，40，84

B) 84，79，56，38，40，46

C) 84，79，56，46，40，38

D) 84，56，79，40，46，38

15．若一组记录的关键码为（46，79，56，38，40，84），则利用快速序的方法，以第一个记录为基准得到的第一趟结果为

A) 38，40，46，56，79，84

B) 40，38，46，79，56，84

C）40，38，46，56，79，84

D) 40，38，46，84，56，79

16．B

17.下列关键字序列中 是堆

A 94，23，31，72，16，53 B 16，72，31，23，94，53

C 16，23，53，31，94，72 D 16，53，23，94，31，72

（ × ）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（ × ）2. 链表的物理存储结构具有同链表一样的顺序。

错，链表的存储结构特点是无序，而链表的示意图有序。

（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

错，链表的结点不会移动，只是指针内容改变。

（ × ）4. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”

（ × ）5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（ × ）6. 线性表在物理存储空间中也一定是连续的。

错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。

（ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。

（ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。