数据结构B复习题

1、华北科技学院 200_/ 20_学年第_学期数据结构B考试试卷 考试科目：数据结构B 选用试卷A_适用专业： 题目 -一一 -二 三 四 五 六 七 八 九 十 总分 得分 一、选择题(每题2分，共10题，总计20分) i 封1、算法的时间复杂度取决于() A.问题的规模 B.待处理数据的初态C. A 和B 2、在下面的程序段中，对 x的赋值语句的频度为() for (i=1; i=n; i+) for (j=1; j=n; j+) x=x+1; A. O(2n) B . 0(n) C . 0(n2)D . O(log 2) 3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和

2、删除运算，则利用 装 ()存储方式最节省时间。 A.顺序表 B.双链表C.带头结点的双循环链表D .单循环链表 4、对于顺序存储的线性表，访问结点和增加结点的时间复杂度为()。 A. O(n) O(n) B. O(n) O(1)C. O(1) O(n)D. O(1) O(1) 5、 假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地 址为 10,则 LOC5，5=()。 A. 808B. 818C. 1010D. 1020 订6、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F对应的二叉 树根结点的右子树上的结

3、点个数是()。 A. M1 B M1+M2 C . M3 D M2+M3 7、设给定权值总数有 n个，其哈夫曼树的结点总数为 () A.不确定B . 2n C . 2n+1 D . 2n-1 如f(abba) 返回1, f(abab)返 回0; int f(1) int i=0,j=0; while (sj)(2); for(j-; ij i+,j-); return(3) 3、写出下图的关键路径以及拓扑排序。 4、现有含8个元素的无序序列（49, 38, 65, 97, 76, 13, 27, 50）,要求画出构造小顶堆的过程。 四、首先将如下图所示的无向图给出其存储结构的邻接链表表示（按字

4、母顺序），然后写出对其分别进行 深度、广度优先遍历的结果 （均从顶点a开始）（本题8分） 五、算法设计：写出统计二叉树中叶子结点的个数的算法（适当加注释）。（本题8分） 七、设有下列递归算法： int vol( int n) int x,s; if (n=0) the n s=0; else scanf(“ d， s=vol(n_1)+x； （本题10分） 六、用普里姆算法算法求下图的最小生成树，要求写出邻接矩阵及求解的详细过程。 return(s); 如该函数被调用时，参数n值为4,读入的x值依次为5,3,4,2 ，函数调用结束时返回值为多少？用图示 描述函数执行过程中，递归调用的变化过程。

5、(本题10分) Whe n you are old and grey and full of sleep, And nodding by the fire, take dow n this book, And slowly read, and dream of the soft look Your eyes had once, and of their shadows deep; How many loved your mome nts of glad grace, And loved your beauty with love false or true, But one man loved

6、 the pilgrim soul in you, And loved the sorrows of your cha nging face; And bending dow n beside the glow ing bars, Murmur, a little sadly, how love fled And paced upon the mountains overhead And hid his face amid a crowd of stars. The furthest dista nee in the world Is not betwee n life and death B

7、ut whe n I sta nd in front of you Yet you dont know that I love you. The furthest dista nee in the world Is not whe n I sta nd in front of you Yet you cant see my love But whe n un doubtedly knowing the love from both Yet cannot be together. The furthest dista nee in the world Is not being apart while being in love But whe n I pla inly cannot resist the year ning Yet prete nding you have n ever bee n in my heart. The furthest dista nee in the world Is not str