内容发布更新时间 : 2024/6/17 19:31:52星期一 下面是文章的全部内容请认真阅读。

《数据结构》单元测试1

一、选择题（每题2分，共40分） 1．数据的最小单位是（ A）。

(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 2. 栈和队列的共同特点是( A )。 (A)只允许在端点处插入和删除元素 (B)都是先进后出 (C)都是先进先出 (D)没有共同点

3. 用链接方式存储的队列，在进行插入运算时( D )。 (A)仅修改头指针 (B)头、尾指针都要修改 (C)仅修改尾指针 (D)头、尾指针可能都要修改 4. 以下数据结构中哪一个是非线性结构？( D ) (A)队列 (B)栈 (C)线性表 (D)二叉树

5．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。 (A) “STRUCTURE” (B) “DATA”

(C) “ASTRUCTUR” (D) “DATASTRUCTURE” 6．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)

7．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ B）。

(A) Nl+N2+……+Nm (B) 1+N2+2N3+3N4+……+(m-1)Nm

(C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm 8．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B）次。

(A) 25 (B) 10 (C) 7 (D) 1 9. 二叉树的第k层的结点数最多为( D )。

(A)2k-1 (B) 2K+1 (C) 2K-1 (D)2k-1 10. 树最适合用来表示( C )。

(A)有序数据元素 (B)无序数据元素

(C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据 11.n个权构成一棵Huffman树，其节点总数为( A )。 (A)2n-1

(B) 2n

(C) 2n+1

(D)不确定

12．下面程序的时间复杂为（B ）

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)

13．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ A）。

(A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)；

14．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D）。

(A) n，e (B) e，n (C) 2n，e (D) n，2e

15. 设某强连通图中有n个顶点，则该强连通图中至少有（ C）条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1) 16．下面关于线性表的叙述错误的是（ D ）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现

17．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

18．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 19．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA

20．设某完全无向图中有n个顶点，则该完全无向图中有（ A）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 二、填空题（每题2分，共28分）

1. 在有n个结点的二叉链表中，空链域的个数为____n+1_____。