数据结构(C)复习思考题三及答案.pdfVIP

数据结构（C）复习思考题三及答案

一、单选题（每题2分，共20分）

1、研究数据结构就是研究（D）。

A、数据的逻辑结构

B、数据的存储结构

C、数据的逻辑结构和存储结构

D、数据的逻辑结构、存储结构及其基本操作

2、线性表采用链式存储时，结点的存储地址（B）。

A、必须是不连续的

B、连续与否均可

C、必须是连续的

D、和头结点的存储地址相连续

3、算法指的是（D）。

A、计算机程序B、解决问题的计算方法

C、排序算法D、解决问题的有限运算序列

4、用链接方式存储的队列，在进行插入运算时（D）。

A、仅修改头指针B、头、尾指针都要修改

C、仅修改尾指针D、头、尾指针可能都要修改

5、以下数据结构中哪一个是非线性结构？（D）

A、队列B、栈C、线性表D、二叉树

6、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（A）。

2

A、O(n)B、O(1)C、O(n)D、O(n-1)

7、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的

移动次数为：(A)。

A、n–i+1B、n–iC、iD、i–1

8、下述哪一条是顺序存储结构的优点？（C）。

A、插入运算方便B、可方便地用于各种逻辑结构的存储表示

C、存储密度大D、删除运算方便

9、二叉树的深度为k，则二叉树最多有（C）个结点。

k-1k

A、2kB、2C、2-1D、2k-1

10、字符串的长度是指（C）。

A、串中不同字符的个数B、串中不同字母的个数

C、串中所含字符的个数D、串中不同数字的个数

二、填空题（每空2分，共20分）

1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，

一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，

则栈的容量至少应该是3。

2、n个顶点的连通图至少有n-1条边。

3、数据的物理结构主要包括__顺序存储结构__和__链式存储结构__两种情况。

4、设一棵完全二叉树中有500个结点，则该二叉树的深度为___9___；若用二叉

链表作为该完全二叉树的存储结构，则共有___501_____个空指针域。

5、通常从四个方面评价算法的质量：时间正确性、占用内存易读性、复杂

度强壮性和准确度高效率。

6、设完全有向图中有n个顶点，则该完全有向图中共有n(n-1)条有向条；

设完全无向图中有n个顶点，则该完