文档介绍：北京理工大学远程教育学院2016学年第一学期
数据结构考试卷（A卷）
姓名： 学号： 成绩：
单项选择题（每空2分共30分，答案请写在后面的答题纸上）
数据结构研究的内容是__________、2、3
下面程序段的时间复杂度为__________________。
for(inti=1; i<m; i++)
for(int j=1; j<n; j++)
a[i][j] = i*j;
A. O(m) B. O(n) C. O(m*n) D. O(m+n)
若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是________。
A. 9 B. 11 C. 15 D. 不确定
首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为
____________。
A. 前序遍历 B. 后序遍历 C. 中序遍历 D. 层次遍历
按照二叉树的定义，具有3个结点的不同形状的二叉树有________种。
A. 3 B. 4 C. 5 D. 6
从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较________个结点。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
栈和队列的共同点是
A. 都是先进后出 B, 都是先进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点
一个有n个顶点的无向图最多有________条边。
A. n B. n (n-1) C. n (n-1)/2 D. 2n
二、是非判断题（每空2分共20分）
1. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（）
2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）
3. 二叉树中任何一个结点的度都是2。（）
4. 有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。（）
5. 线性表的特点是每个元素都有一个前驱和一个后继。（）
6. 按中序遍历二叉排序树所得到中序序列是一个递增有序序列。（）
7. 串的长度是指串中所含不同字母的个数。（）
8. n (n>1)个顶点的无向连通图最少有 n-1 条边。（）
9. 四种插入排序中，shell 排序记录移动的次数最少。（）
10. 非空二叉排序树其根结点的值大于其非空左孩子的值。（）
三、填空题（每空2 共22分）
数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
队列的插入操作是在队列的_______进行，删除操作是在队列的进行。
对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。
设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从