数据结构山东大学版

---

将算术表达式转化成逆波兰式形式，并输出

1：问题:数据处理时采用栈结构的依据是（ ）？

---

选项：

---

A:先进先出

---

B:后进后出

---

C:先进后出

---

D:插入在一端删除在另一端

---

答案: 【先进后出】

2：问题:数据处理时采用队列的依据是什么？

---

选项：

---

A:先进先出

---

B:后进先出

---

C:先进后出

---

D:插入删除在一端进行

---

答案: 【先进后出】

3：问题:最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是（　）。

---

选项：

---

A: (rear+1)%n==front

---

B:rear==front

---

C:rear+1==front

---

D:(rear-l)%n==front

---

答案: 【(rear+1)%n==front】

4：问题:若让元素1，2，3，4依次进栈，则出栈次序不可能出现在（ ）种情况。

---

选项：

---

A:4，3，2，1

---

B:2，1，4，3

---

C:4，3，1，2

---

D:2，3，4，1

---

答案: 【4，3，1，2】

完全二叉树的应用

1：问题:完全二叉树有199个节点，则叶子结点数为（ ）？

---

选项：

---

A:99

---

B:100

---

C:101

---

D:102

---

答案: 【100】

2：问题:设哈夫曼树中有199个结点，则该哈夫曼树有（ ）叶子结点.

---

选项：

---

A:99

---

B:100

---

C:101

---

D:102

---

答案: 【100】

3：问题:一个具有1025个结点二叉树的高h 为（ ）

---

选项：

---

A:10

---

B:11

---

C:111025

---

D:101024

---

答案: 【11~1025】

4：问题:下面不是二叉树的应用是（ ）？

---

选项：

---

A:排序

---

B:文本压缩

---

C:查找

---

D:拓扑排序

---

答案: 【拓扑排序】

网络搜索引擎工作原理分析。

1：问题:图的深度优先遍历类似于树的（ ）？

---

选项：

---

A:先序遍历

---

B:中序遍历

---

C:后序遍历

---

D:层次遍历

---

答案: 【先序遍历】

2：问题:图的广度优先遍历类似于树的（ ）？

---

选项：

---

A:先序遍历

---

B:中序遍历

---

C:后序遍历

---

D:层次遍历

---

答案: 【层次遍历】

3：问题:如果一个图需要频繁进行插入顶点的操作，那么这个图最好采用（ ）存储。

---

选项：

---

A:邻接矩阵

---

B:邻接表

---

C:十字链表

---

D:二叉链表

---

答案: 【邻接表】

4：问题:网络搜索引擎采集网页时运用了下面哪些数据结构的知识（ ）？

---

选项：

---

A:图的遍历

---

B:二叉树遍历

---

C:线性表的查找

---

D:集合的查找

---

答案: 【图的遍历】

内排序方法的比较

1：问题:待排序记录基本有序条件下，下面排序方法中，效率最高的是（ ）。

---

选项：

---

A:归并排序

---

B:选择排序

---

C:冒泡排序

---

D:插入排序

---

答案: 【插入排序】

2：问题:待排序记录规模较大，且分布随机，在对稳定性不作要求的情况下，优先选择的排序方法是（ ）？

---

选项：

---

A:希尔排序

---

B:快速排序

---

C:冒泡排序

---

D:堆排序

---

答案: 【快速排序】

3：问题:下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。

---

选项：

---

A:希尔排序

---

B:快速排序

---

C:冒泡排序

---

D:堆排序

---

答案: 【希尔排序】

4：问题:下述几种排序方法中，要求辅助空间最大的是（ ）

---

选项：

---

A:希尔排序

---

B:快速排序

---

C:归并排序

---

D:堆排序

---

答案: 【归并排序】

第一章 单元测试

1：问题:数据结构的形式定义是（D, S），其中D是数据元素的有限集，S是D上的关系有限集。

---

选项：

---

A:对

---

B:错

---

答案: 【对】

2：问题:在数据结构中，从层次上可以把数据结构分成 。

---

选项：

---

A:动态结构和静态结构

---

B:顺序存储结构和链式存储结构

---

C:线性结构和非线性结构

---

D:逻辑结构和存储结构

---

答案: 【逻辑结构和存储结构】

3：问题:线性表若采用链式存储结构时，要求内存中可用的存储单元的地址 。

---

选项：

---

A:必须是连续的

---

B:部分地址必须是连续的

---

C:一定是不连续的

---

D:连续不连续都可以

---

答案: 【连续不连续都可以】

4：问题:下面程序的时间复杂度为 。for（i=0; iO（m×n）】

5：问题:若需要利用形参直接访问实参，则应把形参变量说明为 参数。

---

选项：

---

A:指针

---

B:引用

---

C:void

---

D:值

---

答案: 【引用】

第二章 单元测试

1：问题:带头结点的单链表L为空的判定条件是 。

---

选项：

---

A:L= =NULL

---

B:L→next= =NULL

---

C:L→next= =L

---

D:L!=NULL

---

答案: 【L→next= =NULL】

2：问题:非空的循环单链表L的尾结点（由p所指向）满足 。

---

选项：

---

A:p→next = =NULL

---

B:p= =NULL

---

C:p→next= =L

---

D:p= =L

---

答案: 【p→next= =L】

3：问题:在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行 。

---

选项：

---

A:s→next=p→next; p→next=s

---

B:p→next=s→next; s→next=p

---

C:q→next=s; s→next=p

---

D:p→next=s; s→next=q

---

答案: 【q→next=s; s→next=p】

4：问题:在一个单链表中，若删除p所指结点的后继结点，则执行 。

---

选项：

---

A:p→next=p→next→next

---

B:q=p→next; p→next=q→next

---

C:p→next=p→next

---

D:p=p→next→next

---

答案: 【q=p→next; p→next=q→next】

5：问题:在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的算法的时间复杂度为 。

---

选项：

---

A:O（1）

---

B:O（n）

---

C:O（n2）

---

D:O（nlog2n）

---

答案: 【O（n）】

第三章 单元测试

1：问题:一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是 。

---

选项：

---

A:EDCBA

---

B:DECBA

---

C:DCEAB

---

D:ABCDE

---

答案: 【DCEAB】