北京大学2016年春季学期《数据结构》课程作业资料

admin

2016年春季学期《数据结构》课程作业
一. 资料来源（谋学网www.mouxue.com），每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分）
1.数据的逻辑结构被形式地定义为B=(K,R),其中K是 ______的有限集合，R是K上的______的有限集合。
a 存储                  b 数据操作                        c数据元素                d操作
e逻辑结构               f 映象                            g算法                    h关系
2.以下关于算法的说法不正确的是______________。
a 一个算法应包含有限个步骤
b算法越简单越好
c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之
d算法中的每个步骤都能在有限时间内完成
3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是______________。
                a 线性结构                b 树型结构                c 物理结构                d 图型结构
            4.下面程序段的时间复杂度为______
int sum=0;
                        for(i=0; i<m;i++)
for(j=i;j<n;j++)
                                  s++;
a. O(m+n)             b. O(n*n)                          c. O(m*n)                  d. O(m*logn)
5. 下列有关线性表的叙述中，正确的是________。
a 一个线性表是 n 个数据元素的有限序列
b 线性表中任何一个元素有且仅有一个直接前驱
c 线性表中任何一个元素有且仅有一个直接后继
d 以上说法都不正确
6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为______
a．n                                b．(n-1)/2                        c．n/2                                d．(n+1)/2
7. 若栈采用链式存储结构,则下面的说法中正确的是________
a.不需要判断栈满但需要判断栈是否为空
b.需要判断栈是否栈空与栈满
c.需要判断栈满但不需要判断栈空
d.栈满栈空都不需要判断
8. 在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为____________。
a  t->next=r;t=r;                 b r->next=s;s=r;
c s->next=r;s=r;                         d r->next=t;
9.链表不具备的特点是____________。
a不必事先估计存储空间               b 插入删除不需要移动元素
c        可顺序访问任一结点          d 所需空间与其长度无关
10.带附加头结点的双循环链表L为空表的条件是____________。
a L==NULL                                                   b L->next==NULL             
c L->prior==L                                         d L->prior==NULL
11.设广义表L=（a,（b,c,d））,则L的长度与深度分别为____________。
a 1和1                b 1和3                c 2和3                d 1和2
12.一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列______
a. 1, 2, 3, 4, 5, 6
b. 3, 2, 6, 4, 5, 1
c. 2, 4, 6, 5, 3, 1
d. 6, 5, 4, 3, 2, 1
13. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____________。
a (rear-front+m)%m                        b rear-front+1        
c rear-front-1                                d rear-front
14.栈和队列的共同特点是____________。
a.只允许在端点处插入和删除元素          b.都是先进后出   
c.都是先进先出                          d.没有共同点
15.中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是______
a．AB+D*E/FA+*DC+                                        b．ABD*+EFAD*+/C+
c．ABDEFADC+*+/+*+                                        d．AB+D*EFAD*+/+C+
16.如下图所示的4棵二叉树，_________不是完全二叉树。
                 
17. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为____________。
         a 9                        b 10                c 11                d 12
18. 深度为6(根的层次为1)的二叉树至多有__________结点
a.64                b.63                c.31                d.32
19.二叉树的第k层的结点数最多为____________。
a. 2k-1       b. 2K+1      c. 2K-1     d. 2k-1
20.如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是__________。
        a 空或只有一个结点                                b 高度等于其结点数
        c 任一结点无右孩子                                d 任一结点无左孩子
21. 树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论__________是正确的。
a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同  
b.树的后根遍历序列与其对应的二叉树的先序遍历序列相同  
c.树的先根遍历序列与其对应的二叉树的中序遍历序列相同  
d.以上都不对
22.根据使用频率为5个字符设计的哈夫曼编码不可能是____________。
a 100，111，110，101，0           b 111，110，10，01，00
c 000，001，010，011，01          d 001，000，01，11，10
23. 下列数据结构中,不属于二叉树的是____________
a. 堆                b. 哈夫曼树                c. 线索二叉树                d. B树
24.采用邻接表存储的图的广度优先遍历算法类似于二叉树的__________。
a 先序遍历                                        b 中序遍历
c 后序遍历                                        d 层次遍历
25.对用邻接表表示的图进行深度优先遍历时，通常是借助_________来实现算法。
a 队列            b栈            c 树             d 图
26. 在一个图中，所有顶点的度数之和等于图的边数的_________倍。
a. 1/2                        b. 1                        c. 2                        d. 4
27.对线性表进行二分查找，要求线性表必须____________。
a 以顺序方式存储                b 以顺序方式存储，且结点按关键字有序排序       
c 以链接方式存储                d 结点按关键字有序排序，存储方式无所谓
28.排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为____________。
a 选择排序                        b 冒泡排序
c 希尔排序                d 插入排序
29.下列四种排序中，____________是最不稳定的。
         a. 选择排序        b. 冒泡排序        c. 归并排序        d. 快速排序
二. 填空题，请将正确资料填在____上。（每空1分，共30分）
1.数据结构分为__________和物理结构两种结构。
2.线性结构中元素之间存在一对一关系，而图形结构中元素之间存在____________关系，树形结构中元素之间存在__________关系。
3.一个算法的最基本的原操作执行次数为(3n2+2nlog2n+4n-7)/(7n),则该算法的时间复杂度为____________。
4.链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过____________间接地反映。
5.向一个长度为n的顺序表中的第i个元素(1≤i≤n)之后插入一个元素时，需向后移动____________个元素。
6.当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用__________存储结构。
7.在单链表中，要删除某一指定的结点，必须找到该结点的____________结点。
8.删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行q=____________,p->next=____________和______________的操作。
9.设广义表L=（a,b,c））,则L的长度为________，深度为_________。
10. 栈的特点是，与之对应后进先出，队列的特点是____________。
11.在栈顶进行插入删除一个元素的时间复杂度是____________。
12.后缀算式9 2 3 +- 10 2 / -的值为__________。
13.一个环形队列中共有MaxSize个单元，那么队满时共有____________个元素。
14.设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是____________。
15.一棵高度为5的完全二叉树至少有________个结点，最多有________个结点。
16.如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为________。
17.设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。
18.已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是____________。
19.一个图的三种存储方法中，____________表示法是唯一的，____________表示法是不唯一的。
20.一个有n个顶点的无向连通图最少有______条边，最多______条边。
21.设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。
22.外排序是指在排序前后，数据在________上，排序时数据调入内存进行的排序方法。
23.在选择排序、冒泡排序、归并排序中，_________排序是空间复杂度最大的。
三.        简答题。（每小题4分，共40分）
1.简述顺序表和链表存储方式的特点。









2.在一个单链表HL中删除指针p所指结点，应执行如下关键操作：
if(________)
                HL = HL->next;
else
{
                q = HL;
                while(________)
                        q = q->next;
_____________;
}
delete p;



以下2个问题基于下面的环形队列：
设环形队列Q[7]的当前状态如下，

0        1        2        3        4        5        6
a1        a2
a3
               
a0




3.写出队列Q的队空、队满定条件及进队、出队操作的的描述语句；
4.画出元素a0,a1,a2出队，元素a4,a5,a6,a7进队后队列Q的状态。

5.写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序列。













6.已知一组元素为(30,46,62,27,32,49,13,45)，画出按元素排列顺序输入生成的一棵二叉搜索树，并写出在这棵二叉搜索树中查找元素49所需的元素比较次数。






7. 给定权值{6,7,12,10,30,25}，构造相应的哈夫曼树，要求写出构造步骤，并计算该树的带权路径长度。









8. 已知一个无向图的邻接表表示为：

画出该图的图形表示，并写出在该邻接表存储结构下，以顶点v4为出发点进行深度优先遍历的遍历序列。









9.对如下的图，用Prim算法从顶点5开始求最小生成树，写出按次序产生的边。采用 Kruscal算法产生的边次序是哪些？画出最小生成树。

10.已知序列（49，39，65，97，76，13，27，49）请用插入排序写出每一趟排序的结果。

xuening258

每学期都来

xln794

顶顶，资料下载试试！