大工16春《数据结构》开卷考试复习资料

机密★启用前

大连理工大学网络教育学院

2016年9月《数据结构》课程

期末复习资料

☆ 注意事项：本复习题满分共：400分。

一、单项选择题（本大题共65小题，每小题3分，共195分）

1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。 (A).正确性 (B). 可行性 (C). 健壮性 (D). 输入性

2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。

for(i=n-1；i>=0；i--)

for(j=0；j

（A）、有序顺序表 （B）、有序单链表 （C）、有序顺序表和有序单链表都可以 （D）、无限制 4．顺序存储结构的优势是（ ）。

（A）、利于插入操作 （B）、利于删除操作 （C）、利于顺序访问 （D）、利于随机访问 5．深度为k的完全二叉树，其叶子结点必在第（ ）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k 6．具有60个结点的二叉树，其叶子结点有12个，则度为1的结点数为（ ） （A）、11 （B）、13 （C）、48 （D）、37 7.下列程序段的时间复杂度为（）。

for(i=0； i

for(i=0； i

9．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 10．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)

11．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。

(A) p->right=s； s->left=p； p->right->left=s； s->right=p->right； (B) s->left=p；s->right=p->right；p->right=s； p->right->left=s； (C) p->right=s； p->right->left=s； s->left=p； s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；

12．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ ）遍历方法的推广。

2

2

（A）、先序 （B）、中序 （C）、后序 （D）、层序 13．在上图列链队列Q中，元素a出队的操作序列为（ ）

（A）、p=Q.front->next; p->next= Q.front->next; （B）、p=Q.front->next; Q.front->next=p->next; （C）、p=Q.rear->next; p->next= Q.rear->next; （D）、p=Q->next; Q->next=p->next;

14． Huffman树的带权路径长度WPL等于（ ）

（A）、除根结点之外的所有结点权值之和 （B）、所有结点权值之和 （C）、各叶子结点的带权路径长度之和 （D）、根结点的值 15．线索二叉链表是利用（ ）域存储后继结点的地址。

（A）、lchild （B）、data （C）、rchild （D）、root 16．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 <4，1>}，则数据结构A是（ ）。

(A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合 18．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 19．二叉树中第i(i≥1)层上的结点数最多有（ ）个。 A．2i B．2i+1 C．2i-1 20. 对一个算法的评价，不包括如下（ ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 21. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 22. 对线性表，在下列哪种情况下应当采用链表表示？( )

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 23.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1

B. 3 2 1

C. 3 1 2 D. 1 2 3 24．下列各种排序算法中平均时间复杂度为O(n2)是（）。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序

25．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能确定 26．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 (A) 小于等于m的最大奇数 (B) 小于等于m的最大素数 (C) 小于等于m的最大偶数 (D) 小于等于m的最大合数

(D) 树

D．2i+2

(C) 数据元素

(D) 数据变量

17．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，

27．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。 (A) 4 (B) 5 (C) 6 (D) 7 28．设完全无向图中有n个顶点，则该完全无向图中有（）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 29． AOV网是一种（ ）。

A．有向图 B．无向图 C．无向无环图 D．有向无环图 30．采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找

31．若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 A．值 B．函数 C．指针 D．引用 32．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）。 A．行号 B．列号 C．元素值 D．非零元素个数 33．快速排序在最坏情况下的时间复杂度为（ ）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 34．从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n) B. O(1) C. O(log2n) D. O(n2) 35．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p

36．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。

(A) 6 (B) 4 (C) 3 (D) 2 37．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。 (A) 100 (B) 40

(C) 55 (D) 80

38．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ ）。 (A) 3 (B) 4 (C) 5 (D) 1 39．根据二叉树的定义，可知具有3个结点的二叉树共有（ ）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 40. 设有以下四种排序方法，则（ ）的空间复杂度最大。

(A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希尔排序 41．设某无向图有n个顶点，则该无向图的邻接表中有（ ）个顶点头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 42．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。 (A) n (B) n-1 (C) 2n (D) 2n-1

43．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 44．（）二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历

45．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 46．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)

47．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0

48．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 (A) 20 (B) 256 (C) 512 (D) 1024

49．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 (A) 1 (B) 2 (C) 3 (D) 4 50．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 51．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

52．用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 53．以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树 54．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3]存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 55．树最适合用来表示( )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 56．设顺序表的长度为n，则顺序查找的平均比较次数为（）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2

57．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 (A) 1 (B) 2 (C) 3 (D) 4

58．设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。 (A) 6 (B) 11 (C) 5 (D) 6.5

59．设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3

60．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。 (A) 4 (B) 5 (C) 6 (D) 7 61 ．二叉树的第k层的结点数最多为( ).