数据结构复习题A.doc

1、1 数据结构复习题 第 1 章 绪论 一、单选题（共有题目 8 题） 1.从一维数组 an中顺序查找出一个最大值元素的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n2) D. O(n!) 标准答案： B 2.输出一个二维数组 bmn中所有元素值的时间复杂度为（ ）。 A. O(m+n) B. O(m n) C. O(m2) D. O(n2) 标准答案： B 3.下面程序段的时间复杂度是（ ）。 for( int i=0;ih) return 1; else return 0; 请问该算法的功能是什么？它的 时间复杂度数量级是哪个？ 标准答案：判断整数 n 是不是素数； O(

2、n) 三、填空题（共有题目 14 题） 1.在 线性结构 中，前驱结点和后继结点之间存在着 1 对 1(1： 1 或 一对一 )的联系。 2.对算法评价一般从正确性、 健壮性、 可读性、简单性、 时间复杂度、空间复杂度 六个方面进行的。 3.在图形结构中，前驱和后继结点之间存在着 多对多 ;m： n 的联系。 4.数据结构研究的内容主要包括 数据的逻辑结 构、 数据的存储结构（数据的物理结构） 和数据的 操作 三部分。 5.数据的物理结构又名 存储结构 _，它主要有 顺序存储、链接存储、索引 和 散 列 4 种方式。 6.在 树形结构 中，前驱和后继结点之间存在着 1 对多（ 1： N） 联系

3、。 7.数据的逻辑结构被分为 集合结构、线性结构、树形结构、图形结构 4 种。 8.算法 是指对特定问题求解步骤的一种描述，是一组指令的有限序列；也可以说是解决特定问题的方法步骤。 9.在一个算法的程序描述中，不同的语句重复执行的次数不同，某语句重复执行的次数称为该语句的 频度（频次） 。 10.记录（数据记录） 是数据处理领域组织数据的基本单位。 11.依据视点的不同，数据结构分为 数据的逻辑结构 和 物理结构 。 数据的逻辑结构 是面向问题的， 数据的物理 结构（数据的存储结构） 是面向计算机的。 12.算法应具备 有穷性 、确定性、 可行性 、输入和输出五个特性。 13.在下面程序段中，

4、 s=s+p 语句的执行次数是 n， p*=j 语句的执行次数是 n(n+1)/2，该程序段的时间复杂度为 O(n 2)。 int i=0,s=0; while(+inext; B. L- next = L- next - next; C. L = L; D. L- next = L; 标准答案： B 4. 给定有 n 个元素的数组，建立一个有序单链表的时间复杂度是（ ） A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 标准答案： B 5.在一个单链表 HL 中，若要删除由指针 q 所指向结点的后继结点，则执行（ ）。 A. p=q-next;p-next=q-ne

5、xt; B. p=q-next;q-next=p; C. p=q-next;q-next=p-next; D. q-next=q-next-next;q-next=q; 标准答案： C 6.在一个长度为 n 的顺序表中删除第 i 个元素（ 0 i n-1）时，需要从前向后依次前移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 标准答案： C 7.若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用 ( )存储方式节省时间。 A. 单链表 B. 双链表 C. 单循环链 表 D. 顺序表 标准答案： D 8.不带头结点的单链表 first 为空的判定条件是（ ）

6、。 A. first = NULL; B. first- next = NULL; C. first- next = first; D. first != NULL; 标准答案： A 9.执行下面程序段时，执行 S 语句的次数为 ( )。 for(int i=1; ilink 所指向的结点，则应执行的操作是（ ）。 A. p-link=p-link-link; B. p=p-link; p-link=p-link-link; C. p-link=p; D. p=p-link-link; 标准答案： A 11. 一个数组元素 ai 与 ( )的表示等价。 A. *(a+i) B. a+i C.

7、*a+i D. B. first- next =NULL; C. first- next =first; D. first!=NULL; 标 准答案： B 16. 一个算法的时间复杂度为 (3n2+2nlog2n+4n-7)/(5n)，其数量级形式的复杂度表示为 ( )。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 标准答案： A 17.某算法仅含程序段 1 和程序段 2，程序段 1 的执行次数 3n2，程序段 2 的执行次数为 0.01n3，则该算法的时间复杂度为（ ）。 A. O(n) B. O(n2) C. O(n3) D. O(1) 标准答案：

8、C 19.有一个含头结点的单链表，头指针为 head，则判断其是否为空的条件为 ( )。 A.head=NULL B. Head-next=NULL C. head-next=head D. Head!=NULL 标准答案： B 20. 设有一个 n n 的对称矩阵 A，将其上三角部分按行存放在一个一维数组 B中， A00存放于 B0中，那么第 i 行的对角元素 Aii存放于 B中（ ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 标准答案： C 21.在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 与

9、p 之间插入结点 s，则执行（ ）。 A. s next = p next; p next = s; B. p next = s; s next = q; C. p next = s next; s next = p; D. q next = s; s next = p; 标准答案： D 22.在一个长度为 n 的顺序存储的线性表中，删除第 i 个元素（ 1 i n）时，需要从前向后依次 前移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 标准答案： A 23.设单链表中结点的结构为（ data, link）。已知指针 q 所指结点是指针 p 所指结点的直接前驱，若

10、在 *q 与*p 之间插入结点 *s，则应执行的操作是（ ）。 A. s-link=p-link; p-link=s; B. q-link=s; s-link=p; C. p-link=s-link; s-link=p; D. p-link=s; s-link=q; 标准答案： B 24.在一个长度为 n 的有序顺序表中搜索值为 x 元素的时间效率最高的算法的渐进时间复杂度为（ ）。 A. O(1) B. O(1) C. O(log2n) D. O(n) 标准答案： C 25.在一个单链表 HL 中，若要在指针 q 所指向结点的后面插入一个由指针 p 所指向的结点，则执行（ ）。 A. q-n

11、ext=p-next; p-next=q; B. p-next=q-next; q=p; C. q-next=p-next; q-next=p; D. p-next=q-next; q-next=p; 标准答案： D 26.已知 L 是一个不带表头的单链表，在表首插入结点 *p 的操作是（ ）。 5 A. p = L; p- next = L; B. p- next = L; p = L; C. p- next = L; L = p; D. L = p; p- next = L; 标准答案： C 27.设单循环链表中结点的结构为（ data, link），且 rear 是指向非空的带表头 结点

12、的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ ）。 A. s = rear; rear = rear-link; delete s; B. rear = rear-link; delete rear; C.rear = rear-link-link; delete rear; D.s = rear-link-link; rear-link-link = s-link; delete s; 标准答案： D 28.某算法的时间代价为 T(n)=100n+10nlog2n+n2+10，其时间复杂度为（ ）。 A. O(n) B. O(nlog2n) C. O(n2) D.

13、O(1) 标准答案： C 29.在一个长度为 n 的顺序表中向第 i 个元素（ 0 i n-1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 标准答案： A 30.在一个长度为 n 的顺序表的任一位置插入一个新元素的时间复杂度为（ ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 标准答案： A 31.多维数组实际上是由嵌套的（ ）实现的。 A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量 标准答案： A 32.设有一个 n n 的对称矩阵 A，将其下三角部分按行存放在一个一维数组 B

14、中， A00存放于 B0中，那么第 i 行的对角元素 Aii存放于 B中（ ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 标准答案： A 33.利用双向链 表作线性表的存储结构的优点是（ ）。 A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作 C. 节省空间 D. 便于销毁结构释放空间 标准答案： B 34.在数据结构的讨论中把数据结构从逻辑上分为（ ）。 A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构 标准答案： C 35.单链表 A

15、长度为 m，单链表 B长度为 n，若将 B联接在 A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n) 标准答案： B 36.带表头的双向循环链表的空表满足（ ）。 A. first NULL; B. first-rLink=first C. first-lLink=NULL D. first-rLink=NULL 标准答案： B 37.一个记录 r 理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为 ( )。 A. 所有域长度之和 B. 最大域所占字节长度 C. 任意一个域长度 D. sizeof(r)的

16、值 6 标准答案： D 38.采用顺序搜索方法查找长度为 n 的顺序表时，搜索成功的平均搜索长度为（ ）。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 标准答案： D 39.在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0 个 B. 1 个 C. 2 个 D. n 个 标准答案： C 40.设单链表中结点的结构为（ data, link）。已知指针 p 所指结点不是尾结点，若在 *p 之后插入结点 *s， 则应执行的操作是（ ）。 A. s-link=p; p-link=s; B. p-link=s; s-link=p; C. s-link=p-link;

17、p=s; D. s-link=p-link; p-link=s; 标准答案： D 41.非空的循环单链表 first 的尾结点（由 p 所指向）满足的条件是（ ）。 A. p-link=NULL; B. p=NULL; C. p-link=first; D. p=first; 标 准答案： C 42.从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需要平均比较的结点数是（ ）。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 标准答案： D 43.采用线性链表表示一个向量时，要求占用的存储空间地址（ ）。 A. 必须是连续的 B. 部分地址必须

18、是连续的 C. 一定是不连续的 D. 可连续可不连续 标准答案： D 44.在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 标准答案： B 45.在一个长度为 n 的顺序存储的线性表中，向第 i 个元素（ 1 i n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 标准答案： B 46.在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行（ ）。 A. HL=p; p-next=HL;

19、B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. p-next=HL-next; HL-next=p; 标准答案： B 47.下面程序段的时间复杂度为 ( )。 for(int i=0; inext=NULL 和 HL-next=HL。 2.线性表的链接存储只能通过 链接指针 顺序访问。 3.链表是一种采用 链式（或链接 _） 存储结构存储的线性表。 4.在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为 p，则其后继结点的地址为 p-next，后继结点的值为 p-next-data。 5.若设 L 是指向带表头的单链表 , 语句 L-link=

20、L-link-link 的作用是 删除 单链表中的第一个结点。 6.在单链表中除了表头结点外，任意结点的 存储位置由其 直接前驱 结点的指针域的值所指示。 7.在双向链表中，每个结点包含两个指针域，一个指向其 前驱（双亲、父） 结点，另一个指向其后 继（孩子、子） 结点。 8.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地 分配 _和释放。 9.在链表中进行插入和 删除 操作的效率比在顺序存储结构中进行相同操作的效率高。 10.在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为 p， p 为一个数组 a 中的下标，则其后继结点的地址为 char * a = new ch

21、armaxSize; 错 9.线性表若采用链式存储表示 , 在删除时不需要移动元素。 对 10.数据的逻辑结构与数据元素本身的内容和形式无关。 对 11. 如果采用如下方式定 义一维字符数组： const int maxSize = 30; char amaxSize; 则这种数组在程序执行过程中不能扩充。 对 12.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。 错 13. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。 对 14.在线性链表中删除中间的结点时，只需将被删结点释放。 错 四、程序填空题（共有题目 3 题） 1.下面程序段实现的功能是向单链表的表头插入一个元素

22、 X，请补充完整程序。 void InsertFirstList(struct sNode *HL,ElemType x) struct sNode *newp; newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(“内存动态空间用完，退出运行！ n“); exit(1); newp-data=X; newp-next=*HL; *HL=newp; 2.下面程序段实现的功能是向单链表的表尾插入一个元素 X，请补充完整程序。 void InsertLastList(struct sNode *HL,ElemType x) struct s

23、Node *newp; newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(“内存动态空间用完，退出运行！ n“); exit(1); newp-data=x; newp-next=NULL 或 0; if(*HL=NULL) *HL=newp; Else struct sNode *p=*HL; while(p-next!=NULL) p=p-next; p-next=newp; 9 3.欲向线性表 L 的表头插入元素 X，完成下面程序段中的部分语句： void InsertFirstList( struct List *L,Elem

24、Type X) int i; if(_L-size=L-MaxSize) againMalloc(L); for(i=L-size-1;i=0;i-) L-listi+1=L-listi; L-list0=X; L-size+; 第 3 章 稀疏矩阵和广义表 一、单选题（共有题目 4 题） 1.设一个具有 t 个非零元素的 m n 大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为（ ）。 A. O(m) B. O(n) C. O(n+t) D. O(n t) 标准答案： D 2.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。 A. 行号 B.

25、 列号 C. 元素值 D. 地址 标准答案： A 3.广义表 ( )的表头是 ( )。 A. ( ) B. 没有表头 C. ( ) D. 0 标准答案： B 4.广义表 ( )的表尾是 ( )。 A. 没有表尾 B. ( ) C. ( ( ) ) D. 0 标准答案： A 二、填空题（共有题目 16 题） 1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 行号、列号 和 元素值 3 项。 2.( ),(e),(a,(b,c,d)的表头是 () 或 空表 。 3.一个广义表中的元素分为 单（原子） 元素和 表（子表） 元素两类。 4.在广义表的存储结构中，单元素结点与表元素结点有一个

26、域对应 不同，各自分别为 值 域和 子表指针 域。 5.一个广义表的深度等于 括号 嵌套的最大层次数。 6.稀疏矩阵是一种非零元素的个数 远远小于 零元素的个数，且非零元素的分布没有规律的矩阵。 7.广义表 ( )的表头是 ( ) 或 空表 。 8.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应 大于 对应三元组线性表的长度。 9.广义表 (e),(a,(b,c,d)的深度是 3。 10.广义表 ( ( ) )的表尾是 ( ) 或 空表 。 11.( ),(e),(a,(b,c,d)的表尾是 (e),(a,(b,c,d)。 12.在一个广义表的存储结构中，每个结点均包含有

27、_3 个域。 13.广义表 (e),(a,(b,c,d)的长度是 2。 14.在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有 4 个域，在相应的十字链接存储中，每个结10 点包含有 5 个域。 15.在稀疏矩阵的十字链接存储中，每个结点的 down 指针域指向 列号 相同的下一个结点， right 指针域指向行号 相同的下一个结点。 16.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 行号 为主序 列号 为辅序的次序排列。 三、判断题（共有题目 1 题） 1.使用三元组表示 稀疏矩阵中的非零元素能节省存储空间。 对 第 4 章 栈和队列 一、单选题（共有题目 9 题） 1.在一个顺

28、序队列中，队首指针指向队首元素的（ ）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 标准答案： A 2.假定利用数组 aN循环顺序存储一个队列，用 f 和 r 分别表示队首和队尾指针，并已知队未空，当进行出队并返回队首元素时所执行的操作为 ( )。 A. return a+r%N; B. return a-r%N; C. return a+f%N; D. return af+%N; 标准答案： C 3.一个链栈的栈顶指针用 top 表示，当进行退栈时所进行的指针操作为（ ）。 A. top-next=top; B. top=top-data; C. top=top-next; D

29、. top-next=top-next-next; 标准答案： C 4.一个链栈的栈顶指针用 top 表示，当 p 所指向的结点进栈时，执行的操作为（ ）。 A. p-next =top; top=top-next; B. top=p; p-next=top; C. p-next=top-next;top-next=p; D. p-next=top;top=p; 标准答案： D 5.栈的插入和删除操作在（ ）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 标准答案： A 6.当利用大小为 N 的数组顺序存储一个队列时，若没设有队列长度的变量，则该队列的最大长度为（ ）。 A.

30、N-2 B. N-1 C. N D. N+1 标准答案： B 7.若让元素 1、 2、 3 依次进栈，则出栈次序不可能出现（ ）情况。 A. 3， 2， 1 B. 2， 1， 3 C. 3， 1， 2 D. 1， 3， 2 标准答案： C 8.从一个顺序队列删除元素时，首先需要（ ）。 A. 队首指针循环加 1 B. 队首指针循环减 1 C. 取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 标准答案： A 9.假定一个链队的队首和队尾指针分别为 front 和 rear，则判断队空的条件为 ( )。 A. front=rear B. front!=NULL C. rear!=NULL D. front=NULL 标准答案： D 二、填空题（共有题目 7 题） 1.后缀表达式“ 4 5 * 3 2 + -”的值为 15。 2.栈又称为 后进先出 表，队列又称为 先进先出 _表。 3.队列的插入操作在 队尾 进行，删除操作在 队首 进行。 4.中缀表达式 3*(x+2)-5 所对应的后缀表达式为 3 x 2 + * 5 -。 5.在一个链队中，若队首指针与队尾指针的值相同，则表示该队为 空 或该队 只含有一个结点 。