数据结构B复习题.doc

数据结构B复习题.doc华北科技学院
200_ / 20学年第 学期数据结构B考试试卷
考试科目：数据结构B 选用试卷土 适用专业：
题目
―*
二
三
四
五
六
七
八
九
十
总分
得分
| 一、选择题(每题2分，共10题，总计20分)
| 1、算法的时间复杂度取决于( )
封 C. A和B
:2、在下面的程序段中，对x的赋值语句的频度为( )
: for (i=l; i<=n; i++)
: for (j=l: j<=n; j++)
i x=x+l;
: A. 0(2n) B. 0(n) C. 0(n2) D. 0(logD
| 3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 装 ( )存储方式最节省时间。
； B,双链表
| 4、对于顺序存储的线性表，访问结点和增加结点的时间复杂度为( )。
| A. 0(n) 0(n) B. 0(n) 0(1) C. 0(1) 0(n) D. 0(1) 0(1)
I 5、假设以行序为主序存储二维数组A=array[l. . 100, 1.. 100],设每个数据元素占2个存储单元，基地
: 址为 10,贝ijL0C[5, 5]= ( )o
: A. 808 B. 818 C. 1010 D. 1020
订6、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为Ml, M2和M3。与森林F对应的二叉
: 树根结点的右了树上的结点个数是( )o
: A. Ml B. M1+M2 C. M3 D. M2+M3
| 7、设给定权值总数有n个，其哈夫曼树的结点总数为()
j B. 2n C. 2n+l D. 2nT
! 8、有六个元素6, 5, 4, 3, 2, 1的顺序进栈，问下列哪一个不是合法的出栈序列( )
: A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
线9、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数( )
1 A. 9 B. 11 C. 15
| 10、适用于折半查找的表的存储方式及元素排列要求为()
1 ，元素无序 ，元素有序
: ，元素无序 ，元素有序
I二、填空题(每空2分，共10空，总计20分)
：1、. —是限定仅在表尾进行插入或删除操作的线性表。
2、已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahf eg ,则该二叉树的后序序列为
3、 设无向图的顶点个数为n,则该图最多有 条边。
4、 具有256个结点的完全二叉树的深度为 o
5、 实现字符串拷贝的函数strcpy为：
void strcpy(char *s , char *t) /*copy t to s*/
{ while ()
}
6、 图有两种基本遍历的方法是：和广度遍历。
7、 己知有序表为(12, 18,24,35,47, 50,62,83,90, 115,